Back to News
quantum-computing

Computational complexity of Berry phase estimation in topological phases of matter

Ryu Hayakawa, Kazuki Sakamoto, and Chusei Kiumi
Loading...
17 min read
0 likes
⚡ Quantum Brief
AbstractThe Berry phase is a fundamental quantity in the classification of topological phases of matter. In this paper, we present a new quantum algorithm and several complexity-theoretical results for the Berry phase estimation (BPE) problems. Our new quantum algorithm achieves BPE in a more general setting than previously known quantum algorithms, with a theoretical guarantee. For the complexity-theoretic results, we consider two main cases. First, we prove $\mathsf{BQP}$-completeness when we are given a guiding state that has a large overlap with the ground state. This result establishes an exponential quantum speedup for estimating the Berry phase.
AI Audio Summary
0:00 / 0:00
Click to play
figure-23.webp
Quantum News · Media Library

AbstractThe Berry phase is a fundamental quantity in the classification of topological phases of matter. In this paper, we present a new quantum algorithm and several complexity-theoretical results for the Berry phase estimation (BPE) problems. Our new quantum algorithm achieves BPE in a more general setting than previously known quantum algorithms, with a theoretical guarantee. For the complexity-theoretic results, we consider two main cases. First, we prove $\mathsf{BQP}$-completeness when we are given a guiding state that has a large overlap with the ground state. This result establishes an exponential quantum speedup for estimating the Berry phase. Second, we prove $\mathsf{UQMA} \cap \mathsf{co}$-$\mathsf{UQMA}$-completeness when we have an $\textit{a priori}$ bound for the ground-state energy. Here, $\mathsf{UQMA}$ is the unique witness version of $\mathsf{QMA}$, and $\mathsf{UQMA} \cap \mathsf{co}$-$\mathsf{UQMA}$ precisely captures the complexity of BPE without the known guiding state. Remarkably, this problem is, to our knowledge, the first natural problem complete for $\mathsf{UQMA} \cap \mathsf{co}$-$\mathsf{UQMA}$. These results advance the role of quantum computing in the study of topological phases of matter and provide a pathway for clarifying the connection between topological phases of matter and computational complexity.Featured image: A Hamiltonian loop encoding a quantum computation imprints a geometric phase on the quantum state.Popular summaryThe Berry phase is a geometric property of quantum states that plays a central role in characterizing topological phases of matter. However, estimating it in large interacting systems can be computationally difficult. We present a quantum algorithm that estimates the Berry phase over its full range modulo \(2\pi\), overcoming a restriction of earlier approaches. We also classify the computational difficulty of Berry phase estimation. With a guiding state close to the ground state, the problem is BQP-complete, providing a natural setting for quantum computational advantage. Without such a guiding state, but with prior information about the ground-state energy, it is complete for UQMA \(\cap\) co-UQMA. To our knowledge, this is the first natural complete problem for this class. These results connect topological physics with fundamental questions about the power of quantum computation.► BibTeX data@article{Hayakawa2026computational, doi = {10.22331/q-2026-11-18-2271}, url = {https://doi.org/10.22331/q-2026-11-18-2271}, title = {Computational complexity of {B}erry phase estimation in topological phases of matter}, author = {Hayakawa, Ryu and Sakamoto, Kazuki and Kiumi, Chusei}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2271}, month = nov, year = {2026} }► References [1] Michael Victor Berry. ``Quantal phase factors accompanying adiabatic changes''. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 392, 45–57 (1984). doi: 10.1098/​rspa.1984.0023. https:/​/​doi.org/​10.1098/​rspa.1984.0023 [2] Alfred Shapere and Frank Wilczek, editors. ``Geometric phases in physics''. Volume 5 of Advanced Series in Mathematical Physics. World Scientific. (1989). doi: 10.1142/​0613. https:/​/​doi.org/​10.1142/​0613 [3] Yasuhiro Hatsugai. ``Quantized Berry phases as a local order parameter of a quantum liquid''. Journal of the Physical Society of Japan 75, 123601 (2006). doi: 10.1143/​JPSJ.75.123601. https:/​/​doi.org/​10.1143/​JPSJ.75.123601 [4] Joshua Zak. ``Berry's phase for energy bands in solids''.

Physical Review Letters 62, 2747–2750 (1989). doi: 10.1103/​PhysRevLett.62.2747. https:/​/​doi.org/​10.1103/​PhysRevLett.62.2747 [5] Wu-Pei Su, John Robert Schrieffer, and Alan Jay Heeger. ``Solitons in polyacetylene''.

Physical Review Letters 42, 1698–1701 (1979). doi: 10.1103/​PhysRevLett.42.1698. https:/​/​doi.org/​10.1103/​PhysRevLett.42.1698 [6] Robert Dominic King-Smith and David Vanderbilt. ``Theory of polarization of crystalline solids''. Physical Review B 47, 1651–1654 (1993). doi: 10.1103/​PhysRevB.47.1651. https:/​/​doi.org/​10.1103/​PhysRevB.47.1651 [7] Raffaele Resta. ``Macroscopic polarization in crystalline dielectrics: the geometric phase approach''. Reviews of Modern Physics 66, 899–915 (1994). doi: 10.1103/​RevModPhys.66.899. https:/​/​doi.org/​10.1103/​RevModPhys.66.899 [8] David James Thouless, Mahito Kohmoto, Michael Peter Nightingale, and Marcel den Nijs. ``Quantized hall conductance in a two-dimensional periodic potential''.

Physical Review Letters 49, 405–408 (1982). doi: 10.1103/​PhysRevLett.49.405. https:/​/​doi.org/​10.1103/​PhysRevLett.49.405 [9] David James Thouless. ``Quantization of particle transport''. Physical Review B 27, 6083–6087 (1983). doi: 10.1103/​PhysRevB.27.6083. https:/​/​doi.org/​10.1103/​PhysRevB.27.6083 [10] Paolo Zanardi and Mario Rasetti. ``Holonomic quantum computation''. Physics Letters A 264, 94–99 (1999). doi: 10.1016/​S0375-9601(99)00803-8. https:/​/​doi.org/​10.1016/​S0375-9601(99)00803-8 [11] Pedram Roushan, Charles Neill, Yu Chen, Michael Kolodrubetz, Chris Quintana, Nelson Leung, Michael Fang, Rami Barends, Brooks Campbell, Zijun Chen, et al. ``Observation of topological transitions in interacting quantum circuits''. Nature 515, 241–244 (2014). doi: 10.1038/​nature13891. https:/​/​doi.org/​10.1038/​nature13891 [12] Jin Ming Koh, Tommy Tai, and Ching Hua Lee. ``Realization of higher-order topological lattices on a quantum computer''. Nature Communications 15, 5807 (2024). doi: 10.1038/​s41467-024-49648-5. https:/​/​doi.org/​10.1038/​s41467-024-49648-5 [13] Feng Mei, Qihao Guo, Ya-Fei Yu, Liantuan Xiao, Shi-Liang Zhu, and Suotang Jia. ``Digital simulation of topological matter on programmable quantum processors''.

Physical Review Letters 125, 160503 (2020). doi: 10.1103/​PhysRevLett.125.160503. https:/​/​doi.org/​10.1103/​PhysRevLett.125.160503 [14] Xiao Xiao, James K Freericks, and Alexander F Kemper. ``Robust measurement of wave function topology on nisq quantum computers''. Quantum 7, 987 (2023). doi: 10.22331/​q-2023-04-27-987. https:/​/​doi.org/​10.22331/​q-2023-04-27-987 [15] Adam Smith, Bernhard Jobst, Andrew G Green, and Frank Pollmann. ``Crossing a topological phase transition with a quantum computer''.

Physical Review Research 4, L022020 (2022). doi: 10.1103/​PhysRevResearch.4.L022020. https:/​/​doi.org/​10.1103/​PhysRevResearch.4.L022020 [16] Takuya Kitagawa, Mark S Rudner, Erez Berg, and Eugene Demler. ``Exploring topological phases with quantum walks''. Physical Review A 82, 033429 (2010). doi: 10.1103/​PhysRevA.82.033429. https:/​/​doi.org/​10.1103/​PhysRevA.82.033429 [17] Bruno Murta, Gonçalo Catarina, and Joaquín Fernández-Rossier. ``Berry phase estimation in gate-based adiabatic quantum simulation''. Physical Review A 101, 020302 (2020). doi: 10.1103/​PhysRevA.101.020302. https:/​/​doi.org/​10.1103/​PhysRevA.101.020302 [18] Marcel Niedermeier, Marc Nairn, Christian Flindt, and Jose L Lado. ``Quantum computing topological invariants of two-dimensional quantum matter''.

Physical Review Research 6, 043288 (2024). doi: 10.1103/​PhysRevResearch.6.043288. https:/​/​doi.org/​10.1103/​PhysRevResearch.6.043288 [19] Shiro Tamiya, Sho Koh, and Yuya O Nakagawa. ``Calculating nonadiabatic couplings and Berry's phase by variational quantum eigensolvers''.

Physical Review Research 3, 023244 (2021). doi: 10.1103/​PhysRevResearch.3.023244. https:/​/​doi.org/​10.1103/​PhysRevResearch.3.023244 [20] Martin Mootz and Yong-Xin Yao. ``Efficient Berry phase calculation via adaptive variational quantum computing approach''. APL Quantum 3, 016111 (2026). doi: 10.1063/​5.0294540. https:/​/​doi.org/​10.1063/​5.0294540 [21] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. ``Classical and quantum computation''. Volume 47 of Graduate Studies in Mathematics.

American Mathematical Soc. (2002). doi: 10.1090/​gsm/​047. https:/​/​doi.org/​10.1090/​gsm/​047 [22] Toby S Cubitt, Ashley Montanaro, and Stephen Piddock. ``Universal quantum hamiltonians''. Proceedings of the National Academy of Sciences 115, 9497–9502 (2018). doi: 10.1073/​pnas.1804949115. https:/​/​doi.org/​10.1073/​pnas.1804949115 [23] Stephen Piddock and Ashley Montanaro. ``The complexity of antiferromagnetic interactions and 2d lattices''. Quantum Information and Computation 17, 636–672 (2017). doi: 10.26421/​QIC17.7-8-6. https:/​/​doi.org/​10.26421/​QIC17.7-8-6 [24] Sevag Gharibian and François Le Gall. ``Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum pcp conjecture''. In Proceedings of the 54th annual ACM SIGACT symposium on theory of computing. Pages 19–32. (2022). doi: 10.1145/​3519935.3519991. https:/​/​doi.org/​10.1145/​3519935.3519991 [25] Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. ``Improved hardness results for the guided local hamiltonian problem''. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023). doi: 10.4230/​LIPIcs.ICALP.2023.32. https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2023.32 [26] Peter C. Richter. ``Two remarks on the local hamiltonian problem'' (2007). doi: 10.48550/​arXiv.0712.4274. https:/​/​doi.org/​10.48550/​arXiv.0712.4274 [27] Martin Schwarz, Toby S Cubitt, and Frank Verstraete. ``An information-theoretic proof of the constructive commutative quantum lovász local lemma'' (2013). doi: 10.48550/​arXiv.1311.6474. https:/​/​doi.org/​10.48550/​arXiv.1311.6474 [28] András Pál Gilyén and Or Sattath. ``On preparing ground states of gapped hamiltonians: An efficient quantum lovász local lemma''. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 439–450. IEEE (2017). doi: 10.1109/​FOCS.2017.47. https:/​/​doi.org/​10.1109/​FOCS.2017.47 [29] Zeph Landau, Umesh Vazirani, and Thomas Vidick. ``A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians''. Nature Physics 11, 566–569 (2015). doi: 10.1038/​nphys3345. https:/​/​doi.org/​10.1038/​nphys3345 [30] Dorit Aharonov, Michael Ben-Or, Fernando G.S.L. Brandão, and Or Sattath. ``The pursuit of uniqueness: Extending valiant-vazirani theorem to the probabilistic and quantum settings''. Quantum 6, 668 (2022). doi: 10.22331/​q-2022-03-17-668. https:/​/​doi.org/​10.22331/​q-2022-03-17-668 [31] Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, and Quynh T Nguyen. ``On the complexity of unique quantum witnesses and quantum approximate counting'' (2024). doi: 10.48550/​arXiv.2410.23811. https:/​/​doi.org/​10.48550/​arXiv.2410.23811 [32] Yimin Ge, Jordi Tura, and Juan Ignacio Cirac. ``Faster ground state preparation and high-precision ground energy estimation with fewer qubits''. Journal of Mathematical Physics 60, 022202 (2019). doi: 10.1063/​1.5027484. https:/​/​doi.org/​10.1063/​1.5027484 [33] Lin Lin and Yu Tong. ``Near-optimal ground state preparation''. Quantum 4, 372 (2020). doi: 10.22331/​q-2020-12-14-372. https:/​/​doi.org/​10.22331/​q-2020-12-14-372 [34] Justin Yirka. ``A note on the complexity of the spectral gap problem'' (2025). doi: 10.48550/​arXiv.2503.02747. https:/​/​doi.org/​10.48550/​arXiv.2503.02747 [35] Yukun Zhang, Yusen Wu, and Xiao Yuan. ``A dequantized algorithm for the guided local hamiltonian problem'' (2024). doi: 10.48550/​arXiv.2411.16163. https:/​/​doi.org/​10.48550/​arXiv.2411.16163 [36] Gabriel Waite. ``The guided local hamiltonian problem for stoquastic hamiltonians'' (2025). doi: 10.48550/​arXiv.2509.25829. https:/​/​doi.org/​10.48550/​arXiv.2509.25829 [37] Jordi Weggemans, Marten Folkertsma, and Chris Cade. ``Guidable local hamiltonian problems with implications to heuristic ansatz state preparation and the quantum pcp conjecture''. In Frédéric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Volume 310 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:24. Dagstuhl, Germany (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi: 10.4230/​LIPIcs.TQC.2024.10. https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2024.10 [38] Andris Ambainis. ``On physical problems that are slightly more difficult than qma''. In 2014 IEEE 29th Conference on Computational Complexity (CCC). Pages 32–43. IEEE (2014). doi: 10.1109/​CCC.2014.12. https:/​/​doi.org/​10.1109/​CCC.2014.12 [39] Andris Ambainis and Oded Regev. ``An elementary proof of the quantum adiabatic theorem'' (2004). doi: 10.48550/​arXiv.quant-ph/​0411152. https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0411152 arXiv:quant-ph/0411152 [40] Gabriel Waite, Karl Lin, Samuel J. Elman, and Michael J. Bremner. ``Physically-motivated guiding states for local hamiltonians'' (2025). doi: 10.48550/​arXiv.2509.25815. https:/​/​doi.org/​10.48550/​arXiv.2509.25815 [41] Chris Marriott and John Watrous. ``Quantum arthur–merlin games''. computational complexity 14, 122–152 (2005). doi: 10.1007/​s00037-005-0194-x. https:/​/​doi.org/​10.1007/​s00037-005-0194-x [42] Sevag Gharibian and Julia Kempe. ``Hardness of approximation for quantum problems''. In Automata, Languages, and Programming. Volume 7391 of Lecture Notes in Computer Science, pages 387–398. Springer (2012). doi: 10.1007/​978-3-642-31594-7_33. https:/​/​doi.org/​10.1007/​978-3-642-31594-7_33 [43] Sevag Gharibian and Justin Yirka. ``The complexity of simulating local measurements on quantum systems''. Quantum 3, 189 (2019). doi: 10.22331/​q-2019-09-30-189. https:/​/​doi.org/​10.22331/​q-2019-09-30-189 [44] Abhinav Deshpande, Alexey V Gorshkov, and Bill Fefferman. ``Importance of the spectral gap in estimating ground-state energies''. PRX Quantum 3, 040327 (2022). doi: 10.1103/​PRXQuantum.3.040327. https:/​/​doi.org/​10.1103/​PRXQuantum.3.040327 [45] Richard Beigel. ``Bounded queries to sat and the boolean hierarchy''.

Theoretical Computer Science 84, 199–223 (1991). doi: 10.1016/​0304-3975(91)90160-4. https:/​/​doi.org/​10.1016/​0304-3975(91)90160-4Cited byCould not fetch Crossref cited-by data during last attempt 2026-11-18 11:04:19: Could not fetch cited-by data for 10.22331/q-2026-11-18-2271 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-11-18 11:04:20: Cannot retrieve data from ADS due to rate limitations.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. AbstractThe Berry phase is a fundamental quantity in the classification of topological phases of matter. In this paper, we present a new quantum algorithm and several complexity-theoretical results for the Berry phase estimation (BPE) problems. Our new quantum algorithm achieves BPE in a more general setting than previously known quantum algorithms, with a theoretical guarantee. For the complexity-theoretic results, we consider two main cases. First, we prove $\mathsf{BQP}$-completeness when we are given a guiding state that has a large overlap with the ground state. This result establishes an exponential quantum speedup for estimating the Berry phase. Second, we prove $\mathsf{UQMA} \cap \mathsf{co}$-$\mathsf{UQMA}$-completeness when we have an $\textit{a priori}$ bound for the ground-state energy. Here, $\mathsf{UQMA}$ is the unique witness version of $\mathsf{QMA}$, and $\mathsf{UQMA} \cap \mathsf{co}$-$\mathsf{UQMA}$ precisely captures the complexity of BPE without the known guiding state. Remarkably, this problem is, to our knowledge, the first natural problem complete for $\mathsf{UQMA} \cap \mathsf{co}$-$\mathsf{UQMA}$. These results advance the role of quantum computing in the study of topological phases of matter and provide a pathway for clarifying the connection between topological phases of matter and computational complexity.Featured image: A Hamiltonian loop encoding a quantum computation imprints a geometric phase on the quantum state.Popular summaryThe Berry phase is a geometric property of quantum states that plays a central role in characterizing topological phases of matter. However, estimating it in large interacting systems can be computationally difficult. We present a quantum algorithm that estimates the Berry phase over its full range modulo \(2\pi\), overcoming a restriction of earlier approaches. We also classify the computational difficulty of Berry phase estimation. With a guiding state close to the ground state, the problem is BQP-complete, providing a natural setting for quantum computational advantage. Without such a guiding state, but with prior information about the ground-state energy, it is complete for UQMA \(\cap\) co-UQMA. To our knowledge, this is the first natural complete problem for this class. These results connect topological physics with fundamental questions about the power of quantum computation.► BibTeX data@article{Hayakawa2026computational, doi = {10.22331/q-2026-11-18-2271}, url = {https://doi.org/10.22331/q-2026-11-18-2271}, title = {Computational complexity of {B}erry phase estimation in topological phases of matter}, author = {Hayakawa, Ryu and Sakamoto, Kazuki and Kiumi, Chusei}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2271}, month = nov, year = {2026} }► References [1] Michael Victor Berry. ``Quantal phase factors accompanying adiabatic changes''. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 392, 45–57 (1984). doi: 10.1098/​rspa.1984.0023. https:/​/​doi.org/​10.1098/​rspa.1984.0023 [2] Alfred Shapere and Frank Wilczek, editors. ``Geometric phases in physics''. Volume 5 of Advanced Series in Mathematical Physics. World Scientific. (1989). doi: 10.1142/​0613. https:/​/​doi.org/​10.1142/​0613 [3] Yasuhiro Hatsugai. ``Quantized Berry phases as a local order parameter of a quantum liquid''. Journal of the Physical Society of Japan 75, 123601 (2006). doi: 10.1143/​JPSJ.75.123601. https:/​/​doi.org/​10.1143/​JPSJ.75.123601 [4] Joshua Zak. ``Berry's phase for energy bands in solids''.

Physical Review Letters 62, 2747–2750 (1989). doi: 10.1103/​PhysRevLett.62.2747. https:/​/​doi.org/​10.1103/​PhysRevLett.62.2747 [5] Wu-Pei Su, John Robert Schrieffer, and Alan Jay Heeger. ``Solitons in polyacetylene''.

Physical Review Letters 42, 1698–1701 (1979). doi: 10.1103/​PhysRevLett.42.1698. https:/​/​doi.org/​10.1103/​PhysRevLett.42.1698 [6] Robert Dominic King-Smith and David Vanderbilt. ``Theory of polarization of crystalline solids''. Physical Review B 47, 1651–1654 (1993). doi: 10.1103/​PhysRevB.47.1651. https:/​/​doi.org/​10.1103/​PhysRevB.47.1651 [7] Raffaele Resta. ``Macroscopic polarization in crystalline dielectrics: the geometric phase approach''. Reviews of Modern Physics 66, 899–915 (1994). doi: 10.1103/​RevModPhys.66.899. https:/​/​doi.org/​10.1103/​RevModPhys.66.899 [8] David James Thouless, Mahito Kohmoto, Michael Peter Nightingale, and Marcel den Nijs. ``Quantized hall conductance in a two-dimensional periodic potential''.

Physical Review Letters 49, 405–408 (1982). doi: 10.1103/​PhysRevLett.49.405. https:/​/​doi.org/​10.1103/​PhysRevLett.49.405 [9] David James Thouless. ``Quantization of particle transport''. Physical Review B 27, 6083–6087 (1983). doi: 10.1103/​PhysRevB.27.6083. https:/​/​doi.org/​10.1103/​PhysRevB.27.6083 [10] Paolo Zanardi and Mario Rasetti. ``Holonomic quantum computation''. Physics Letters A 264, 94–99 (1999). doi: 10.1016/​S0375-9601(99)00803-8. https:/​/​doi.org/​10.1016/​S0375-9601(99)00803-8 [11] Pedram Roushan, Charles Neill, Yu Chen, Michael Kolodrubetz, Chris Quintana, Nelson Leung, Michael Fang, Rami Barends, Brooks Campbell, Zijun Chen, et al. ``Observation of topological transitions in interacting quantum circuits''. Nature 515, 241–244 (2014). doi: 10.1038/​nature13891. https:/​/​doi.org/​10.1038/​nature13891 [12] Jin Ming Koh, Tommy Tai, and Ching Hua Lee. ``Realization of higher-order topological lattices on a quantum computer''. Nature Communications 15, 5807 (2024). doi: 10.1038/​s41467-024-49648-5. https:/​/​doi.org/​10.1038/​s41467-024-49648-5 [13] Feng Mei, Qihao Guo, Ya-Fei Yu, Liantuan Xiao, Shi-Liang Zhu, and Suotang Jia. ``Digital simulation of topological matter on programmable quantum processors''.

Physical Review Letters 125, 160503 (2020). doi: 10.1103/​PhysRevLett.125.160503. https:/​/​doi.org/​10.1103/​PhysRevLett.125.160503 [14] Xiao Xiao, James K Freericks, and Alexander F Kemper. ``Robust measurement of wave function topology on nisq quantum computers''. Quantum 7, 987 (2023). doi: 10.22331/​q-2023-04-27-987. https:/​/​doi.org/​10.22331/​q-2023-04-27-987 [15] Adam Smith, Bernhard Jobst, Andrew G Green, and Frank Pollmann. ``Crossing a topological phase transition with a quantum computer''.

Physical Review Research 4, L022020 (2022). doi: 10.1103/​PhysRevResearch.4.L022020. https:/​/​doi.org/​10.1103/​PhysRevResearch.4.L022020 [16] Takuya Kitagawa, Mark S Rudner, Erez Berg, and Eugene Demler. ``Exploring topological phases with quantum walks''. Physical Review A 82, 033429 (2010). doi: 10.1103/​PhysRevA.82.033429. https:/​/​doi.org/​10.1103/​PhysRevA.82.033429 [17] Bruno Murta, Gonçalo Catarina, and Joaquín Fernández-Rossier. ``Berry phase estimation in gate-based adiabatic quantum simulation''. Physical Review A 101, 020302 (2020). doi: 10.1103/​PhysRevA.101.020302. https:/​/​doi.org/​10.1103/​PhysRevA.101.020302 [18] Marcel Niedermeier, Marc Nairn, Christian Flindt, and Jose L Lado. ``Quantum computing topological invariants of two-dimensional quantum matter''.

Physical Review Research 6, 043288 (2024). doi: 10.1103/​PhysRevResearch.6.043288. https:/​/​doi.org/​10.1103/​PhysRevResearch.6.043288 [19] Shiro Tamiya, Sho Koh, and Yuya O Nakagawa. ``Calculating nonadiabatic couplings and Berry's phase by variational quantum eigensolvers''.

Physical Review Research 3, 023244 (2021). doi: 10.1103/​PhysRevResearch.3.023244. https:/​/​doi.org/​10.1103/​PhysRevResearch.3.023244 [20] Martin Mootz and Yong-Xin Yao. ``Efficient Berry phase calculation via adaptive variational quantum computing approach''. APL Quantum 3, 016111 (2026). doi: 10.1063/​5.0294540. https:/​/​doi.org/​10.1063/​5.0294540 [21] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. ``Classical and quantum computation''. Volume 47 of Graduate Studies in Mathematics.

American Mathematical Soc. (2002). doi: 10.1090/​gsm/​047. https:/​/​doi.org/​10.1090/​gsm/​047 [22] Toby S Cubitt, Ashley Montanaro, and Stephen Piddock. ``Universal quantum hamiltonians''. Proceedings of the National Academy of Sciences 115, 9497–9502 (2018). doi: 10.1073/​pnas.1804949115. https:/​/​doi.org/​10.1073/​pnas.1804949115 [23] Stephen Piddock and Ashley Montanaro. ``The complexity of antiferromagnetic interactions and 2d lattices''. Quantum Information and Computation 17, 636–672 (2017). doi: 10.26421/​QIC17.7-8-6. https:/​/​doi.org/​10.26421/​QIC17.7-8-6 [24] Sevag Gharibian and François Le Gall. ``Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum pcp conjecture''. In Proceedings of the 54th annual ACM SIGACT symposium on theory of computing. Pages 19–32. (2022). doi: 10.1145/​3519935.3519991. https:/​/​doi.org/​10.1145/​3519935.3519991 [25] Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. ``Improved hardness results for the guided local hamiltonian problem''. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023). doi: 10.4230/​LIPIcs.ICALP.2023.32. https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2023.32 [26] Peter C. Richter. ``Two remarks on the local hamiltonian problem'' (2007). doi: 10.48550/​arXiv.0712.4274. https:/​/​doi.org/​10.48550/​arXiv.0712.4274 [27] Martin Schwarz, Toby S Cubitt, and Frank Verstraete. ``An information-theoretic proof of the constructive commutative quantum lovász local lemma'' (2013). doi: 10.48550/​arXiv.1311.6474. https:/​/​doi.org/​10.48550/​arXiv.1311.6474 [28] András Pál Gilyén and Or Sattath. ``On preparing ground states of gapped hamiltonians: An efficient quantum lovász local lemma''. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 439–450. IEEE (2017). doi: 10.1109/​FOCS.2017.47. https:/​/​doi.org/​10.1109/​FOCS.2017.47 [29] Zeph Landau, Umesh Vazirani, and Thomas Vidick. ``A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians''. Nature Physics 11, 566–569 (2015). doi: 10.1038/​nphys3345. https:/​/​doi.org/​10.1038/​nphys3345 [30] Dorit Aharonov, Michael Ben-Or, Fernando G.S.L. Brandão, and Or Sattath. ``The pursuit of uniqueness: Extending valiant-vazirani theorem to the probabilistic and quantum settings''. Quantum 6, 668 (2022). doi: 10.22331/​q-2022-03-17-668. https:/​/​doi.org/​10.22331/​q-2022-03-17-668 [31] Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, and Quynh T Nguyen. ``On the complexity of unique quantum witnesses and quantum approximate counting'' (2024). doi: 10.48550/​arXiv.2410.23811. https:/​/​doi.org/​10.48550/​arXiv.2410.23811 [32] Yimin Ge, Jordi Tura, and Juan Ignacio Cirac. ``Faster ground state preparation and high-precision ground energy estimation with fewer qubits''. Journal of Mathematical Physics 60, 022202 (2019). doi: 10.1063/​1.5027484. https:/​/​doi.org/​10.1063/​1.5027484 [33] Lin Lin and Yu Tong. ``Near-optimal ground state preparation''. Quantum 4, 372 (2020). doi: 10.22331/​q-2020-12-14-372. https:/​/​doi.org/​10.22331/​q-2020-12-14-372 [34] Justin Yirka. ``A note on the complexity of the spectral gap problem'' (2025). doi: 10.48550/​arXiv.2503.02747. https:/​/​doi.org/​10.48550/​arXiv.2503.02747 [35] Yukun Zhang, Yusen Wu, and Xiao Yuan. ``A dequantized algorithm for the guided local hamiltonian problem'' (2024). doi: 10.48550/​arXiv.2411.16163. https:/​/​doi.org/​10.48550/​arXiv.2411.16163 [36] Gabriel Waite. ``The guided local hamiltonian problem for stoquastic hamiltonians'' (2025). doi: 10.48550/​arXiv.2509.25829. https:/​/​doi.org/​10.48550/​arXiv.2509.25829 [37] Jordi Weggemans, Marten Folkertsma, and Chris Cade. ``Guidable local hamiltonian problems with implications to heuristic ansatz state preparation and the quantum pcp conjecture''. In Frédéric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Volume 310 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:24. Dagstuhl, Germany (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi: 10.4230/​LIPIcs.TQC.2024.10. https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2024.10 [38] Andris Ambainis. ``On physical problems that are slightly more difficult than qma''. In 2014 IEEE 29th Conference on Computational Complexity (CCC). Pages 32–43. IEEE (2014). doi: 10.1109/​CCC.2014.12. https:/​/​doi.org/​10.1109/​CCC.2014.12 [39] Andris Ambainis and Oded Regev. ``An elementary proof of the quantum adiabatic theorem'' (2004). doi: 10.48550/​arXiv.quant-ph/​0411152. https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0411152 arXiv:quant-ph/0411152 [40] Gabriel Waite, Karl Lin, Samuel J. Elman, and Michael J. Bremner. ``Physically-motivated guiding states for local hamiltonians'' (2025). doi: 10.48550/​arXiv.2509.25815. https:/​/​doi.org/​10.48550/​arXiv.2509.25815 [41] Chris Marriott and John Watrous. ``Quantum arthur–merlin games''. computational complexity 14, 122–152 (2005). doi: 10.1007/​s00037-005-0194-x. https:/​/​doi.org/​10.1007/​s00037-005-0194-x [42] Sevag Gharibian and Julia Kempe. ``Hardness of approximation for quantum problems''. In Automata, Languages, and Programming. Volume 7391 of Lecture Notes in Computer Science, pages 387–398. Springer (2012). doi: 10.1007/​978-3-642-31594-7_33. https:/​/​doi.org/​10.1007/​978-3-642-31594-7_33 [43] Sevag Gharibian and Justin Yirka. ``The complexity of simulating local measurements on quantum systems''. Quantum 3, 189 (2019). doi: 10.22331/​q-2019-09-30-189. https:/​/​doi.org/​10.22331/​q-2019-09-30-189 [44] Abhinav Deshpande, Alexey V Gorshkov, and Bill Fefferman. ``Importance of the spectral gap in estimating ground-state energies''. PRX Quantum 3, 040327 (2022). doi: 10.1103/​PRXQuantum.3.040327. https:/​/​doi.org/​10.1103/​PRXQuantum.3.040327 [45] Richard Beigel. ``Bounded queries to sat and the boolean hierarchy''.

Theoretical Computer Science 84, 199–223 (1991). doi: 10.1016/​0304-3975(91)90160-4. https:/​/​doi.org/​10.1016/​0304-3975(91)90160-4Cited byCould not fetch Crossref cited-by data during last attempt 2026-11-18 11:04:19: Could not fetch cited-by data for 10.22331/q-2026-11-18-2271 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-11-18 11:04:20: Cannot retrieve data from ADS due to rate limitations.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.

Read Original

Tags

energy-climate
quantum-computing
quantum-algorithms

Source Information

Source: Quantum Journal

Discussion

0 professional contributions

Sign in to join this professional discussion.

Be the first to add a constructive contribution.