Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Quantum Information Processing
Erschienen in: Quantum Information Processing 7/2018

01.07.2018

Shorter unentangled proofs for ground state connectivity

verfasst von: Libor Caha, Daniel Nagaj, Martin Schwarz

Erschienen in: Quantum Information Processing | Ausgabe 7/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Can one considerably shorten a proof for a quantum problem by using a protocol with a constant number of unentangled provers? We consider a frustration-free variant of the \(\textsf {QCMA}\)-complete ground state connectivity (GSCON) problem for a system of size n with a proof of superlinear size. We show that we can shorten this proof in \(\textsf {QMA}(2)\): There exists a two-copy, unentangled proof with length of order n, up to logarithmic factors, while the completeness–soundness gap of the new protocol becomes a small inverse polynomial in n.
Vorheriger Artikel Enhancing the absorption and energy transfer process via quantum entanglement

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
In general, this could be also l-local unitaries; we choose \(l=2\). This variant of the problem is still QCMA complete [11].
 
2
This inverse polynomial is quite small, as shown in Sect. 4.4: \(c'-s' = \Omega \left( \Delta ^{13} m^{-32} G^{-10} \right) \), with \(\Delta \) from the definition of GSCON and G the gate set size.
 
3
Note that there are squares in the expression, while [3], Lemma 3.3, has a typo, missing the squares.
 
4
Our proof would also go through for a very small \(\eta _1\), or could be avoided with more copies of the proof. However, we have not found a good enough way of performing a single measurement of energy for non-frustration-free Hamiltonians, that would with high enough probability tell if an energy of a single copy of a state (a superposition of eigenstates with various energies) is below or above thresholds that could be very close together.
 
Literatur
1.
Aaronson, S., Beigi, S., Drucker, A., Fefferman, B., Shor, P.: The power of unentanglement. Theory Comput. 5(1), 1–42 (2009)MathSciNetCrossRefMATH
2.
3.
4.
5.
Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett. 87, 167902 (2001)ADSCrossRef
6.
Chen, J., Drucker, A.: Short multi-prover quantum proofs for SAT without entangled measurements. arXiv e-print: arXiv:​1011.​0716 (2010)
7.
Chiesa, A., Forbes, M.A.: Improved soundness for QMA with multiple provers. Chic. J. Theor. Comput. Sci. 2013, 1 (2013)ADSMathSciNetMATH
8.
9.
Gall, F.L., Nakagawa, S., Nishimura, H.: On QMA protocols with two short quantum proofs. Quantum Inf. Comput. 12(7–8), 589–600 (2012)MathSciNetMATH
10.
Gharibian, S.: Strong NP-hardness of the quantum separability problem. Quantum Inf. Comput. 10(3&4), 343–360 (2010)MathSciNetMATH
11.
Gharibian, S., Sikora, J.: Ground state connectivity of local Hamiltonians. In: Automata, Languages, and Programming: 42nd International Colloquium, ICALP: Kyoto, Japan, July 6–10, 2015, Proceedings, Part I, pp. 617–628. Springer, Berlin (2015)
12.
Gurvits, L.: Classical deterministic complexity of Edmonds’ problem and quantum entanglement. In: Proceedings of 35th Annual ACM Symposium on Theory of Computing, STOC ’03, pp. 10–19. ACM, New York (2003)
13.
Harrow, A.W., Montanaro, A.: An efficient test for product states with applications to quantum Merlin–Arthur games. In: Proceedings of 51st Annual Symposium on Foundations of Computer Science, pp. 633–642 (2010)
14.
Jordan, S.P., Kobayashi, H., Nagaj, D., Nishimura, H.: Achieving perfect completeness in classical-witness quantum Merlin–Arthur proof systems. Quantum Inf. Comput. 12(5–6), 461–471 (2012)MathSciNetMATH
15.
Kitaev, A., Shen, A., Vyalyi, M.: Classical and Quantum Computation. Graduate studies in mathematics. American Mathematical Society, Providence (2002)CrossRefMATH
16.
Liu, Y.: The complexity of the consistency and N-representability problems for quantum states. PhD thesis, University of California, San Diego (2007)
17.
18.
Watrous, J.: Quantum computational complexity. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and Systems Science, pp. 7174–7201. Springer, New York (2009)CrossRef
Metadaten
Titel
Shorter unentangled proofs for ground state connectivity
verfasst von
Libor Caha
Daniel Nagaj
Martin Schwarz
Publikationsdatum
01.07.2018
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 7/2018
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-018-1944-4

Weitere Artikel der Ausgabe 7/2018

Quantum Information Processing 7/2018 Zur Ausgabe

OriginalPaper

Quantum-enhanced feature selection with forward selection and backward elimination

OriginalPaper

Controlling the loss of quantum correlations via quantum memory channels

OriginalPaper

Efficient schemes for the quantum teleportation of a sub-class of tripartite entangled states

OriginalPaper

Geometric structure of quantum resources for Bell-diagonal states

OriginalPaper

Element distinctness revisited

OriginalPaper

The dynamics of local quantum uncertainty and trace distance discord for two-qubit X states under decoherence: a comparative study

Neuer Inhalt

    Bildnachweise