Quantum Adiabatic Algorithm Design using Reinforcement Learning
This work addresses the challenge of automating quantum algorithm design for researchers and practitioners in quantum computing, offering a novel method that could inspire broader applications, though it is incremental in combining RL with quantum adiabatic methods.
The researchers tackled the problem of designing quantum adiabatic algorithms by developing a deep reinforcement learning approach, which achieved significant improvements in success probability for Grover-search and 3-SAT problems, including automatically producing an algorithm with quadratic speedup in Grover search.
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.