Efficient Classical Simulation of Slightly Entangled Quantum Computations

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.