×

Shorter unentangled proofs for ground state connectivity. (English) Zbl 1448.81034

Summary: 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 \(\text{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 \(\text{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\).

MSC:

81P15 Quantum measurement theory, state operations, state preparations
81P68 Quantum computation
68Q12 Quantum algorithms and complexity in the theory of computing
81P42 Entanglement measures, concurrencies, separability criteria
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aaronson, S; Beigi, S; Drucker, A; Fefferman, B; Shor, P, The power of unentanglement, Theory Comput., 5, 1-42, (2009) · Zbl 1213.68280 · doi:10.4086/toc.2009.v005a001
[2] Beigi, S, NP vs QMA\(_{{\rm log}}(2)\), Quantum Inf. Comput., 10, 2, (2010) · Zbl 1187.81058
[3] Blier, H; Tapp, A, A quantum characterization of NP, Comput. Complex., 21, 499-510, (2012) · Zbl 1288.68079 · doi:10.1007/s00037-011-0016-2
[4] Brandão, FGSL; Christandl, M; Yard, J, Faithful squashed entanglement, Commun. Math. Phys., 306, 805-830, (2011) · Zbl 1231.81011 · doi:10.1007/s00220-011-1302-1
[5] Buhrman, H; Cleve, R; Watrous, J; Wolf, R, Quantum fingerprinting, Phys. Rev. Lett., 87, 167902, (2001) · doi:10.1103/PhysRevLett.87.167902
[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, MA, Improved soundness for QMA with multiple provers, Chic. J. Theor. Comput. Sci., 2013, 1, (2013) · Zbl 1286.68150
[8] Dinur, I, The PCP theorem by gap amplification, J. ACM, 54, 3, (2007) · Zbl 1292.68074 · doi:10.1145/1236457.1236459
[9] Gall, FL; Nakagawa, S; Nishimura, H, On QMA protocols with two short quantum proofs, Quantum Inf. Comput., 12, 589-600, (2012) · Zbl 1260.81048
[10] Gharibian, S, Strong NP-hardness of the quantum separability problem, Quantum Inf. Comput., 10, 343-360, (2010) · Zbl 1234.81033
[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) · Zbl 1440.68097
[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) · Zbl 1192.68252
[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, SP; Kobayashi, H; Nagaj, D; Nishimura, H, Achieving perfect completeness in classical-witness quantum merlin-Arthur proof systems, Quantum Inf. Comput., 12, 461-471, (2012) · Zbl 1260.81019
[15] Kitaev, A., Shen, A., Vyalyi, M.: Classical and Quantum Computation. Graduate studies in mathematics. American Mathematical Society, Providence (2002) · Zbl 1022.68001 · doi:10.1090/gsm/047
[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; Meyers, RA (ed.), Quantum computational complexity, 7174-7201, (2009), New York · doi:10.1007/978-0-387-30440-3_428
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.