Division of Computing and Communication Foundations

With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.

As noted on our webpage, the Proceedings of the IEEE specializes in surveys, reviews, and tutorials. The distinction between surveys and reviews is not always clear to readers and authors. Our working definition is that surveys discuss the current state of a subject and give an overview and summary of the published and ongoing work by researchers from all geographical regions and from all organizations contributing to the topic. Reviews contain more technical depth of the topics and usually discuss the technical background needed to understand and evaluate the contributions to the topics under investigation. Tutorials are teaching tools that present the background and current theory and methodologies of a topic. A tutorial is not about presenting new theory or methods, but may use current research as examples of applications of the techniques discussed. Currently, we publish many more surveys and reviews than tutorials.