Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms
Abstract
The Berry phase is a fundamental geometric quantity for characterizing the geometry and topology of quantum many-body systems. Previous work established a super-polynomial quantum advantage in Berry phase estimation at inverse-polynomial precision, given an ansatz state approximating the initial ground state. However, whether this hardness persists for Berry phases quantized by symmetry, which can be distinguished at constant precision, remained open. In this work, we characterize the computational complexity of quantized Berry phase estimation. First, we prove that deciding whether the Berry phase is exactly $0$ or π is BQP-complete when the spectral gap is inverse-polynomially small. This result implies that distinguishing the quantized Berry phase still has a super-polynomial quantum advantage, assuming BPP≠ BQP. To prove this result, we introduce an encoding that maps the output of any quantum computation to a Berry phase that is exactly $0$ or π. Second, we extend this hardness to physically motivated Hamiltonians on a 2D square lattice, including Heisenberg and XY interactions. Third, we provide a classical polynomial-time algorithm for geometrically local Hamiltonians on fixed-dimensional lattices with constant spectral gaps. Therefore we identify that the spectral gap is a key resource for the classical tractability, rather than precision. These results establish a super-polynomial quantum advantage for computing a quantized topological invariant that is unchanged under symmetry- and gap-preserving deformations, and provide new steps towards practical quantum advantage in quantum physics.
Related
- Classical Algorithms for Function Computation in Gaussian Boson Sampling
- First-quantized quantum simulation with non-local potentials by matrix-product-state encoding
- HTM: A Hybrid Classical-Quantum Computation Model
- An example of universal braiding in Links--Gould topological quantum computation
- From Block-encoding to Generalized Quantum Signal Processing: Principles, Algorithms and Applications
BibTeX
@misc{sakamoto2026encoding,
title = {{Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms}},
author = {Kazuki Sakamoto and Keisuke Fujii},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37199},
eprint = {2609.37199},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37199},
}
RIS
TY - UNPB
TI - Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms
AU - Kazuki Sakamoto
AU - Keisuke Fujii
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37199
UR - https://arxiv.org/abs/2609.37199
AB - The Berry phase is a fundamental geometric quantity for characterizing the geometry and topology of quantum many-body systems. Previous work established a super-polynomial quantum advantage in Berry phase estimation at inverse-polynomial precision, given an ansatz state approximating the initial ground state. However, whether this hardness persists for Berry phases quantized by symmetry, which can be distinguished at constant precision, remained open. In this work, we characterize the computational complexity of quantized Berry phase estimation. First, we prove that deciding whether the Berry phase is exactly $0$ or π is BQP-complete when the spectral gap is inverse-polynomially small. This result implies that distinguishing the quantized Berry phase still has a super-polynomial quantum advantage, assuming BPP≠ BQP. To prove this result, we introduce an encoding that maps the output of any quantum computation to a Berry phase that is exactly $0$ or π. Second, we extend this hardness to physically motivated Hamiltonians on a 2D square lattice, including Heisenberg and XY interactions. Third, we provide a classical polynomial-time algorithm for geometrically local Hamiltonians on fixed-dimensional lattices with constant spectral gaps. Therefore we identify that the spectral gap is a key resource for the classical tractability, rather than precision. These results establish a super-polynomial quantum advantage for computing a quantized topological invariant that is unchanged under symmetry- and gap-preserving deformations, and provide new steps towards practical quantum advantage in quantum physics.
ER -