Quantum Adiabatic Algorithm Design using Reinforcement Learning

Abstract

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 non-linear Hamiltonian path when the encoding Hamiltonian is solvable, and that this RL-design approach remains applicable even when the non-linear 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 hardwares from trapped-ions and optical-lattices to superconducting-qubit devices.

arXiv comment11 pages, 10 figures

References in corpus (20)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Probing many-body dynamics on a 51-atom quantum simulator
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computing
• Quantum Computational Supremacy
• Photonic quantum information processing: a review
• Shortcut to adiabatic passage in two and three level atoms
• Quantum Search by Local Adiabatic Evolution
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Reinforcement Learning in Different Phases of Quantum Control
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Genuine 12-qubit entanglement on a superconducting quantum processor
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Stern-Gerlach detection of neutral atom qubits in a state dependent optical lattice
• Neural-network-designed pulse sequences for robust control of singlet-triplet qubits
• Analog Nature of Quantum Adiabatic Unstructured Search
• Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm

Cited by in corpus (20)

• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Faster State Preparation across Quantum Phase Transition Assisted by Reinforcement Learning
• Quantum imaginary time evolution steered by reinforcement learning
• A brief introduction to quantum algorithms
• Generalizable control for multiparameter quantum metrology
• Deep reinforcement learning for universal quantum state preparation via dynamic pulse control
• Active Learning Approach to Optimization of Experimental Control
• Detection of entangled states supported by reinforcement learning
• Universal Quantum Optimization with Cold Atoms in an Optical Cavity
• Practical Few-Atom Quantum Reservoir Computing
• Universal quantum state preparation via revised greedy algorithm
• Enhanced quantum state preparation via stochastic prediction of neural network
• The quantum annealing gap and quench dynamics in the exact cover problem
• Hard instance learning for quantum adiabatic prime factorization
• Quantum annealing sampling with a bias field
• Atom Cavity Encoding for NP-Complete Problems
• Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
• Preparation of Many-body Ground States by Time Evolution with Variational Microscopic Magnetic Fields and Incomplete Interactions
• Adiabatic Dynamics of Entanglement