Improved upper bounds on the stabilizer rank of magic states
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
<jats:p>In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>m</mml:mi></mml:math> copies of the magic state <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>T</mml:mi><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mo>=</mml:mo><mml:msup><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">(</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mn>0</mml:mn><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mo>+</mml:mo><mml:msup><mml:mi>e</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>i</mml:mi><mml:mi>π</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>4</mml:mn></mml:mrow></mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mn>1</mml:mn><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math> in the limit of large <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>m</mml:mi></mml:math>. In particular, we show that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>T</mml:mi><mml:msup><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>⊗</mml:mo><mml:mi>m</mml:mi></mml:mrow></mml:msup></mml:math> can be exactly expressed as a superposition of at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>α</mml:mi><mml:mi>m</mml:mi></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> stabilizer states, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>α</mml:mi><mml:mo>≤</mml:mo><mml:mn>0.3963</mml:mn></mml:math>, improving on the best previously known bound <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>α</mml:mi><mml:mo>≤</mml:mo><mml:mn>0.463</mml:mn></mml:math>. This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math>-qubit Clifford + T circuit <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>U</mml:mi></mml:math> with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>m</mml:mi></mml:math> uses of the T gate to within a given inverse polynomial relative error using a runtime <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">p</mml:mi><mml:mi mathvariant="normal">o</mml:mi><mml:mi mathvariant="normal">l</mml:mi><mml:mi mathvariant="normal">y</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>α</mml:mi><mml:mi>m</mml:mi></mml:mrow></mml:msup></mml:math>. We also provide improved upper bounds on the stabilizer rank of symmetric product states <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>ψ</mml:mi><mml:msup><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>⊗</mml:mo><mml:mi>m</mml:mi></mml:mrow></mml:msup></mml:math> more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>m</mml:mi></mml:math> instances of any (fixed) single-qubit <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Z</mml:mi></mml:math>-rotation gate with runtime <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>poly</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>m</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:math>. We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.</jats:p>