Physical consequences of P NP and the density matrix renormalization group annealing conjecture

DOI10.1088/1742-5468/2014/07/P07006MaRDI QIDQ3301992zbMATH OpenWikidataFDO

Authors Silvia N. Santalla, J. Rodriguez-Laguna

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.0128

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Phase transitions (general) in equilibrium statistical mechanics (82B26)

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 {�f P} and {�f 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.

Recommendations

• Publication:4939149
• P/NP , and the quantum field computer
• Computing quantum discord is NP-complete
• Physical portrayal of computational complexity
• Computational Complexity of Projected Entangled Pair States

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• An area law for one-dimensional quantum systems
• Anderson localization makes adiabatic quantum optimization fail
• Colloquium: Quantum annealing and analog quantum computation
• Colloquium: area laws for the entanglement entropy
• Computational Complexity of Projected Entangled Pair States
• Density matrix renormalization on random graphs and the quantum spin-glass transition
• Entropy and area
• Matrix product state representations
• Quantum annealing and related optimization methods
• The complexity of theorem-proving procedures
• The density-matrix renormalization group in the age of matrix product states
• Two-dimensional tensor product variational formulation

Cited in

(2)

• Physical portrayal of computational complexity
• scientific article; zbMATH DE number 1406123 (Why is no real title available?)

This page was built for publication: Physical consequences of \(P \neq\) NP and the density matrix renormalization group annealing conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301992)