arXiv:2110.04782 · Physical Review A

Hard-instance learning for quantum adiabatic prime factorization

Jian Hui Lin, Zhengfeng Zhang, Junping Zhang, Xiaopeng Li

Published Jun 29, 2022• 6 citations

Abstract

Prime factorization is a difficult problem with classical computing, whose exponential hardness is the foundation of Rivest-Shamir-Adleman cryptography. With programable quantum devices, adiabatic quantum computing has been proposed as a plausible approach to solve prime factorization, having promising advantage over classical computing. Here, we find there are certain hard instances that are consistently intractable for both classical simulated annealing and unconfigured adiabatic quantum computing (AQC). Aiming at an automated architecture for optimal configuration of quantum adiabatic factorization, we apply a deep reinforcement learning (RL) method to configure the AQC algorithm. By setting the success probability of the worst-case problem instances as the reward to RL, we show the AQC performance on the hard instances is dramatically improved by RL configuration. The success probability also becomes more evenly distributed over different problem instances, meaning the configured AQC is more stable as compared to the unconfigured case. Through a technique of transfer learning, we find prominent evidence that the framework of AQC configuration is scalable---the configured AQC as trained on five qubits remains working efficiently on nine qubits with a minimal amount of additional training cost.

DOI: 10.1103/physreva.105.062455

Related papers

Reinforcement-Learning-Based Quantum Adiabatic Algorithm Design for Integer Programming

Jiawei Zhu

Adiabatic quantum computing (AQC) is a computation protocol to solve difficult problems exploiting quantum advantage, directly applicable to optimization problems. In performing the AQC, different configurations of the Hamiltonian path could lead to dramatic differences in the computation efficiency. It is thus crucial to configure the Hamiltonian path to optimize the computation performance of AQC. Here we apply a reinforcement learning approach to configure AQC for integer programming, where we find the learning process automatically converges to a quantum algorithm that exhibits scaling advantage over the trivial AQC using a linear Hamiltonian path. This reinforcement-learning-based approach for quantum adiabatic algorithm design for integer programming can well be adapted to the quantum resources in different quantum computation devices, due to its built-in flexibility.

SPINSep 1, 20210 citations

Quantum adiabatic algorithm design using reinforcement learning

Jian Hui Lin, Zhong Yuan Lai, Xiaopeng Li

Quantum algorithm design plays a crucial role in exploiting the computational advantage of quantum devices. Here we develop a deep-reinforcement-learning based approach for quantum adiabatic algorithm design. Our approach is generically applicable to a class of problems with solution hard-to-find but easy-to-verify, e.g., searching and NP-complete problems. We benchmark this approach in Grover-search and 3-SAT problems, and find that the adiabatic algorithm obtained by our RL approach leads to significant improvement in the resultant success probability. In application to Grover search, our RL design automatically produces an adiabatic quantum algorithm that has the quadratic speedup. We find for all our studied cases that quantitatively the RL-designed algorithm has a better performance compared to the analytically constructed nonlinear Hamiltonian path when the encoding Hamiltonian is solvable, and that this RL-design approach remains applicable even when the nonlinear Hamiltonian path is not analytically available. In 3-SAT we find RL design has fascinating transferability---the adiabatic algorithm obtained by training on a specific choice of clause number leads to better performance consistently over the linear algorithm on different clause numbers. These findings suggest the applicability of reinforcement learning for automated quantum adiabatic algorithm design. Further considering the established complexity equivalence of circuit and adiabatic quantum algorithms, we expect the RL-designed adiabatic algorithm to inspire novel circuit algorithms as well. Our approach is potentially applicable to different quantum hardware from trapped ions and optical lattices to superconducting-qubit devices.

arXiv:1812.10797Physical Review AMay 18, 202039 citations

Reinforcement learning architecture for automated quantum-adiabatic-algorithm design.

Jian Hui Lin, Zhong Yuan Lai, Xiaopeng Li

Quantum algorithm design lies in the hallmark of applications of quantum computation and quantum simulation. Here we put forward a deep reinforcement learning (RL) architecture for automated algorithm design in the framework of quantum adiabatic algorithm, where the optimal Hamiltonian path to reach a quantum ground state that encodes a compution problem is obtained by RL techniques. We benchmark our approach in Grover search and 3-SAT problems, and find that the adiabatic algorithm obtained by our RL approach leads to significant improvement in the success probability and computing speedups for both moderate and large number of qubits compared to conventional algorithms. The RL-designed algorithm is found to be qualitatively distinct from the linear algorithm in the resultant distribution of success probability. Considering the established complexity-equivalence of circuit and adiabatic quantum algorithms, we expect the RL-designed adiabatic algorithm to inspire novel circuit algorithms as well. Our approach offers a recipe to design quantum algorithms for generic problems through a machinery RL process, which paves a novel way to automated quantum algorithm design using artificial intelligence, potentially applicable to different quantum simulation and computation platforms from trapped ions and optical lattices to superconducting-qubit devices.

Dec 27, 20180 citations

Parametrized Quantum Policies for Reinforcement Learning

Sofiène Jerbi, Casper Gyurik, Marshall, Simon C. +2 more

With the advent of real-world quantum computing, the idea that parametrized quantum computations can be used as hypothesis families in a quantum-classical machine learning system is gaining increasing traction. Such hybrid systems have already shown the potential to tackle real-world tasks in supervised and generative learning, and recent works have established their provable advantages in special artificial tasks. Yet, in the case of reinforcement learning, which is arguably most challenging and where learning boosts would be extremely valuable, no proposal has been successful in solving even standard benchmarking tasks, nor in showing a theoretical learning advantage over classical algorithms. In this work, we achieve both. We propose a hybrid quantum-classical reinforcement learning model using very few qubits, which we show can be effectively trained to solve several standard benchmarking environments. Moreover, we demonstrate, and formally prove, the ability of parametrized quantum circuits to solve certain learning tasks that are intractable to classical models, including current state-of-art deep neural networks, under the widely-believed classical hardness of the discrete logarithm problem.

arXiv:2103.05577neural information processing systemsMar 9, 202173 citations

Quantum Semantic Learning by Reverse Annealing of an Adiabatic Quantum Computer

Lorenzo Rocutto, C. Destri, Enrico Prati

Abstract Restricted Boltzmann machines (RBMs) constitute a class of neural networks for unsupervised learning with applications ranging from pattern classification to quantum state reconstruction. Despite the potential representative power, the diffusion of RBMs is quite limited since their training process proves to be hard. The advent of commercial adiabatic quantum computers (AQCs) raised the expectation that the implementations of RBMs on such quantum devices can increase the training speed with respect to conventional hardware. Here, the feasibility of a complete RBM on AQCs is demonstrated, thanks to an embedding that associates the nodes of the neural networks to virtual qubits. A semantic quantum search is implemented thanks to a reverse annealing schedule. Such an approach exploits more information from the training data, mimicking the behavior of the classical Gibbs sampling algorithm. The semantic training is shown to quickly raise the sampling probability of a subset of the set of the configurations. Even without a proper optimization of the annealing schedule, the RBM semantically trained achieves good scores on reconstruction tasks. The development of such techniques paves the way toward the establishment of a quantum advantage of adiabatic quantum computers, especially given the foreseen improvement of such hardware.

arXiv:2003.11945Advanced Quantum TechnologiesDec 14, 202048 citations

Binary classification with adiabatic quantum optimization

Vasil S. Denchev

We study the problem of supervised binary classification from the perspective of deploying adiabatic quantum optimization in training. A vast body of prior academic work consisting of both theoretical and numerical studies has indicated that quantum technology promises to provide computational power that may be fundamentally superior to any classical computing methods. Given the abundance of NP-hard optimization problems that naturally arise in learning, it is clear that machine learning can immensely benefit from such an optimization tool. We describe a series of increasingly complex designs that result in computationally hard training problems of combinatorial nature. In return for accepting classical computational hardness, we retain theoretical properties such as maximal sparsity and robustness to label noise, which are otherwise sacrificed by convex methods for the sake of computational efficiency and sound theoretical footing. In order to be compatible with emerging quantum hardware technology, we formalize the training problem as quadratic unconstrained binary optimization. Our initial investigations focus on a simple training formulation with non-convex regularization that conforms to the architecture of existing quantum hardware and makes frugal use of a limited number of available physical qubits. Next, we extend this baseline formulation to a scalable algorithm, QBoost, which is able to train incrementally large-scale classifiers on data sets of practical interest. Further, we derive another algorithm, TotalQBoost, as a theoretically motivated totally corrective boosting algorithm with cardinality penalization that also makes use of quantum optimization. Both QBoost and TotalQBoost perform explicit cardinality regularization, which is the only known way of achieving maximal sparsity in the trained classifiers. We apply QBoost and TotalQBoost to three different real-world computer vision problems and make use of a quantum processor for solving the sequence of discrete optimization problems generated by one of them. Finally, we study a learning formulation with convex regularization and a non-convex loss function, q-loss, specifically designed for robust supervised learning in the presence of label noise as it occurs in practice. For compatibility with quantum hardware we derive the corresponding quadratic binary problem via variational approximation. For all proposed algorithms we compare results on a variety of popular synthetic and natural data sets against a rich selection of existing rival learning formulations.

Jan 1, 20134 citations