2018/07/31 by Markus Heinrich, David Gross · 2 citations
Computer Science · Physics and Astronomy · #Exponential function #MAGIC (telescope) #Monte Carlo method #Polytope #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Robustness (evolution) #Rounding #quant-ph
paper · pdf · doi:10.22331/q-2019-04-08-132
published as Quantum 3, 132 (2019) · Minor changes, final version accepted for publication in Quantum; 35 pages, many figures
openalex created_date 2018/08/03 · arxiv created 2019/04/04 · openalex publication_date 2019/04/08 · arxiv updated 2019/04/09 · openalex updated_date 2026/08/06
We give a new algorithm for computing the<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">robustness of magic</mml:mtext></mml:mrow></mml:math>- a measure of the utility of quantum states as a computational resource. Our work is motivated by the<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">magic state model</mml:mtext></mml:mrow></mml:math>of fault-tolerant quantum computation. In this model, all unitaries belong to the Clifford group. Non-Clifford operations are effected by injecting non-stabiliser states, which are referred to as<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">magic states</mml:mtext></mml:mrow></mml:math>in this context. The<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">robustness of magic</mml:mtext></mml:mrow></mml:math>measures the complexity of simulating such a circuit using a classical Monte Carlo algorithm. It is closely related to the degree negativity that slows down Monte Carlo simulations through the infamous<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">sign problem</mml:mtext></mml:mrow></mml:math>. Surprisingly, the robustness of magic is<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">sub</mml:mtext></mml:mrow></mml:math>- multiplicative. This implies that the classical simulation overhead scales subexponentially with the number of injected magic states - better than a naive analysis would suggest. However, determining the robustness of<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">n</mml:mtext></mml:mrow></mml:math>copies of a magic state is difficult, as its definition involves a convex optimisation problem in a 4<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:msup><mml:mi/><mml:mi>n</mml:mi></mml:msup></mml:mrow></mml:math>-dimensional space. In this paper, we make use of inherent symmetries to reduce the problem to<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">n</mml:mtext></mml:mrow></mml:math>dimensions. The total run-time of our algorithm, while still exponential in<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">n</mml:mtext></mml:mrow></mml:math>, is super-polynomially faster than previously published methods. We provide a computer implementation and give the robustness of up to 10 copies of the most commonly used magic states. Guided by the exact results, we find a finite hierarchy of approximate solutions where each level can be evaluated in polynomial time and yields rigorous upper bounds to the robustness. Technically, we use symmetries of the stabiliser polytope to connect the robustness of magic to the geometry of a low-dimensional convex polytope generated by certain<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">signed quantum weight enumerators</mml:mtext></mml:mrow></mml:math>. As a by-product, we characterised the automorphism group of the stabiliser polytope, and, more generally, of projections onto complex projective 3-designs.