Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.01.2015 | Ausgabe 1/2015

Quantum Information Processing 1/2015

The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{{NP}}\)

Zeitschrift:
Quantum Information Processing > Ausgabe 1/2015
Autoren:
Dorit Aharonov, Lior Eldar

Abstract

The local Hamiltonian problem is famously complete for the class \(\mathsf{{QMA}}\), the quantum analogue of \(\mathsf{{NP}}\). The complexity of its semiclassical version, in which the terms of the Hamiltonian are required to commute (the \(\mathsf{{CLH}}\) problem), has attracted considerable attention recently due to its intriguing nature, as well as in relation to growing interest in the \(\mathsf{{qPCP}}\) conjecture. We show here that if the underlying bipartite interaction graph of the \(\mathsf{{CLH}}\) instance is a good locally expanding graph, namely the expansion of any constant-size set is \(\varepsilon \)-close to optimal, then approximating its ground energy to within additive factor \(O(\varepsilon )\) lies in \(\mathsf{{NP}}\). The proof holds for \(k\)-local Hamiltonians for any constant \(k\) and any constant dimensionality of particles \(d\). We also show that the approximation problem of \(\mathsf{{CLH}}\) on such good local expanders is \(\mathsf{{NP}}\)-hard. This implies that too good local expansion of the interaction graph constitutes an obstacle against quantum hardness of the approximation problem, though it retains its classical hardness. The result highlights new difficulties in trying to mimic classical proofs (in particular, Dinur’s \(\mathsf{{PCP}}\) proof) in an attempt to prove the quantum \(\mathsf{{PCP}}\) conjecture. A related result was discovered recently independently by Brandão and Harrow, for \(2\)-local general Hamiltonians, bounding the quantum hardness of the approximation problem on good expanders, though no \(\mathsf{{NP}}\) hardness is known in that case.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2015

Quantum Information Processing 1/2015 Zur Ausgabe