Toward the first quantum simulation with quantum speedup

By Andrew M. Childs, Dmitri Maslov, Y. Nam, Neil J. Ross, Yuan Su. Proceedings of the National Academy of Sciences of the United States of America, 2017

617 citations recorded by the source corpus.

Significance Near-term quantum computers will have limited numbers of qubits and will only be able to reliably perform limited numbers of gates. Therefore, it is crucial to identify applications of quantum processors that use the fewest possible resources. We argue that simulating the time evolution of spin systems is a classically hard problem of practical interest that is among the easiest to address with early quantum devices. We develop optimized implementations and perform detailed resource analyses for several leading quantum algorithms for this problem. By evaluating the best approaches to small-scale quantum simulation, we provide a detailed blueprint for what could be an early practical application of quantum computers. 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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/9308071e9e4e29c95b6cfc8a9e06510f931a28dd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Hamiltonian Simulation by Qubitization (2016, methodology): “Numerical Quantum signal processing: The numerical algorithm for decomposing target polynomials of degree Q into phases was originally claimed to be polynomial time [37], but only when counting arbitrary-precision arithmetical operations, and appeared to be ill-conditioned in case studies [49].”
t|ket⟩: a retargetable compiler for NISQ devices (2020, methodology): “These circuits are thought to be candidates for quantum advantage [85], and were used as a test case for the circuit optimizer by Nam et al [38].”
Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity (2018, methodology): “Compared to [50] we lower the T-count from 6L− 4 to 4L− 4 and explain how to apply the scheme to sizes L that are not powers of 2.”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, background): “Within the last few years, a host of new techniques have led to ever more powerful methods [18].”