Top

Quantum Information Processing

Published in:

01-07-2018

Shorter unentangled proofs for ground state connectivity

Authors: Libor Caha, Daniel Nagaj, Martin Schwarz

Published in: Quantum Information Processing | Issue 7/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Enhancing the absorption and energy transfer process via quantum entanglement

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

In general, this could be also l-local unitaries; we choose \(l=2\). This variant of the problem is still QCMA complete [11].

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.

Note that there are squares in the expression, while [3], Lemma 3.3, has a typo, missing the squares.

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.

Aaronson, S., Beigi, S., Drucker, A., Fefferman, B., Shor, P.: The power of unentanglement. Theory Comput. 5(1), 1–42 (2009)MathSciNetCrossRefMATH

Beigi, S.: NP vs QMA \(_{{\rm log}}(2)\). Quantum Inf. Comput. 10(1&2), 2 (2010)MathSciNetMATH

Blier, H., Tapp, A.: A quantum characterization of NP. Comput. Complex. 21(3), 499–510 (2012)MathSciNetCrossRefMATH

Brandão, F.G.S.L., Christandl, M., Yard, J.: Faithful squashed entanglement. Commun. Math. Phys. 306, 805–830 (2011)ADSMathSciNetCrossRefMATH

Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett. 87, 167902 (2001)ADSCrossRef

Chen, J., Drucker, A.: Short multi-prover quantum proofs for SAT without entangled measurements. arXiv e-print: arXiv:1011.0716 (2010)

Chiesa, A., Forbes, M.A.: Improved soundness for QMA with multiple provers. Chic. J. Theor. Comput. Sci. 2013, 1 (2013)ADSMathSciNetMATH

Dinur, I.: The PCP theorem by gap amplification. J. ACM 54, 3 (2007)MathSciNetCrossRefMATH

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.

Nakagawa, S., Nishimura, H.: On the soundness of the Blier–Tapp QMA protocol. In: 23rd quantum information technology symposium (QIT23), pp. 132–135. http://www.math.cm.is.nagoya-u.ac.jp/~hnishimura/NN10.pdf (2010). Accessed 1 Oct 2017 (in Japanese)

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

Title: Shorter unentangled proofs for ground state connectivity
Authors: Libor Caha
Daniel Nagaj
Martin Schwarz
Publication date: 01-07-2018
Publisher: Springer US
Published in: Quantum Information Processing / Issue 7/2018
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-018-1944-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 7/2018

Spin coherent states phenomena probed by quantum state tomography in Zeeman perturbed nuclear quadrupole resonance

Complete optimal convex approximations of qubit states under distance

How does Grover walk recognize the shape of crystal lattice?

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

Self-assisted complete analysis of three-photon hyperentangled Greenberger–Horne–Zeilinger states with nitrogen-vacancy centers in microcavities

Quantum conference