DC FieldValueLanguage
dc.contributor.authorBittel, Lennart-
dc.contributor.authorKliesch, Martin-
dc.date.accessioned2022-09-15T17:23:18Z-
dc.date.available2022-09-15T17:23:18Z-
dc.date.issued2021-09-17-
dc.identifier.citationPhysical Review Letters 127 (12) : 120502 (2021-09-17)de_DE
dc.identifier.issn0031-9007de_DE
dc.identifier.urihttp://hdl.handle.net/11420/13620-
dc.description.abstractVariational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.en
dc.language.isoende_DE
dc.relation.ispartofPhysical review lettersde_DE
dc.titleTraining variational quantum algorithms Is NP-hardde_DE
dc.typeArticlede_DE
dc.type.diniarticle-
dcterms.DCMITypeText-
tuhh.abstract.englishVariational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.de_DE
tuhh.publisher.doi10.1103/PhysRevLett.127.120502-
tuhh.type.opus(wissenschaftlicher) Artikel-
dc.type.driverarticle-
dc.type.casraiJournal Article-
tuhh.container.issue12de_DE
tuhh.container.volume127de_DE
dc.identifier.pmid34597099-
dc.identifier.scopus2-s2.0-85115298198-
tuhh.container.articlenumber120502de_DE
datacite.resourceTypeArticle-
datacite.resourceTypeGeneralJournalArticle-
item.grantfulltextnone-
item.cerifentitytypePublications-
item.openairetypeArticle-
item.creatorOrcidBittel, Lennart-
item.creatorOrcidKliesch, Martin-
item.languageiso639-1en-
item.creatorGNDBittel, Lennart-
item.creatorGNDKliesch, Martin-
item.fulltextNo Fulltext-
item.openairecristypehttp://purl.org/coar/resource_type/c_6501-
item.mappedtypeArticle-
crisitem.author.deptQuantum-Inspired and Quantum Optimization E-25-
crisitem.author.orcid0000-0002-8009-0549-
crisitem.author.parentorgStudiendekanat Elektrotechnik, Informatik und Mathematik (E)-
Appears in Collections:Publications without fulltext
Show simple item record

Page view(s)

43
checked on Dec 7, 2022

PubMed Central
Citations

1
checked on Dec 6, 2022

Google ScholarTM

Check

Add Files to Item

Note about this record

Cite this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.