Neil Julien Ross, Dalhousie University
As we approach the development of a quantum computer with tens of
well-controlled qubits, it is natural to ask what can be done with
such a device. Specifically, we would like to construct an example of
a practical problem that is beyond the reach of classical computers,
but that requires the fewest possible resources to solve on a quantum
computer. We address this problem by considering quantum simulation of
spin systems, a task that could be applied to understand phenomena in
condensed matter physics such as many-body localization. We synthesize
explicit quantum circuits for three leading quantum simulation
algorithms, one based on product formulas (PF), one based on
implementing the Taylor series as a linear combination of unitaries
(TS), and another using the recent quantum signal processing approach
(QSP). We employ a wide range of techniques to develop tighter error
bounds and optimize gate-level implementations. Surprisingly, even
for simulations of small systems, we find that the fourth-order PF
algorithm outperforms lower-order PF algorithms and that the TS and
QSP algorithms require even fewer gates (although at the cost of
requiring more qubits). However, the cost of PF algorithms can be
reduced significantly by using empirical error bounds, so that PF
algorithms remain competitive in contexts where a rigorous guarantee
on the accuracy of the simulation is not essential. Our circuits are
smaller by several orders of magnitude than those for the simplest
classically-hard instances of problems such as factoring and quantum
chemistry, and we hope they will pave the way toward the first
practical application of a quantum computer. Joint work with
A.M. Childs, D. Maslov, Y. Nam, and Y. Su.