Abstract:

Much current quantum computing research focuses on building quantum annealers, which are analogous to purposebuilt simulated annealing machines but enhanced by quantum properties. However, quantum annealing is not yet shown to provide a quantum speedup 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 quantumenhanced 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 runtime, 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 nonquantum 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.
