Computing quopit Clifford circuit amplitudes by the sum-over-paths technique

Abstract

By the Gottesman-Knill Theorem, the outcome probabilities of Clifford circuits can be computed efficiently. We present an alternative proof of this result for quopit Clifford circuits (i.e., Clifford circuits on collections of $p$-level systems, where $p$ is an odd prime) using Feynman's sum-over-paths technique, which allows the amplitudes of arbitrary quantum circuits to be expressed in terms of a weighted sum over computational paths. For a general quantum circuit, the sum over paths contains an exponential number of terms, and no efficient classical algorithm is known that can compute the sum. For quopit Clifford circuits, however, we show that the sum over paths takes a special form: it can be expressed as a product of Weil sums with quadratic polynomials, which can be computed efficiently. This provides a method for computing the outcome probabilities and amplitudes of such circuits efficiently, and is an application of the circuit-polynomial correspondence which relates quantum circuits to low-degree polynomials.

10 pages, 2 figures

References in corpus (1)

• Further extensions of Clifford circuits and their classical simulation complexities

Cited by in corpus (11)

• Towards Large-scale Functional Verification of Universal Quantum Circuits
• On the CNOT-complexity of CNOT-PHASE circuits
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures
• Classical simulation of quantum circuits by half Gauss sums
• Discrete Wigner Function Derivation of the Aaronson-Gottesman Tableau Algorithm
• Symbolic Synthesis of Clifford Circuits and Beyond
• Quantum Path Computing: Computing Architecture with Propagation Paths in Multiple Plane Diffraction of Classical Sources of Fermion and Boson Particles
• Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank
• Wasserstein Complexity of Quantum Circuits
• Improved Strong Simulation of Universal Quantum Circuits
• Unitary Subgroup Testing