Quantum Algorithms Arising from Ideas in Physics

Currently, quantum computers are able to manipulate no more than a few handfuls of qubits. However, it is widely expected that in the next few decades, quantum computers that are large enough to do interesting things will be built. Currently, the most lucrative application of these appear to be in the areas of cryptography and the areas of simulation of quantum mechanics, which it is hoped will have great impact in the areas of physics, chemistry, and pharmaceutical research. However, a toolbox of techniques for designing algorithms could give quantum computers a much greater impact, if algorithms could be developed for them that speed up other classes of problems, especially ones that speed up finding either the optimal or approximation solutions for combinatorial search problems.

The PIs intend to investigate several algorithms in quantum computing, approaching them by using ideas from physics, computer science, and mathematics. The PIs view quantum information science as a branch of all of these disciplines, and believe that techniques from each area can open insights into the others. The questions the PIs intend to address are related to algorithms and protocols: (1) exploration instances of adiabatic quantum algorithms where they outperform classical algorithms, (2) an in-depth study of knot-based quantum money schemes, (3) an attempt to solve quantum versions of the satisfiability problem, and (4) investigate quantum approximate optimization algorithms.