research

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

Prem Nigam Kar, David E. Roberson, Tim Seppelt, and Peter Zeman

13 min read

0 likes

⚡ Quantum Brief

Researchers Kar, Roberson, Seppelt, and Zeman proved that each level of the NPA hierarchy—a quantum semidefinite programming relaxation—can determine quantum isomorphism by comparing homomorphism counts from specific planar graph classes. The study offers a new proof of Mančinska and Roberson’s 2020 result, showing quantum isomorphism equals homomorphism indistinguishability from all planar graphs, without relying on quantum group theory. The NPA hierarchy’s convergence ensures that as levels increase, the graph classes’ union covers all planar graphs, reinforcing the equivalence between quantum isomorphism and homomorphism-based indistinguishability. A key breakthrough is a randomized polynomial-time algorithm to decide the feasibility of any fixed NPA hierarchy level, addressing computational challenges in quantum graph isomorphism testing. The work bridges classical and quantum graph theory, extending Roberson and Seppelt’s 2023 Lasserre hierarchy characterization to the noncommutative NPA framework for quantum isomorphism relaxations.

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractMančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general, which motivates the study of its relaxations. In the classical setting, Roberson and Seppelt [ICALP'23] characterized the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism in terms of equality of homomorphism counts from an appropriate graph class. The NPA hierarchy, a noncommutative generalization of the Lasserre hierarchy, provides a sequence of semidefinite programming relaxations for quantum isomorphism. In the quantum setting, we show that the feasibility of each level of the NPA hierarchy for quantum isomorphism is equivalent to equality of homomorphism counts from an appropriate class of planar graphs. Combining this characterization with the convergence of the NPA hierarchy, and noting that the union of these classes is the set of all planar graphs, we obtain a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of quantum groups. Moreover, this homomorphism indistinguishability characterization also yields a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism. ► BibTeX data@article{Kar2026npahierarchyquantum, doi = {10.22331/q-2026-01-28-1989}, url = {https://doi.org/10.22331/q-2026-01-28-1989}, title = {{NPA} {H}ierarchy for {Q}uantum {I}somorphism and {H}omomorphism {I}ndistinguishability}, author = {Kar, Prem Nigam and Roberson, David E. and Seppelt, Tim and Zeman, Peter}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1989}, month = jan, year = {2026} }► References [1] László Lovász. ``Operations with structures''.

Acta Mathematica Academiae Scientiarum Hungarica 18, 321–328 (1967). https://doi.org/10.1007/BF02280291 [2] Zdeněk Dvořák. ``On recognizing graphs by numbers of homomorphisms''. Journal of Graph Theory 64, 330–342 (2010). https://doi.org/10.1002/jgt.20461 [3] Martin Grohe. ``Counting bounded tree depth homomorphisms''. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). Pages 507–520. (2020). https://doi.org/10.1145/3373718.3394739 [4] Eva Fluck, Tim Seppelt, and Gian Luca Spitzer. ``Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth''. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Volume 288, pages 27:1–27:17. (2024). https://doi.org/10.4230/LIPIcs.CSL.2024.27 [5] Holger Dell, Martin Grohe, and Gaurav Rattan. ``Lovász Meets Weisfeiler and Leman''. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Volume 107, pages 40:1–40:14. (2018). https://doi.org/10.4230/LIPIcs.ICALP.2018.40 [6] Martin Grohe, Gaurav Rattan, and Tim Seppelt. ``Homomorphism Tensors and Linear Equations''. Advances in Combinatorics (2025). https://doi.org/10.19086/aic.2025.4 [7] David E. Roberson and Tim Seppelt. ``Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability''. TheoretiCS (2024). https://doi.org/10.46298/theoretics.24.20 [8] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. ``How Powerful are Graph Neural Networks?''.

In International Conference on Learning Representations. (2018). url: https://openreview.net/forum?id=ryGs6iA5Km. https://openreview.net/forum?id=ryGs6iA5Km [9] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. ``Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks''. Proceedings of the AAAI Conference on Artificial Intelligence 33, 4602–4609 (2019). https://doi.org/10.1609/aaai.v33i01.33014602 [10] Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. ``Beyond Weisfeiler–Lehman: A Quantitative Framework for GNN Expressiveness''.

In The Twelfth International Conference on Learning Representations. (2024). url: https://openreview.net/forum?id=HSKaGOi7Ar. https://openreview.net/forum?id=HSKaGOi7Ar [11] Anuj Dawar, Tomáš Jakl, and Luca Reggio. ``Lovász-Type Theorems and Game Comonads''. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021. Pages 1–13. IEEE (2021). https://doi.org/10.1109/LICS52264.2021.9470609 [12] Samson Abramsky, Tomáš Jakl, and Thomas Paine. ``Discrete Density Comonads and Graph Parameters''.

In Helle Hvid Hansen and Fabio Zanasi, editors, Coalgebraic Methods in Computer Science. Pages 23–44. Cham (2022).

Springer International Publishing. https://doi.org/10.1007/978-3-031-10736-8_2 [13] Yoàv Montacute and Nihil Shah. ``The Pebble-Relation Comonad in Finite Model Theory''.

In Christel Baier and Dana Fisman, editors, LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022. Pages 13:1–13:11. ACM (2022). https://doi.org/10.1145/3531130.3533335 [14] David E. Roberson. ``Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree'' (2022). arXiv:2206.10321v1. arXiv:2206.10321v1 [15] Tim Seppelt. ``Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors''. In Jérôme Leroux, Sylvain Lombardy, and David Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Volume 272 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1–82:15. Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2023.82 [16] Daniel Neuen. ``Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width''.

In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Volume 289 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1–53:12. Dagstuhl, Germany (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2024.53 [17] Tim Seppelt. ``An Algorithmic Meta Theorem for Homomorphism Indistinguishability''.

In Rastislav Královič and Antonín Kučera, editors, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Volume 306 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1–82:19. Dagstuhl, Germany (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2024.82 [18] Tim Seppelt. ``Homomorphism Indistinguishability''. Dissertation. RWTH Aachen University. Aachen (2024). https://doi.org/10.18154/RWTH-2024-11629 [19] Laura Mančinska and David E. Roberson. ``Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs''. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Pages 661–672. (2020). https://doi.org/10.1109/FOCS46700.2020.00067 [20] Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. ``Quantum and non-signalling graph isomorphisms''. Journal of Combinatorial Theory, Series B 136, 289–328 (2019). https://doi.org/10.1016/j.jctb.2018.11.002 [21] László Babai. ``Graph isomorphism in quasipolynomial time [extended abstract]''.

In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. Pages 684–697. ACM (2016). https://doi.org/10.1145/2897518.2897542 [22] Miguel Navascués, Stefano Pironio, and Antonio Acín. ``A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations''. New Journal of Physics 10, 073013 (2008). https://doi.org/10.1088/1367-2630/10/7/073013 [23] Gaurav Rattan and Tim Seppelt. ``Weisfeiler–Leman and Graph Spectra''. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 2268–2285. Society for Industrial and Applied Mathematics (2023). https://doi.org/10.1137/1.9781611977554.ch87 [24] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''.

Cambridge University Press. (2010). https://doi.org/10.1017/CBO9780511976667 [25] Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis. ``Graph isomorphism: physical resources, optimization models, and algebraic characterizations''. Math. Program. 205, 617–660 (2024). https://doi.org/10.1007/s10107-023-01989-7 [26] Neil Robertson and Paul D. Seymour. ``Graph minors. iii. planar tree-width''. Journal of Combinatorial Theory, Series B 36, 49–64 (1984). https://doi.org/10.1016/0095-8956(84)90013-3 [27] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. ``PRIMES is in P''. Annals of Mathematics 160, 781–793 (2004). https://doi.org/10.4007/annals.2004.160.781 [28] Man-Duen Choi. ``Completely positive linear maps on complex matrices''. Linear Algebra and its Applications 10, 285–290 (1975). https://doi.org/10.1016/0024-3795(75)90075-0 [29] John Watrous. ``Advanced topics in quantum information theory'' (2020). [30] Travis B. Russell. ``A synchronous NPA hierarchy with applications''. Operators and Matrices 17, 901–924 (2023). https://doi.org/10.7153/oam-2023-17-60 [31] Miguel Navascués, Stefano Pironio, and Antonio Acín. ``Sdp relaxations for non-commutative polynomial optimization''. Pages 601–634. Springer US. New York, NY (2012). https://doi.org/10.1007/978-1-4614-0769-0_21 [32] Gereon Koßmann, René Schwonnek, and Jonathan Steinberg. ``Hierarchies for Semidefinite Optimization in $C^\star$-Algebras'' (2023). url: http://arxiv.org/abs/2309.13966. arXiv:2309.13966Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-28 10:24:25: Could not fetch cited-by data for 10.22331/q-2026-01-28-1989 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-28 10:24:26: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractMančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general, which motivates the study of its relaxations. In the classical setting, Roberson and Seppelt [ICALP'23] characterized the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism in terms of equality of homomorphism counts from an appropriate graph class. The NPA hierarchy, a noncommutative generalization of the Lasserre hierarchy, provides a sequence of semidefinite programming relaxations for quantum isomorphism. In the quantum setting, we show that the feasibility of each level of the NPA hierarchy for quantum isomorphism is equivalent to equality of homomorphism counts from an appropriate class of planar graphs. Combining this characterization with the convergence of the NPA hierarchy, and noting that the union of these classes is the set of all planar graphs, we obtain a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of quantum groups. Moreover, this homomorphism indistinguishability characterization also yields a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism. ► BibTeX data@article{Kar2026npahierarchyquantum, doi = {10.22331/q-2026-01-28-1989}, url = {https://doi.org/10.22331/q-2026-01-28-1989}, title = {{NPA} {H}ierarchy for {Q}uantum {I}somorphism and {H}omomorphism {I}ndistinguishability}, author = {Kar, Prem Nigam and Roberson, David E. and Seppelt, Tim and Zeman, Peter}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1989}, month = jan, year = {2026} }► References [1] László Lovász. ``Operations with structures''.

In Helle Hvid Hansen and Fabio Zanasi, editors, Coalgebraic Methods in Computer Science. Pages 23–44. Cham (2022).

Springer International Publishing. https://doi.org/10.1007/978-3-031-10736-8_2 [13] Yoàv Montacute and Nihil Shah. ``The Pebble-Relation Comonad in Finite Model Theory''.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.