Efficient classical simulation of slightly entangled quantum computations
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 7 Pith papers
-
An Exponential Sample-Complexity Advantage for Coherent Quantum Inference
Coherent quantum inference achieves O(1/ε) sample complexity for d-dimensional quantum purity amplification, exponentially better than the Ω(d/ε) required by any incoherent measurement-mediated protocol.
-
The one clean qubit model without entanglement is classically simulable
The one clean qubit model without entanglement is efficiently classically simulable.
-
Diagonal Isometric Form for Tensor Product States in Two Dimensions
A new diagonal isometric representation for 2D isoTPS enables efficient TEBD computation of area-law states and short-time dynamics in the transverse-field Ising model.
-
Bowtie VarQTE: A Resource-Efficient Quantum State Preparation Primitive
Bowtie VarQTE is a hybrid classical-quantum variational time evolution method that exploits causal light-cones to reduce quantum resource use for state preparation while achieving fidelities comparable to approximate ...
-
Universal Non-stabilizerness Dynamics Across Quantum Phase Transitions
Stabilizer Rényi entropies and Pauli spectrum cumulants show universal power-law scaling with driving rate in slow processes across quantum phase transitions, with the logarithmic Pauli spectrum asymptotically Gaussia...
-
On the Complexity of the Succinct State Local Hamiltonian Problem
The succinct state 2-local Hamiltonian problem for qubit Hamiltonians is promise-MA-complete.
-
Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
Systematic numerical study of QAOA parameter transfer on heavy-hex Ising models with local cubic terms shows transferred angles from small instances yield improving expectation values up to 49 layers on instances up t...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.