Modeling and Benchmarking Quantum Annealers as Optimizers and Samplers
Abstract
Quantum computing no longer resides in the realm of theory. Quantum information processing devices of increasing size are becoming readily available, and very soon they will be capable of performing computational tasks that are infeasible using classical computing. At the forefront of this race towards demonstrating the utility of quantum processing devices have been physical implementations of quantum annealing. Quantum annealing is a quantum algorithm to solve combinatorial optimization problems and to sample from probability distributions. It operates in an analogous way to the process of classical annealing, whereby, instead of slowly reducing the temperature, quantum fluctuations are slowly turned off. The hope is that quantum fluctuations allow for a more efficient exploration of the configuration space, leading to a quantum speedup over classical algorithms. If demonstrated, this would have immediate ramifications, since combinatorial optimization and sampling problems are ubiquitous. However, the theoretical basis for whether physically realizable quantum annealers can provide an unambiguous quantum speedup over classical computing remains incomplete. Progress has also been hampered by the detrimental effect of various sources of noise and errors on the performance of experimental quantum annealing devices. Consequently, no compelling theoretical or experimental evidence of the superiority of physically realizable quantum annealing over classical algorithms has been demonstrated to date. In order to tackle this problem, the Intelligence Advanced Research Projects Activity (IARPA) has initiated the Quantum Enhanced Optimization (QEO) program. In order to address both the theoretical and experimental obstacles facing quantum annealing, the program will undertake the design and implementation of a quantum annealing test bed with novel functionality that Òwill serve to demonstrate a plausible path to enhancement and a basis for design of application-scale quantum annealers." IARPA has selected USC to lead the QEO team, with one of us as the PI. Critical to the success of the QEO program is the ability to validate and benchmark quantum annealing devices. Confirming the presence of quantum effects a necessary condition for any quantum enhancement, requires realistic modeling of the system, including the effects of noise sources. Benchmarking requires a thorough comparison between the quantum annealer and state-of-the-art classical algorithms for solving the same computational task. Both of these aspects require a substantial amount of classical computation capability, that can be met with a computing cluster with multi-core CPUs and GPUs, as described in this proposal. The computational parallelism offered by such a setup will help to ensure our ability to successfully validate and benchmark the quantum annealing devices that will be developed under the QEO program, and thus to meet the QEO objectives.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1810227
Entities
People
- Tameem Albash
Organizations
- Army Contracting Command
- United States Army
- University of Southern California