Kazuki Sakamoto

The Berry phase is a fundamental quantity for classifying topological phases of matter. We present a new quantum algorithm for Berry phase estimation (BPE) that is both more general than previously known approaches and comes with a rigorous polynomial-time performance guarantee. Moreover, we provide a new circuit-to-Hamiltonian construction that results in a closed loop of parameterized Hamiltonians. Building on these, we prove that a BPE formulation is \BQP-complete when given a guiding state with large overlap with the ground state. This shows the first complexity-theoretic evidence of an exponential quantum speedup for quantum-computational approaches to studying topological phases of matter. We also establish several complexity-theoretic results for BPE, including \textsf{dUQMA}-completeness, \(\mathsf{P}^{\mathsf{dUQMA}[\log]}\)-hardness, and containment in \(\mathsf{P}^{\mathsf{PGQMA}[\log]}\), depending on the BPE setting. Here, \textsf{dUQMA} is a variant of the unique-witness class \textsf{UQMA} that we introduce and remarkably, this \textsf{dUQMA}-complete BPE variant appears to be the first natural problem known to lie in \textsf{UQMA} \(\cap\) \textsf{co-UQMA}.