Bryan O'Gorman

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2021-184

August 12, 2021

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-184.pdf

Quantum computers now exist, and will likely continue to get bigger and better. But will they ever be useful? That is, are there real-world problems that future quantum computers will be able to solve well enough in a reasonable amount of time, but for which classical computers cannot do the same? This thesis presents a collection of results that together address this question from different directions. The first part limits the utility of quantum computers. We show how to characterize and minimize the cost (in time and memory) of simulating quantum computations on a classical computer in terms of the congestion (a graph property) of a graphical representation of the quantum computation. Therefore, for a quantum computation to have an advantage over classical computation, it must have large congestion. Even when that is the case, better classical simulations, costly though they may be, can help validate and develop quantum computers. We also prove that the fundamental problem of quantum chemistry, the electronic structure problem, is QMA-complete. Therefore, under standard complexity-theoretic assumptions, the solution must be represented using a quantum state, and yet still even quantum computers cannot efficiently find it. The second part includes methods for applying and compiling quantum algorithms in order to maximize the utility of the hardware we have, now and in the future. We introduce the strategy of generalized swap networks and show how to use them to compile quantum algorithms for quantum chemistry and classical optimization. We combine quantum computation with constraint programming in two ways: we show how to combine existing quantum algorithms to speed up the solution of constraint programming problems, which capture a wide range of realistic application domains, and also discuss the application of constraint programming to compiling quantum algorithms. We also present a framework for generalizing the Quantum Approximate Optimization Algorithm to what we call the Quantum Alternating Operator Ansatz. Many of the algorithms are heuristic, but by improving the efficiency of their implementation on actual devices, we improve our chances of successfully trying them out and seeing if they work or not.

Advisors: Umesh Vazirani and Birgitta Whaley

---

BibTeX citation:

@phdthesis{O'Gorman:EECS-2021-184,
    Author= {O'Gorman, Bryan},
    Title= {Quantum Simulation: Upper and Lower Bounds},
    School= {EECS Department, University of California, Berkeley},
    Year= {2021},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-184.html},
    Number= {UCB/EECS-2021-184},
    Abstract= {Quantum computers now exist, and will likely continue to get bigger and better. But will they
ever be useful? That is, are there real-world problems that future quantum computers will be
able to solve well enough in a reasonable amount of time, but for which classical computers
cannot do the same? This thesis presents a collection of results that together address this
question from different directions. The first part limits the utility of quantum computers. We
show how to characterize and minimize the cost (in time and memory) of simulating quantum
computations on a classical computer in terms of the congestion (a graph property) of a
graphical representation of the quantum computation. Therefore, for a quantum computation
to have an advantage over classical computation, it must have large congestion. Even when
that is the case, better classical simulations, costly though they may be, can help validate
and develop quantum computers. We also prove that the fundamental problem of quantum
chemistry, the electronic structure problem, is QMA-complete. Therefore, under standard
complexity-theoretic assumptions, the solution must be represented using a quantum state,
and yet still even quantum computers cannot efficiently find it. The second part includes
methods for applying and compiling quantum algorithms in order to maximize the utility
of the hardware we have, now and in the future. We introduce the strategy of generalized
swap networks and show how to use them to compile quantum algorithms for quantum
chemistry and classical optimization. We combine quantum computation with constraint
programming in two ways: we show how to combine existing quantum algorithms to speed
up the solution of constraint programming problems, which capture a wide range of realistic
application domains, and also discuss the application of constraint programming to compiling
quantum algorithms. We also present a framework for generalizing the Quantum Approximate
Optimization Algorithm to what we call the Quantum Alternating Operator Ansatz. Many
of the algorithms are heuristic, but by improving the efficiency of their implementation on
actual devices, we improve our chances of successfully trying them out and seeing if they
work or not.},
}

EndNote citation:

%0 Thesis
%A O'Gorman, Bryan 
%T Quantum Simulation: Upper and Lower Bounds
%I EECS Department, University of California, Berkeley
%D 2021
%8 August 12
%@ UCB/EECS-2021-184
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-184.html
%F O'Gorman:EECS-2021-184