Ryu Hayakawa

We show the existence of an MA-complete homology problem for a certain subclass of simplicial complexes. The problem is defined through a new concept of orientability of simplicial complexes that we call a ``uniform orientable filtration'', which is related to sign-problem freeness in homology. The containment in MA is achieved through the design of new, higher-order random walks on simplicial complexes associated with the filtration. For the MA-hardness, we design a new gadget with which we can reduce from an MA-hard stoquastic satisfiability problem. Therefore, our result provides the first natural MA-complete problem for higher-order random walks on simplicial complexes, combining the concepts of topology, persistent homology, and quantum computing.

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}.