J. Mater. Chem. A
Oct. 2022

### 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.

J. Chem. Theory Comput.
Oct. 2022

### 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.

Sci. China Technol. Sci.
Sep. 2022

### 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.

ESA 2022
Sep. 2022

### 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 $Õ(2^{n/2})$ and $Õ(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 $Õ(2^{n/2})$ and $Õ(2^{2n/5})$, respectively.

Aug. 2022

### 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.

Phys. Rev. Lett.
Aug. 2022

### 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.

Front. Drug Des. Discov.
Jul. 2022

### 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.

Nat. Mach. Intell.
Jun. 2022

### 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.

AAAI
Jun. 2022

### 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.

ACL
May 2022

### 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.

Nat. Commun.
May 2022

### 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.

J. Chem. Theory Comput.
Apr. 2022

### 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.

Nat. Mach. Intell.
Mar. 2022

### 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.

Brief. Bioinform.
Mar. 2022

### 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.

J. Chem. Theory Comput.
Mar. 2022

### 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.

Phys. Rev. Lett.
Mar. 2022

### 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.

ASPLOS
Feb. 2022

### 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.

ICML
Jan. 2022

### 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.

Nat. Commun.
Jan. 2022

### 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.

NeurIPS
Dec. 2021

### 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.

J. Med. Chem.
Dec. 2021

### 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.

AAAI
Dec. 2021

### 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.

PRX Quantum
Dec. 2021

### 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.

CCC
Nov. 2021

### 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.

Green Energy Environ.
Nov. 2021

### 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.

ESA
Nov. 2021

### 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})$.

Nat. Commun.
Nov. 2021

### 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.

J. Chem. Theory Comput.
Nov. 2021

### 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.

NeurIPS
Oct. 2021

### 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.

Nat. Mach. Intell.
Oct. 2021

### 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.

Nat. Commun.
Oct. 2021

### 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.

IOP Mach. Learn.
Oct. 2021

### 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.

npj Comput. Mater.
Sep. 2021

### 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 ab initio 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.

CIKM
Sep. 2021

### 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.

MICRO
Aug. 2021

### 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.

Chem. Eng. J.
Jun. 2021

### 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.

Brief. Bioinform.
May 2021

### 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.

J. Med. Chem.
May 2021

### 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.

Phys. Rev. Res.
May 2021

### 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.

IEEE Trans. Power Syst.
May 2021

### 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.

Brief. Bioinform.
Apr. 2021

### 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/.

Chem. Eng. J.
Apr. 2021

### 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.

J. Cheminformatics
Feb. 2021

### 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.

J. Chem. Phys.
Jan. 2021

### 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.

npj Quantum Inform.
Jan. 2021

### 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.

NeurIPS
Dec. 2020

### 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.

Phys. Rev. Appl.
Dec. 2020

### 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.

Brief. Bioinform.
Nov. 2020

### 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

ACM Trans. Quantum. Comput.
Oct. 2020

### 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.

Quantum
Oct. 2020

### 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.

J. Chem. Phys.
Aug. 2020

### 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.

J. Phys. Chem. B
Aug. 2020

### 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.

Phys. Lett. A
Aug. 2020

### 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.

Quantum Sci. Technol.
Jul. 2020

### 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.

SODA
Jul. 2020

### 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.

Quantum Sci. Technol.
Jun. 2020

### 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.

J. Phys. Chem. C
Apr. 2020

### 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.

Phys. Rev. Appl.
Mar. 2020

### 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.

RecSys
Sep. 2019

### 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.

ICML
Jun. 2019

### 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.

Natl. Sci. Rev.
Nov. 2018

### 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.

RecSys
Sep. 2018

### 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.

COCOON
Sep. 2018

### 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.

ĲCAI
Jul. 2018

### 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.

AAAI
Jun. 2018

### 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.

AAAI
Apr. 2018

### 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.

Theory Comput.
Mar. 2018

### 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.