Universität zu Köln

Pashayan, Hakop, Bartlett, Stephen D. and Gross, David (2020). From estimation of quantum probabilities to simulation of quantum circuits. Quantum, 4. WIEN: VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF. ISSN 2521-327X

Full text not available from this repository.

Abstract

Investigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depends quite critically on the precise notion of classical simulation and in particular on the required accuracy. We argue that a notion of classical simulation, which we call epsilon-simulation (or epsilon-simulation for short), captures the essence of possessing equivalent computational power as the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an epsilon-simulator from one possessing the simulated quantum system. We relate epsilon-simulation to various alternative notions of simulation predominantly focusing on a simulator we call a poly-box. A poly-box outputs 1/poly precision additive estimates of Born probabilities and marginals. This notion of simulation has gained prominence through a number of recent simulability results. Accepting some plausible computational theoretic assumptions, we show that epsilon-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to epsilon-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution (poly-sparsity).

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Pashayan, Hakop UNSPECIFIED UNSPECIFIED UNSPECIFIED Bartlett, Stephen D. UNSPECIFIED UNSPECIFIED UNSPECIFIED Gross, David UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-348933
Journal or Publication Title:	Quantum
Volume:	4
Date:	2020
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 CLASSICAL SIMULATION; COMPLEXITY; COMPUTATION Multiple languages Quantum Science & Technology; Physics, Multidisciplinary Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/34893