Source-linked AI summary
Efficient classical simulation of slightly entangled quantum computations
Guifre Vidal
TL;DR
The paper asks when quantum dynamics that appear classically difficult can nevertheless be simulated efficiently, focusing on restricted entanglement or correlations. It develops a classical simulation scheme whose resources scale linearly with system size and exponentially with entanglement, showing that exponential pure-state speed-ups require entanglement to grow with n.
Problem
Classically simulating general n-qubit dynamics requires an exponential description, motivating the question of which physical resource enables quantum computational speed-ups.
Source: p. 1Method
The paper represents multipartite states using Schmidt decompositions and simulates circuit evolutions while tracking restricted entanglement.
Source: p. 1Results
Polynomially bounded entanglement permits polynomial classical simulation, while subexponential entanglement permits subexponential simulation, so exponential speed-ups require entanglement growth with n.
Source: p. 3Takeaways & Limitations
For pure states, entanglement is necessary for exponential quantum computational speed-ups, and analogous correlation bounds apply to mixed states.
Source: p. 1The analysis focuses on circuit-model evolutions initialized in |0⟩^⊗n and assumes entanglement remains restricted throughout the computation.
Source: pp. 1–2
Abstract
from arXiv · showhide
We present a scheme to efficiently simulate, with a classical computer, the dynamics of multipartite quantum systems on which the amount of entanglement (or of correlations in the case of mixed-state dynamics) is conveniently restricted. The evolution of a pure state of n qubits can be simulated by using computational resources that grow linearly in n and exponentially in the entanglement. We show that a pure-state quantum computation can only yield an exponential speed-up with respect to classical computations if the entanglement increases with the size n of the computation, and gives a lower bound on the required growth.