Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups
Summarize this article with:
AbstractThis work investigates whether quantum walks on simplicial complexes exhibit quantum advantages. We introduce a novel quantum walk that encodes the combinatorial Laplacian, a key object reflecting the topology of the simplicial complex. We construct a unitary encoding projecting onto the kernel of the Laplacian, representing the harmonic cycles in the complex's homology. Our efficient construction of quantum walk unitaries for clique complexes paves the way for exploring higher-order interactions within topological structures. Our construction requires $O(n^3\log(1/\epsilon)/\lambda_k)$ gates, where $n$ is the number of vertices, $\lambda_k$ is the smallest non-zero eigenvalue of the Laplacian, and $\epsilon$ is the projection error. Our results indicate apparent superpolynomial quantum speedup with quantum walks, without quantum oracles, provided the spectral gap of the Laplacian is inverse-polynomially bounded and efficient simplex sampling is available. Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This is our major technical contribution. We also extend the framework by constructing variant quantum walks that enable us to: (1) estimate normalized persistent Betti numbers throughout a deformation process, (2) verify a specific QMA$_1$-hard problem related to clique complex homology, showcasing potential applications in computational complexity theory, and (3) solve the high-dimensional discrete Dirichlet problem (HDDP), generalizing the classical discrete Dirichlet problem on graphs to simplicial complexes, with an apparent superpolynomial speedup over the best known classical algorithm.Popular summaryData in the real world often has a hidden shape like clusters, loops, and voids.Topological data analysis (TDA) detects these features, but for large data sets the computation quickly becomes intractable. In this work, we design a new quantum algorithm for TDA based on quantum walks on simplicial complexes, higher-dimensional generalizations of graphs. Our key idea is to let a quantum walker move over simplices with both positive and negative orientations and utilize quantum interference between them to encodes the combinatorial Laplacian, whose zero-energy states correspond to the topology of the data. This quantum walk runs without access to a costly quantum oracle, and it estimates topological invariants of clique complexes with an apparent superpolynomial speedup over the best known classical algorithms.► BibTeX data@article{Hayakawa2026quantumwalks, doi = {10.22331/q-2026-06-15-2138}, url = {https://doi.org/10.22331/q-2026-06-15-2138}, title = {Quantum {W}alks on {S}implicial {C}omplexes and {H}armonic {H}omology: {A}pplication to {T}opological {D}ata {A}nalysis with {S}uperpolynomial {S}peedups}, author = {Hayakawa, Ryu and Chen, Kuo-Chin and Hsieh, Min-Hsiu}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2138}, month = jun, year = {2026} }► References [1] Frank Acasiete, Flavia P Agostini, J Khatibi Moqadam, and Renato Portugal. Implementation of quantum walks on ibm quantum computers.
Quantum Information Processing, 19:1–20, 2020. doi:10.1007/s11128-020-02938-5. https://doi.org/10.1007/s11128-020-02938-5 [2] Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis. Quadratic speedup for finding marked vertices by quantum walks. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 412–424, 2020. doi:10.1145/3357713.3384252. https://doi.org/10.1145/3357713.3384252 [3] Simon Apers, Sander Gribling, Sayantan Sen, and Dániel Szabó. A (simple) classical algorithm for estimating betti numbers. Quantum, 7:1202, 2023. doi:10.22331/q-2023-12-06-1202. https://doi.org/10.22331/q-2023-12-06-1202 [4] Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM (JACM), 51(4):595–605, 2004. doi:10.1145/1008731.1008735. https://doi.org/10.1145/1008731.1008735 [5] Simon Apers and Alain Sarlette. Quantum fast-forwarding: Markov chains and graph property testing. Quantum Information & Computation, 19(3-4):181–213, 2019. doi:10.26421/qic19.3-4-1. https://doi.org/10.26421/qic19.3-4-1 [6] Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri. Networks beyond pairwise interactions: Structure and dynamics. Physics Reports, 874:1–92, 2020. doi:10.1016/j.physrep.2020.05.004. https://doi.org/10.1016/j.physrep.2020.05.004 [7] Christian Bick, Elizabeth Gross, Heather A Harrington, and Michael T Schaub. What are higher-order networks? SIAM Review, 65(3):686–731, 2023. doi:10.1137/21m1414024. https://doi.org/10.1137/21m1414024 [8] Shankar Balasubramanian, Tongyang Li, and Aram W Harrow. Exponential speedups for quantum walks in random hierarchical graphs. Communications in Mathematical Physics, 406(9):209, 2025. doi:10.1007/s00220-025-05370-x. https://doi.org/10.1007/s00220-025-05370-x [9] Harry Buhrman and Robert Špalek. Quantum verification of matrix products. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 880–889, 2006. doi:10.1145/1109557.1109654. https://doi.org/10.1145/1109557.1109654 [10] Dominic W Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, and Ryan Babbush. Analyzing prospects for quantum advantage in topological data analysis. PRX Quantum, 5(1):010319, 2024. doi:10.1103/prxquantum.5.010319. https://doi.org/10.1103/prxquantum.5.010319 [11] Chris Cade and P Marcos Crichigno. Complexity of supersymmetric systems and the cohomology problem. Quantum, 8:1325, 2024. doi:10.22331/q-2024-04-30-1325. https://doi.org/10.22331/q-2024-04-30-1325 [12] Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 59–68, 2003. doi:10.1145/780542.780552. https://doi.org/10.1145/780542.780552 [13] Marcos Crichigno and Tamara Kohler. Clique homology is qma 1-hard. Nature Communications, 15(1):9846, 2024. doi:10.1038/s41467-024-54118-z. https://doi.org/10.1038/s41467-024-54118-z [14] Chen-Fu Chiang, Daniel Nagaj, and Pawel Wocjan. Efficient circuits for quantum walks. Quantum Information & Computation, 10(5):420–434, 2010. doi:10.26421/qic10.5-6-4. https://doi.org/10.26421/qic10.5-6-4 [15] Siamak Dadras, Alexander Gresch, Caspar Groiseau, Sandro Wimberger, and Gil S Summy. Experimental realization of a momentum-space quantum walk. Physical Review A, 99(4):043617, 2019. doi:10.1103/physreva.99.043617. https://doi.org/10.1103/physreva.99.043617 [16] Peter G Doyle and J Laurie Snell. Random walks and electric networks, volume 22.
American Mathematical Soc., 1984. doi:10.5948/UPO9781614440222. https://doi.org/10.5948/UPO9781614440222 [17] Tamal Krishna Dey and Yusu Wang. Computational topology for data analysis.
Cambridge University Press, 2022. doi:10.1017/9781009099950. https://doi.org/10.1017/9781009099950 [18] Herbert Edelsbrunner and John L Harer. Computational topology: an introduction.
American Mathematical Society, 2022. doi:10.1090/mbk/069. https://doi.org/10.1090/mbk/069 [19] Marzieh Eidi and Sayan Mukherjee. Irreducibility of markov chains on simplicial complexes, the spectrum of the discrete hodge laplacian and homology. arXiv preprint arXiv:2310.07912, 2023. doi:10.48550/arXiv.2310.07912. https://doi.org/10.48550/arXiv.2310.07912 arXiv:2310.07912 [20] Joseph F Fitzsimons, Michal Hajdušek, and Tomoyuki Morimae. Post hoc verification of quantum computation. Physical review letters, 120(4):040501, 2018. doi:10.1103/physrevlett.120.040501. https://doi.org/10.1103/physrevlett.120.040501 [21] Casper Gyurik, Chris Cade, and Vedran Dunjko. Towards quantum advantage via topological data analysis. Quantum, 6:855, 2022. doi:10.22331/q-2022-11-10-855. https://doi.org/10.22331/q-2022-11-10-855 [22] Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi. Verification of quantum computation: An overview of existing approaches. Theory of computing systems, 63:715–808, 2019. doi:10.1007/s00224-018-9872-3. https://doi.org/10.1007/s00224-018-9872-3 [23] Casper Gyurik, Alexander Schmidhuber, Robbie King, Vedran Dunjko, and Ryu Hayakawa. Quantum computing and persistence in topological data analysis. arXiv preprint arXiv:2410.21258, 2024. doi:10.48550/arXiv.2410.21258. https://doi.org/10.48550/arXiv.2410.21258 arXiv:2410.21258 [24] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. doi:10.1145/3313276.3316366. https://doi.org/10.1145/3313276.3316366 [25] Ryu Hayakawa. Quantum algorithm for persistent betti numbers and topological data analysis. Quantum, 6:873, 2022. doi:10.22331/q-2022-12-07-873. https://doi.org/10.22331/q-2022-12-07-873 [26] Ryu Hayakawa, Casper Gyurik, Mahtab Yaghubi Rad, and Vedran Dunjko. Computational complexity of the homology problem with orientable filtration: Ma-completeness. arXiv preprint arXiv:2510.07014, 2025. doi:10.48550/arXiv.2510.07014. https://doi.org/10.48550/arXiv.2510.07014 arXiv:2510.07014 [27] Peter Høyer and Zhan Yu. Analysis of lackadaisical quantum walks. Quantum Information and Computation, 20(13&14):1138–1153, 2020. doi:10.26421/qic20.13-14-4. https://doi.org/10.26421/qic20.13-14-4 [28] Stacey Jeffery and Sebastian Zur. Multidimensional quantum walks. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1125–1130, 2023. doi:10.1145/3564246.3585158. https://doi.org/10.1145/3564246.3585158 [29] Robbie King and Tamara Kohler. Gapped clique homology on weighted graphs is ${\text{qma}\_1}$-hard and contained in qma. SIAM Journal on Computing, 0(0):FOCS24–137–FOCS24–235, 2024. doi:10.1137/24M1710243. https://doi.org/10.1137/24M1710243 [30] Tali Kaufman and Izhar Oppenheim. High order random walks: Beyond spectral gap. Combinatorica, 40:245–281, 2020. doi:10.1007/s00493-019-3847-0. https://doi.org/10.1007/s00493-019-3847-0 [31] Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. Quantum algorithms for topological and geometric analysis of data. Nature communications, 7(1):10138, 2016. doi:10.1038/ncomms10138. https://doi.org/10.1038/ncomms10138 [32] Caesnan MG Leditto, Angus Southwell, Behnam Tonekaboni, Muhammad Usman, and Kavan Modi. Quantum hodgerank: Topology-based rank aggregation on quantum computers.
Physical Review Applied, 23(6):L061005, 2025. doi:10.1103/m6nc-ypl7. https://doi.org/10.1103/m6nc-ypl7 [33] Caesnan MG Leditto, Angus Southwell, Behnam Tonekaboni, Gregory AL White, Muhammad Usman, and Kavan Modi. Topological signal processing on quantum computers for higher-order network analysis.
Physical Review Applied, 23(5):054054, 2025. doi:10.1103/physrevapplied.23.054054. https://doi.org/10.1103/physrevapplied.23.054054 [34] Xin Luo and Tatsuya Tate. Up and down grover walks on simplicial complexes. Linear Algebra and its Applications, 545:174–206, 2018. doi:10.1016/j.laa.2018.01.036. https://doi.org/10.1016/j.laa.2018.01.036 [35] Sam McArdle, András Gilyén, and Mario Berta. A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits. Quantum 10, 2058, 2026. doi:10.22331/q-2026-04-10-2058. https://doi.org/10.22331/q-2026-04-10-2058 [36] Nikola Milosavljević, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multiplication time. In Proceedings of the twenty-seventh Annual Symposium on Computational Geometry, pages 216–225, 2011. doi:10.1145/1998196.1998229. https://doi.org/10.1145/1998196.1998229 [37] Frédéric Magniez and Ashwin Nayak. Quantum complexity of testing group commutativity. Algorithmica, 48(3):221–232, 2007. doi:10.1007/s00453-007-0057-8. https://doi.org/10.1007/s00453-007-0057-8 [38] Konstantin Mischaikow and Vidit Nanda. Morse theory for filtrations and efficient computation of persistent homology. Discrete & Computational Geometry, 50:330–353, 2013. doi:10.1007/s00454-013-9529-6. https://doi.org/10.1007/s00454-013-9529-6 [39] Kaname Matsue, Osamu Ogurisu, and Etsuo Segawa. Quantum walks on simplicial complexes.
Quantum Information Processing, 15:1865–1896, 2016. doi:10.1007/s11128-016-1247-6. https://doi.org/10.1007/s11128-016-1247-6 [40] Kaname Matsue, Osamu Ogurisu, and Etsuo Segawa. Quantum search on simplicial complexes. Quantum Studies: Mathematics and Foundations, 5:551–577, 2018. doi:10.1007/s40509-017-0144-8. https://doi.org/10.1007/s40509-017-0144-8 [41] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algorithms. PRX Quantum, 2(4):040203, 2021. doi:10.1103/prxquantum.2.040203. https://doi.org/10.1103/prxquantum.2.040203 [42] Sayan Mukherjee and John Steenbergen. Random walks on simplicial complexes and harmonics. Random structures & algorithms, 49(2):379–405, 2016. doi:10.1002/rsa.20645. https://doi.org/10.1002/rsa.20645 [43] Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Persistent laplacians: Properties, algorithms and implications. SIAM Journal on Mathematics of Data Science, 4(2):858–884, 2022. doi:10.1137/21m1435471. https://doi.org/10.1137/21m1435471 [44] Ori Parzanchevski and Ron Rosenthal. Simplicial complexes: spectrum, homology and random walks. Random Structures & Algorithms, 50(2):225–261, 2017. doi:10.1002/rsa.20657. https://doi.org/10.1002/rsa.20657 [45] Xiaogang Qiang, Shixin Ma, and Haijing Song. Quantum walk computing: Theory, implementation, and application. Intelligent Computing, 3:0097, 2024. doi:10.34133/icomputing.0097. https://doi.org/10.34133/icomputing.0097 [46] Patrick Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5:566, 2021. doi:10.22331/q-2021-10-19-566. https://doi.org/10.22331/q-2021-10-19-566 [47] Ron Rosenthal. Simplicial branching random walks and their applications. arXiv preprint arXiv:1412.5406, 2014. doi:10.48550/arXiv.1412.5406. https://doi.org/10.48550/arXiv.1412.5406 arXiv:1412.5406 [48] Rolando D Somma, Sergio Boixo, Howard Barnum, and Emanuel Knill. Quantum simulations of classical annealing processes. Physical review letters, 101(13):130504, 2008. doi:10.1103/physrevlett.101.130504. https://doi.org/10.1103/physrevlett.101.130504 [49] Michael T Schaub, Austin R Benson, Paul Horn, Gabor Lippner, and Ali Jadbabaie. Random walks on simplicial complexes and the normalized hodge 1-laplacian. SIAM Review, 62(2):353–391, 2020. doi:10.1137/18m1201019. https://doi.org/10.1137/18m1201019 [50] Alexander Schmidhuber and Seth Lloyd. Complexity-theoretic limitations on quantum algorithms for topological data analysis. PRX Quantum, 4(4):040349, 2023. doi:10.1103/prxquantum.4.040349. https://doi.org/10.1103/prxquantum.4.040349 [51] Mario Szegedy. Quantum speed-up of markov chain based algorithms. In 45th Annual IEEE symposium on foundations of computer science, pages 32–41. IEEE, 2004. doi:10.1109/focs.2004.53. https://doi.org/10.1109/focs.2004.53 [52] Michael T Schaub, Yu Zhu, Jean-Baptiste Seby, T Mitchell Roddenberry, and Santiago Segarra. Signal processing on higher-order networks: Livin’on the edge... and beyond. Signal Processing, 187:108149, 2021. doi:10.1016/j.sigpro.2021.108149. https://doi.org/10.1016/j.sigpro.2021.108149 [53] Hao Tang, Xiao-Feng Lin, Zhen Feng, Jing-Yuan Chen, Jun Gao, Ke Sun, Chao-Yue Wang, Peng-Cheng Lai, Xiao-Yun Xu, Yao Wang, et al. Experimental two-dimensional quantum walk on a photonic chip. Science advances, 4(5):eaat3174, 2018. doi:10.1126/sciadv.aat3174. https://doi.org/10.1126/sciadv.aat3174 [54] Rui Wang, Duc Duy Nguyen, and Guo-Wei Wei. Persistent spectral graph. International journal for numerical methods in biomedical engineering, 36(9):e3376, 2020. doi:10.1002/cnm.3376. https://doi.org/10.1002/cnm.3376 [55] Thomas G Wong. Grover search with lackadaisical quantum walks. Journal of Physics A: Mathematical and Theoretical, 48(43):435304, 2015. doi:10.1088/1751-8113/48/43/435304. https://doi.org/10.1088/1751-8113/48/43/435304 [56] Xiaoqi Wei and Guo-Wei Wei. Persistent topological laplacians—a survey. Mathematics, 13(2):208, 2025. doi:10.3390/math13020208. https://doi.org/10.3390/math13020208Cited by[1] Ryu Hayakawa, Casper Gyurik, Mahtab Yaghubi Rad, and Vedran Dunjko, "Computational complexity of the homology problem with orientable filtration: MA-completeness", arXiv:2510.07014, (2025). [2] Alexander Schmidhuber, Michele Reilly, Paolo Zanardi, Seth Lloyd, and Aaron Lauda, "A quantum algorithm for Khovanov homology", arXiv:2501.12378, (2025). [3] Nhat A. Nghiem, "New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes", arXiv:2506.01432, (2025). [4] Nhat A. Nghiem, "Quantum topological data analysis algorithm for dynamical systems", arXiv:2509.22372, (2025). [5] Caesnan M. G. Leditto, Angus Southwell, Muhammad Usman, and Kavan Modi, "Efficient Quantum Algorithms for Higher-Order Coupled Oscillators", arXiv:2604.20108, (2026). The above citations are from SAO/NASA ADS (last updated successfully 2026-06-15 13:48:16). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-06-15 13:48:08: Could not fetch cited-by data for 10.22331/q-2026-06-15-2138 from Crossref. This is normal if the DOI was registered recently.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. AbstractThis work investigates whether quantum walks on simplicial complexes exhibit quantum advantages. We introduce a novel quantum walk that encodes the combinatorial Laplacian, a key object reflecting the topology of the simplicial complex. We construct a unitary encoding projecting onto the kernel of the Laplacian, representing the harmonic cycles in the complex's homology. Our efficient construction of quantum walk unitaries for clique complexes paves the way for exploring higher-order interactions within topological structures. Our construction requires $O(n^3\log(1/\epsilon)/\lambda_k)$ gates, where $n$ is the number of vertices, $\lambda_k$ is the smallest non-zero eigenvalue of the Laplacian, and $\epsilon$ is the projection error. Our results indicate apparent superpolynomial quantum speedup with quantum walks, without quantum oracles, provided the spectral gap of the Laplacian is inverse-polynomially bounded and efficient simplex sampling is available. Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This is our major technical contribution. We also extend the framework by constructing variant quantum walks that enable us to: (1) estimate normalized persistent Betti numbers throughout a deformation process, (2) verify a specific QMA$_1$-hard problem related to clique complex homology, showcasing potential applications in computational complexity theory, and (3) solve the high-dimensional discrete Dirichlet problem (HDDP), generalizing the classical discrete Dirichlet problem on graphs to simplicial complexes, with an apparent superpolynomial speedup over the best known classical algorithm.Popular summaryData in the real world often has a hidden shape like clusters, loops, and voids.Topological data analysis (TDA) detects these features, but for large data sets the computation quickly becomes intractable. In this work, we design a new quantum algorithm for TDA based on quantum walks on simplicial complexes, higher-dimensional generalizations of graphs. Our key idea is to let a quantum walker move over simplices with both positive and negative orientations and utilize quantum interference between them to encodes the combinatorial Laplacian, whose zero-energy states correspond to the topology of the data. This quantum walk runs without access to a costly quantum oracle, and it estimates topological invariants of clique complexes with an apparent superpolynomial speedup over the best known classical algorithms.► BibTeX data@article{Hayakawa2026quantumwalks, doi = {10.22331/q-2026-06-15-2138}, url = {https://doi.org/10.22331/q-2026-06-15-2138}, title = {Quantum {W}alks on {S}implicial {C}omplexes and {H}armonic {H}omology: {A}pplication to {T}opological {D}ata {A}nalysis with {S}uperpolynomial {S}peedups}, author = {Hayakawa, Ryu and Chen, Kuo-Chin and Hsieh, Min-Hsiu}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2138}, month = jun, year = {2026} }► References [1] Frank Acasiete, Flavia P Agostini, J Khatibi Moqadam, and Renato Portugal. Implementation of quantum walks on ibm quantum computers.
Quantum Information Processing, 19:1–20, 2020. doi:10.1007/s11128-020-02938-5. https://doi.org/10.1007/s11128-020-02938-5 [2] Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis. Quadratic speedup for finding marked vertices by quantum walks. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 412–424, 2020. doi:10.1145/3357713.3384252. https://doi.org/10.1145/3357713.3384252 [3] Simon Apers, Sander Gribling, Sayantan Sen, and Dániel Szabó. A (simple) classical algorithm for estimating betti numbers. Quantum, 7:1202, 2023. doi:10.22331/q-2023-12-06-1202. https://doi.org/10.22331/q-2023-12-06-1202 [4] Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM (JACM), 51(4):595–605, 2004. doi:10.1145/1008731.1008735. https://doi.org/10.1145/1008731.1008735 [5] Simon Apers and Alain Sarlette. Quantum fast-forwarding: Markov chains and graph property testing. Quantum Information & Computation, 19(3-4):181–213, 2019. doi:10.26421/qic19.3-4-1. https://doi.org/10.26421/qic19.3-4-1 [6] Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri. Networks beyond pairwise interactions: Structure and dynamics. Physics Reports, 874:1–92, 2020. doi:10.1016/j.physrep.2020.05.004. https://doi.org/10.1016/j.physrep.2020.05.004 [7] Christian Bick, Elizabeth Gross, Heather A Harrington, and Michael T Schaub. What are higher-order networks? SIAM Review, 65(3):686–731, 2023. doi:10.1137/21m1414024. https://doi.org/10.1137/21m1414024 [8] Shankar Balasubramanian, Tongyang Li, and Aram W Harrow. Exponential speedups for quantum walks in random hierarchical graphs. Communications in Mathematical Physics, 406(9):209, 2025. doi:10.1007/s00220-025-05370-x. https://doi.org/10.1007/s00220-025-05370-x [9] Harry Buhrman and Robert Špalek. Quantum verification of matrix products. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 880–889, 2006. doi:10.1145/1109557.1109654. https://doi.org/10.1145/1109557.1109654 [10] Dominic W Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, and Ryan Babbush. Analyzing prospects for quantum advantage in topological data analysis. PRX Quantum, 5(1):010319, 2024. doi:10.1103/prxquantum.5.010319. https://doi.org/10.1103/prxquantum.5.010319 [11] Chris Cade and P Marcos Crichigno. Complexity of supersymmetric systems and the cohomology problem. Quantum, 8:1325, 2024. doi:10.22331/q-2024-04-30-1325. https://doi.org/10.22331/q-2024-04-30-1325 [12] Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 59–68, 2003. doi:10.1145/780542.780552. https://doi.org/10.1145/780542.780552 [13] Marcos Crichigno and Tamara Kohler. Clique homology is qma 1-hard. Nature Communications, 15(1):9846, 2024. doi:10.1038/s41467-024-54118-z. https://doi.org/10.1038/s41467-024-54118-z [14] Chen-Fu Chiang, Daniel Nagaj, and Pawel Wocjan. Efficient circuits for quantum walks. Quantum Information & Computation, 10(5):420–434, 2010. doi:10.26421/qic10.5-6-4. https://doi.org/10.26421/qic10.5-6-4 [15] Siamak Dadras, Alexander Gresch, Caspar Groiseau, Sandro Wimberger, and Gil S Summy. Experimental realization of a momentum-space quantum walk. Physical Review A, 99(4):043617, 2019. doi:10.1103/physreva.99.043617. https://doi.org/10.1103/physreva.99.043617 [16] Peter G Doyle and J Laurie Snell. Random walks and electric networks, volume 22.
American Mathematical Soc., 1984. doi:10.5948/UPO9781614440222. https://doi.org/10.5948/UPO9781614440222 [17] Tamal Krishna Dey and Yusu Wang. Computational topology for data analysis.
Cambridge University Press, 2022. doi:10.1017/9781009099950. https://doi.org/10.1017/9781009099950 [18] Herbert Edelsbrunner and John L Harer. Computational topology: an introduction.
American Mathematical Society, 2022. doi:10.1090/mbk/069. https://doi.org/10.1090/mbk/069 [19] Marzieh Eidi and Sayan Mukherjee. Irreducibility of markov chains on simplicial complexes, the spectrum of the discrete hodge laplacian and homology. arXiv preprint arXiv:2310.07912, 2023. doi:10.48550/arXiv.2310.07912. https://doi.org/10.48550/arXiv.2310.07912 arXiv:2310.07912 [20] Joseph F Fitzsimons, Michal Hajdušek, and Tomoyuki Morimae. Post hoc verification of quantum computation. Physical review letters, 120(4):040501, 2018. doi:10.1103/physrevlett.120.040501. https://doi.org/10.1103/physrevlett.120.040501 [21] Casper Gyurik, Chris Cade, and Vedran Dunjko. Towards quantum advantage via topological data analysis. Quantum, 6:855, 2022. doi:10.22331/q-2022-11-10-855. https://doi.org/10.22331/q-2022-11-10-855 [22] Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi. Verification of quantum computation: An overview of existing approaches. Theory of computing systems, 63:715–808, 2019. doi:10.1007/s00224-018-9872-3. https://doi.org/10.1007/s00224-018-9872-3 [23] Casper Gyurik, Alexander Schmidhuber, Robbie King, Vedran Dunjko, and Ryu Hayakawa. Quantum computing and persistence in topological data analysis. arXiv preprint arXiv:2410.21258, 2024. doi:10.48550/arXiv.2410.21258. https://doi.org/10.48550/arXiv.2410.21258 arXiv:2410.21258 [24] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. doi:10.1145/3313276.3316366. https://doi.org/10.1145/3313276.3316366 [25] Ryu Hayakawa. Quantum algorithm for persistent betti numbers and topological data analysis. Quantum, 6:873, 2022. doi:10.22331/q-2022-12-07-873. https://doi.org/10.22331/q-2022-12-07-873 [26] Ryu Hayakawa, Casper Gyurik, Mahtab Yaghubi Rad, and Vedran Dunjko. Computational complexity of the homology problem with orientable filtration: Ma-completeness. arXiv preprint arXiv:2510.07014, 2025. doi:10.48550/arXiv.2510.07014. https://doi.org/10.48550/arXiv.2510.07014 arXiv:2510.07014 [27] Peter Høyer and Zhan Yu. Analysis of lackadaisical quantum walks. Quantum Information and Computation, 20(13&14):1138–1153, 2020. doi:10.26421/qic20.13-14-4. https://doi.org/10.26421/qic20.13-14-4 [28] Stacey Jeffery and Sebastian Zur. Multidimensional quantum walks. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1125–1130, 2023. doi:10.1145/3564246.3585158. https://doi.org/10.1145/3564246.3585158 [29] Robbie King and Tamara Kohler. Gapped clique homology on weighted graphs is ${\text{qma}\_1}$-hard and contained in qma. SIAM Journal on Computing, 0(0):FOCS24–137–FOCS24–235, 2024. doi:10.1137/24M1710243. https://doi.org/10.1137/24M1710243 [30] Tali Kaufman and Izhar Oppenheim. High order random walks: Beyond spectral gap. Combinatorica, 40:245–281, 2020. doi:10.1007/s00493-019-3847-0. https://doi.org/10.1007/s00493-019-3847-0 [31] Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. Quantum algorithms for topological and geometric analysis of data. Nature communications, 7(1):10138, 2016. doi:10.1038/ncomms10138. https://doi.org/10.1038/ncomms10138 [32] Caesnan MG Leditto, Angus Southwell, Behnam Tonekaboni, Muhammad Usman, and Kavan Modi. Quantum hodgerank: Topology-based rank aggregation on quantum computers.
Physical Review Applied, 23(6):L061005, 2025. doi:10.1103/m6nc-ypl7. https://doi.org/10.1103/m6nc-ypl7 [33] Caesnan MG Leditto, Angus Southwell, Behnam Tonekaboni, Gregory AL White, Muhammad Usman, and Kavan Modi. Topological signal processing on quantum computers for higher-order network analysis.
Physical Review Applied, 23(5):054054, 2025. doi:10.1103/physrevapplied.23.054054. https://doi.org/10.1103/physrevapplied.23.054054 [34] Xin Luo and Tatsuya Tate. Up and down grover walks on simplicial complexes. Linear Algebra and its Applications, 545:174–206, 2018. doi:10.1016/j.laa.2018.01.036. https://doi.org/10.1016/j.laa.2018.01.036 [35] Sam McArdle, András Gilyén, and Mario Berta. A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits. Quantum 10, 2058, 2026. doi:10.22331/q-2026-04-10-2058. https://doi.org/10.22331/q-2026-04-10-2058 [36] Nikola Milosavljević, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multiplication time. In Proceedings of the twenty-seventh Annual Symposium on Computational Geometry, pages 216–225, 2011. doi:10.1145/1998196.1998229. https://doi.org/10.1145/1998196.1998229 [37] Frédéric Magniez and Ashwin Nayak. Quantum complexity of testing group commutativity. Algorithmica, 48(3):221–232, 2007. doi:10.1007/s00453-007-0057-8. https://doi.org/10.1007/s00453-007-0057-8 [38] Konstantin Mischaikow and Vidit Nanda. Morse theory for filtrations and efficient computation of persistent homology. Discrete & Computational Geometry, 50:330–353, 2013. doi:10.1007/s00454-013-9529-6. https://doi.org/10.1007/s00454-013-9529-6 [39] Kaname Matsue, Osamu Ogurisu, and Etsuo Segawa. Quantum walks on simplicial complexes.
Quantum Information Processing, 15:1865–1896, 2016. doi:10.1007/s11128-016-1247-6. https://doi.org/10.1007/s11128-016-1247-6 [40] Kaname Matsue, Osamu Ogurisu, and Etsuo Segawa. Quantum search on simplicial complexes. Quantum Studies: Mathematics and Foundations, 5:551–577, 2018. doi:10.1007/s40509-017-0144-8. https://doi.org/10.1007/s40509-017-0144-8 [41] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algorithms. PRX Quantum, 2(4):040203, 2021. doi:10.1103/prxquantum.2.040203. https://doi.org/10.1103/prxquantum.2.040203 [42] Sayan Mukherjee and John Steenbergen. Random walks on simplicial complexes and harmonics. Random structures & algorithms, 49(2):379–405, 2016. doi:10.1002/rsa.20645. https://doi.org/10.1002/rsa.20645 [43] Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Persistent laplacians: Properties, algorithms and implications. SIAM Journal on Mathematics of Data Science, 4(2):858–884, 2022. doi:10.1137/21m1435471. https://doi.org/10.1137/21m1435471 [44] Ori Parzanchevski and Ron Rosenthal. Simplicial complexes: spectrum, homology and random walks. Random Structures & Algorithms, 50(2):225–261, 2017. doi:10.1002/rsa.20657. https://doi.org/10.1002/rsa.20657 [45] Xiaogang Qiang, Shixin Ma, and Haijing Song. Quantum walk computing: Theory, implementation, and application. Intelligent Computing, 3:0097, 2024. doi:10.34133/icomputing.0097. https://doi.org/10.34133/icomputing.0097 [46] Patrick Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5:566, 2021. doi:10.22331/q-2021-10-19-566. https://doi.org/10.22331/q-2021-10-19-566 [47] Ron Rosenthal. Simplicial branching random walks and their applications. arXiv preprint arXiv:1412.5406, 2014. doi:10.48550/arXiv.1412.5406. https://doi.org/10.48550/arXiv.1412.5406 arXiv:1412.5406 [48] Rolando D Somma, Sergio Boixo, Howard Barnum, and Emanuel Knill. Quantum simulations of classical annealing processes. Physical review letters, 101(13):130504, 2008. doi:10.1103/physrevlett.101.130504. https://doi.org/10.1103/physrevlett.101.130504 [49] Michael T Schaub, Austin R Benson, Paul Horn, Gabor Lippner, and Ali Jadbabaie. Random walks on simplicial complexes and the normalized hodge 1-laplacian. SIAM Review, 62(2):353–391, 2020. doi:10.1137/18m1201019. https://doi.org/10.1137/18m1201019 [50] Alexander Schmidhuber and Seth Lloyd. Complexity-theoretic limitations on quantum algorithms for topological data analysis. PRX Quantum, 4(4):040349, 2023. doi:10.1103/prxquantum.4.040349. https://doi.org/10.1103/prxquantum.4.040349 [51] Mario Szegedy. Quantum speed-up of markov chain based algorithms. In 45th Annual IEEE symposium on foundations of computer science, pages 32–41. IEEE, 2004. doi:10.1109/focs.2004.53. https://doi.org/10.1109/focs.2004.53 [52] Michael T Schaub, Yu Zhu, Jean-Baptiste Seby, T Mitchell Roddenberry, and Santiago Segarra. Signal processing on higher-order networks: Livin’on the edge... and beyond. Signal Processing, 187:108149, 2021. doi:10.1016/j.sigpro.2021.108149. https://doi.org/10.1016/j.sigpro.2021.108149 [53] Hao Tang, Xiao-Feng Lin, Zhen Feng, Jing-Yuan Chen, Jun Gao, Ke Sun, Chao-Yue Wang, Peng-Cheng Lai, Xiao-Yun Xu, Yao Wang, et al. Experimental two-dimensional quantum walk on a photonic chip. Science advances, 4(5):eaat3174, 2018. doi:10.1126/sciadv.aat3174. https://doi.org/10.1126/sciadv.aat3174 [54] Rui Wang, Duc Duy Nguyen, and Guo-Wei Wei. Persistent spectral graph. International journal for numerical methods in biomedical engineering, 36(9):e3376, 2020. doi:10.1002/cnm.3376. https://doi.org/10.1002/cnm.3376 [55] Thomas G Wong. Grover search with lackadaisical quantum walks. Journal of Physics A: Mathematical and Theoretical, 48(43):435304, 2015. doi:10.1088/1751-8113/48/43/435304. https://doi.org/10.1088/1751-8113/48/43/435304 [56] Xiaoqi Wei and Guo-Wei Wei. Persistent topological laplacians—a survey. Mathematics, 13(2):208, 2025. doi:10.3390/math13020208. https://doi.org/10.3390/math13020208Cited by[1] Ryu Hayakawa, Casper Gyurik, Mahtab Yaghubi Rad, and Vedran Dunjko, "Computational complexity of the homology problem with orientable filtration: MA-completeness", arXiv:2510.07014, (2025). [2] Alexander Schmidhuber, Michele Reilly, Paolo Zanardi, Seth Lloyd, and Aaron Lauda, "A quantum algorithm for Khovanov homology", arXiv:2501.12378, (2025). [3] Nhat A. Nghiem, "New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes", arXiv:2506.01432, (2025). [4] Nhat A. Nghiem, "Quantum topological data analysis algorithm for dynamical systems", arXiv:2509.22372, (2025). [5] Caesnan M. G. Leditto, Angus Southwell, Muhammad Usman, and Kavan Modi, "Efficient Quantum Algorithms for Higher-Order Coupled Oscillators", arXiv:2604.20108, (2026). The above citations are from SAO/NASA ADS (last updated successfully 2026-06-15 13:48:16). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-06-15 13:48:08: Could not fetch cited-by data for 10.22331/q-2026-06-15-2138 from Crossref. This is normal if the DOI was registered recently.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.