Treasure Hunt for Computational Problems That Can Be Solved Faster by Quantum Annealing

• Activity Number: 650 - Quantum Computing: Optimization Algorithms and Applications
• Type: Topic Contributed
• Date/Time: Thursday, August 1, 2019 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Computing
• Author(s): Barry Sanders* and Archismita Dalal and Radhakrishnan Balu
• Companies: University of Calgary and University of Calgary and United States Army Research Laboratory
• Keywords: Quantum computing; Quantum annealing

Abstract

Much current quantum computing research focuses on building quantum annealers, which are analogous to purpose-built simulated annealing machines but enhanced by quantum properties. However, quantum annealing is not yet shown to provide a quantum speed-up for any computational problem thus far. On the other hand, optimism is rife that a computational speedup will be found for the right problem. We explain this search for quantum-enhanced computational problems as a treasure hunt for potential benefits of quantum annealing. This treasure hunt could have many buried treasures of similar types or be of quite different types, or perhaps no buried treasure exists at all.

We discuss how the value of these treasures are assessed, such as run-time, which is complicated and nuanced. The time to solve a problem instance, the scaling of the time to solve with respect to growing problem size, and fairly comparing quantum annealing times to non-quantum alternatives are subtle and discussed in detail. We formalize this treasure hunt as a search problem and discuss how machine intelligence could assist with solving the problem of finding computational problems that exhibit quantum speedup.