Efficient classical simulation of slightly entangled quantum computations.

By Guifré Vidal. 2003

2,031 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “Suitable conditions that imply a unique MPS representation can be found in [222, 265].”
Unitary circuits of finite depth and infinite width from quantum channels (2019, background): “A key distinction between the quantum channel approach and standard methods (such as time-evolving block decimation [42]) for evolving a matrix-product state is that the quantum channel approach constructs the entanglement spectrum without explicitly representing the physical wavefunction at time t.”
O(dlog N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling (2011, methodology): “Moreover, DMRG calculations in [46, 45] show that QTC/QTT-type “matrix product states” tensor formats are indispensable in moder quantum computations.”
Quantized-TT-Cayley Transform for Computing the Dynamics and the Spectrum of High-Dimensional Hamiltonians (2011, methodology): “Matrix product states tensor model by the QTT format To get rid of the ”curse of dimensionality“, we apply modern tensor formats based on the dimension splitting via factorized representation, matrix product states (MPS) (see [44, 42, 37]).”
Quantum Entanglement in Neural Network States (2017, background): “In addition, they are also the backbones of a number of efficient classical algorithms for solving intricate manybody problems, e.g., DMRG (density-matrix renormalization group) [9, 17, 18], TEBD (time-evolving block decimation) [19], PEPS [10, 12] (projected entangled pair states), and MERA (multis”
Two-level Tucker-TT-QTT format for optimized tensor calculus (2012, methodology): “…different formats were proposed and analyzed , such as canonical [8] [9] [10] [11], Tucker [12] [13] [14] [15], Matrix Product States [16] [17] [18] [19] and MCTDH [20] in quantum physics community, HT (Hierarchical Tucker) [21] [22] and TT (Tensor Train) in numerical algebra community [23]…”
Tensors-structured Numerical Methods in Scientific Computing: Survey on Recent Advances (2012, methodology): “In the quantum information theory the concept of MPS was also introduced as the state decomposition of slightly entangled systems [98].”
Entanglement in a fermion chain under continuous monitoring (2018, background): “Understanding entanglement is also crucial for designing effective quantum simulators and determining the limits thereof [10–12].”
Negative quasi-probability as a resource for quantum computation (2012, background): “Similarly, it is known that for pure states large amounts of entanglement are required for quantum computational speed-up (Vidal 2003), but for mixed states this is still an open question.”
Improved Simulation of Stabilizer Circuits (2004, background): “Notably, in a follow-up paper [7], Vidal actually implemented his algorithm and used it to simulate 1-dimensional quantum spin chains consisting of hundreds of spins.”
F ¨ Ur Mathematik in Den Naturwissenschaften Leipzig on Minimal Subspaces in Tensor Representations on Minimal Subspaces in Tensor Representations (positive): “…solution of problems defined in high-dimensional tensor spaces, such as PDEs arising in stochastic calculus [1] [4] [9] (e.g., Fokker-Planck equation), stochastic parametric PDEs arising in uncertainty quantification with spectral approaches [18] [8] [19], and quantum chemistry (cf., e.g., [25]).”