References
- 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.
- 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.
- 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.
- 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.
- A. Chirvasitu and M. Wasilewski (2022). “Random quantum graphs.” Transactions of the American Mathematical Society. DOI: 10.1090/tran/8584.
- 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.
- M. Kennedy, T. Kolomatski, and D. Spivak (2020). “An infinite quantum Ramsey theorem.” Journal of Operator Theory, 84. DOI: 10.7900/jot.2018dec11.2259.
- 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.
- 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.
- I. G. Todorov and L. Turowska (2020). “Quantum no-signalling correlations and non-local games.” arXiv: 2009.07016.
- M. Sipser (2012). Introduction to the Theory of Computation, 3rd ed. Cengage Learning.
- A. Y. Kitaev, A. Shen, and M. N. Vyalyi (2002). Classical and Quantum Computation. American Mathematical Society.
- 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.
- S. Bravyi (2006). “Efficient algorithm for a quantum analogue of 2-SAT.” arXiv: quant-ph/0602108.
- S. Beigi and P. W. Shor (2008). “On the complexity of computing zero-error and holevo capacity of quantum channels.” arXiv: 0709.2090.
- 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.
- 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.
- 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.
- 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.
- 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.
- N. Weaver (2010). “Quantum relations.” Memoirs of the American Mathematical Society, 215. DOI: 10.1090/S0065-9266-2011-00637-4.
- N. Weaver (2021). “Quantum graphs as quantum relations.” The Journal of Geometric Analysis, 31: 9, 90909112. DOI: 10.1007/s12220-020-00578-w.
- V. I. Paulsen (2002). Completely bounded maps and operator algebras. Cambridge studies in advanced mathematics; 78. Cambridge: Cambridge University Press.
- V. Paulsen (2016). “Online course notes: Entanglement and non-locality,” University of Waterloo. Available at www.math.uwaterloo.ca/_vpaulsen/EntanglementAndNonlocality_LectureNotes_7.pdf.
- M. Daws (2022). “Quantum graphs: different perspectives, homomorphisms and quantum automorphisms.” arXiv: 2203.08716.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- S. J. Harris (2023). “Universality of graph homomorphism games and the quantum coloring problem.” arXiv: 2305.18116.
- 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.
- 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.
- 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.
- S. Bravyi and B. Terhal (2010). “Complexity of stoquastic frustration-free Hamiltonians.” SIAM Journal on Computing, 39: 4, 1462–1485. DOI: 10.1137/08072689X.
- 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.
- 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.
- R. Bassirian, B. Fefferman, and K. Marwaha (2023). “Quantum Merlin-Arthur and proofs without relative phase.” arXiv: 2306.13247.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- T. Vidick and T. Zhang (2020). “Classical zero-knowledge arguments for quantum computations.” Quantum, 4, 266. DOI: 10.22331/q-2020–05-14-266.
- 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.
- 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.
- N. Weaver. (2017). “A ‘quantum’ Ramsey theorem for operator systems.” Proceedings of the American Mathematical Society, 145, 4595–4605. DOI: 10.1090/proc/13606.
- H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf (2001). “Quantum fingerprinting.” Physical Review Letters, 87, 167902. DOI: 10.1103/PhysRevLett.87.167902.
- 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.
- J. Watrous (2018). The Theory of Quantum Information, 1st ed. Cambridge University Press.
- P. H. Schönemann (1966). “A generalized solution of the orthogonal Procrustes problem.” Psychometrika, 31: 1, 1–10. DOI: 10.1007/BF02289451.