Stabilizer extent is not multiplicative - Kölner UniversitätsPublikationsServer

Heimendahl, Arne ORCID: 0000-0002-8366-953X, Montealegre-Mora, Felipe, Vallentin, Frank ORCID: 0000-0002-3205-4607 and Gross, David (2021). Stabilizer extent is not multiplicative. Quantum, 5. WIEN: VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF. ISSN 2521-327X

Full text not available from this repository.

DOI:10.22331/q-2021-02-24-400

Abstract

The Gottesman-Knill theorem states that a Clifford circuit acting on stabilizer states can be simulated efficiently on a classical computer. Recently, this result has been generalized to cover inputs that are close to a coherent superposition of polynomially many stabilizer states. The runtime of the classical simulation is governed by the stabilizer extent, which roughly measures how many stabilizer states are needed to approximate the state. An important open problem is to decide whether the extent is multiplicative under tensor products. An affirmative answer would yield an efficient algorithm for computing the extent of product inputs, while a negative result implies the existence of more efficient classical algorithms for simulating large-scale quantum circuits. Here, we answer this question in the negative. Our result follows from very general properties of the set of stabilizer states, such as having a size that scales subexponentially in the dimension, and can thus be readily adapted to similar constructions for other resource theories.

Item Type:

Journal Article

Creators:

Creators	Email	ORCID	ORCID Put Code
Heimendahl, Arne	UNSPECIFIED	orcid.org/0000-0002-8366-953X	UNSPECIFIED
Montealegre-Mora, Felipe	UNSPECIFIED	UNSPECIFIED	UNSPECIFIED
Vallentin, Frank	UNSPECIFIED	orcid.org/0000-0002-3205-4607	UNSPECIFIED
Gross, David	UNSPECIFIED	UNSPECIFIED	UNSPECIFIED