Physical consequences of P[not equal]NP and the DMRG-annealing conjecture

e-Archivo Repository

Show simple item record Rodríguez Laguna, Javier Santalla, Silvia N. 2020-05-29T16:47:12Z 2020-05-29T16:47:12Z 2014-07-02
dc.identifier.bibliographicCitation Journal of Statistical Mechanics: Theory and Experiment, (2014), 7(P07006), 16 pp.
dc.identifier.issn 1742-5468
dc.description.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.
dc.description.sponsorship This work was supported by the Spanish government by grants FIS2012-33642 and FIS2012-38866-C05-1 and ERC grant QUAGATUA.
dc.format.extent 16
dc.language.iso eng
dc.publisher IOP
dc.rights © 2014 IOP Publishing Ltd and SISSA Medialab srl.
dc.subject.other Frustrated systems
dc.subject.other Quantum phase transitions
dc.subject.other Analysis of algorithms
dc.subject.other Entanglement in extended quantum systems
dc.subject.other Ising spin-glass
dc.title Physical consequences of P[not equal]NP and the DMRG-annealing conjecture
dc.title.alternative Physical consequences of P[not equal]NP and the density matrix renormalization group annealing conjecture
dc.type article
dc.subject.eciencia Física
dc.subject.eciencia Matemáticas
dc.rights.accessRights openAccess
dc.relation.projectID Gobierno de España. FIS2012-33642
dc.relation.projectID Gobierno de España. FIS2012-38866-C05-1
dc.type.version submittedVersion
dc.identifier.publicationfirstpage 1
dc.identifier.publicationissue 7(P07006)
dc.identifier.publicationlastpage 16
dc.identifier.publicationtitle Journal of Statistical Mechanics: Theory and Experiment
dc.identifier.uxxi AR/0000015701
dc.contributor.funder Ministerio de Economía y Competitividad (España)
 Find Full text

Files in this item

*Click on file's image for preview. (Embargoed files's preview is not supported)

This item appears in the following Collection(s)

Show simple item record