Simulation of quantum circuits by low-rank stabilizer decompositions 论文

摘要

Recent work has explored using the stabilizer formalism to classically simulate quantum circuits containing a few non-Clifford gates. The computational cost of such methods is directly related to the notion of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-mathit" mathvariant="italic">s</mml:mi><mml:mi class="MJX-tex-mathit" mathvariant="italic">t</mml:mi><mml:mi class="MJX-tex-mathit" mathvariant="italic">a</mml:mi><mml:mi class="MJX-tex-mathit" mathvariant="italic">b</mml:mi><mml:mi class="MJX-tex-mathit" mathvariant="italic">i</mml:mi><mml:mi class="MJX-tex-mathit" mathvariant="italic">l</mml:mi><mml:mi class="MJX-tex-mathit" mathvariant="italic">i</mml:mi><mml:mi class="MJX-tex-mathit" mathvariant="italic">z</mml:mi><mml:mi class="MJX-tex-mathit" mathvariant="italic">e</mml:mi><mml:mi class="MJX-tex-mathit" mathvariant="italic">r</mml:mi></mml:mrow></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext class="MJX-tex-mathit" mathvariant="italic">rank</mml:mtext></mml:mrow></mml:math>, which for a pure state<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ψ</mml:mi></mml:math>is defined to be the smallest integer<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>χ</mml:mi></mml:math>such that<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ψ</mml:mi></mml:math>is a superposition of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>χ</mml:mi></mml:math>stabilizer states. Here we develop a comprehensive mathematical theory of the stabilizer rank and the related approximate stabilizer rank. We also present a suite of classical simulation algorithms with broader applicability and significantly improved performance over the previous state-of-the-art. A new feature is the capability to simulate circuits composed of Clifford gates and arbitrary diagonal gates, extending the reach of a previous algorithm specialized to the Clifford+T gate set. We implemented the new simulation methods and used them to simulate quantum algorithms with 40-50 qubits and over 60 non-Clifford gates, without resorting to high-performance computers. We report a simulation of the Quantum Approximate Optimization Algorithm in which we process superpositions of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>χ</mml:mi><mml:mo>∼</mml:mo><mml:msup><mml:mn>10</mml:mn><mml:mn>6</mml:mn></mml:msup></mml:math>stabilizer states and sample from the full<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math>-bit output distribution, improving on previous simulations which used<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>∼</mml:mo><mml:msup><mml:mn>10</mml:mn><mml:mn>3</mml:mn></mml:msup></mml:math>stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math>gates or 16 CCZ gates; these simulations showcase the performance gains available by optimizing the decomposition of a circuit's non-Clifford components.