Classical Simulability of Quantum Circuits with Shallow Magic Depth
Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the amount of quantum magic, characterized by the number of T gates or the stabilizer rank, to classical simulability. However, the effect of the distribut...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2025-02-01
|
| Series: | PRX Quantum |
| Online Access: | http://doi.org/10.1103/PRXQuantum.6.010337 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the amount of quantum magic, characterized by the number of T gates or the stabilizer rank, to classical simulability. However, the effect of the distribution of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and T layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case in which all T gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one T-gate layer or merely replacing all T gates with T^{1/2}, the Pauli evaluation task reveals a sharp complexity transition from being in P to being GapP-complete. Nevertheless, when the precision requirement is relaxed to 1/poly(n) additive error, we are able to give a polynomial-time classical algorithm to compute amplitudes, Pauli observables, and sampling from log(n)-sized marginal distributions for any magic-depth-1 circuit that is decomposable into a product of diagonal gates. This rules out certain forms of quantum advantage in these circuits. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth. |
|---|---|
| ISSN: | 2691-3399 |