Polynomial-time method estimates shallow quantum circuit outputs
Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
Computational ComplexityData Structures and Algorithms
Summary
Estimating the chances of certain outputs from quantum computers is usually very hard for regular computers to do quickly. The authors found a way to approximate these probabilities efficiently when the quantum circuits are shallow (have constant depth), even if the circuits connect qubits in complex ways. This means classical computers can now better mimic some tasks of such quantum devices in polynomial time, improving over previous much slower methods. The approach works for any output and uses a fixed level of accuracy.
What this means in practice
- •For quantum algorithm developers: Check output probabilities of shallow quantum circuits quickly on classical computers to guide algorithm design and testing.
- •For quantum hardware testers: Classically estimate expected quantum circuit outputs to validate and debug shallow quantum processors without relying only on quantum measurements.
A theory result. No direct application yet.
Authors
Matthew Coudron, Michael J. Gullans, Jon Nelson, Joel Rajakumar, Shi Jie Samuel Tan
Abstract
We give a deterministic classical algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and $x$ is an arbitrary $n$-bit output string. This improves over prior state-of-the-art algorithms that takes $n^{O(log(n))}$ time for the same task, $n^{O(log(log(n))}$ when $U$ is geometrically local, and $n^{O(1)}$ for 2D geometrically-local circuits.