Classical Simulability of Quantum Circuits with Shallow Magic Depth
Y. Zhang, Yuxuan Zhang
Abstract
Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the of quantum magic, characterized by the number of <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <a:mi>T</a:mi> </a:math> gates or the stabilizer rank, to classical simulability. However, the effect of the 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 <d:math xmlns:d="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <d:mi>T</d:mi> </d:math> layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case in which all <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <g:mi>T</g:mi> </g:math> 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 <j:math xmlns:j="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <j:mi>T</j:mi> </j:math> -gate layer or merely replacing all <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <m:mi>T</m:mi> </m:math> gates with <p:math xmlns:p="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <p:msup> <p:mi>T</p:mi> <p:mrow> <p:mn>1</p:mn> <p:mo>/</p:mo> <p:mn>2</p:mn> </p:mrow> </p:msup> </p:math> , 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 <s:math xmlns:s="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <s:mn>1</s:mn> <s:mrow> <s:mrow> <s:mo>/</s:mo> <s:mi>poly</s:mi> </s:mrow> </s:mrow> <s:mo stretchy="false">(</s:mo> <s:mi>n</s:mi> <s:mo stretchy="false">)</s:mo> </s:math> additive error, we are able to give a polynomial-time classical algorithm to compute amplitudes, Pauli observables, and sampling from <x:math xmlns:x="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <x:mi>log</x:mi> <x:mo></x:mo> <x:mo stretchy="false">(</x:mo> <x:mi>n</x:mi> <x:mo stretchy="false">)</x:mo> </x:math> -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.