Publication: Physical consequences of P[not equal]NP and the DMRG-annealing conjecture
Loading...
Identifiers
Publication date
2014-07-02
Defense date
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
IOP
Impact
Export
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 need not be a Turing machine and, thus, these theorems do not apply directly to it. But 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 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 P and NP differ. As a by-product, an alternative measure of entanglement is proposed which, via Chebyshev's inequality, allows us to establish strict bounds on the required computational time.
Description
Keywords
Frustrated systems, Quantum phase transitions, Analysis of algorithms, Entanglement in extended quantum systems, Ising spin-glass
Bibliographic citation
Journal of Statistical Mechanics: Theory and Experiment, (2014), 7(P07006), 16 pp.