Online Program Home
My Program

Abstract Details

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
Abstract #303014 Presentation
Title: Treasure Hunt for Computational Problems That Can Be Solved Faster by Quantum Annealing
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

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.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2019 program