Optimization Via Open System Quantum Annealing
Technical Report,01 Sep 2012,31 Aug 2015
University of Southern California Los Angeles United States
Pagination or Media Count:
Many computationally challenging problems can be reduced to Quadratic Unconstrained Binary Optimization QUBO, which can be solved by a quantum evolution from a strong transverse field to a spin glass Hamiltonian also known as quantum annealing or QA. We have examined open system QA, using theoretical and experimental techniques to deepen our understanding of open system QA by situating it in the context of related, well studied classical and quantum problems. We have explored and elucidated the significance of tunneling in QA with Path Integral Monte Carlo. We have also provided signatures of quantum behavior of QA against closely related simulated annealing implementations, analytically, numerically, and experimentally. We have carried out a comprehensive comparison of geometrically-local open-system QA and classical solvers for computationally hard problems such as MAX-2-SAT. We have exploited and further developed a graph-theoretical mapping between the Ising spin glass partition function and circuit model decision problems, discovered in a previous ARO Quantum Algorithms funded project. We have made significant progress on error correction techniques for QA, both theoretically and experimentally, and in demonstration of quantum speedup.