Fast joint parity measurement via collective interactions induced by stimulated emission

Sainan Huai, Kunliang Bu, Xiu Gu, Zhenxing Zhang, Shuoming An, Xiaopei Yang, Yuan Li, Tianqi Cai and Yicong Zheng

Parity detection is essential in quantum error correction. Error syndromes coded in parity are detected routinely by sequential CNOT gates. Here, different from the standard CNOT-gate based scheme, we propose a reliable joint parity measurement (JPM) scheme inspired by stimulated emission. By controlling the collective behavior between data qubits and syndrome qubit, we realize the parity detection and experimentally implement the weight-2 and weight-4 JPM scheme in a tunable coupling superconducting circuit, which shows comparable performance to the CNOT scheme. Moreover, with the aid of the coupling tunability in quantum system, this scheme can be further utilized for specific joint entangling state preparation (JEP) with high fidelity, such as multiqubit entangled state preparation for non-adjacent qubits. This strategy, combined with the superconducting qubit system with tunable couplers, reveals tremendous potential and applications in the surface code architecture without adding extra circuit elements. Besides, the method we develop here can readily be applied in large-scale quantum computation and quantum simulation.

A Parametric EDA Method for Coplanar Waveguide Channel Recognition and Air-Bridge Construction in Quantum Chip Design

Yanghepu Li, Shengming Ma, Jonathan Allcock, Tianyu Zhang, Xiong Xu, Sainan Huai and Shengyu Zhang

Coplanar Waveguides (CPW) are ideally suited for coherently interfacing resonators with superconducting qubits. However, integrating CPWs with circuit elements on quantum chips involves curvature and discontinuities of the central conductors and corresponding ground planes, which may generate undesired parasitic modes. Experiments have demonstrated that air-bridges can effectively suppress this unwanted effect. Nevertheless, as quantum processors increase in size, manual air-bridge placement on the chip layout becomes increasingly time-consuming and error-prone. Automation of this process is therefore highly desirable, especially when the center line (channel) of the CPWs is not pre-established. In this paper we propose a parametric EDA method for coplanar waveguide channel identification and air-bridge construction in quantum chips. Our approach applies to both separated and full-package air-bridges and scales efficiently, with running time linear in the number of points and quadratic in the number of arcs in the corresponding chip layout. We evaluate our approach on a set of open-source quantum chip layouts, generating air-bridges in times ranging from 0.05 to 0.5 seconds—a practical speedup of over 10,000 times compared to manual generation. Furthermore, We propose two original quantitative metrics, accuracy and overlap, and verify that our method yields reliable results, producing air-bridges in the required shapes and locations. We fabricate a 13-qubit chip using our method for air-bridge placement, and observe excellent performance with minimal microwave and flux crosstalk. This research enables rapid generation of air-bridges when CPW channels are not pre-specified, paving the way for more flexible, automated, and modular design of superconducting quantum EDA.

Cluster sampling and scalable Bayesian optimization with constraints for negative tone development resist model calibration

Le Ma, Xingyu Ma, Shaogang Hao, Lisong Dong, Yayi Wei and Zhengguo Tian

As the semiconductor technology node continues to shrink, achieving smaller critical dimension in lithography becomes increasingly challenging. Negative tone development (NTD) process is widely employed in advanced node due to their large process window. However, the unique characteristics of NTD, such as shrinkage effect, make the NTD resist model calibration more complex. Gradient descent (GD) and heuristic methods have been applied for calibration of NTD resist model. Nevertheless, these methods depend on initial parameter selection and tend to fall into local optima, resulting in poor accuracy of the NTD model and massive computational time. In this paper, we propose cluster sampling and scalable Bayesian optimization (BO) with constraints method for NTD resist model calibration. This approach utilizes cluster sampling strategy to enhance the capability for global initial sampling and employs scalable BO with constraints for global optimization of high-dimensional parameter space. With this approach, the calibration accuracy is significantly enhanced in comparison with results from GD and heuristic methods, and the computational efficiency is substantially improved compared with GD. By gearing up cluster sampling strategy and scalable BO with constraints, this method offers a new and efficient resist model calibration.

Quantum approximate optimization via learning-based adaptive optimization

Lixue Cheng, Yuqin Chen, Shixin Zhang and Shengyu Zhang

Combinatorial optimization problems are ubiquitous and computationally hard to solve in general. Quantum approximate optimization algorithm (QAOA), one of the most representative quantum-classical hybrid algorithms, is designed to solve combinatorial optimization problems by transforming the discrete optimization problem into a classical optimization problem over continuous circuit parameters. QAOA objective landscape is notorious for pervasive local minima, and its viability significantly relies on the efficacy of the classical optimizer. In this work, we design double adaptive-region Bayesian optimization (DARBO) for QAOA. Our numerical results demonstrate that the algorithm greatly outperforms conventional optimizers in terms of speed, accuracy, and stability. We also address the issues of measurement efficiency and the suppression of quantum noise by conducting the full optimization loop on a superconducting quantum processor as a proof of concept. This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks.

Determination of molecular energies via variational-based quantum imaginary time evolution in a superconducting qubit system

Zhiwen Zong, Sainan Huai, Tianqi Cai, Wenyan Jin, Ze Zhan, Zhenxing Zhang, Kunliang Bu, Liyang Sui, Ying Fei, Yicong Zheng, Shengyu Zhang, Jianlan Wu and Yi Yin

As a valid tool for solving ground state problems, imaginary time evolution (ITE) is widely used in physical and chemical simulations. Different ITE-based algorithms in their quantum counterpart have recently been proposed and applied to some real systems. We experimentally realize the variational-based quantum imaginary time evolution (QITE) algorithm to simulate the ground state energy of hydrogen (H2) and lithium hydride (LiH) molecules in a superconducting qubit system. The H2 molecule is directly simulated using the 3-qubit circuit with unitary-coupled clusters (UCC) ansatz. We also combine QITE with the cluster mean-field (CMF) method to obtain an effective Hamiltonian. The LiH molecule is correspondingly simulated using the 3-qubit circuit with hardware-efficient ansatz. For comparison, the LiH molecule is also directly simulated using the 4-qubit circuit with UCC ansatz at the equilibrium point. All the experimental results show a convergence within 4 iterations, with high-fidelity ground state energy obtained. For a more complex system in the future, the CMF may allow further grouping of interactions to obtain an effective Hamiltonian, then the hybrid QITE algorithm can possibly simulate a relatively large-scale system with fewer qubits.

Does Qubit Connectivity Impact Quantum Circuit Complexity?

Pei Yuan, Jonathan Allcock and Shengyu Zhang

Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. These connectivity constraints are commonly viewed as a significant disadvantage. For example, compiling an unrestricted n -qubit quantum circuit to one with poor qubit connectivity, such as a 1-D chain, usually results in a blowup of depth by O(n2) and size by O(n) . It is appealing to conjecture that this overhead is unavoidable—a random circuit on n qubits has Θ(n) two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance Θ(n) . While it is known that almost all n -qubit unitary operations need quantum circuits of Ω(4n/n) depth and Ω(4n) size to realize with all-to-all qubit connectivity, in this article, we show that all n -qubit unitary operations can be implemented by quantum circuits of O(4n/n) depth and O(4n) size even under 1-D chain qubit connectivity constraint. We extend this result and investigate qubit connectivity in three directions. First, we consider more general connectivity graphs and show that the circuit size can always be made O(4n) as long as the graph is connected. For circuit depth, we study d -dimensional grids, complete d -ary trees and expander graphs, and show results similar to the 1-D chain. Second, we consider the case when ancillary qubits are available. We show that, with ancilla, the circuit depth can be made polynomial, and the space-depth trade-off is not impaired by connectivity constraints unless we have exponentially many ancillary qubits. Third, we obtain nearly optimal results on special families of unitaries, including diagonal unitaries, 2-by-2 block diagonal unitaries, and quantum state preparation (QSP) unitaries, the last being a fundamental task used in many quantum algorithms for machine learning and linear algebra.

Inverse lithography physics-informed deep neural level set for mask optimization

Xingyu Ma and Shaogang Hao

As the feature size of integrated circuits continues to decrease, optical proximity correction (OPC) has emerged as a crucial resolution enhancement technology for ensuring high printability in the lithography process. Recently, level set-based inverse lithography technology (ILT) has drawn considerable attention as a promising OPC solution, showcasing its powerful pattern fidelity, especially in advanced processing. However, the massive computational time consumption of ILT limits its applicability to mainly correcting partial layers and hotspot regions. Deep learning (DL) methods have shown great potential in accelerating ILT. However, the lack of domain knowledge of inverse lithography limits the ability of DL-based algorithms in process window (PW) enhancement, etc. In this paper, we propose an inverse lithography physics-informed deep neural level set (ILDLS) approach for mask optimization. This approach utilizes level set-based ILT as a layer within the DL framework and iteratively conducts mask prediction and correction to significantly enhance printability and PW in comparison with results from pure DL and ILT. With this approach, the computational efficiency is significantly improved compared with ILT. By gearing up DL with the knowledge of inverse lithography physics, ILDLS provides a new and efficient mask optimization solution.

TenCirChem: An Efficient Quantum Computational Chemistry Package for the NISQ Era

Weitang Li, Jonathan Allcock, Lixue Cheng, Shixin Zhang, Yuqin Chen, Jonathan P. Mailoa, Zhigang Shuai and Shengyu Zhang

TenCirChem is an open-source Python library for simulating variational quantum algorithms for quantum computational chemistry. TenCirChem shows high-performance in the simulation of unitary coupled-cluster circuits, using compact representations of quantum states and excitation operators. Additionally, TenCirChem supports noisy circuit simulation and provides algorithms for variational quantum dynamics. TenCirChem's capabilities are demonstrated through various examples, such as the calculation of the potential energy curve of H2O with a 6-31G(d) basis set using a 34-qubit quantum circuit, the examination of the impact of quantum gate errors on the variational energy of the H2 molecule, and the exploration of the Marcus inverted region for charge transfer rate based on variational quantum dynamics. Furthermore, TenCirChem is capable of running real quantum hardware experiments, making it a versatile tool for both simulation and experimentation in the field of quantum computational chemistry.

A mutation-induced drug resistance database (MdrDB)

Ziyi Yang, Zhaofeng Ye, Jiezhong Qiu, Rongjun Feng, Danyu Li, Changyu Hsieh, Jonathan Allcock and Shengyu Zhang

Mutation-induced drug resistance is a significant challenge to the clinical treatment of many diseases, as structural changes in proteins can diminish drug efficacy. Understanding how mutations affect protein-ligand binding affinities is crucial for developing new drugs and therapies. However, the lack of a large-scale and high-quality database has hindered the research progresses in this area. To address this issue, we have developed MdrDB, a database that integrates data from seven publicly available datasets, which is the largest database of its kind. By integrating information on drug sensitivity and cell line mutations from Genomics of Drug Sensitivity in Cancer and DepMap, MdrDB has substantially expanded the existing drug resistance data. MdrDB is comprised of 100,537 samples of 240 proteins (which encompass 5119 total PDB structures), 2503 mutations, and 440 drugs. Each sample brings together 3D structures of wild type and mutant protein-ligand complexes, binding affinity changes upon mutation ({$\Delta\Delta$G}), and biochemical features. Experimental results with MdrDB demonstrate its effectiveness in significantly enhancing the performance of commonly used machine learning models when predicting $\Delta$$\Delta$G in three standard benchmarking scenarios. In conclusion, MdrDB is a comprehensive database that can advance the understanding of mutation-induced drug resistance, and accelerate the discovery of novel chemicals.

Universal Kardar-Parisi-Zhang scaling in noisy hybrid quantum circuits

Shuo Liu, Mingrui Li, Shixin Zhang, Shaokai Jian and Hong Yao

Measurement-induced phase transitions (MIPTs) have attracted increasing attention due to the rich phenomenology of entanglement structures and their relation with quantum information processing. Since physical systems are unavoidably coupled to environment, quantum noise, which can qualitatively modify or even destroy certain entanglement structure, needs to be considered in analyzing a system with MIPT. In this Letter, we investigate the effect of quantum noise modeled by a reset quantum channel acting on each site with a probability $q$ on MIPT. Based on the numerical results from Clifford circuits, we show that the quantum noise can qualitatively change the entanglement properties—the entanglement obeys “area law” instead of “volume law” with a measurement rate $p<p_c$. In the noise-induced area law phase, the entanglement exhibits a novel $q^{-1 / 3}$ power-law scaling. Using an analytic mapping from the quantum model to a classical statistical model, we further show that the area law entanglement is the consequence of noise-driven symmetry-breaking field, and the $q^{-1 / 3}$ scaling can be understood as the result of Kardar-Parisi-Zhang fluctuations of directed polymer with an effective length scale $L_{\text {eff }} \sim q^{-1}$ in a random environment.

Quantum imaginary-time control for accelerating the ground-state preparation

Yucheng Chen, Yuqin Chen, Alice Hu, Changyu Hsieh and Shengyu Zhang

Quantum computers have been widely speculated to offer significant advantages in obtaining the ground state of difficult Hamiltonian in chemistry and physics. In this work, we first propose a Lyapunov control-inspired strategy to accelerate the well-established imaginary-time method for ground-state preparation. We also dig for the source of acceleration of the imaginary-time process under Lyapunov control with theoretical understanding and dynamic process visualization. To make the method accessible in the noisy intermediate-scale quantum era, we further propose a variational form of the algorithm that could work with shallow quantum circuits. Through numerical experiments on a broad spectrum of realistic models, including molecular systems, 2D Heisenberg models, and Sherrington-Kirkpatrick models, we show that imaginary-time control may substantially accelerate the imaginary-time evolution for all systems and even generate orders of magnitude acceleration (suggesting order-of-magnitude acceleration) for challenging molecular Hamiltonians involving small energy gaps as impressive special cases. Finally, with a proper selection of the control Hamiltonian, the new variational quantum algorithm does not incur additional measurement costs compared to the original variational quantum imaginary-time algorithm.

Efficient quantum simulation of electron-phonon systems by variational basis state encoder

Weitang Li, Jiajun Ren, Sainan Huai, Tianqi Cai, Zhigang Shuai and Shengyu Zhang

Digital quantum simulation of electron-phonon systems requires truncating infinite phonon levels into $N$ basis states and then encoding them with qubit computational basis. Unary encoding and binary encoding are the two most representative encoding schemes, which demand $O(N)$ and $O(\log N)$ qubits as well as $O(N)$ and $O(N \log N)$ quantum gates, respectively. In this paper, we propose a variational basis state encoding algorithm that reduces the scaling of the number of qubits and quantum gates to both $O(1)$ for systems obeying the area law of entanglement entropy. The cost for the scaling reduction is a constant amount of additional measurement. The accuracy and efficiency of the approach are verified by both numerical simulation and realistic quantum hardware experiments. In particular, we find using one or two qubits for each phonon mode is sufficient to produce quantitatively correct results across weak and strong coupling regimes. Our approach paves the way for practical quantum simulation of electron-phonon systems on both near-term hardware and error-corrected quantum computers.

Non-Hermitian ground-state-searching algorithm enhanced by a variational toolbox

Yuqin Chen, Shixin Zhang, Changyu Hsieh and Shengyu Zhang

Ground-state preparation for a given Hamiltonian is a common quantum-computing task of great importance and has relevant applications in quantum chemistry, computational material modeling, and combinatorial optimization. We consider an approach to simulate dissipative non-Hermitian Hamiltonian quantum dynamics using Hamiltonian simulation techniques to efficiently recover the ground state of a target Hamiltonian. The proposed method facilitates the energy transfer by repeatedly projecting ancilla qubits to the desired state, rendering the effective non-Hermitian Hamiltonian evolution on the system qubits. To make the method more resource friendly in the noisy intermediate-scale quantum (NISQ) and early fault-tolerant era, we combine the non-Hermitian projection algorithm with multiple variational gadgets, including variational module enhancement and variational state recording, to reduce the required circuit depth and avoid the exponentially vanishing success probability for postselections. We compare our method, the non-Hermitian-variational algorithm, with a pure variational method, the quantum approximate optimization algorithm (QAOA), for solving the 3-SAT problem and preparing the ground state for the transverse field Ising model. As demonstrated by numerical evidence, the non-Hermitian-variational algorithm outperforms QAOA in convergence speed with improved quantum resource efficiency.

Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits

Pei Yuan and Shengyu Zhang

As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of $|i\rangle |0^n\rangle \to |i\rangle |\psi_i\rangle $ for all $i\in \{0,1\}^k$ for the given $n$-qubit states $|\psi_i\rangle$. In this paper, we construct a quantum circuit for implementing CQSP, with depth $O\left(n+k+\frac{2^{n+k}}{n+k+m}\right)$ and size $O(2^{n+k})$ for any given number $m$ of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are optimal for any integer parameters $m,k\ge 0$ and $n\ge 1$. When $k=0$, the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation $|0^n\rangle|0^m\rangle \to |\psi\rangle |0^m\rangle$. This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to $\Theta(n+2^{n}/(n+m))$ and its size complexity to $\Theta(2^{n})$ for any $m$. Another fundamental problem, unitary synthesis, asks to implement a general $n$-qubit unitary by a quantum circuit. Previous work shows a lower bound of $\Omega(n+4^n/(n+m))$ and an upper bound of $O(n2^n)$ for $m=\Omega(2^n/n)$ ancillary qubits. In this paper, we quadratically shrink this gap by presenting a quantum circuit of the depth of $O\left(n2^{n/2}+\frac{n^{1/2}2^{3n/2}}{m^{1/2}}~~\right)$.

TensorCircuit: a Quantum Software Framework for the NISQ Era

Shixin Zhang, Jonathan Allcock, Zhouquan Wan, Shuo Liu, Jiace Sun, Hao Yu, Xinghan Yang, Jiezhong Qiu, Zhaofeng Ye, Yuqin Chen, Cheekong Lee, Yicong Zheng, Shaokai Jian, Hong Yao, Changyu Hsieh and Shengyu Zhang

TensorCircuit is an open source quantum circuit simulator based on tensor network contraction, designed for speed, flexibility and code efficiency. Written purely in Python, and built on top of industry-standard machine learning frameworks, TensorCircuit supports automatic differentiation, just-in-time compilation, vectorized parallelism and hardware acceleration. These features allow TensorCircuit to simulate larger and more complex quantum circuits than existing simulators, and are especially suited to variational algorithms based on parameterized quantum circuits. TensorCircuit enables orders of magnitude speedup for various quantum simulation tasks compared to other common quantum software, and can simulate up to 600 qubits with moderate circuit depth and low-dimensional connectivity. With its time and space efficiency, flexible and extensible architecture and compact, user-friendly API, TensorCircuit has been built to facilitate the design, simulation and analysis of quantum algorithms in the Noisy Intermediate-Scale Quantum (NISQ) era.

Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis

Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan and Shengyu Zhang

The quantum state preparation problem aims to prepare an n -qubit quantum state |ψv⟩=∑2n−1k=0vk|k⟩ from the initial state |0⟩⊗n , for a given unit vector v=(v0,v1,v2,…,v2n−1)T∈C2n with ∥v∥2=1 . The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth complexity remains open when ancillary qubits are available. In this article, we study quantum circuits when there are m ancillary qubits available. We construct, for any m , circuits that can prepare |ψv⟩ in depth O~((2n/[m+n])+n) and size O(2n) , achieving the optimal value for both measures simultaneously. These results also imply a depth complexity of Θ(4n/[m+n]) for quantum circuits implementing a general n -qubit unitary for any m≤O(2n/n) number of ancillary qubits. This resolves the depth complexity for circuits without ancillary qubits. And for circuits with exponentially many ancillary qubits, our result quadratically improves the currently best upper bound of O(4n) to Θ~(2n) . Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide parameter regime. The results can be viewed as (optimal) time-space tradeoff bounds, which is not only theoretically interesting, but also practically relevant in the current trend that the number of qubits starts to take off, by showing a way to use a large number of qubits to compensate the short qubit lifetime.

Multi-constraint molecular generation using sparsely labelled training data for localized high-concentration electrolyte diluent screening

Jonathan P. Mailoa, Xin Li, Jiezhong Qiu and Shengyu Zhang

Recently{,} machine learning methods have been used to propose molecules with desired properties{,} which is especially useful for exploring large chemical spaces efficiently. However{,} these methods rely on fully labelled training data{,} and are not practical in situations where molecules with multiple property constraints are required. There is often insufficient training data for all those properties from publicly available databases{,} especially when ab initio simulation or experimental property data is also desired for training the conditional molecular generative model. In this work{,} we show how to modify a semi-supervised variational auto-encoder (SSVAE) model which only works with fully labelled and fully unlabelled molecular property training data into the ConGen model{,} which also works on training data that have sparsely populated labels. We evaluate ConGen{'}s performance in generating molecules with multiple constraints when trained on a dataset combined from multiple publicly available molecule property databases{,} and demonstrate an example application of building the virtual chemical space for potential lithium-ion battery localized high-concentration electrolyte (LHCE) diluents.

Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits

Jonathan Allcock, Jinge Bao, João F. Doriguello, Alessandro Luongo and Miklos Santha

We explore the power of the unbounded Fan-Out gate and the Global Tunable gates generated by Ising-type Hamiltonians in constructing constant-depth quantum circuits, with particular attention to quantum memory devices. We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. These gates include the Fan-In gates defined by |x⟩|b⟩↦|x⟩|b⊕f(x)⟩ for x∈{0,1}n and b∈{0,1}, where f is a Boolean function. The first of our constructions is based on computing the one-hot encoding of the control register |x⟩, while the second is based on Boolean analysis and exploits different representations of f such as its Fourier expansion. Via these constructions, we obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices -- Quantum Random Access Memory (QRAM) and Quantum Random Access Gate (QRAG) -- of memory size n. The implementation based on one-hot encoding requires either O(nlognloglogn) ancillae and O(nlogn) Fan-Out gates or O(nlogn) ancillae and 6 Global Tunable gates. On the other hand, the implementation based on Boolean analysis requires only 2 Global Tunable gates at the expense of O(n2) ancillae.

Multi-task Bioassay Pre-training for Protein-ligand Binding Affinity Prediction

Jiaxian Yan, Zhaofeng Ye, Ziyi Yang, Chengqiang Lu, Shengyu Zhang, Qi Liu and Jiezhong Qiu

Protein-ligand binding affinity (PLBA) prediction is the fundamental task in drug discovery. Recently, various deep learning-based models predict binding affinity by incorporating the three-dimensional structure of protein-ligand complexes as input and achieving astounding progress. However, due to the scarcity of high-quality training data, the generalization ability of current models is still limited. In addition, different bioassays use varying affinity measurement labels (i.e., IC50, Ki, Kd), and different experimental conditions inevitably introduce systematic noise, which poses a significant challenge to constructing high-precision affinity prediction models. To address these issues, we (1) propose Multi-task Bioassay Pre-training (MBP), a pre-training framework for structure-based PLBA prediction; (2) construct a pre-training dataset called ChEMBL-Dock with more than 300k experimentally measured affinity labels and about 2.8M docked three-dimensional structures. By introducing multi-task pre-training to treat the prediction of different affinity labels as different tasks and classifying relative rankings between samples from the same bioassay, MBP learns robust and transferrable structural knowledge from our new ChEMBL-Dock dataset with varied and noisy labels. Experiments substantiate the capability of MBP as a general framework that can improve and be tailored to mainstream structure-based PLBA prediction tasks. To the best of our knowledge, MBP is the first affinity pre-training model and shows great potential for future development.

On the quantum time complexity of divide and conquer

Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee and Miklos Santha

We initiate a systematic study of the time complexity of quantum divide and conquer algorithms for classical problems. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup and apply these theorems to an array of problems involving strings, integers, and geometric objects. They include LONGEST DISTINCT SUBSTRING, KLEE'S COVERAGE, several optimization problems on stock transactions, and k-INCREASING SUBSEQUENCE. For most of these results, our quantum time upper bound matches the quantum query lower bound for the problem, up to polylogarithmic factors.

Variational Quantum-Neural Hybrid Error Mitigation

Shixin Zhang, Zhouquan Wan, Changyu Hsieh, Hong Yao and Shengyu Zhang

Abstract Quantum error mitigation (QEM) is crucial for obtaining reliable results on quantum computers by suppressing quantum noise with moderate resources. It is a key factor for successful and practical quantum algorithm implementations in the noisy intermediate scale quantum (NISQ) era. Since quantum-classical hybrid algorithms can be executed with moderate and noisy quantum resources, combining QEM with quantum-classical hybrid schemes is one of the most promising directions toward practical quantum advantages. This work shows how the variational quantum-neural hybrid eigensolver (VQNHE) algorithm, which seamlessly combines the expressive power of a parameterized quantum circuit with a neural network, is inherently noise resilient with a unique QEM capacity, which is absent in vanilla variational quantum eigensolvers (VQE). The study carefully analyzes and elucidates the asymptotic scaling of this unique QEM capacity in VQNHE from both theoretical and experimental perspectives. Finally, a variational basis transformation is proposed for the Hamiltonian to be measured under the VQNHE framework, yielding a powerful tri-optimization setup, dubbed as VQNHE++. VQNHE++ can further enhance the quantum-neural hybrid expressive power and error mitigation capacity.

Electronic structure manipulation via composition tuning for the development of highly conductive and acid-stable oxides

Youngwoon Byeon, Jonathan P Mailoa, Mordechai Kornbluth, Gihyeok Lee, Zijian Cai, Yingzhi Sun, Wanli Yang, Christina Johnston, Jake Christensen, Soo Kim, Lei Cheng and Haegyeom Kim

Exploring materials that simultaneously possess high conductivity and electrochemical stability is critical for various energy-conversion applications. In this study{,} our combined computations and experiments suggest the Mg–Ti–O chemical space for novel ternary oxide compounds offering high electrical conductivity and corrosion stability in acidic conditions to be potentially used as catalyst supporter of polymer electrolyte membrane fuel cells. High electrical conductivity (6.09 × 10−1 S/cm) is achieved at room temperature by tuning the chemical composition of Mg1−xTi2+xO5 while still maintaining good corrosion stability (1.2 × 10−4 mA cm−2 after six days) in acidic conditions. Furthermore{,} we discover that a reducing gas environment during the synthesis increases the Ti solubility in Mg1−xTi2+xO5 with a reduced valence state of Ti{,} thus resulting in high conductivity.

Orbital Mixer: Using Atomic Orbital Features for Basis-Dependent Prediction of Molecular Wavefunctions

Kirill Shmilovich, Devin Willmott, Ivan Batalov, Mordechai Kornbluth, Jonathan Mailoa and J. Zico Kolter

Leveraging ab initio data at scale has enabled the development of machine learning models capable of extremely accurate and fast molecular property prediction. A central paradigm of many previous studies focuses on generating predictions for only a fixed set of properties. Recent lines of research instead aim to explicitly learn the electronic structure via molecular wavefunctions, from which other quantum chemical properties can be directly derived. While previous methods generate predictions as a function of only the atomic configuration, in this work we present an alternate approach that directly purposes basis-dependent information to predict molecular electronic structure. Our model, Orbital Mixer, is composed entirely of multi-layer perceptrons (MLPs) using MLP-Mixer layers within a simple, intuitive, and scalable architecture that achieves competitive Hamiltonian and molecular orbital energy and coefficient prediction accuracies compared to the state-of-the-art.

Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming

Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer and Miklos Santha

Subset-Sum is an NP-complete problem where one must decide if a multiset of n integers contains a subset whose elements sum to a target value m. The best known classical and quantum algorithms run in time $Õ(2^{n/2})$ and $Õ(2^{n/3})$, respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel classical dynamic-programming-based data structure with applications to Subset-Sum and a number of variants, including Equal-Sums (where one seeks two disjoint subsets with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each item in the input set can be used twice in the summation), and Shifted-Sums, a generalization of both of these variants, where one seeks two disjoint subsets whose sums differ by some specified value. Given any modulus p, our data structure can be constructed in time $O(np)$, after which queries can be made in time $O(n)$ to the lists of subsets summing to any value modulo p. We use this data structure in combination with variable-time amplitude amplification and a new quantum pair finding algorithm, extending the quantum claw finding algorithm to the multiple solutions case, to give an $O(2^{0.504n})$ quantum algorithm for Shifted-Sums. This provides a notable improvement on the best known $O(2^{0.773n})$ classical running time established by Mucha et al. [Mucha et al., 2019]. We also study Pigeonhole Equal-Sums, a variant of Equal-Sums where the existence of a solution is guaranteed by the pigeonhole principle. For this problem we give faster classical and quantum algorithms with running time $Õ(2^{n/2})$ and $Õ(2^{2n/5})$, respectively.

Machine learning accelerated carbon neutrality research using big data—-from predictive models to interatomic potentials

Lingjun Wu, Zhenming Xu, Zixuan Wang, Zijian Chen, Zhichao Huang, Chao Peng, Xiangdong Pei, Xiangguo Li, Jonathan P. Mailoa, Changyu Hsieh, Tao Wu, Xuefeng Yu and Haitao Zhao

Carbon neutrality has been proposed as a solution for the current severe energy and climate crisis caused by the overuse of fossil fuels, and machine learning (ML) has exhibited excellent performance in accelerating related research owing to its powerful capacity for big data processing. This review presents a detailed overview of ML accelerated carbon neutrality research with a focus on energy management, screening of novel energy materials, and ML interatomic potentials (MLIPs), with illustrations of two selected MLIP algorithms: moment tensor potential (MTP) and neural equivariant interatomic potential (NequIP). We conclude by outlining the important role of ML in accelerating the achievement of carbon neutrality from global-scale energy management, unprecedented screening of advanced energy materials in massive chemical space, to the revolution of atomic-scale simulations of MLIPs, which has the bright prospect of applications.

Mitigating Pt Loss in Polymer Electrolyte Membrane Fuel Cell Cathode Catalysts Using Graphene Nanoplatelet Pickering Emulsion Processing

Kyuyoung Park, Matthew E. Sweers, Ulrich Berner, Erhard Hirth, Julia R. Downing, Janan Hui, Jonathan Mailoa, Christina Johnston, Soo Kim, Linsey C. Seitz and Mark C. Hersam

Abstract Carbon-supported Pt nanoparticles are the leading catalysts for the cathode oxygen reduction reaction (ORR) in polymer electrolyte membrane fuel cells. However, these ORR catalysts suffer from poor electrochemical durability, particularly the loss of electrochemical surface area (ECSA) due to Pt nanoparticle dissolution and agglomeration. Here, Pt loss is mitigated through a Pickering emulsion-processing strategy that employs graphene nanoplatelet dispersions stabilized by the polymer ethyl cellulose. The resulting graphene-Pt/Vulcan carbon (Pt/C) catalysts exhibit superior durability and ECSA retention throughout an accelerated stress test compared with a commercial Pt/C standard catalyst, both in a diagnostic-rotating disc electrode setup and in a membrane electrode assembly full cell. These graphene-Pt/C catalysts also improve durability at high-voltage conditions, providing further evidence of their exceptional electrochemical stability. Consistent with density functional theory calculations, postelectrochemical characterization reveals that Pt nanoparticles localize at graphene defects both on the basal plane and especially at the edges of the graphene nanoplatelets. Since this Pt nanoparticle localization suppresses Pt nanoparticle dissolution and agglomeration without hindering accessibility of the reactant species to the catalyst surface, the ORR performance under both idealized and practical experimental conditions shows significantly improved durability while maintaining high electrochemical activity.

Discrete time crystal enabled by Stark many-body localization

Shuo Liu, Shixin Zhang, Changyu Hsieh, Shengyu Zhang and Hong Yao

Discrete time crystal (DTC) has recently attracted increasing attention, but most DTC models and their properties are only revealed after disorder average. In this Letter, we propose a simple disorder-free periodically driven model that exhibits nontrivial DTC order stabilized by Stark many-body localization (MBL). We demonstrate the existence of DTC phase by analytical analysis from perturbation theory and convincing numerical evidence from observable dynamics. The new DTC model paves a new promising way for further experiments and deepens our understanding of DTC. Since the DTC order doesn't require special quantum state preparation and the strong disorder average, it can be naturally realized on the noisy intermediate-scale quantum (NISQ) hardware with much fewer resources and repetitions. Moreover, besides the robust subharmonic response, there are other novel robust beating oscillations in Stark-MBL DTC phase which are absent in random or quasi-periodic MBL DTC.

Differentiable quantum architecture search

Shixin Zhang, Changyu Hsieh, Shengyu Zhang and Hong Yao

Quantum architecture search (QAS) is the process of automating architecture engineering of quantum circuits. It has been desired to construct a powerful and general QAS platform which can significantly accelerate current efforts to identify quantum advantages of error-prone and depth-limited quantum circuits in the NISQ era. Hereby, we propose a general framework of differentiable quantum architecture search (DQAS), which enables automated designs of quantum circuits in an end-to-end differentiable fashion. We present several examples of circuit design problems to demonstrate the power of DQAS. For instance, unitary operations are decomposed into quantum gates, noisy circuits are re-designed to improve accuracy, and circuit layouts for quantum approximation optimization algorithm are automatically discovered and upgraded for combinatorial optimization problems. These results not only manifest the vast potential of DQAS being an essential tool for the NISQ application developments, but also present an interesting research topic from the theoretical perspective as it draws inspirations from the newly emerging interdisciplinary paradigms of differentiable programming, probabilistic programming, and quantum programming.

The Prospects of Monte Carlo Antibody Loop Modelling on a Fault-Tolerant Quantum Computer

Jonathan Allcock, Anna Vangone, Agnes Meyder, Stanislaw Adaszewski, Martin Strahm, Changyu Hsieh and Shengyu Zhang

Quantum computing for the biological sciences is an area of rapidly growing interest, but specific industrial applications remain elusive. Quantum Markov chain Monte Carlo has been proposed as a method for accelerating a broad class of computational problems, including problems of pharmaceutical interest. Here we investigate the prospects of quantum advantage via this approach, by applying it to the problem of modelling antibody structure, a crucial task in drug development. To minimize the resources required while maintaining pharmaceutical-level accuracy, we propose a specific encoding of molecular dihedral angles into registers of qubits and a method for implementing, in quantum superposition, a Markov chain Monte Carlo update step based on a classical all-atom force field. We give the first detailed analysis of the resources required to solve a problem of industrial size and relevance and find that, though the time and space requirements of using a quantum computer in this way are considerable, continued technological improvements could bring the required resources within reach in the future.

GLAM: An adaptive graph learning method for automated molecular interactions and properties predictions

Yuquan Li, Changyu Hsieh, Ruiqiang Lu, Xiaoqing Gong, Xiaorui Wang, Pengyong Li, Shuo Liu, Yanan Tian, Dejun Jiang, Jiaxian Yan, Qifeng Bai, Huanxiang Liu, Shengyu Zhang and Xiaojun Yao

Improving drug discovery efficiency is a core and long-standing challenge in drug discovery. For this purpose, many graph learning methods have been developed to search potential drug candidates with fast speed and low cost. In fact, the pursuit of high prediction performance on a limited number of datasets has crystallized their architectures and hyperparameters, making them lose advantage in repurposing to new data generated in drug discovery. Here we propose a flexible method that can adapt to any dataset and make accurate predictions. The proposed method employs an adaptive pipeline to learn from a dataset and output a predictor. Without any manual intervention, the method achieves far better prediction performance on all tested datasets than traditional methods, which are based on hand-designed neural architectures and other fixed items. In addition, we found that the proposed method is more robust than traditional methods and can provide meaningful interpretability. Given the above, the proposed method can serve as a reliable method to predict molecular interactions and properties with high adaptability, performance, robustness and interpretability. This work takes a solid step forward to the purpose of aiding researchers to design better drugs with high efficiency.

The Secretary Problem with Competing Employers on Random Edge Arrivals

Xiaohui Bei and Shengyu Zhang

The classic secretary problem concerns the problem of an employer facing a random sequence of candidates and making online hiring decisions to try to hire the best candidate. In this paper, we study a game-theoretic generalization of the secretary problem where a set of employers compete with each other to hire the best candidate. Different from previous secretary market models, our model assumes that the sequence of candidates arriving at each employer is uniformly random but independent from other sequences. We consider two versions of this secretary game where employers can have adaptive or non-adaptive strategies, and provide characterizations of the best response and Nash equilibrium of each game.

Mitigating Contradictions in Dialogue Based on Contrastive Learning

Weizhao Li, Junsheng Kong, Ben Liao and Yi Cai

Chatbot models have achieved remarkable progress in recent years but tend to yield contradictory responses. In this paper, we exploit the advantage of contrastive learning technique to mitigate this issue. To endow the model with the ability of discriminating contradictory patterns, we minimize the similarity between the target response and contradiction related negative example. The negative example is generated with learnable latent noise, which receives contradiction related feedback from the pretrained critic. Experimental results show that our method helps to avoid contradictions in response generation while preserving response fluency, outperforming existing methods on both automatic and human evaluation.

E(3)-equivariant graph neural networks for data-efficient and accurate interatomic potentials

Simon Batzner, Albert Musaelian, Lixin Sun, Mario Geiger, Jonathan P. Mailoa, Mordechai Kornbluth, Nicola Molinari, Tess E. Smidt and Boris Kozinsky

This work presents Neural Equivariant Interatomic Potentials (NequIP), an E(3)-equivariant neural network approach for learning interatomic potentials from ab-initio calculations for molecular dynamics simulations. While most contemporary symmetry-aware models use invariant convolutions and only act on scalars, NequIP employs E(3)-equivariant convolutions for interactions of geometric tensors, resulting in a more information-rich and faithful representation of atomic environments. The method achieves state-of-the-art accuracy on a challenging and diverse set of molecules and materials while exhibiting remarkable data efficiency. NequIP outperforms existing models with up to three orders of magnitude fewer training data, challenging the widely held belief that deep neural networks require massive training sets. The high data efficiency of the method allows for the construction of accurate potentials using high-order quantum chemical level of theory as reference and enables high-fidelity molecular dynamics simulations over long time scales.

Variational Quantum Simulation of Chemical Dynamics with Quantum Computers

Cheekong Lee, Changyu Hsieh, Shengyu Zhang and Liang Shi

Classical simulations of real-space quantum dynamics are challenging due to the exponential scaling of computational cost with system dimensions. Quantum computers offer the potential to simulate quantum dynamics with polynomial complexity; however, existing quantum algorithms based on the split-operator techniques require large-scale fault-tolerant quantum computers that remain elusive in the near future. Here, we present variational simulations of real-space quantum dynamics suitable for implementation in noisy intermediate-scale quantum (NISQ) devices. The Hamiltonian is first encoded onto qubits using a discrete variable representation and binary encoding scheme. We show that direct application of a real-time variational quantum algorithm based on the McLachlan's principle is inefficient as the measurement cost grows exponentially with the qubit number for general potential energy, and an extremely small time-step size is required to achieve accurate results. Motivated by the insights that many chemical dynamics occur in the low-energy subspace, we propose a subspace expansion method by projecting the total Hamiltonian, including the time-dependent driving field, onto the system low-energy eigenstate subspace using quantum computers, and the exact quantum dynamics within the subspace can then be solved classically. We show that the measurement cost of the subspace approach grows polynomially with dimensionality for general potential energy. Our numerical examples demonstrate the capability of our approach, even under intense laser fields. Our work opens the possibility of simulating chemical dynamics with NISQ hardware.

SPLDExtraTrees: robust machine learning approach for predicting kinase inhibitor resistance

Ziyi Yang, Zhaofeng Ye, Yijia Xiao, Changyu Hsieh and Shengyu Zhang

{Drug resistance is a major threat to the global health and a significant concern throughout the clinical treatment of diseases and drug development. The mutation in proteins that is related to drug binding is a common cause for adaptive drug resistance. Therefore, quantitative estimations of how mutations would affect the interaction between a drug and the target protein would be of vital significance for the drug development and the clinical practice. Computational methods that rely on molecular dynamics simulations, Rosetta protocols, as well as machine learning methods have been proven to be capable of predicting ligand affinity changes upon protein mutation. However, the severely limited sample size and heavy noise induced overfitting and generalization issues have impeded wide adoption of machine learning for studying drug resistance. In this paper, we propose a robust machine learning method, termed SPLDExtraTrees, which can accurately predict ligand binding affinity changes upon protein mutation and identify resistance-causing mutations. Especially, the proposed method ranks training data following a specific scheme that starts with easy-to-learn samples and gradually incorporates harder and diverse samples into the training, and then iterates between sample weight recalculations and model updates. In addition, we calculate additional physics-based structural features to provide the machine learning model with the valuable domain knowledge on proteins for these data-limited predictive tasks. The experiments substantiate the capability of the proposed method for predicting kinase inhibitor resistance under three scenarios and achieve predictive accuracy comparable with that of molecular dynamics and Rosetta methods with much less computational costs.}

Variational Quantum-Neural Hybrid Eigensolver

Shixin Zhang, Zhouquan Wan, Cheekong Lee, Changyu Hsieh, Shengyu Zhang and Hong Yao

The variational quantum eigensolver (VQE) is one of the most representative quantum algorithms in the noisy intermediate-scale quantum (NISQ) era, and is generally speculated to deliver one of the first quantum advantages for the ground-state simulations of some nontrivial Hamiltonians. However, short quantum coherence time and limited availability of quantum hardware resources in the NISQ hardware strongly restrain the capacity and expressiveness of VQEs. In this Letter, we introduce the variational quantum-neural hybrid eigensolver (VQNHE) in which the shallow-circuit quantum Ansatz can be further enhanced by classical post-processing with neural networks. We show that the VQNHE consistently and significantly outperforms the VQE in simulating ground-state energies of quantum spins and molecules given the same amount of quantum resources. More importantly, we demonstrate that, for arbitrary postprocessing neural functions, the VQNHE only incurs a polynomial overhead of processing time and represents the first scalable method to exponentially accelerate the VQE with nonunitary postprocessing that can be efficiently implemented in the NISQ era.

Optimizing quantum annealing schedules with Monte Carlo tree search enhanced with neural networks

Yuqin Chen, Yu Chen, Cheekong Lee, Shengyu Zhang and Changyu Hsieh

Quantum annealing is a practical approach to approximately implement the adiabatic quantum computational model in a real-world setting. The goal of an adiabatic algorithm is to prepare the ground state of a problem-encoded Hamiltonian at the end of an annealing path. This is typically achieved by driving the dynamical evolution of a quantum system slowly to enforce adiabaticity. Properly optimized annealing schedules often considerably accelerate the computational process. Inspired by the recent success of deep reinforcement learning such as DeepMind's AlphaZero, we propose a Monte Carlo tree search (MCTS) algorithm and its enhanced version boosted by neural networks---which we name QuantumZero (QZero)---to automate the design of annealing schedules in a hybrid quantum--classical framework. Both the MCTS and QZero algorithms perform remarkably well in discovering effective annealing schedules even when the annealing time is short for the 3-SAT examples considered in this study. Furthermore, the flexibility of neural networks allows us to apply transfer-learning techniques to boost QZero's performance. We demonstrate in benchmark studies that MCTS and QZero perform more efficiently than other reinforcement learning algorithms in designing annealing schedules.

Simulating Energy Transfer in Molecular Systems with Digital Quantum Computers

Cheekong Lee, Jonathan Wei Zhong Lau, Liang Shi and Leong Chuan Kwek

Quantum computers have the potential to simulate chemical systems beyond the capability of classical computers. Recent developments in hybrid quantum-classical approaches enable the determinations of the ground or low energy states of molecular systems. Here, we extend near-term quantum simulations of chemistry to time-dependent processes by simulating energy transfer in organic semiconducting molecules. We developed a multi-scale modeling workflow that combines conventional molecular dynamics and quantum chemistry simulations with hybrid variational quantum algorithm to compute the exciton dynamics in both the single excitation subspace (i.e. Frenkel Hamiltonian) and the full-Hilbert space (i.e. multi-exciton) regimes. Our numerical examples demonstrate the feasibility of our approach, and simulations on IBM Q devices capture the qualitative behaviors of exciton dynamics, but with considerable errors. We present an error mitigation technique that combines experimental results from the variational and Trotter algorithms, and obtain significantly improved quantum dynamics. Our approach opens up new opportunities for modeling quantum dynamics in chemical, biological and material systems with quantum computers.

Suppressing ZZ Crosstalk of Quantum Computers through Pulse and Scheduling Co-Optimization

Lei Xie, Jidong Zhai, Zhenxing Zhang, Jonathan Allcock, Shengyu Zhang and Yicong Zheng

Noise is a significant obstacle to quantum computing, and ZZ crosstalk is one of the most destructive types of noise affecting superconducting qubits. Previous approaches to suppressing ZZ crosstalk have mainly relied on specific chip design that can complicate chip fabrication and aggravate decoherence. To some extent, special chip design can be avoided by relying on pulse optimization to suppress ZZ crosstalk. However, existing approaches are non-scalable, as their required time and memory grow exponentially with the number of qubits involved. To address the above problems, we propose a scalable approach by co-optimizing pulses and scheduling. We optimize pulses to offer an ability to suppress ZZ crosstalk surrounding a gate, and then design scheduling strategies to exploit this ability and achieve suppression across the whole circuit. A main advantage of such co-optimization is that it does not require special hardware support. Besides, we implement our approach as a general framework that is compatible with different pulse optimization methods. We have conducted extensive evaluations by simulation and on a real quantum computer. Simulation results show that our proposal can improve the fidelity of quantum computing on 4∼12 qubits by up to 81\texttimes{} (11\texttimes{} on average). Ramsey experiments on a real quantum computer also demonstrate that our method can eliminate the effect of ZZ crosstalk to a great extent.

Quantum Networks with Multiple Service Providers: Transport Layer Protocols and Research Opportunities

Maoli Liu, Jonathan Allcock, Kechao Cai, Shengyu Zhang and John C.s. Lui

Retroformer: Pushing the Limits of Interpretable End-to-end Retrosynthesis Transformer

Yue Wan, Benben Liao, Changyu Hsieh and Shengyu Zhang

Retrosynthesis prediction is one of the fundamental challenges in organic synthesis. The task is to predict the reactants given a core product. With the advancement of machine learning, computer-aided synthesis planning has gained increasing interest. Numerous methods were proposed to solve this problem with different levels of dependency on additional chemical knowledge. In this paper, we propose Retroformer, a novel Transformer-based architecture for retrosynthesis prediction without relying on any cheminformatics tools for molecule editing. Via the proposed local attention head, the model can jointly encode the molecular sequence and graph, and efficiently exchange information between the local reactive region and the global reaction context. Retroformer reaches the new state-of-the-art accuracy for the end-to-end template-free retrosynthesis, and improves over many strong baselines on better molecule and reaction validity. In addition, its generative procedure is highly interpretable and controllable. Overall, Retroformer pushes the limits of the reaction reasoning ability of deep generative models.

Shortcuts to adiabaticity for open systems in circuit quantum electrodynamics

Zelong Yin, Chunzhen Li, Jonathan Allcock, Yicong Zheng, Xiu Gu, Maochun Dai, Shengyu Zhang and Shuoming An

Shortcuts to adiabaticity are powerful quantum control methods, allowing quick evolution into target states of otherwise slow adiabatic dynamics. Such methods have widespread applications in quantum technologies, and various shortcuts to adiabaticity protocols have been demonstrated in closed systems. However, realizing shortcuts to adiabaticity for open quantum systems has presented a challenge due to the complex controls in existing proposals. Here, we present the experimental demonstration of shortcuts to adiabaticity for open quantum systems, using a superconducting circuit quantum electrodynamics system. By applying a counterdiabatic driving pulse, we reduce the adiabatic evolution time of a single lossy mode from 800{\thinspace}ns to 100{\thinspace}ns. In addition, we propose and implement an optimal control protocol to achieve fast and qubit-unconditional equilibrium of multiple lossy modes. Our results pave the way for precise time-domain control of open quantum systems and have potential applications in designing fast open-system protocols of physical and interdisciplinary interest, such as accelerating bioengineering and chemical reaction dynamics.

Graph Self-Supervised Learning for Optoelectronic Properties of Organic Semiconductors

Zaixi Zhang, Qi Liu, Shengyu Zhang, Changyu Hsieh, Liang Shi and Cheekong Lee

The search for new high-performance organic semiconducting molecules is challenging due to the vastness of the chemical space, machine learning methods, particularly deep learning models like graph neural networks (GNNs), have shown promising potential to address such challenge. However, practical applications of GNNs for chemistry are often limited by the availability of labelled data. Meanwhile, unlabelled molecular data is abundant and could potentially be utilized to alleviate the scarcity issue of labelled data. Here, we advocate the use of self-supervised learning to improve the performance of GNNs by pre-training them with unlabeled molecular data. We investigate regression problems involving ground and excited state properties, both relevant for optoelectronic properties of organic semiconductors. Additionally, we extend the self-supervised learning strategy to molecules in non-equilibrium configurations which are important for studying the effects of disorder. In all cases, we obtain considerable performance improvement over results without pre-training, in particular when labelled training data is limited, and such improvement is attributed to the capability of self-supervised learning in identifying structural similarity among unlabeled molecules.

InteractionGraphNet: A Novel and Efficient Deep Graph Representation Learning Framework for Accurate Protein—Ligand Interaction Predictions

Dejun Jiang, Changyu Hsieh, Zhenxing Wu, Yu Kang, Jike Wang, Ercheng Wang, Ben Liao, Chao Shen, Lei Xu, Jian Wu, Dongsheng Cao and Tingjun Hou

Accurate quantification of protein--ligand interactions remains a key challenge to structure-based drug design. However, traditional machine learning (ML)-based methods based on handcrafted descriptors, one-dimensional protein sequences, and/or two-dimensional graph representations limit their capability to learn the generalized molecular interactions in 3D space. Here, we proposed a novel deep graph representation learning framework named InteractionGraphNet (IGN) to learn the protein--ligand interactions from the 3D structures of protein--ligand complexes. In IGN, two independent graph convolution modules were stacked to sequentially learn the intramolecular and intermolecular interactions, and the learned intermolecular interactions can be efficiently used for subsequent tasks. Extensive binding affinity prediction, large-scale structure-based virtual screening, and pose prediction experiments demonstrated that IGN achieved better or competitive performance against other state-of-the-art ML-based baselines and docking programs. More importantly, such state-of-the-art performance was proven from the successful learning of the key features in protein--ligand interactions instead of just memorizing certain biased patterns from data.

ProtGNN: Towards Self-Explaining Graph Neural Networks

Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu and Cheekong Lee

Despite the recent progress in Graph Neural Networks (GNNs), it remains challenging to explain the predictions made by GNNs. Existing explanation methods mainly focus on post-hoc explanations where another explanatory model is employed to provide explanations for a trained GNN. The fact that post-hoc methods fail to reveal the original reasoning process of GNNs raises the need of building GNNs with built-in interpretability. In this work, we propose Prototype Graph Neural Network (ProtGNN), which combines prototype learning with GNNs and provides a new perspective on the explanations of GNNs. In ProtGNN, the explanations are naturally derived from the case-based reasoning process and are actually used during classification. The prediction of ProtGNN is obtained by comparing the inputs to a few learned prototypes in the latent space. Furthermore, for better interpretability and higher efficiency, a novel conditional subgraph sampling module is incorporated to indicate which part of the input graph is most similar to each prototype in ProtGNN+. Finally, we evaluate our method on a wide range of datasets and perform concrete case studies. Extensive results show that ProtGNN and ProtGNN+ can provide inherent interpretability while achieving accuracy on par with the noninterpretable counterparts.

Fast Multiqubit Gates through Simultaneous Two-Qubit Gates

Xiu Gu, Jorge Fernándezpendás, Pontus Vikstål, Tahereh Abad, Christopher Warren, Andreas Bengtsson, Giovanna Tancredi, Vitaly Shumeiko, Jonas Bylander, Göran Johansson and Anton Frisk Kockum

Near-term quantum computers are limited by the decoherence of qubits to only being able to run low-depth quantum circuits with acceptable fidelity. This severely restricts what quantum algorithms can be compiled and implemented on such devices. One way to overcome these limitations is to expand the available gate set from single- and two-qubit gates to multiqubit gates, which entangle three or more qubits in a single step. Here, we show that such multiqubit gates can be realized by the simultaneous application of multiple two-qubit gates to a group of qubits where at least one qubit is involved in two or more of the two-qubit gates. Multiqubit gates implemented in this way are as fast as, or sometimes even faster than, the constituent two-qubit gates. Furthermore, these multiqubit gates do not require any modification of the quantum processor, but are ready to be used in current quantum-computing platforms. We demonstrate this idea for two specific cases: simultaneous controlled-Z gates and simultaneous iswap gates. We show how the resulting multiqubit gates relate to other well-known multiqubit gates and demonstrate through numerical simulations that they would work well in available quantum hardware, reaching gate fidelities well above 99{\%}. We also present schemes for using these simultaneous two-qubit gates to swiftly create large entangled states like Dicke and Greenberger-Horne-Zeilinger states.

Classical and quantum dynamic programming for Subset-Sum and variants

Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer and Miklos Santha

Subset-Sum is an NP-complete problem where one must decide if a multiset of $n$ integers contains a subset whose elements sum to a target value $m$. The best known classical and quantum algorithms run in time $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$, respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel dynamic programming data structure with applications to Subset-Sum and a number of variants, including Equal-Sums (where one seeks two disjoint subsets with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each item in the input set can be used twice in the summation), and Shifted-Sums, a generalization of both of these variants, where one seeks two disjoint subsets whose sums differ by some specified value. Given any modulus $p$, our data structure can be constructed in time $O(np)$, after which queries can be made in time $O(n)$ to the lists of subsets summing to a same value modulo $p$. We use this data structure to give new $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$ classical and quantum algorithms for Subset-Sum, not based on the meet-in-the-middle method. We then use the data structure in combination with variable time amplitude amplification and a quantum pair finding algorithm, extending quantum element distinctness and claw finding algorithms to the multiple solutions case, to give an $O(2^{0.504n})$ quantum algorithm for Shifted-Sums, an improvement on the best known $O(2^{0.773n})$ classical running time. We also study Pigeonhole Equal-Sums and Pigeonhole Modular Equal-Sums, where the existence of a solution is guaranteed by the pigeonhole principle. For the former problem we give classical and quantum algorithms with running time $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{2n/5})$, respectively. For the more general modular problem we give a classical algorithm which also runs in time $\tilde{O}(2^{n/2})$.

Accelerated Prediction of Cu-based Single-Atom Alloy Catalysts for CO2 Reduction by Machine Learning

Dashuai Wang, Runfeng Cao, Shaogang Hao, Chen Liang, Guangyong Chen, Pengfei Chen, Yang Li and Xiaolong Zou

Various strategies, including controls of morphology, oxidation state, defect, and doping, have been developed to improve the performance of Cu-based catalysts for CO2 reduction reaction (CO2RR), generating a large amount of data. However, a unified understanding of underlying mechanism for further optimization is still lacking. In this work, combining first-principles calculations and machine learning (ML) techniques, we elucidate critical factors influencing the catalytic properties, taking Cu-based single atom alloys (SAAs) as examples. Our method relies on high-throughput calculations of 2669 CO adsorption configurations on 43 types of Cu-based SAAs with various surfaces. Extensive ML analyses reveal that low generalized coordination numbers and valence electron number are key features to determine catalytic performance. Applying our ML model with cross-group learning scheme, we demonstrate the model generalizes well between Cu-based SAAs with different alloying elements. Further, electronic structure calculations suggest surface negative center could enhance CO adsorption by back donating electrons to antibonding orbitals of CO. Finally, several SAAs, including PCu, AgCu, GaCu, ZnCu, SnCu, GeCu, InCu, and SiCu, are identified as promising CO2RR catalysts. Our work provides a paradigm for the rational design and fast screening of SAAs for various electrocatalytic reactions.

A unified drug—target interaction prediction framework based on knowledge graph and recommendation system

Qing Ye, Changyu Hsieh, Ziyi Yang, Yu Kang, Jiming Chen, Dongsheng Cao, Shibo He and Tingjun Hou

Prediction of drug-target interactions (DTI) plays a vital role in drug development in various areas, such as virtual screening, drug repurposing and identification of potential drug side effects. Despite extensive efforts have been invested in perfecting DTI prediction, existing methods still suffer from the high sparsity of DTI datasets and the cold start problem. Here, we develop KGE{\_}NFM, a unified framework for DTI prediction by combining knowledge graph (KG) and recommendation system. This framework firstly learns a low-dimensional representation for various entities in the KG, and then integrates the multimodal information via neural factorization machine (NFM). KGE{\_}NFM is evaluated under three realistic scenarios, and achieves accurate and robust predictions on four benchmark datasets, especially in the scenario of the cold start for proteins. Our results indicate that KGE{\_}NFM provides valuable insight to integrate KG and recommendation system-based techniques into a unified framework for novel DTI discovery.

On the Cut Dimension of a Graph

Troy Lee, Tongyang Li, Miklos Santha and Shengyu Zhang

Let G=(V,w) be a weighted undirected graph with m edges. The cut dimension of G is the dimension of the span of the characteristic vectors of the minimum cuts of G, viewed as vectors in {0,1}m. For every n≥2 we show that the cut dimension of an n-vertex graph is at most 2n−3, and construct graphs realizing this bound. The cut dimension was recently defined by Graur et al. \\cite{GPRW20}, who show that the maximum cut dimension of an n-vertex graph is a lower bound on the number of cut queries needed by a deterministic algorithm to solve the minimum cut problem on n-vertex graphs. For every n≥2, Graur et al.\ exhibit a graph on n vertices with cut dimension at least 3n/2−2, giving the first lower bound larger than n on the deterministic cut query complexity of computing mincut. We observe that the cut dimension is even a lower bound on the number of \emph{linear} queries needed by a deterministic algorithm to solve mincut, where a linear query can ask any vector x∈R(n2) and receives the answer wTx. Our results thus show a lower bound of 2n−3 on the number of linear queries needed by a deterministic algorithm to solve minimum cut on n-vertex graphs, and imply that one cannot show a lower bound larger than this via the cut dimension. We further introduce a generalization of the cut dimension which we call the ℓ1-approximate cut dimension. The ℓ1-approximate cut dimension is also a lower bound on the number of linear queries needed by a deterministic algorithm to compute minimum cut. It is always at least as large as the cut dimension, and we construct an infinite family of graphs on n=3k+1 vertices with ℓ1-approximate cut dimension 2n−2, showing that it can be strictly larger than the cut dimension.

Simulation of Condensed-Phase Spectroscopy with Near-Term Digital Quantum Computers

Cheekong Lee, Changyu Hsieh, Shengyu Zhang and Liang Shi

Spectroscopy is an indispensable tool for understanding the structures and dynamics of molecular systems. However, computational modeling of spectroscopy is challenging due to the exponential scaling of computational complexity with system sizes unless drastic approximations are made. Quantum computers could potentially overcome these classically intractable computational tasks, but the existing approaches using quantum computers to simulate spectroscopy can only handle isolated and static molecules. In this work, we develop a workflow that combines multi-scale modeling and a time-dependent variational quantum algorithm to compute the linear spectroscopy of systems interacting with their condensed-phase environment via the relevant time correlation function. We demonstrate the feasibility of our approach by numerically simulating the UV–vis absorption spectra of organic semiconductors. We show that our dynamical approach captures several spectral features that are otherwise overlooked by static methods. Our method can be directly used for other linear condensed-phase spectroscopy and could potentially be extended to nonlinear multi-dimensional spectroscopy.

Multi-constraint molecular generation based on conditional transformer, knowledge distillation and reinforcement learning

Jike Wang, Changyu Hsieh, Mingyang Wang, Xiaorui Wang, Zhenxing Wu, Dejun Jiang, Benben Liao, Xujun Zhang, Bo Yang, Qiaojun He, Dongsheng Cao, Xi Chen and Tingjun Hou

Machine learning-based generative models can generate novel molecules with desirable physiochemical and pharmacological properties from scratch. Many excellent generative models have been proposed, but multi-objective optimizations in molecular generative tasks are still quite challenging for most existing models. Here we proposed the multi-constraint molecular generation (MCMG) approach that can satisfy multiple constraints by combining conditional transformer and reinforcement learning algorithms through knowledge distillation. A conditional transformer was used to train a molecular generative model by efficiently learning and incorporating the structure--property relations into a biased generative process. A knowledge distillation model was then employed to reduce the model's complexity so that it can be efficiently fine-tuned by reinforcement learning and enhance the structural diversity of the generated molecules. As demonstrated by a set of comprehensive benchmarks, MCMG is a highly effective approach to traverse large and complex chemical space in search of novel compounds that satisfy multiple property constraints.

Motif-based Graph Self-Supervised Learning for Molecular Property Prediction

ZAIXI ZHANG, Qi Liu, Hao Wang, Chengqiang Lu and Cheekong Lee

Predicting molecular properties with data-driven methods has drawn much attention in recent years. Particularly, Graph Neural Networks (GNNs) have demonstrated remarkable success in various molecular generation and prediction tasks. In cases where labeled data is scarce, GNNs can be pre-trained on unlabeled molecular data to first learn the general semantic and structural information before being finetuned for specific tasks. However, most existing self-supervised pretraining frameworks for GNNs only focus on node-level or graph-level tasks. These approaches cannot capture the rich information in subgraphs or graph motifs. For example, functional groups (frequently-occurred subgraphs in molecular graphs) often carry indicative information about the molecular properties. To bridge this gap, we propose Motif-based Graph Self-supervised Learning (MGSSL) by introducing a novel self-supervised motif generation framework for GNNs. First, for motif extraction from molecular graphs, we design a molecule fragmentation method that leverages a retrosynthesis-based algorithm BRICS and additional rules for controlling the size of motif vocabulary. Second, we design a general motif-based generative pretraining framework in which GNNs are asked to make topological and label predictions. This generative framework can be implemented in two different ways, i.e., breadth-first or depth-first. Finally, to take the multi-scale information in molecular graphs into consideration, we introduce a multi-level self-supervised pre-training. Extensive experiments on various downstream benchmark tasks show that our methods outperform all state-of-the-art baselines.

Rapid and unconditional parametric reset protocol for tunable superconducting qubits

Yu Zhou, Zhenxing Zhang, Zelong Yin, Sainan Huai, Xiu Gu, Xiong Xu, Jonathan Allcock, Fuming Liu, Guanglei Xi, Qiaonian Yu, Hualiang Zhang, Mengyu Zhang, Hekang Li, Xiaohui Song, Zhan Wang, Dongning Zheng, Shuoming An, Yarui Zheng and Shengyu Zhang

Qubit initialization is a critical task in quantum computation and communication. Extensive efforts have been made to achieve this with high speed, efficiency and scalability. However, previous approaches have either been measurement-based and required fast feedback, suffered from crosstalk or required sophisticated calibration. Here, we report a fast and high-fidelity reset scheme, avoiding the issues above without any additional chip architecture. By modulating the flux through a transmon qubit, we realize a swap between the qubit and its readout resonator that suppresses the excited state population to 0.08{\%}{\thinspace}{\textpm}{\thinspace}0.08{\%} within 34 ns (284 ns if photon depletion of the resonator is required). Furthermore, our approach (i) can achieve effective second excited state depletion, (ii) has negligible effects on neighboring qubits, and (iii) offers a way to entangle the qubit with an itinerant single photon, useful in quantum communication applications.

Neural predictor based quantum architecture search

Shixin Zhang, Changyu Hsieh, Shengyu Zhang and Hong Yao

Variational quantum algorithms (VQAs) are widely speculated to deliver quantum advantages for practical problems under the quantum–classical hybrid computational paradigm in the near term. Both theoretical and practical developments of VQAs share many similarities with those of deep learning. For instance, a key component of VQAs is the design of task-dependent parameterized quantum circuits (PQCs) as in the case of designing a good neural architecture in deep learning. Partly inspired by the recent success of AutoML and neural architecture search (NAS), quantum architecture search (QAS) is a collection of methods devised to engineer an optimal task-specific PQC. It has been proven that QAS-designed VQAs can outperform expert-crafted VQAs in various scenarios. In this work, we propose to use a neural network based predictor as the evaluation policy for QAS. We demonstrate a neural predictor guided QAS can discover powerful quantum circuit ansatz, yielding state-of-the-art results for various examples from quantum simulation and quantum machine learning. Notably, neural predictor guided QAS provides a better solution than that by the random-search baseline while using an order of magnitude less of circuit evaluations. Moreover, the predictor for QAS as well as the optimal ansatz found by QAS can both be transferred and generalized to address similar problems.

Fast Extraction of Word Embedding from Q-Contexts

Junsheng Kong, Weizhao Li, Zeyi Liu, Ben Liao, Jiezhong Qiu, Changyu Hsieh, Yi Cai and Shengyu Zhang

The notion of word embedding plays a fundamental role in natural language processing (NLP). However, pre-training word embedding for very large-scale vocabulary is computationally challenging for most existing methods. In this work, we show that with merely a small fraction of contexts (Q-contexts) which are typical in the whole corpus (and their mutual information with words), one can construct high-quality word embedding with negligible errors. Mutual information between contexts and words can be encoded canonically as a sampling state, thus, Q-contexts can be fast constructed. Furthermore, we present an efficient and effective WEQ method, which is capable of extracting word embedding directly from these typical contexts. In practical scenarios, our algorithm runs 11 $\sim$ 13 times faster than well-established methods. By comparing with well-known methods such as matrix factorization, word2vec, GloVe and fasttext, we demonstrate that our method achieves comparable performance on a variety of downstream NLP tasks, and in the meanwhile maintains run-time and resource advantages over all these baselines.

Heterogeneous relational message passing networks for molecular dynamics simulations

Zun Wang, Chong Wang, Sibo Zhao, Yong Xu, Shaogang Hao, Chang Yu Hsieh, Binglin Gu and Wenhui Duan

With many frameworks based on message passing neural networks proposed to predict molecular and bulk properties, machine learning methods have tremendously shifted the paradigms of computational sciences underpinning physics, material science, chemistry, and biology. While existing machine learning models have yielded superior performances in many occasions, most of them model and process molecular systems in terms of homogeneous graph, which severely limits the expressive power for representing diverse interactions. In practice, graph data with multiple node and edge types is ubiquitous and more appropriate for molecular systems. Thus, we propose the heterogeneous relational message passing network (HermNet), an end-to-end heterogeneous graph neural networks, to efficiently express multiple interactions in a single model with <i>ab initio</i> accuracy. HermNet performs impressively against many top-performing models on both molecular and extended systems. Specifically, HermNet outperforms other tested models in nearly 75{\%}, 83{\%} and 94{\%} of tasks on MD17, QM9 and extended systems datasets, respectively. Finally, we elucidate how the design of HermNet is compatible with quantum mechanics from the perspective of the density functional theory. Besides, HermNet is a universal framework, whose sub-networks could be replaced by other advanced models.

Exploiting Different Levels of Parallelism in the Quantum Control Microarchitecture for Superconducting Qubits

Mengyu Zhang, Lei Xie, Zhenxing Zhang, Qiaonian Yu, Guanglei Xi, Hualiang Zhang, Fuming Liu, Yarui Zheng, Yicong Zheng and Shengyu Zhang

As current Noisy Intermediate Scale Quantum (NISQ) devices suffer from decoherence errors, any delay in the instruction execution of quantum control microarchitecture can lead to the loss of quantum information and incorrect computation results. Hence, it is crucial for the control microarchitecture to issue quantum operations to the Quantum Processing Unit (QPU) in time. As in classical microarchitecture, parallelism in quantum programs needs to be exploited for speedup. However, three challenges emerge in the quantum scenario: 1) the quantum feedback control can introduce significant pipeline stall latency; 2) timing control is required for all quantum operations; 3) QPU requires a deterministic operation supply to prevent the accumulation of quantum errors. In this paper, we propose a novel control microarchitecture design to exploit Circuit Level Parallelism (CLP) and Quantum Operation Level Parallelism (QOLP). Firstly, we develop a Multiprocessor architecture to exploit CLP, which supports dynamic scheduling of different sub-circuits. This architecture can handle parallel feedback control and minimize the potential overhead that disrupts the timing control. Secondly, we propose a Quantum Superscalar approach that exploits QOLP by efficiently executing massive quantum instructions in parallel. Both methods issue quantum operations to QPU deterministically. In the benchmark test of a Shor syndrome measurement, a six-core implementation of our proposal achieves up to 2.59 \texttimes{} speedup compared with a single core. For various canonical quantum computing algorithms, our superscalar approach achieves an average of 4.04 \texttimes{} improvement over a baseline design. Finally, We perform a simultaneous randomized benchmarking (simRB) experiment on a real QPU using the proposed microarchitecture for validation.

Introducing block design in graph neural networks for molecular properties prediction

Yuquan Li, Pengyong Li, Xing Yang, Changyu Hsieh, Shengyu Zhang, Xiaorui Wang, Ruiqiang Lu, Huanxiang Liu and Xiaojun Yao

The number of states required for describing a many-body quantum system increases exponentially with the number of particles; thus, it is time- and effort-consuming to exactly calculate molecular properties. Herein, we propose a deep learning algorithm named block-based graph neural network (BGNN) as an approximate solution. The algorithm can be understood as a representation learning process to extract useful interactions between a target atom and its neighboring atomic groups. Compared to other graph model variants, BGNN achieved the smallest mean absolute errors in most tasks on two large molecular datasets, QM9 and Alchemy. Our advanced machine learning method exhibits general applicability and can be readily employed for bioactivity prediction and other tasks relevant to drug discovery and materials design.

MG-BERT: leveraging unsupervised atomic representation learning for molecular property prediction

Xiaochen Zhang, Chengkun Wu, Zhijiang Yang, Zhenxing Wu, Jiacai Yi, Changyu Hsieh, Tingjun Hou and Dongsheng Cao

{Motivation: Accurate and efficient prediction of molecular properties is one of the fundamental issues in drug design and discovery pipelines. Traditional feature engineering-based approaches require extensive expertise in the feature design and selection process. With the development of artificial intelligence (AI) technologies, data-driven methods exhibit unparalleled advantages over the feature engineering-based methods in various domains. Nevertheless, when applied to molecular property prediction, AI models usually suffer from the scarcity of labeled data and show poor generalization ability.Results: In this study, we proposed molecular graph BERT (MG-BERT), which integrates the local message passing mechanism of graph neural networks (GNNs) into the powerful BERT model to facilitate learning from molecular graphs. Furthermore, an effective self-supervised learning strategy named masked atoms prediction was proposed to pretrain the MG-BERT model on a large amount of unlabeled data to mine context information in molecules. We found the MG-BERT model can generate context-sensitive atomic representations after pretraining and transfer the learned knowledge to the prediction of a variety of molecular properties. The experimental results show that the pretrained MG-BERT model with a little extra fine-tuning can consistently outperform the state-of-the-art methods on all 11 ADMET datasets. Moreover, the MG-BERT model leverages attention mechanisms to focus on atomic features essential to the target property, providing excellent interpretability for the trained model. The MG-BERT model does not require any hand-crafted feature as input and is more reliable due to its excellent interpretability, providing a novel framework to develop state-of-the-art models for a wide range of drug discovery tasks.}

Mining Toxicity Information from Large Amounts of Toxicity Data

Zhenxing Wu, Dejun Jiang, Jike Wang, Changyu Hsieh, Dongsheng Cao and Tingjun Hou

Safety is a main reason for drug failures, and therefore, the detection of compound toxicity and potential adverse effects in the early stage of drug development is highly desirable. However, accurate prediction of many toxicity endpoints is extremely challenging due to low accessibility of sufficient and reliable toxicity data, as well as complicated and diversified mechanisms related to toxicity. In this study, we proposed the novel multitask graph attention (MGA) framework to learn the regression and classification tasks simultaneously. MGA has shown excellent predictive power on 33 toxicity data sets and has the capability to extract general toxicity features and generate customized toxicity fingerprints. In addition, MGA provides a new way to detect structural alerts and discover the relationship between different toxicity tasks, which will be quite helpful to mine toxicity information from large amounts of toxicity data.

DeepOPF: A Deep Neural Network Approach for Security-Constrained DC Optimal Power Flow

Xiang Pan, Tianyu Zhao, Minghua Chen and Shengyu Zhang

We develop DeepOPF as a Deep Neural Network (DNN) approach for solving security-constrained direct current optimal power flow (SC-DCOPF) problems, which are critical for reliable and cost-effective power system operation. DeepOPF is inspired by the observation that solving SC-DCOPF problems for a given power network is equivalent to depicting a high-dimensional mapping from the load inputs to the generation and phase angle outputs. We first train a DNN to learn the mapping and predict the generations from the load inputs. We then directly reconstruct the phase angles from the generations and loads by using the power flow equations. Such a predict-and-reconstruct approach reduces the dimension of the mapping to learn, subsequently cutting down the size of the DNN and the amount of training data needed. We further derive a condition for tuning the size of the DNN according to the desired approximation accuracy of the load-generation mapping. We develop a post-processing procedure based on $\ell _1$-projection to ensure the feasibility of the obtained solution, which can be of independent interest. Simulation results for IEEE test cases show that DeepOPF generates feasible solutions with less than 0.2{\%} optimality loss, while speeding up the computation time by up to two orders of magnitude as compared to a state-of-the-art solver.

Neural-network variational quantum algorithm for simulating many-body dynamics

Chee Kong Lee, Pranay Patil, Shengyu Zhang and Chang Yu Hsieh

We propose a neural-network variational quantum algorithm to simulate the time evolution of quantum many-body systems. Based on a modified restricted Boltzmann machine (RBM) wave function ansatz, the proposed algorithm can be efficiently implemented in near-term quantum computers with low measurement cost. Using a qubit recycling strategy, only one ancilla qubit is required to represent all the hidden spins in an RBM architecture. The variational algorithm is extended to open quantum systems by employing a stochastic Schrödinger equation approach. Numerical simulations of spin-lattice models demonstrate that our algorithm is capable of capturing the dynamics of closed and open quantum many-body systems with high accuracy without suffering from the vanishing gradient (or “barren plateau”) issue for the considered system sizes.

RetroPrime: A Diverse, plausible and Transformer-based method for Single-Step retrosynthesis predictions

Xiaorui Wang, Yuquan Li, Jiezhong Qiu, Guangyong Chen, Huanxiang Liu, Benben Liao, Changyu Hsieh and Xiaojun Yao

Retrosynthesis prediction is a crucial task for organic synthesis. In this work, we propose a single-step template-free and Transformer-based method dubbed RetroPrime, integrating chemists’ retrosynthetic strategy of (1) decomposing a molecule into synthons then (2) generating reactants by attaching leaving groups. These two stages are accomplished with versatile Transformer models, respectively. RetroPrime achieves the Top-1 accuracy of 64.8{\%} and 51.4{\%}, when the reaction type is known and unknown, respectively, in the USPTO-50 K dataset. And the Top-1 accuracy is close to the state-of-the-art transformer-based method in the large dataset USPTO-full. It is known that outputs of the Transformer-based retrosynthesis model tend to suffer from insufficient diversity and high chemical implausibility. These problems may limit the potential of Transformer-based methods in real practice, yet few works address both issues simultaneously. RetroPrime is designed to tackle these challenges.

Hyperbolic relational graph convolution networks plus: a simple but highly efficient QSAR-modeling method

Zhenxing Wu, Dejun Jiang, Changyu Hsieh, Guangyong Chen, Ben Liao, Dongsheng Cao and Tingjun Hou

{Accurate predictions of druggability and bioactivities of compounds are desirable to reduce the high cost and time of drug discovery. After more than five decades of continuing developments, quantitative structure–activity relationship (QSAR) methods have been established as indispensable tools that facilitate fast, reliable and affordable assessments of physicochemical and biological properties of compounds in drug-discovery programs. Currently, there are mainly two types of QSAR methods, descriptor-based methods and graph-based methods. The former is developed based on predefined molecular descriptors, whereas the latter is developed based on simple atomic and bond information. In this study, we presented a simple but highly efficient modeling method by combining molecular graphs and molecular descriptors as the input of a modified graph neural network, called hyperbolic relational graph convolution network plus (HRGCN+). The evaluation results show that HRGCN+ achieves state-of-the-art performance on 11 drug-discovery-related datasets. We also explored the impact of the addition of traditional molecular descriptors on the predictions of graph-based methods, and found that the addition of molecular descriptors can indeed boost the predictive power of graph-based methods. The results also highlight the strong anti-noise capability of our method. In addition, our method provides a way to interpret models at both the atom and descriptor levels, which can help medicinal chemists extract hidden information from complex datasets. We also offer an HRGCN+'s online prediction service at https://quantum.tencent.com/hrgcn/.}

Could graph neural networks learn better molecular representation for drug discovery? A comparison study of descriptor-based and graph-based models

Dejun Jiang, Zhenxing Wu, Changyu Hsieh, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dongsheng Cao, Jian Wu and Tingjun Hou

Graph neural networks (GNN) has been considered as an attractive modelling method for molecular property prediction, and numerous studies have shown that GNN could yield more promising results than traditional descriptor-based methods. In this study, based on 11 public datasets covering various property endpoints, the predictive capacity and computational efficiency of the prediction models developed by eight machine learning (ML) algorithms, including four descriptor-based models (SVM, XGBoost, RF and DNN) and four graph-based models (GCN, GAT, MPNN and Attentive FP), were extensively tested and compared. The results demonstrate that on average the descriptor-based models outperform the graph-based models in terms of prediction accuracy and computational efficiency. SVM generally achieves the best predictions for the regression tasks. Both RF and XGBoost can achieve reliable predictions for the classification tasks, and some of the graph-based models, such as Attentive FP and GCN, can yield outstanding performance for a fraction of larger or multi-task datasets. In terms of computational cost, XGBoost and RF are the two most efficient algorithms and only need a few seconds to train a model even for a large dataset. The model interpretations by the SHAP method can effectively explore the established domain knowledge for the descriptor-based models. Finally, we explored use of these models for virtual screening (VS) towards HIV and demonstrated that different ML algorithms offer diverse VS profiles. All in all, we believe that the off-the-shelf descriptor-based models still can be directly employed to accurately predict various chemical endpoints with excellent computability and interpretability.

Unitary-coupled restricted Boltzmann machine ansatz for quantum simulations

Chang Yu Hsieh, Qiming Sun, Shengyu Zhang and Chee Kong Lee

Neural-network quantum state (NQS) has attracted significant interests as a powerful wave-function ansatz to model quantum phenomena. In particular, a variant of NQS based on the restricted Boltzmann machine (RBM) has been adapted to model the ground state of spin lattices and the electronic structures of small molecules in quantum devices. Despite these progresses, significant challenges remain with the RBM-NQS-based quantum simulations. In this work, we present a state-preparation protocol to generate a specific set of complex-valued RBM-NQS, which we name the unitary-coupled RBM-NQS, in quantum circuits. Our proposal expands the applicability of NQS as prior works deal exclusively with real-valued RBM-NQS for quantum algorithms. With this scheme, we achieve (1) modeling complex-valued wave functions, (2) using as few as one ancilla qubit to simulate M hidden spins in an RBM architecture, and (3) avoiding post-selections to improve scalability.

Transfer learning with graph neural networks for optoelectronic properties of conjugated oligomers

Cheekong Lee, Chengqiang Lu, Yue Yu, Qiming Sun, Changyu Hsieh, Shengyu Zhang, Qi Liu and Liang Shi

Despite the remarkable progress of machine learning (ML) techniques in chemistry, modeling the optoelectronic properties of long conjugated oligomers and polymers with ML remains challenging due to the difficulty in obtaining sufficient training data. Here, we use transfer learning to address the data scarcity issue by pre-training graph neural networks using data from short oligomers. With only a few hundred training data, we are able to achieve an average error of about 0.1 eV for the excited-state energy of oligothiophenes against time-dependent density functional theory (TDDFT) calculations. We show that the success of our transfer learning approach relies on the relative locality of low-lying electronic excitations in long conjugated oligomers. Finally, we demonstrate the transferability of our approach by modeling the lowest-lying excited-state energies of poly(3-hexylthiophene) in its single-crystal and solution phases using the transfer learning models trained with the data of gas-phase oligothiophenes. The transfer learning predicted excited-state energy distributions agree quantitatively with TDDFT calculations and capture some important qualitative features observed in experimental absorption spectra.

Spectral Transfer Tensor Method for Non-Markovian Noise Characterization

Yuqin Chen, Yicong Zheng, Shengyu Zhang and Changyu Hsieh

With continuing improvements on the quality of fabricated quantum devices, it becomes increasingly crucial to analyze noisy quantum process in greater details such as characterizing the non-Markovianity in a quantitative manner. In this work, we propose an experimental protocol, termed Spectral Transfer Tensor Maps (SpecTTM), to accurately predict the RHP non-Markovian measure of any Pauli channels without state-preparation and measurement (SPAM) errors. In fact, for Pauli channels, SpecTTM even allows the reconstruction of highly-precised noise power spectrum for qubits. At last, we also discuss how SpecTTM can be useful to approximately characterize non-Markovianity of non-Pauli channels via Pauli twirling in an optimal basis.

A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices

Jiezhong Qiu, Chi Wang, Ben Liao, Richard Peng and Jie Tang

We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a regular (aperiodic and irreducible) finite Markov chain. Specially, consider a random walk on a regular Markov chain and a Hermitian matrix-valued function on its state space. Our result gives exponentially decreasing bounds on the tail distributions of the extreme eigenvalues of the sample mean matrix. Our proof is based on the matrix expander (regular undirected graph) Chernoff bound [Garg et al. STOC '18] and scalar Chernoff-Hoeffding bounds for Markov chains [Chung et al. STACS '12]. Our matrix Chernoff bound for Markov chains can be applied to analyze the behavior of co-occurrence statistics for sequential data, which have been common and important data signals in machine learning. We show that given a regular Markov chain with n states and mixing time t, we need a trajectory of length O(t(log(n) + log(t))/$e^{2}$) to achieve an estimator of the co-occurrence matrix with error bound e. We conduct several experiments and the experimental results are consistent with the exponentially fast convergence rate from theoretical analysis. Our result gives the first bound on the convergence rate of the co-occurrence matrix and the first sample complexity analysis in graph representation learning.

TrimNet: learning molecular representation from triplet messages for biomedicine

Pengyong Li, Yuquan Li, Changyu Hsieh, Shengyu Zhang, Xianggen Liu, Huanxiang Liu, Sen Song and Xiaojun Yao

{Computational methods accelerate drug discovery and play an important role in biomedicine, such as molecular property prediction and compound–protein interaction (CPI) identification. A key challenge is to learn useful molecular representation. In the early years, molecular properties are mainly calculated by quantum mechanics or predicted by traditional machine learning methods, which requires expert knowledge and is often labor-intensive. Nowadays, graph neural networks have received significant attention because of the powerful ability to learn representation from graph data. Nevertheless, current graph-based methods have some limitations that need to be addressed, such as large-scale parameters and insufficient bond information extraction.In this study, we proposed a graph-based approach and employed a novel triplet message mechanism to learn molecular representation efficiently, named triplet message networks (TrimNet). We show that TrimNet can accurately complete multiple molecular representation learning tasks with significant parameter reduction, including the quantum properties, bioactivity, physiology and CPI prediction. In the experiments, TrimNet outperforms the previous state-of-the-art method by a significant margin on various datasets. Besides the few parameters and high prediction accuracy, TrimNet could focus on the atoms essential to the target properties, providing a clear interpretation of the prediction tasks. These advantages have established TrimNet as a powerful and useful computational tool in solving the challenging problem of molecular representation learning.The quantum and drug datasets are available on the website of MoleculeNet: http://moleculenet.ai. The source code is available in GitHub: https://github.com/yvquanli/trimnet.xjyao@lzu.edu.cn, songsen@tsinghua.edu.cn}

A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time

Jonathan Allcock and Changyu Hsieh

We propose a quantum algorithm for training nonlinear support vector machines (SVM) for feature space learning where classical input data is encoded in the amplitudes of quantum states. Based on the classical SVM-perf algorithm of Joachims, our algorithm has a running time which scales linearly in the number of training examplesm(up to polylogarithmic factors) and applies to the standard soft-marginℓ1-SVM model. In contrast, while classical SVM-perf has demonstrated impressive performance on both linear and nonlinear SVMs, its efficiency is guaranteed only in certain cases: it achieves linearmscaling only for linear SVMs, where classification is performed in the original input data space, or for the special cases of low-rank or shift-invariant kernels. Similarly, previously proposed quantum algorithms either have super-linear scaling inm, or else apply to different SVM models such as the hard-margin or least squaresℓ2-SVM which lack certain desirable properties of the soft-marginℓ1-SVM model. We classically simulate our algorithm and give evidence that it can perform well in practice, and not only for asymptotically large data sets.

Quantum Algorithms for Feedforward Neural Networks

Jonathan Allcock, Changyu Hsieh, Iordanis Kerenidis and Shengyu Zhang

Quantum machine learning has the potential for broad industrial applications, and the development of quantum algorithms for improving the performance of neural networks is of particular interest given the central role they play in machine learning today. We present quantum algorithms for training and evaluating feedforward neural networks based on the canonical classical feedforward and backpropagation algorithms. Our algorithms rely on an efficient quantum subroutine for approximating inner products between vectors in a robust way, and on implicitly storing intermediate values in quantum random access memory for fast retrieval at later stages. The running times of our algorithms can be quadratically faster in the size of the network than their standard classical counterparts since they depend linearly on the number of neurons in the network, and not on the number of connections between neurons. Furthermore, networks trained by our quantum algorithm may have an intrinsic resilience to overfitting, as the algorithm naturally mimics the effects of classical techniques used to regularize networks. Our algorithms can also be used as the basis for new quantum-inspired classical algorithms with the same dependence on the network dimensions as their quantum counterparts but with quadratic overhead in other parameters that makes them relatively impractical.

Machine learning Frenkel Hamiltonian parameters to accelerate simulations of exciton dynamics

Ardavan Farahvash, Cheekong Lee, Qiming Sun, Liang Shi and Adam P. Willard

In this manuscript, we develop multiple machine learning (ML) models to accelerate a scheme for parameterizing site-based models of exciton dynamics from all-atom configurations of condensed phase sexithiophene systems. This scheme encodes the details of a system’s specific molecular morphology in the correlated distributions of model parameters through the analysis of many single-molecule excited-state electronic-structure calculations. These calculations yield excitation energies for each molecule in the system and the network of pair-wise intermolecular electronic couplings. Here, we demonstrate that the excitation energies can be accurately predicted using a kernel ridge regression (KRR) model with Coulomb matrix featurization. We present two ML models for predicting intermolecular couplings. The first one utilizes a deep neural network and bi-molecular featurization to predict the coupling directly, which we find to perform poorly. The second one utilizes a KRR model to predict unimolecular transition densities, which can subsequently be analyzed to compute the coupling. We find that the latter approach performs excellently, indicating that an effective, generalizable strategy for predicting simple bimolecular properties is through the indirect application of ML to predict higher-order unimolecular properties. Such an approach necessitates a much smaller feature space and can incorporate the insight of well-established molecular physics.

ASGN: An Active Semi-Supervised Graph Neural Network for Molecular Property Prediction

Zhongkai Hao, Chengqiang Lu, Zhenya Huang, Hao Wang, Zheyuan Hu, Qi Liu, Enhong Chen and Cheekong Lee

Molecular property prediction (e.g., energy) is an essential problem in chemistry and biology. Unfortunately, many supervised learning methods usually suffer from the problem of scarce labeled molecules in the chemical space, where such property labels are generally obtained by Density Functional Theory (DFT) calculation which is extremely computational costly. An effective solution is to incorporate the unlabeled molecules in a semi-supervised fashion. However, learning semi-supervised representation for large amounts of molecules is challenging, including the joint representation issue of both molecular essence and structure, the conflict between representation and property leaning. Here we propose a novel framework called Active Semi-supervised Graph Neural Network (ASGN) by incorporating both labeled and unlabeled molecules. Specifically, ASGN adopts a teacher-student framework. In the teacher model, we propose a novel semi-supervised learning method to learn general representation that jointly exploits information from molecular structure and molecular distribution. Then in the student model, we target at property prediction task to deal with the learning loss conflict. At last, we proposed a novel active learning strategy in terms of molecular diversities to select informative data during the whole framework learning. We conduct extensive experiments on several public datasets. Experimental results show the remarkable performance of our ASGN framework.

A survey on HHL algorithm: From theory to application in quantum machine learning

Bojia Duan, Jiabin Yuan, Chaohua Yu, Jianbang Huang and Changyu Hsieh

The Harrow-Hassidim-Lloyd (HHL) algorithm is a method to solve the quantum linear system of equations that may be found at the core of various scientific applications and quantum machine learning models including the linear regression, support vector machines and recommender systems etc. After reviewing the necessary background on elementary quantum algorithms, we provide detailed account of how HHL is exploited in different quantum machine learning (QML) models, and how it provides the desired quantum speedup in all these models. At the end, we briefly discuss some of the remaining challenges ahead for HHL-based QML models and related methods.

Constant depth fault-tolerant Clifford circuits for multi-qubit large block codes

Yicong Zheng, Chingyi Lai, Todd A Brun and Leongchuan Kwek

Fault-tolerant quantum computation (FTQC) schemes using large block codes that encode k > 1 qubits in n physical qubits can potentially reduce the resource overhead to a great extent because of their high encoding rate. However, the fault-tolerant (FT) logical operations for the encoded qubits are difficult to find and implement, which usually takes not only a very large resource overhead but also long in situ computation time. In this paper, we focus on Calderbank–Shor–Steane [[n, k, d]] (CSS) codes and their logical FT Clifford circuits. We show that the depth of an arbitrary logical Clifford circuit can be implemented fault-tolerantly in O(1) steps in situ via either Knill or Steane syndrome measurement circuit, with the qualified ancilla states efficiently prepared. Particularly, for those codes satisfying k/n ∼ Θ(1), the resource scaling for Clifford circuits implementation on the logical level can be the same as on the physical level up to a constant, which is independent of code distance d. With a suitable pipeline to produce ancilla states, our scheme requires only a modest resource cost in physical qubits, physical gates, and computation time for very large scale FTQC.

Quantum algorithms for graph problems with cut queries

Troy Lee, Miklos Santha and Shengyu Zhang

Let G be an n-vertex graph with m edges. When asked a subset S of vertices, a cut query on G returns the number of edges of G that have exactly one endpoint in S. We show that there is a bounded-error quantum algorithm that determines all connected components of G after making O(log(n)6) many cut queries. In contrast, it follows from results in communication complexity that any randomized algorithm even just to decide whether the graph is connected or not must make at least Ω(n/log(n)) many cut queries. We further show that with O(log(n)8) many cut queries a quantum algorithm can with high probability output a spanning forest for G. En route to proving these results, we design quantum algorithms for learning a graph using cut queries. We show that a quantum algorithm can learn a graph with maximum degree d after O(d log(n)2) many cut queries, and can learn a general graph with many cut queries. These two upper bounds are tight up to the poly-logarithmic factors, and compare to Ω(dn) and Ω(m/log(n)) lower bounds on the number of cut queries needed by a randomized algorithm for the same problems, respectively. The key ingredients in our results are the Bernstein-Vazirani algorithm, approximate counting with “OR queries”, and learning sparse vectors from inner products as in compressed sensing.

Representing the Molecular Signatures of Disordered Molecular Semiconductors in Size-Extendable Models of Exciton Dynamics

Chee Kong Lee and Adam P. Willard

This manuscript presents an approach to developing size-extendable phenomenological site-based models for simulating exciton dynamics in disordered organic molecular semiconducting materials. This approach extends an existing methodology that assigns the parameters of the time-dependent Frenkel exciton model by applying fragmentation-based electronic structure calculations to the output of classical molecular dynamics simulations. This methodology is inherently limited by the system size of the all-atom simulation, which is well below the performance capability of site-based models. Here, we demonstrate that this system size limitation can be effectively overcome by defining a size-extendable surrogate model based on the correlated parameter statistics derived from existing fragmentation-based methods. We demonstrate our approach on a monolayer film of sexithiophene molecules, first validating the accuracy of the surrogate system in reproducing exciton dynamical properties of a 150 molecule system, then extending it to systems of 2500 molecules. With this extended system, we explore the sensitivity of exciton dynamics to variations in the temperature as well as the amplitude and spatial correlations of energetic disorder. We conclude that exciton dynamics can be significantly enhanced in morphologies with spatially correlated molecular configurations but only if the overall distribution of site energies is sufficiently broad.

Deep Learning for Optoelectronic Properties of Organic Semiconductors

Chengqiang Lu, Qi Liu, Qiming Sun, Changyu Hsieh, Shengyu Zhang, Liang Shi and Cheekong Lee

Atomistic modeling of the optoelectronic properties of organic semiconductors (OSCs) requires a large number of excited-state electronic-structure calculations, a computationally daunting task for many OSC applications. In this work, we advocate the use of deep learning to address this challenge and demonstrate that state-of-the-art deep neural networks (DNNs) are capable of accurately predicting various electronic properties of an important class of OSCs, i.e., oligothiophenes (OTs), including their HOMO and LUMO energies, excited-state energies and associated transition dipole moments. Among the tested DNNs, SchNet shows the best performance for OTs of different sizes, achieving average prediction errors in the range of 20–80 meV. We show that SchNet also consistently outperforms shallow feed-forward neural networks, especially in difficult cases with large molecules or limited training data. We further show that SchNet could predict the transition dipole moment accurately, a task previously known to be difficult for feed-forward neural networks, and we ascribe the relatively large errors in transition dipole prediction seen for some OT configurations to the charge-transfer character of their excited states. Finally, we demonstrate the effectiveness of SchNet by modeling the UV–vis absorption spectra of OTs in dichloromethane, and a good agreement is observed between the calculated and experimental spectra.

Non-Markovian Noise Characterization with the Transfer Tensor Method

Yuqin Chen, Kaili Ma, Yicong Zheng, Jonathan Allcock, Shengyu Zhang and Changyu Hsieh

We propose simple protocols for performing quantum noise spectroscopy based on the method of transfer tensor maps (TTM), [Phys. Rev. Lett. 112, 110401 (2014)]. The TTM approach is a systematic way to deduce the memory kernel of a time-nonlocal quantum master equation via quantum process tomography. With access to the memory kernel it is possible to (1) assess the non-Markovianity of a quantum process, (2) reconstruct the noise spectral density beyond pure dephasing models, and (3) investigate collective decoherence in multiqubit devices. We illustrate the usefulness of TTM spectroscopy on the IBM Quantum Experience platform, and demonstrate that the qubits in the IBM device are subject to mild non-Markovian dissipation with spatial correlations.

Personalized Fairness-Aware Re-Ranking for Microlending

Weiwen Liu, Jun Guo, Nasim Sonboli, Robin Burke and Shengyu Zhang

Microlending can lead to improved access to capital in impoverished countries. Recommender systems could be used in microlending to provide efficient and personalized service to lenders. However, increasing concerns about discrimination in machine learning hinder the application of recommender systems to the microfinance industry. Most previous recommender systems focus on pure personalization, with fairness issue largely ignored. A desirable fairness property in microlending is to give borrowers from different demographic groups a fair chance of being recommended, as stated by Kiva. To achieve this goal, we propose a Fairness-Aware Re-ranking (FAR) algorithm to balance ranking quality and borrower-side fairness. Furthermore, we take into consideration that lenders may differ in their receptivity to the diversification of recommended loans, and develop a Personalized Fairness-Aware Re-ranking (PFAR) algorithm. Experiments on a real-world dataset from Kiva.org show that our re-ranking algorithm can significantly promote fairness with little sacrifice in accuracy, and be attentive to individual lender preference on loan diversity.

Understanding and Utilizing Deep Neural Networks Trained with Noisy Labels

Pengfei Chen, Ben Ben Liao, Guangyong Chen and Shengyu Zhang

Noisy labels are ubiquitous in real-world datasets, which poses a challenge for robustly training deep neural networks (DNNs) as DNNs usually have the high capacity to memorize the noisy labels. In this paper, we find that the test accuracy can be quantitatively characterized in terms of the noise ratio in datasets. In particular, the test accuracy is a quadratic function of the noise ratio in the case of symmetric noise, which explains the experimental findings previously published. Based on our analysis, we apply cross-validation to randomly split noisy datasets, which identifies most samples that have correct labels. Then we adopt the Co-teaching strategy which takes full advantage of the identified samples to train DNNs robustly against noisy labels. Compared with extensive state-of-the-art methods, our strategy consistently improves the generalization performance of DNNs under both synthetic and real-world training noise.

Quantum machine learning

Jonathan Allcock and Shengyu Zhang

Quantum machine learning is at the crossroads of two of the most exciting current areas of research: quantum computing and classical machine learning. Although the field is still in its infancy, the body of literature is already large enough to warrant several review articles [1–3]. This short survey focuses on a selection of significant recent results on the subtopic of quantum neural networks, an area that hopes to build on the enormous impact that classical neural networks have had. In particular, we concentrate on quantum generalizations of popular neural-network concepts such as Boltzmann machines, generative adversarial networks and autoencoders, as well as applications of classical neural networks to quantum information and vice versa.

Psrec: Social Recommendation with Pseudo Ratings

Yitong Meng, Guangyong Chen, Jiajin Li and Shengyu Zhang

Data sparsity and cold start are two major problems of collaborative filtering based recommender systems. In many modern Internet applications, we have a social network over the users of recommender systems, from which social information can be utilized to improve the accuracy of recommendation. In this paper, we propose a novel trust-based matrix factorization model. Unlike most existing social recommender systems which use social information in the form of a regularizer on parameters of recommendation algorithms, we utilize the social information to densify the training data set by filling certain missing values (handle the data sparsity problem). In addition, by employing different pseudo rating generating criteria on cold start users and normal users, we can also partially solve the cold start problem effectively. Experiment results on real-world data sets demonstrated the superiority of our method over state-of-art approaches.

Field-Aware Probabilistic Embedding Neural Network for CTR Prediction

Weiwen Liu, Ruiming Tang, Jiajin Li, Jinkai Yu, Huifeng Guo, Xiuqiang He and Shengyu Zhang

For Click-Through Rate (CTR) prediction, Field-aware Factorization Machines (FFM) have exhibited great effectiveness by considering field information. However, it is also observed that FFM suffers from the overfitting problem in many practical scenarios. In this paper, we propose a Field-aware Probabilistic Embedding Neural Network (FPENN) model with both good generalization ability and high accuracy. FPENN estimates the probability distribution of the field-aware embedding rather than using the single point estimation (the maximum a posteriori estimation) to prevent overfitting. Both low-order and high-order feature interactions are considered to improve the accuracy. FPENN consists of three components, i.e., FPE component, Quadratic component and Deep component. FPE component outputs probabilistic embedding to the other two components, where various confidence levels for feature embeddings are incorporated to enhance the robustness and the accuracy. Quadratic component is designed for extracting low-order feature interactions, while Deep component aims at capturing high-order feature interactions. Experiments are conducted on two benchmark datasets, Avazu and Criteo. The results confirm that our model alleviates the overfitting problem while having a higher accuracy.

Policy Optimization with Second-Order Advantage Information

Jiajin Li, Baoxiang Wang and Shengyu Zhang

Policy optimization on high-dimensional continuous control tasks exhibits its difficulty caused by the large variance of the policy gradient estimators. We present the action subspace dependent gradient (ASDG) estimator which incorporates the Rao-Blackwell theorem (RB) and Control Variates (CV) into a unified framework to reduce the variance. To invoke RB, our proposed algorithm (POSA) learns the underlying factorization structure among the action space based on the second-order advantage information. POSA captures the quadratic information explicitly and efficiently by utilizing the wide \& deep architecture. Empirical studies show that our proposed approach demonstrates the performance improvements on high-dimensional synthetic settings and OpenAI Gym's MuJoCo continuous control tasks.

Contextual Dependent Click Bandit Algorithm for Web Recommendation

Shuai Li and Shengyu Zhang

In recommendation systems, it has been an increasing emphasis on recommending potentially novel and interesting items in addition to currently confirmed attractive ones. In this paper, we propose a contextual bandit algorithm for web page recommendation in the dependent click model (DCM), which takes user and web page features into consideration and automatically balances between exploration and exploitation. In addition, unlike many previous contextual bandit algorithms which assume that the click through rate is a linear function of features, we enhance the representability by adopting the generalized linear models, which include both linear and logistic regressions and have exhibited stronger performance in many binary-reward applications. We prove an upper bound of $\\~{O}(d\sqrt{n})$ on the regret of the proposed algorithm. Experiments are conducted on both synthetic and real-world data, and the results demonstrate significant advantages of our algorithm.

Algorithms for Trip-Vehicle Assignment in Ride-Sharing

Xiaohui Bei and Shengyu Zhang

We investigate the ride-sharing assignment problem from an algorithmic resource allocation point of view. Given a number of requests with source and destination locations, and a number of available car locations, the task is to assign cars to requests with two requests sharing one car. We formulate this as a combinatorial optimization problem, and show that it is NP-hard. We then design an approximation algorithm which guarantees to output a solution with at most 2.5 times the optimal cost. Experiments are conducted showing that our algorithm actually has a much better approximation ratio (around 1.2) on synthetically generated data.

Linear-Time Algorithm for Quantum 2SAT

Itai Arad, Miklos Santha, Aarthi Sundaram and Shengyu Zhang

A well-known result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors Πij on a system of n qubits, and the task is to decide whether the Hamiltonian H=∑Πij has a 0-eigenvalue, or all eigenvalues are greater than 1/nα for some α=O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding a ground state of 2-local frustration-free Hamiltonians of spin 12, a well-studied model believed to capture certain key properties in modern condensed matter physics. Bravyi has shown that the quantum 2-SAT problem has a deterministic algorithm of complexity O(n4) in the algebraic model of computation where every arithmetic operation on complex numbers can be performed in unit time, and n is the number of variables. In this paper we give a deterministic algorithm in the algebraic model with running time O(n+m), where m is the number of local projectors, therefore achieving the best possible complexity in that model. We also show that if in the input every number has a constant size representation then the bit complexity of our algorithm is O((n+m)M(n)), where M(n) denotes the complexity of multiplying two n-bit integers.