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 12 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.
-
Mapping twist fields to local operators via tensor networks
Constructs explicit physical local operators whose expectation values match twist field actions in MPS, exact in the injectivity limit and at the center of orthogonality, with numerical tests in the transverse-field I...
-
Diagonal Isometric Form for Tensor Network 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.
-
Wigner negativity in Krylov space and emergent semiclassicality
Wigner negativity in Krylov space stays O(1) or grows as t^{1/2} (without Hilbert-space scaling) in 2d CFTs, one-cut matrix models, and double-scaled SYK, indicating emergent semiclassicality.
-
Simulating quantum circuits with a neural statebank
A compact neural statebank based on autoregressive Transformers simulates 34-qubit quantum circuits with ~0.01 infidelity using 0.3 million parameters, outperforming tested approximate simulators.
-
Photonic Analog Quantum Simulation of (1+1)-Dimensional $U(1)$ Lattice Gauge Theory with Dynamical Matter
A mapping of the Jaynes-Cummings-Hubbard model onto the spin-1/2 Quantum Link Model via tuned polaritonic resonances in cavity arrays enables analog simulation of U(1) LGT dynamics with matter, verified by exact diago...
-
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...
-
Ground state preparation of random all-to-all Hamiltonians using ADAPT-VQE
TETRIS-ADAPT-VQE achieves fidelities above 99.3% for SYK (N=20) and 99.9998% for SK (L=18) but requires large resources for SYK models.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.