Universität zu Köln

Heinrich, Markus and Gross, David (2019). Robustness of Magic and Symmetries of the Stabiliser Polytope. Quantum, 3. WIEN: VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF. ISSN 2521-327X

Full text not available from this repository.

Abstract

We give a new algorithm for computing the robustness of magic-a measure of the utility of quantum states as a computational resource. Our work is motivated by the magic state model 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 magic states in this context. The robustness of magic 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 sign problem. Surprisingly, the robustness of magic is submultiplicative. 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 n copies of a magic state is difficult, as its definition involves a convex optimisation problem in a 4(n)-dimensional space. In this paper, we make use of inherent symmetries to reduce the problem to n dimensions. The total run-time of our algorithm, while still exponential in n, 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 signed quantum weight enumerators. As a by-product, we characterised the automorphism group of the stabiliser polytope, and, more generally, of projections onto complex projective 3-designs.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Heinrich, Markus UNSPECIFIED UNSPECIFIED UNSPECIFIED Gross, David UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-150903
Journal or Publication Title:	Quantum
Volume:	3
Date:	2019
Publisher:	VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF
Place of Publication:	WIEN
ISSN:	2521-327X
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Physics > Institute for Theoretical Physics
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language CLIFFORD GROUP Multiple languages Quantum Science & Technology; Physics, Multidisciplinary Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/15090