Solving Verification and Validation Problems with Quantum Annealing Samplers
Abstract
In this effort, we studied the extent to which quantum annealer computing systems can provide a powerful platform for achieving quantum enhancements in tasks of counting or listing the solutions of combinatorial optimization problems that implement verification and validation (V and V) problems. In order to generate meaningful benchmarks that can be run on experimental quantum annealers, we devised an algorithm for verifiability and certifiably test the density of states of hard optimization problems based on population annealing, which then allowed us to enumerate beforehand the degeneracies of energy levels of V and V instances. We then tested the performance of the D-Wave 2000-qubit processor on the generated instances. Our observations show that quantum annealers do indeed sample the ground state manifolds of V and V problems rather uniformly however for these devices to be effective fair ground state samplers, their temperature and error rates must be substantially lowered. We hope that the results presented here will provide insight into the computational power of quantum devices and be useful for solving V and V problems going forward.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 13, 2020
- Accession Number
- AD1091305
Entities
People
- Itay Hen
Organizations
- University of Southern California