Quantum circuit amplitude calculations are either easy or very hard

A Dichotomy for Exact Quantum Circuit Amplitudes

Computational Complexity

Summary

The paper shows which quantum circuits let you calculate exact probabilities quickly and which ones are much harder to solve. The authors classify all fixed sets of quantum gates into three kinds where computations are easy: those that just shuffle basis states with phases, those that keep states separate, and those changing to a special Clifford form. Any other set makes exact calculations as hard as counting problems known to be very difficult. Their proof builds connections between quantum circuits and tensor graph computations.

What this means in practice

  • For quantum software engineers: Decide if exact amplitude calculations for a quantum gate set are computationally feasible before building simulation tools.
  • For quantum hardware architects: Avoid certain gate libraries in hardware that require hard-to-compute amplitude evaluations for diagnostics and verification.

A theory result. No direct application yet.

Authors

Chenghua Liu, Boning Meng

Abstract

We classify the complexity of exactly computing computational-basis amplitudes for circuits over any fixed finite library of unitary qubit gates, with each gate allowed to act on any ordered tuple of distinct wires. Exact evaluation is polynomial-time computable if all gates permute the computational basis up to phases, all preserve product states, or all become Clifford under a common diagonal one-qubit unitary change of basis on every wire. For every other library, the problem is $\#\mathrm P$-hard under polynomial-time Turing reductions. Our proof connects circuit amplitudes to the Boolean Holant classification of tensor contractions on arbitrary graphs. For an algebraic library containing a nonmonomial gate and an entangling gate, we show how to simulate the joint use of a symmetric maximally entangled state and its adjoint at polynomial cost, using only amplitude queries over the original library. This lets us evaluate unrestricted contractions of the resulting gate and boundary tensors. Unitarity and the computational-basis boundaries then restrict the tractable cases to the three forms above. Algebraic specialization extends the dichotomy to arbitrary fixed complex gate entries under a symbolic exact-output convention.