Quantum Information & Computation
Volume 25, Issue 5
RESEARCH ARTICLE Open access

New Approaches to Complexity via Quantum Graphs

Eric Culf, Arthur Mehta

Author affiliations
  • Eric Culf1
  • Arthur Mehta2
  1. Faculty of Mathematics and Institute for Quantum Computing, University of Waterloo, 200 University Ave W, Waterloo
  2. Department of Mathematics and Statistics, University of Ottawa, 75 Laurier Avenue East, Ottawa

pp. 453-487 · 10.2478/qic-2025-0026

Read PDF View on Reference Global
On this page

Abstract

Problems based on the structure of graphs—for example, finding cliques, independent sets, or colorings—are of fundamental importance in classical complexity. Defining well-formulated decision problems for quantum graphs, which are an operator system generalization of graphs, presents several technical challenges. Consequently, the connections between quantum graphs and complexity have been underexplored. In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We show that when quantifying over all channels, this problem is complete for QMA(2); in fact, it remains QMA(2) -complete when restricted to channels that are probabilistic mixtures of entanglement-breaking and partial trace channels. Quantifying over a subset of entanglementbreaking channels, this problem becomes QMA-complete, and restricting further to deterministic or classical noisy channels gives rise to complete problems for NP and MA, respectively. In this way, we exhibit a classical complexity problem whose natural quantization is QMA(2), rather than QMA, and provide the first problem that allows for a direct comparison of the classes QMA(2), QMA, MA, and NP by quantifying over increasingly larger families of instances. We use methods that are inspired by self-testing to provide a direct proof of QMA(2)-completeness, rather than reducing to a previously studied complete problem. We also give a new proof of the celebrated reduction of QMA(k) to QMA(2). In parallel, we study a version of the closely related independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case.
Open accessCC BY-NC-ND 4.0

Keywords

  • Complexity Theory
  • Quantum Graphs
  • Quantum Channels
  • Unentanglement

Suggested citation

Eric Culf, Arthur Mehta (2025). New Approaches to Complexity via Quantum Graphs. Quantum Information & Computation, 25(5), 453-487. https://doi.org/10.2478/qic-2025-0026

Download BibTeX

References (56)

  1. C. Shannon (1956). “The zero error capacity of a noisy channel.” IRE Transactions on Information Theory, 2: 3, 8–19, DOI: 10.1109/TIT.1956.1056798.DOI: 10.1109/TIT.1956.1056798Google Scholar
  2. R. Duan, S. Severini, and A. Winter (2013). “Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lová sz number.” IEEE Transactions on Information Theory, 59: 2, 1164–1174. DOI: 10.1109/tit.2012.2221677.DOI: 10.1109/TIT.2012.2221677Google Scholar
  3. M. Brannan, K. Eifler, C. Voigt, and M. Weber (2022). “Quantum Cuntz-Krieger algebras.” Transactions of the American Mathematical, 9. DOI: https://doi.org/10.1090/btran/88.DOI: 10.1090/btran/88Google Scholar
  4. A. Connes and W. D. van Suijlekom (2022). “Tolerance relations and operator systems.” Acta Scientiarum Mathematicarum, 88. DOI: https://doi.org/10.1007/s44146-022-00012-3.DOI: 10.1007/s44146-022-00012-3Google Scholar
  5. A. Chirvasitu and M. Wasilewski (2022). “Random quantum graphs.” Transactions of the American Mathematical Society. DOI: 10.1090/tran/8584.DOI: 10.1090/tran/8584Google Scholar
  6. P. Ganesan (2023). “Spectral bounds for the quantum chromatic number of quantum graphs.” Linear Algebra and its Applications, 674, 351–376. DOI: https://doi.org/10.1016/j.laa.2023.06.007.DOI: 10.1016/j.laa.2023.06.007Google Scholar
  7. M. Kennedy, T. Kolomatski, and D. Spivak (2020). “An infinite quantum Ramsey theorem.” Journal of Operator Theory, 84. DOI: 10.7900/jot.2018dec11.2259.DOI: 10.7900/jot.2018dec11.2259Google Scholar
  8. J. Matsuda (2022). Classification of quantum graphs on M2 and their quantum automorphism groups. Journal of Mathematical Physics, 63, 9. DOI: 10.1063/5.0081059.DOI: 10.1063/5.0081059Google Scholar
  9. D. Stahlke (2016). “Quantum zero-error source-channel coding and non-commutative graph theory.” IEEE Transactions on Information Theory, 62: 1, 554–577. DOI: 10.1109/tit.2015.2496377.DOI: 10.1109/TIT.2015.2496377Google Scholar
  10. I. G. Todorov and L. Turowska (2020). “Quantum no-signalling correlations and non-local games.” arXiv: 2009.07016.Google Scholar
  11. M. Sipser (2012). Introduction to the Theory of Computation, 3rd ed. Cengage Learning.Google Scholar
  12. A. Y. Kitaev, A. Shen, and M. N. Vyalyi (2002). Classical and Quantum Computation. American Mathematical Society.DOI: 10.1090/gsm/047Google Scholar
  13. A. Broadbent and A. B. Grilo (2022). “QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge.” SIAM Journal on Computing, 51: 4, 1400–1450. DOI: 10.1137/21m140729x.DOI: 10.1137/21M140729XGoogle Scholar
  14. S. Bravyi (2006). “Efficient algorithm for a quantum analogue of 2-SAT.” arXiv: quant-ph/0602108.Google Scholar
  15. S. Beigi and P. W. Shor (2008). “On the complexity of computing zero-error and holevo capacity of quantum channels.” arXiv: 0709.2090.Google Scholar
  16. S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor (2009). “The power of unentanglement.” Theory of Computing, 5: 1, 1–42. DOI: 10.4086/toc.2009.v005a001.DOI: 10.4086/toc.2009.v005a001Google Scholar
  17. H. Kobayashi, K. Matsumoto, and T. Yamakami (2003). “Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur?” In Algorithms and Computation, pp. 189–198, Berlin, Heidelberg. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-24587-2_21.DOI: 10.1007/978-3-540-24587-2_21Google Scholar
  18. A. Chailloux and O. Sattath (2012). “The complexity of the separable Hamiltonian problem.” In 2012 IEEE 27th Conference on Computational Complexity. IEEE. DOI: 10.1109/ccc.2012.42.DOI: 10.1109/CCC.2012.42Google Scholar
  19. G. Gutoski, P. Hayden, K. Milner, and M. M. Wilde (2015). “Quantum interactive proofs and the complexity of separability testing.” Theory of Computing, 11: 1, 59–103. DOI: 10.4086/toc.2015.v011a003.DOI: 10.4086/toc.2015.v011a003Google Scholar
  20. J. Erdos, A. Katavolos, and V. Shulman (1998). “Rank one subspaces of bimodules over maximal abelian selfadjoint algebras.” Journal of Functional Analysis, 157: 2, 554–587. DOI: https://doi.org/10.1006/jfan.1998.3274.DOI: 10.1006/jfan.1998.3274Google Scholar
  21. N. Weaver (2010). “Quantum relations.” Memoirs of the American Mathematical Society, 215. DOI: 10.1090/S0065-9266-2011-00637-4.DOI: 10.1090/S0065-9266-2011-00637-4Google Scholar
  22. N. Weaver (2021). “Quantum graphs as quantum relations.” The Journal of Geometric Analysis, 31: 9, 90909112. DOI: 10.1007/s12220-020-00578-w.DOI: 10.1007/s12220-020-00578-wGoogle Scholar
  23. V. I. Paulsen (2002). Completely bounded maps and operator algebras. Cambridge studies in advanced mathematics; 78. Cambridge: Cambridge University Press.DOI: 10.1017/CBO9780511546631Google Scholar
  24. V. Paulsen (2016). “Online course notes: Entanglement and non-locality,” University of Waterloo. Available at www.math.uwaterloo.ca/_vpaulsen/EntanglementAndNonlocality_LectureNotes_7.pdf.Google Scholar
  25. M. Daws (2022). “Quantum graphs: different perspectives, homomorphisms and quantum automorphisms.” arXiv: 2203.08716.Google Scholar
  26. G. Boreland, I. Todorov, and A. Winter (2021). “Sandwich theorems and capacity bounds for non-commutative graphs.” Journal of Combinatorial Theory, Series A, 177, 105302. DOI: 10.1016/j.jcta.2020.105302.DOI: 10.1016/j.jcta.2020.105302Google Scholar
  27. S.-J. Kim and A. Mehta (2019). “Chromatic numbers, Sabidussi’s theorem and Hedetniemi’s conjecture for non-commutative graphs.” Linear Algebra and its Applications, 582, 291–309. DOI: https://doi.org/10.1016/j.laa.2019.08.002.DOI: 10.1016/j.laa.2019.08.002Google Scholar
  28. C. M. Ortiz and V. I. Paulsen (2016). “Quantum graph homomorphisms via operator systems.” Linear Algebra and its Applications, 497, 23–43. DOI: https://doi.org/10.1016/j.laa.2016.02.019.DOI: 10.1016/j.laa.2016.02.019Google Scholar
  29. J. W. Helton, K. P. Meyer, V. I. Paulsen, and M. Satriano (2019). “Algebras, synchronous games, and chromatic numbers of graphs.” New York Journal of Mathematics, 25, 328–361. Available at nyjm.albany.edu/j/2019/25-16.html.Google Scholar
  30. L. Mančinska and D. E. Roberson (2016). “Quantum homomorphisms.” Journal of Combinatorial Theory, Series B, 118, 228–267. DOI: https://doi.org/10.1016/j.jctb.2015.12.009.DOI: 10.1016/j.jctb.2015.12.009Google Scholar
  31. M. Brannan, P. Ganesan, and S. J. Harris (2022). “The quantum-to-classical graph homomorphism game.” Journal ofMathematical Physics, 63: 11, 112204. DOI: 10.1063/5.0072288.DOI: 10.1063/5.0072288Google Scholar
  32. M. Coudron and W. Slofstra (2019). “Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision.” In A. Shpilka (ed.), 34th Computational Complexity Conference (CCC 2019), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 25:1–25: 20, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. DOI: 10.4230/LIPIcs.CCC.2019.25.Google Scholar
  33. Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen (2021). “MIP* = RE.” Communications of the ACM, 64: 11, 131–138. DOI: 10.1145/3485628.DOI: 10.1145/3485628Google Scholar
  34. H. Mousavi, S. S. Nezhadi, and H. Yuen (2022). “Nonlocal games, compression theorems, and the arithmetical hierarchy.” In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. ACM. DOI: 10.1145/3519935.3519949.DOI: 10.1145/3519935.3519949Google Scholar
  35. S. J. Harris (2023). “Universality of graph homomorphism games and the quantum coloring problem.” arXiv: 2305.18116.Google Scholar
  36. H. Galperin and A. Wigderson (1983). “Succinct representations of graphs.” Information and Control, 56: 3, 183–198, DOI: https://doi.org/10.1016/S0019-9958(83)80004-7.DOI: 10.1016/S0019-9958(83)80004-7Google Scholar
  37. A. W. Harrow and A. Montanaro (2013). “Testing product states, quantum Merlin-Arthur games and tensor optimization.” Journal of the ACM, 60: 1, 1–43. DOI: 10.1145/2432622.2432625.DOI: 10.1145/2432622.2432625Google Scholar
  38. D. Aharonov and A. B. Grilo (2019). “Stoquastic pcp vs. randomness.” In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1000–1023. IEEE. DOI: 10.1109/FOCS.2019.00065.DOI: 10.1109/FOCS.2019.00065Google Scholar
  39. S. Bravyi and B. Terhal (2010). “Complexity of stoquastic frustration-free Hamiltonians.” SIAM Journal on Computing, 39: 4, 1462–1485. DOI: 10.1137/08072689X.DOI: 10.1137/08072689XGoogle Scholar
  40. A. Broadbent, A. Mehta, and Y. Zhao (2024). “Quantum delegation with an off-the-shelf device.” In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, DOI: 10.4230/LIPIcs.TQC.2024.12.Google Scholar
  41. A. B. Grilo (2019). “A simple protocol for verifiable delegation of quantum computation in one round.” In 46th International Colloquium on Automata, Languages, and Programming—ICALP 2019, pp. 28. DOI: 10.4230/LIPIcs.ICALP.2019.28.Google Scholar
  42. R. Bassirian, B. Fefferman, and K. Marwaha (2023). “Quantum Merlin-Arthur and proofs without relative phase.” arXiv: 2306.13247.Google Scholar
  43. F. G. d. S. L. Brandão (2008). Entanglement Theory and the Quantum Simulation of Many-Body Physics. PhD thesis, University of London. arXiv: 0810.0026.Google Scholar
  44. L. Lovász (1973). “Coverings and colorings of hypergraphs.” In In Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Online: www.cs.elte.hu/ lovasz/scans/covercolor.pdf.Google Scholar
  45. M. Ben-Or, O. Goldreich, S. Goldwasser, J. Håstad, J. Kilian, S. Micali, and P. Rogaway (1988). “Everything provable is provable in zero-knowledge.” In Advances in Cryptology—CRYPTO 1988, pp. 37–56. DOI: 10.1007/0-387-34799-2_4.DOI: 10.1007/0-387-34799-2_4Google Scholar
  46. O. Goldreich, S. Micali, and A. Wigderson(1991). “Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems.” Journal of the ACM, 38: 3, 690–728. DOI: 10.1145/116825.116852.DOI: 10.1145/116825.116852Google Scholar
  47. A. Chiesa, M. Forbes, T. Gur, and N. Spooner (2018). “Spatial isolation implies zero knowledge even in a quantum world.” In 59th Annual Symposium on Foundations of Computer Science—FOCS 2018, pp. 755–765. DOI: 10.1109/FOCS.2018.00077.DOI: 10.1109/FOCS.2018.00077Google Scholar
  48. A. Grilo, W. Slofstra, and H. Yuen (2019). “Perfect zero knowledge for quantum multiprover interactive proofs.” In Proceedings of FOCS, pp. 611–635. DOI: 10.1109/FOCS.2019.00044.DOI: 10.1109/FOCS.2019.00044Google Scholar
  49. T. Vidick and T. Zhang (2020). “Classical zero-knowledge arguments for quantum computations.” Quantum, 4, 266. DOI: 10.22331/q-2020–05-14-266.DOI: 10.22331/q-2020-05-14-266Google Scholar
  50. F. Ramsey (1930). “On a problem of formal logic.” Proceedings of the London Mathematical Society, 30, 264286. DOI: 10.1112/plms/s2-30.1.264.DOI: 10.1112/plms/s2-30.1.264Google Scholar
  51. S. A. Burr (1990). On the Computational Complexity of Ramsey—Type Problems, pp. 46–52. Springer Berlin Heidelberg, Berlin, Heidelberg. DOI: 10.1007/978-3-642-72905-8_5.DOI: 10.1007/978-3-642-72905-8_5Google Scholar
  52. N. Weaver. (2017). “A ‘quantum’ Ramsey theorem for operator systems.” Proceedings of the American Mathematical Society, 145, 4595–4605. DOI: 10.1090/proc/13606.DOI: 10.1090/proc/13606Google Scholar
  53. H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf (2001). “Quantum fingerprinting.” Physical Review Letters, 87, 167902. DOI: 10.1103/PhysRevLett.87.167902.DOI: 10.1103/PhysRevLett.87.167902Google Scholar
  54. M. Horodecki, P. W. Shor, and M. B. Ruskai (2003). “Entanglement breaking channels.” Reviews in Mathematical Physics, 15: 6, 629–641. DOI: 10.1142/s0129055x03001709.DOI: 10.1142/S0129055X03001709Google Scholar
  55. J. Watrous (2018). The Theory of Quantum Information, 1st ed. Cambridge University Press.DOI: 10.1017/9781316848142Google Scholar
  56. P. H. Schönemann (1966). “A generalized solution of the orthogonal Procrustes problem.” Psychometrika, 31: 1, 1–10. DOI: 10.1007/BF02289451.DOI: 10.1007/BF02289451Google Scholar