From estimation of quantum probabilities to simulation of quantum circuits

Understand

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, 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.