Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Total functions in QMA

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

The complexity class \({\textsc {QMA}}\) is the quantum analog of the classical complexity class \({\textsc {NP}}\). The functional analogs of \({\textsc {NP}}\) and \({\textsc {QMA}}\), called functional \({\textsc {NP}}\) (\({\textsc {FNP}}\)) and functional \({\textsc {QMA}}\) (\({\textsc {FQMA}}\)), consist in either outputting a (classical or quantum) witness or outputting NO if there does not exist a witness. The classical complexity class total functional \({\textsc {NP}}\) (\({\textsc {TFNP}}\)) is the subset of \({\textsc {FNP}}\) for which it can be shown that the NO outcome never occurs. \({\textsc {TFNP}}\) includes many natural and important problems. Here we introduce the complexity class total functional \({\textsc {QMA}}\) (\({\textsc {TFQMA}}\)), the quantum analog of \({\textsc {TFNP}}\). We show that \({\textsc {FQMA}}\) and \({\textsc {TFQMA}}\) can be defined in such a way that they do not depend on the values of the completeness and soundness probabilities. We provide examples of problems that lie in \({\textsc {TFQMA}}\), coming from areas such as the complexity of k-local Hamiltonians and public key quantum money. In the context of black-box groups, we note that group non-membership, which was known to belong to \({\textsc {QMA}}\), in fact belongs to \({\textsc {TFQMA}}\). We also provide a simple oracle with respect to which we have a separation between \({\textsc {FBQP}}\) and \({\textsc {TFQMA}}\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Aaronson, S.: Quantum copy-protection and quantum money. In: 24th Annual IEEE Conference on Computational Complexity, 2009. CCC’09, pp. 229–242. IEEE (2009)

  2. Aaronson, S.: On perfect completeness for QMA. Quant. Inf. Comput. 9, 81–89 (2009)

    MathSciNet  MATH  Google Scholar 

  3. Aharonov, D., Ben-Or, M., Brandao, F.G.S.L., Sattath, O.: The pursuit for uniqueness: extending Valiant–Vazirani theorem to the probabilistic and quantum settings. arXiv:0810.4840 (2008)

  4. Aaronson, S., Kuperberg, G.: Quantum versus classical proofs and advice. In: IEEE Conference on Computational Complexity Twenty-Second Annual, 2007. CCC’07, pp. 115–128. IEEE (2007)

  5. Aharonov, D., Eldar, L.: On the complexity of commuting local Hamiltonians, and tight conditions for topological order in such systems. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 334–343. IEEE (2011)

  6. Aharonov, D., Eldar, L.: The commuting local Hamiltonian problem on locally expanding graphs is approximable in NP. Quant. Inf. Process. 14, 83–101 (2015)

    Article  ADS  MathSciNet  Google Scholar 

  7. Alexander, J.W.: Topological invariants of knots and links. Trans. Am. Math. Soc. 30(2), 275–306 (1928)

    Article  MathSciNet  Google Scholar 

  8. Ambainis, A., Kempe, J., Sattath, O.: A quantum Lovász local lemma. J. ACM (JACM) 59, 24 (2012)

    Article  Google Scholar 

  9. Atia, Y., Aharonov, D.: Fast-forwarding of Hamiltonians and exponentially precise measurements. Nat. Commun. 8, 1572 (2017)

    Article  ADS  Google Scholar 

  10. Babai, L., Szemerédi, E.: On the complexity of matrix group problems I. In: Proceedings on IEEE FOCS, pp. 229–240 (1984)

  11. Bennett, C., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997)

    Article  MathSciNet  Google Scholar 

  12. Bookatz, A.D.: QMA-complete problems. Quantum Inf. Comput. 14, 361–383 (2014)

    MathSciNet  Google Scholar 

  13. Bravyi, S.: Efficient algorithm for a quantum analogue of 2-SAT. Contemp. Math. 536, 33–48 (2011)

    Article  MathSciNet  Google Scholar 

  14. Bravyi, S., Vyalyi, M.: Commutative version of the local Hamiltonian problem and common eigenspace problem. Quantum Inf. Comput. 5(3), 187–215 (2005)

    MathSciNet  MATH  Google Scholar 

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

    Article  ADS  Google Scholar 

  16. Cubitt, T.S., Schwarz, M.: A constructive commutative quantum Lovász Local Lemma, and beyond. arXiv: 1112.1413 (2011)

  17. Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. J. ACM (JACM) 56(3), 14 (2009)

    Article  MathSciNet  Google Scholar 

  18. Berry, D.W., Childs, A.M., Cleve, R., Kothari, R., Somma, R.D.: Exponential improvement in precision for simulating sparse Hamiltonians. In: Forum of Mathematics, Sigma, vol. 5. Cambridge University Press (2017)

  19. Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. Proc. R. Soc. Lond. A: Math. Phys. Eng. Sci. 454(1969), 339–354 (1998)

    Article  ADS  MathSciNet  Google Scholar 

  20. Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195–259 (2009)

    Article  MathSciNet  Google Scholar 

  21. Farhi, E., Gosset, D., Hassidim, A., Lutomirski, A., Shor, P.: Quantum money from knots. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 276–289. ACM (2012)

  22. Gilyén, A., Sattath, O.: On preparing ground states of gapped Hamiltonians: an efficient quantum Lovász Local Lemma. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 439–450. IEEE, 2017. arXiv preprint arXiv:1611.08571 (2016)

  23. Goldberg, P.W., Papadimitriou, C.: Towards a unified complexity theory of total functions. J. Comput. Syst. Sci. 94, 167–192 (2018)

    Article  MathSciNet  Google Scholar 

  24. Gosset, D., Nagaj, D.: Quantum 3-SAT is QMA \(_1\)-complete. SIAM J. Comput. 45(3), 1080–1128 (2016)

    Article  MathSciNet  Google Scholar 

  25. Grover, L.K.: A fast quantum mechanical algorithm for database search? In: Proceedings of 28th Annual ACM Symposium on Theory of Computing, May, pp. 212–219 (1996)

  26. Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325–328 (1997)

    Article  ADS  Google Scholar 

  27. He, K., Li, Q., Sun, X., Zhang, J.: Quantum Lovász local lemma: Shearer’s bound is tight. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 461–472 (2019)

  28. Janzing, D., Wocjan, P., Beth, T.: Cooling and low energy state preparation for 3-local Hamiltonians are FQMA-complete. arXiv:quant-ph/0303186 (2003)

  29. Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79–100 (1988)

    Article  MathSciNet  Google Scholar 

  30. Jordan, C.: Essai sur la géométrie à \(n\) dimensions. Bulletin de la Société mathématique de France 3, 103–174 (1875)

    Article  MathSciNet  Google Scholar 

  31. Kempe, J., Regev, O.: 3-Local Hamiltonian is QMA-complete. Quantum Inf. Comput. 3(3), 258–264 (2003)

    MathSciNet  MATH  Google Scholar 

  32. Kitaev, A.Y.: Quantum measurements and the Abelian stabilizer problem. arXiv preprint, arXiv:quant-ph/9511026 (1995)

  33. Kempe, J., Kitaev, A., Regev, O.: The complexity of the local Hamiltonian problem. SIAM J. Comput. 35(5), 1070–1097 (2006)

    Article  MathSciNet  Google Scholar 

  34. Kitaev, A.Y., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation. Graduate Studies in Mathematics, vol. 47. AMS, Providence, RI (2002)

    MATH  Google Scholar 

  35. Krentel, M.W.: Structure in locally optimal solutions. In: 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 216–221 (October). IEEE (1989)

  36. Marriott, C., Watrous, J.: Quantum Arthur–Merlin games. Comput. Complex. 14(2), 122152 (2005)

    Article  MathSciNet  Google Scholar 

  37. Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 317–324 (1991)

    Article  MathSciNet  Google Scholar 

  38. Moser, R.A.: A constructive proof of the Lovász Local Lemma. In: STOC, pp. 343–350. arXiv:0810.4812 (2009)

  39. Moser, R.A., Tardos, G.: A constructive proof of the general Lovász local lemma. J. ACM 57(2), 11 (2010)

    Article  Google Scholar 

  40. Nagaj, D., Wocjan, P., Zhang, Y.: Fast amplification of QMA. Quantum Inf. Comput. 9(11), 1053–1068 (2009)

    MathSciNet  MATH  Google Scholar 

  41. Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498–532 (1994)

    Article  MathSciNet  Google Scholar 

  42. Papadimitriou, C.H., Schaeffer, A.A., Yannakakis, M.: On the complexity of local search. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 438–445. ACM (1990, April)

  43. Regev, O.: Witness-Preserving QMA Amplification, Quantum Computation Lecture Notes, Spring 2006. Tel Aviv University, Tel Aviv-Yafo (2006)

    Google Scholar 

  44. Sattath, O., Arad, I.: A Constructive quantum Lovász Local Lemma for commuting projectors. Quantum Inf. Comput. 15(12), 987–996 (2015)

    MathSciNet  Google Scholar 

  45. Sattath, O., Morampudi, S.C., Laumann, C.R., Moessner, R.: When a local Hamiltonian must be frustration-free. Proc. Natl. Acad. Sci. 113(23), 6433–6437 (2016)

    Article  ADS  Google Scholar 

  46. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings, pp. 124–134. IEEE (1994)

  47. Schuch, N.: Complexity of commuting Hamiltonians on a square lattice of qubits. Quantum Inf. Comput. 11, 901 (2011)

    MathSciNet  MATH  Google Scholar 

  48. Schwarz, M., Cubitt, T.S., Verstraete, F.: An information-theoretic proof of the constructive commutative quantum Lovász Local Lemma. arXiv:1311.6474 (2013)

  49. Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 32–41 (2004)

  50. Watrous, J.: Succinct quantum proofs for properties of finite groups. In: Proceedings on 41st Annual Symposium on Foundations of Computer Science, 2000, pp. 537–546. IEEE (2000)

Download references

Acknowledgements

We thank András Gilyén, Han-Hsuan Lin, Frank Verstraete and Ronald de Wolf for useful discussions. Our research was partially funded by the Singapore Ministry of Education and the National Research Foundation under Grant R-710-000-012-135 and by the QuantERA ERA-NET Cofund project QuantAlgo. S.M. thanks the Center for Quantum Technologies, Singapore, where part of this work was carried out.

Author information

Authors and Affiliations

  1. Laboratoire d’Information Quantique CP224, Université libre de Bruxelles, 1050, Brussels, Belgium

    Serge Massar

  2. CNRS, IRIF, Université Paris Diderot, 75205, Paris, France

    Miklos Santha

  3. Centre for Quantum Technologies & MajuLab, National University of Singapore, Singapore, Singapore

    Miklos Santha

Authors
  1. Serge Massar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Miklos Santha
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Serge Massar.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Massar, S., Santha, M. Total functions in QMA. Quantum Inf Process 20, 35 (2021). https://doi.org/10.1007/s11128-020-02959-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-020-02959-0

Keywords

Search

Navigation