Physical consequences of PNP and the DMRG-annealing conjecture
arXiv:1010.0128 · doi:10.1088/1742-5468/2014/07/P07006
Abstract
Computational complexity theory contains a corpus of theorems and conjectures regarding the time a Turing machine will need to solve certain types of problems as a function of the input size. Nature {\em need not} be a Turing machine and, thus, these theorems do not apply directly to it. But {\em classical simulations} of physical processes are programs running on Turing machines and, as such, are subject to them. In this work, computational complexity theory is applied to classical simulations of systems performing an adiabatic quantum computation (AQC), based on an annealed extension of the density matrix renormalization group (DMRG). We conjecture that the computational time required for those classical simulations is controlled solely by the {\em maximal entanglement} found during the process. Thus, lower bounds on the growth of entanglement with the system size can be provided. In some cases, quantum phase transitions can be predicted to take place in certain inhomogeneous systems. Concretely, physical conclusions are drawn from the assumption that the complexity classes {\bf P} and {\bf NP} differ. As a by-product, an alternative measure of entanglement is proposed which, via Chebyshev's inequality, allows to establish strict bounds on the required computational time.
arXiv commentAccepted for publication in JSTAT
References in corpus (35)
- The density-matrix renormalization group in the age of matrix product states
- Area laws for the entanglement entropy - a review
- Entanglement in quantum critical phenomena
- Efficient classical simulation of slightly entangled quantum computations
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Entropy and Area
- Efficient simulation of one-dimensional quantum many-body systems
- A class of quantum many-body states that can be efficiently simulated
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Quantum Search by Local Adiabatic Evolution
- The computational complexity of PEPS
- Anderson localization casts clouds over adiabatic quantum optimization
- Spin Gaps in a Frustrated Heisenberg model for CaVO
- Hamiltonian complexity
- Two-Dimensional Tensor Product Variational Formulation
- Quantum phase transitions and quantum fidelity in free fermion graphs
- Entanglement spectra of quantum Heisenberg ladders
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- Simulating adiabatic evolution of gapped spin systems
- Entanglement entropy at infinite randomness fixed points in higher dimensions
- Universality of Entanglement and Quantum Computation Complexity
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- The computational difficulty of finding MPS ground states
- Entanglement entropy and multifractality at localization transitions
- Simulation of many-qubit quantum computation with matrix product states
- Computational Difficulty of Global Variations in the Density Matrix Renormalization Group
- Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
- Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm
- Quantum Adiabatic Computation With a Constant Gap is Not Useful in One Dimension
- An Efficient Algorithm for approximating 1D Ground States
- Frustration, Area Law, and Interference in Quantum Spin Models
- Density matrix renormalization on random graphs and the quantum spin-glass transition
- Inference from Matrix Products: A Heuristic Spin Glass Algorithm
- Quantum wavefunction annealing of spin glasses