Efficient classical simulation of slightly entangled quantum computations |
| |
Authors: | Vidal Guifré |
| |
Institution: | Institute for Quantum Information, California Institute of Technology, Pasadena, California 91125, USA. |
| |
Abstract: | We present a classical protocol to efficiently simulate any pure-state quantum computation that involves only a restricted amount of entanglement. More generally, we show how to classically simulate pure-state quantum computations on n qubits by using computational resources that grow linearly in n and exponentially in the amount of entanglement in the quantum computer. Our results imply that a necessary condition for an exponential computational speedup (with respect to classical computations) is that the amount of entanglement increases with the size n of the computation, and provide an explicit lower bound on the required growth. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|