- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review Applied

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Topological signal processing on quantum computers for higher-order network analysis

Caesnan M.G. Leditto1,2,*, Angus Southwell1,3,†, Behnam Tonekaboni2,4, Gregory A.L. White1,5, Muhammad Usman2,6,1, and Kavan Modi7,1,3,‡

  • 1School of Physics and Astronomy, Monash University, Clayton, VIC 3168, Australia
  • 2Quantum Systems, Data61, CSIRO, Clayton, VIC 3168, Australia
  • 3Quantum for New South Wales, Haymarket, NSW 2000, Australia
  • 4Infleqtion, Melbourne, VIC 3000, Australia
  • 5Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
  • 6School of Physics, The University of Melbourne, Parkville, VIC 3052, Australia
  • 7Science, Mathematics and Technology Cluster, Singapore University of Technology and Design, 8 Somapah Road, 487372 Singapore

  • *Contact author: caesnan.leditto@monash.edu
  • †Contact author: angus.southwell@monash.edu
  • ‡Contact author: kavan@quantumlah.org
PDF

Phys. Rev. Applied 23, 054054 – Published 21 May, 2025

DOI: https://doi.org/10.1103/PhysRevApplied.23.054054

Abstract

Predicting and analyzing global behavior of complex systems is challenging due to the intricate nature of their component interactions. Recent work has started modeling complex systems using networks endowed with multiway interactions among nodes, known as higher-order networks. Simplicial complexes are a class of higher-order networks that have received significant attention due to their topological structure and connections to Hodge theory. Topological signal processing (TSP) utilizes these connections to analyze and manipulate signals defined on non-Euclidean domains such as simplicial complexes. Such analysis of higher-order network data is important for many real-world problems, such as detecting failure or error in communication networks, sensor coverage analysis, statistical ranking problems, finding arbitrage currency markets, etc. However, as the dimension of higher-order networks increases, the complexity of TSP scales exponentially. In this work, we present a general quantum algorithm for implementing filtering processes in TSP and describe its application to extracting network data based on the Hodge decomposition. We leverage preexisting tools introduced in recent quantum algorithms for topological data analysis and combine them with spectral filtering techniques using the quantum singular value transformation framework. While this paper serves as a proof of concept, we obtain a superpolynomial improvement over the best-known classical algorithms for TSP filtering processes, modulo some important caveats about encoding and retrieving the data from a quantum state. The proposed algorithm generalizes the applicability of tools from quantum topological data analysis to novel applications in analyzing high-dimensional complex systems.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (95)

  1. A. Sandryhaila and J. M. F. Moura, Discrete signal processing on graphs, IEEE. Trans. Signal Process. 61, 1644 (2013).
  2. A. Sandryhaila and J. M. F. Moura, Discrete signal processing on graphs: Frequency analysis, IEEE. Trans. Signal Process. 62, 3042 (2014).
  3. A. Ortega, P. Frossard, J. Kovacevic, J. M. F. Moura, and P. Vandergheynst, Graph signal processing: Overview, challenges, and applications, Proc. IEEE 106, 808 (2018).
  4. S. Barbarossa and S. Sardellitti, Topological signal processing over simplicial complexes, IEEE. Trans. Signal Process. 68, 2992 (2020).
  5. M. T. Schaub, Y. Zhu, J. B. Seby, T. M. Roddenberry, and S. Segarra, Signal processing on higher-order networks: Livin’ on the edge... and beyond, Signal Process. 187, 108149 (2021).
  6. F. Battiston, G. Cencetti, I. Iacopini, V. Latora, M. Lucas, A. Patania, J.-G. Young, and G. Petri, Networks beyond pairwise interactions: Structure and dynamics, Phys. Rep. 874, 1 (2020).
  7. F. Battiston, E. Amico, A. Barrat, G. Bianconi, G. F. de Arruda, B. Franceschiello, I. Iacopini, S. Kéfi, V. Latora, Y. Moreno, M. M. Murray, T. P. Peixoto, F. Vaccarino, and G. Petri, The physics of higher-order interactions in complex systems, Nat. Phys. 17, 1093 (2021).
  8. S. Majhi, M. Perc, and D. Ghosh, Dynamics on higher-order networks: A review, J. R. Soc. Interface 19, 20220043 (2022).
  9. C. Bick, E. Gross, H. A. Harrington, and M. T. Schaub, What are higher-order networks? SIAM Rev. 65, 686 (2023).
  10. L. Calmon, M. T. Schaub, and G. Bianconi, in 2022 56th Asilomar Conference on Signals, Systems, and Computers (IEEE, 2022), pp. 925–929.
  11. I. Jablonski, Graph signal processing in applications to sensor networks, smart grids, and smart cities, IEEE Sens. J. 17, 7659 (2017).
  12. W. Huang, L. Goldsberry, N. F. Wymbs, S. T. Grafton, D. S. Bassett, and A. Ribeiro, Graph frequency analysis of brain signals, IEEE J. Sel. Top. Signal Process. 10, 1189 (2016).
  13. L. Goldsberry, W. Huang, N. F. Wymbs, S. T. Grafton, D. S. Bassett, and A. Ribeiro, Brain signal analytics from graph signal processing perspective, IEEE Signal Process. Soc., 851 (2017).
  14. W. Huang, T. A. W. Bolton, J. D. Medaglia, D. S. Bassett, A. Ribeiro, and D. Van De Ville, A graph signal processing perspective on functional brain imaging, Proc. IEEE 106, 868 (2018).
  15. S. Segarra, A. G. Marques, G. Mateos, and A. Ribeiro, Network topology inference from spectral templates, IEEE Trans. Signal Inf. Process. Netw. 3, 467 (2017).
  16. V. K. Sharma, D. K. Srivastava, and P. Mathur, Efficient image steganography using graph signal processing, IET Image Process. 12, 1065 (2018).
  17. G. Cheung, E. Magli, Y. Tanaka, and M. K. Ng, Graph spectral image processing, Proc. IEEE 106, 907 (2018).
  18. M. Lucas, G. Cencetti, and F. Battiston, Multiorder Laplacian for synchronization in higher-order networks, Phys. Rev. Res. 2, 033410 (2020).
  19. A. Patania, G. Petri, and F. Vaccarino, The shape of collaborations, EPJ Data Sci. 6, 18 (2017).
  20. Z. Cang, L. Mu, K. Wu, K. Opron, K. Xia, and G.-W. Wei, A topological approach for protein classification, Comput. Math. Biophys. 3, 140 (2015).
  21. G. Carlsson, Topology and data, Bull. Am. Math. Soc. 46, 255 (2009).
  22. A. Patania, F. Vaccarino, and G. Petri, Topological analysis of data, EPJ Data Sci. 6, 7 (2017).
  23. L. Wasserman, Topological data analysis, Ann. Rev. Stat. Appl. 5, 501 (2018).
  24. F. Chazal and B. Michel, An introduction to topological data analysis: Fundamental and practical aspects for data scientists, Front. Artif. Intell. 4, 108 (2021).
  25. V. de Silva and R. Ghrist, Coverage in sensor networks via persistent homology, Algebr. Geom. Topol. 7, 339 (2007).
  26. M. Gidea and Y. Katz, Topological data analysis of financial time series: Landscapes of crashes, Physica A 491, 820 (2018).
  27. T. Qaiser, Y. W. Tsang, D. Taniyama, N. Sakamoto, K. Nakane, D. Epstein, and N. Rajpoot, Fast and accurate tumor segmentation of histology images using persistent homology and deep convolutional features, Med. Image Anal. 55, 1 (2019).
  28. C. J. Carstens and K. J. Horadam, Persistent homology of collaboration networks, Math. Prob. Eng. 2013, 815305 (2013).
  29. H. Adams, T. Emerson, M. Kirby, R. Neville, C. Peterson, P. Shipman, S. Chepushtanova, E. Hanson, F. Motta, and L. Ziegelmeier, Persistence images: A stable vector representation of persistent homology, J. Mach. Learn. Res. 18, 1 (2017).
  30. A. J. Blumberg, I. Gal, M. A. Mandell, and M. Pancia, Robust statistics, hypothesis testing, and confidence intervals for persistent homology on metric measure spaces, Found. Comput. Math. 14, 745 (2014).
  31. F. Hensel, M. Moor, and B. Rieck, A survey of topological machine learning methods, Frontiers in Artificial Intelligence 4, 681108 (2021).
  32. S. Lloyd, S. Garnerone, and P. Zanardi, Quantum algorithms for topological and geometric analysis of data, Nat. Commun. 7, 10138 (2016).
  33. C. Cade and P. M. Crichigno, Complexity of supersymmetric systems and the cohomology problem, Quantum 8, 1325 (2024).
  34. C. Gyurik, C. Cade, and V. Dunjko, Towards quantum advantage via topological data analysis, Quantum 6, 1 (2022).
  35. I. Y. Akhalwaya, S. Ubaru, K. L. Clarkson, M. S. Squillante, V. Jejjala, Y.-H. He, K. Naidoo, V. Kalantzis, and L. Horesh, in The Twelfth International Conference on Learning Representations (ICLR, 2024).
  36. R. Hayakawa, Quantum algorithm for persistent Betti numbers and topological data analysis, Quantum 6, 873 (2022).
  37. S. McArdle, A. Gilyén, and M. Berta, A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits, arXiv:2209.12887.
  38. A. Schmidhuber and S. Lloyd, Complexity-theoretic limitations on quantum algorithms for topological data analysis, PRX Quantum 4, 040349 (2023).
  39. D. W. Berry, Y. Su, C. Gyurik, R. King, J. Basso, A. D. T. Barba, A. Rajput, N. Wiebe, V. Dunjko, and R. Babbush, Analyzing prospects for quantum advantage in topological data analysis, PRX Quantum 5, 010319 (2024).
  40. Y. R. Sanders, D. W. Berry, P. C. Costa, L. W. Tessler, N. Wiebe, C. Gidney, H. Neven, and R. Babbush, Compilation of fault-tolerant quantum heuristics for combinatorial optimization, PRX Quantum 1, 020312 (2020).
  41. R. Babbush, J. R. McClean, M. Newman, C. Gidney, S. Boixo, and H. Neven, Focus beyond quadratic speedups for error-corrected quantum advantage, PRX Quantum 2, 010103 (2021).
  42. C. M. G. Leditto, A.Southwell,B. Tonekaboni, M. Usman, and K. Modi, Quantum hodgerank: Topology-based rank aggregation on quantum computers, arXiv:2407.20452.
  43. L. H. Lim, Hodge Laplacians on graphs, SIAM Rev. 62, 685 (2020).
  44. T. E. Goldberg, Combinatorial Laplacians of simplicial complexes, Senior Thesis, Bard College, 2002.
  45. M. Yang, E. Isufi, M. T. Schaub, and G. Leus, in European Signal Processing Conference, Vol. 2021-August (EUSIPCO, 2021), pp. 2005–2009.
  46. M. Yang, M. T. Isufi, E. Schaub, and G. Leus, Simplicial convolutional filters, IEEE Trans. Signal Process. 2021, 4633 (2022).
  47. S. Ebli, M. Defferrard, and G. Spreemann, Simplicial neural networks, arXiv:2010.03633.
  48. D. I. Shuman, P. Vandergheynst, and P. Frossard, in 2011 International Conference on Distributed Computing in Sensor Systems and Workshops (DCOSS) (IEEE, 2011), pp. 1–8.
  49. F. Baccini, F. Geraci, and G. Bianconi, Weighted simplicial complexes and their representation power of higher-order network data and topology, Phys. Rev. E 106, 034319 (2022).
  50. S. Krishnagopal and G. Bianconi, Spectral detection of simplicial communities via Hodge Laplacians, Phys. Rev. E 104, 064303 (2021).
  51. A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Phys. Rev. Lett. 103, 150502 (2009).
  52. P. Rebentrost, M. Mohseni, and S. Lloyd, Quantum support vector machine for big data classification, Phys. Rev. Lett. 113, 130503 (2014).
  53. S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum principal component analysis, Nat. Phys. 10, 631 (2014).
  54. I. Kerenidis and A. Prakash, in Leibniz International Proceedings in Informatics, LIPIcs (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017), Vol. 67.
  55. I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, in Proceedings of the 33rd International Conference on Neural Information Processing Systems (NeurIPS, 2019).
  56. I. Kerenidis and J. Landman, Quantum spectral clustering, Phys. Rev. A 103, 042415 (2021).
  57. S. Aaronson, Read the fine print, Nat. Phys. 11, 291 (2015).
  58. N.-H. Chia, A. P. Gilyén, T. Li, H.-H. Lin, E. Tang, and C. Wang, Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning, J. ACM 69, 33 (2022).
  59. S. Gharibian and F. Le Gall, in Proceedings of the Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, 2022), pp. 19–32.
  60. X. M. Zhang, T. Li, and X. Yuan, Quantum state preparation with optimal circuit depth: Implementations and applications, Phys. Rev. Lett. 129, 230504 (2022).
  61. R. M. S. Farias, T. O. Maciel, G. Camilo, R. Lin, S. Ramos-Calderer, and L. Aolita, Quantum encoder for fixed hamming-weight subspaces, arXiv:2405.20408 [quant-ph].
  62. T. J. Proctor, P. A. Knott, and J. A. Dunningham, Multiparameter estimation in networked quantum sensors, Phys. Rev. Lett. 120, 080501 (2018).
  63. J. van Apeldoorn, A. Cornelissen, A. Gilyén, and G. Nannicini, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (SIAM, 2023), pp. 1265–1318.
  64. J. Friedman, Computing Betti numbers via combinatorial Laplacians, Algorithmica 21, 331 (1998).
  65. H. Bhatia, G. Norgard, V. Pascucci, and P. T. Bremer, The Helmholtz-Hodge decomposition – A survey, IEEE Trans. Vis. Comput. Graph. 19, 1386 (2013).
  66. X. Jiang, L. H. Lim, Y. Yao, and Y. Ye, Statistical ranking and combinatorial Hodge theory, Math. Program. 127, 203 (2011).
  67. J. Steenbergen, C. Klivans, and S. Mukherjee, A Cheeger-type inequality on simplicial complexes, Adv. Appl. Math. 56, 56 (2014).
  68. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, in Proceedings of the Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, 2019), pp. 193–204.
  69. A. M. Childs, R. Kothari, and R. D. Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM J. Comput. 46, 1920 (2017).
  70. Y. Dong, X. Meng, K. B. Whaley, and L. Lin, Efficient phase-factor evaluation in quantum signal processing, Phys. Rev. A 103, 042419 (2021).
  71. I. Kerenidis and A. Prakash, Quantum machine learning with subspace states, arXiv:2202.00054.
  72. M. Black and A. Nayyeri, in Leibniz International Proceedings in Informatics, LIPIcs (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022), Vol. 229.
  73. Z. M. Rossi and I. L. Chuang, Multivariable quantum signal processing (M-QSP): Prophecies of the two-headed oracle, Quantum 6, 811 (2022).
  74. Z. Zhang and Q. Zhuang, Distributed quantum sensing, Quantum Sci. Technol. 6, 043001 (2021).
  75. J. Rubio, P. A. Knott, T. J. Proctor, and J. A. Dunningham, Quantum sensing networks for the estimation of linear functions, J. Phys. A: Math. Theor. 53, 344001 (2020).
  76. T. Qian, J. Bringewatt, I. Boettcher, P. Bienias, and A. V. Gorshkov, Optimal measurement of field properties with quantum sensor networks, Phys. Rev. A 103, L030601 (2021).
  77. J. Bringewatt, I. Boettcher, P. Niroula, P. Bienias, and A. V. Gorshkov, Protocols for estimating multiple functions with quantum sensor networks: Geometry and performance, Phys. Rev. Res. 3, 033011 (2021).
  78. Y. Kuramoto, in International Symposium on Mathematical Problems in Theoretical Physics, edited by H. Araki (Springer, Berlin, Heidelberg, 1975), pp. 420–422.
  79. A. P. Millán, J. J. Torres, and G. Bianconi, Explosive higher-order Kuramoto dynamics on simplicial complexes, Phys. Rev. Lett. 124, 218301 (2020).
  80. A. M. Karmelic, T. Perez-Acle, and M. O. Ferreiro, in 2022 41st International Conference of the Chilean Computer Science Society (SCCC) (IEEE, 2022), pp. 1–4.
  81. S. Strogatz, Sync: The Emerging Science of Spontaneous Order (Hyperion Press, New York, 2003).
  82. M. Nurisso, A. Arnaudon, M. Lucas, R. L. Peach, P. Expert, F. Vaccarino, and G. Petri, A unified framework for simplicial Kuramoto models, Chaos 34, 053118 (2024).
  83. T. M. Roddenberry, N. Glaze, and S. Segarra, in Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, edited by M. Meila and T. Zhang (PMLR, 2021), Vol. 139, pp. 9020–9029.
  84. A. D. Keros, V. Nanda, and K. Subr, in 36th AAAI Conference on Artificial Intelligence (AAAI, 2022).
  85. N. Guo, K. Mitarai, and K. Fujii, Nonlinear transformation of complex amplitudes via quantum singular value transformation, Phys. Rev. Res. 6, 043227 (2024).
  86. A. G. Rathew and P. Rebentrost, Non-linear transformations of quantum amplitudes: Exponential improvement, generalization, and applications, arXiv:2309.09839.
  87. D. W. Berry, A. Childs, and R. Kothari, in Proceedings – Annual IEEE Symposium on Foundations of Computer Science, FOCS (IEEE Computer Society, 2015), Vol. 2015-December, pp. 792–809.
  88. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Simulating Hamiltonian dynamics with a truncated Taylor series, Phys. Rev. Lett. 114, 090502 (2015).
  89. J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, Grand unification of quantum algorithms, PRX Quantum 2, 040203 (2021).
  90. G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
  91. G. H. Low and I. L. Chuang, Optimal Hamiltonian simulation by quantum signal processing, Phys. Rev. Lett. 118, 010501 (2017).
  92. S. A. Metwalli, F. Le Gall, and R. Van Meter, Finding small and large k-clique instances on a quantum computer, IEEE Trans. Quantum Eng. 1, 1 (2021).
  93. I. Y. Akhalwaya, Y.-H. He, L. Horesh, W. Jejjala, V. Kirby, K. Naidoo, and S. Ubaru, Representation of the fermionic boundary operator, Phys. Rev. A 106, 022407 (2022).
  94. S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, A new quantum ripple-carry addition circuit, arXiv:quant-ph/0410184.
  95. D. Horak and J. Jost, Spectra of combinatorial Laplace operators on simplicial complexes, Adv. Math. 244, 303 (2013).

Outline

Information

Phys. Rev. Applied 23, 054054– Published 21 May, 2025
  • Received 4 November 2024
  • Revised 14 February 2025
  • Accepted 17 March 2025
Crossmark - Check for updates button

© 2025 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation