arXiv:2609.37199
Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms
Kazuki Sakamoto, Keisuke Fujii
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 $\mathsf{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 $\mathsf{BPP}\neq \mathsf{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.
AI Summary
The paper asks whether estimating symmetry-quantized Berry phases remains quantum-hard when only constant phase precision is needed, and when the problem admits classical algorithms. It studies smooth loops of local Hamiltonians with unique ground states, given a guiding state approximating the initial ground state. Distinguishing Berry phase exactly $0$ from $\pi$ is shown to be $\mathsf{BQP}$-complete for inverse-polynomial spectral gaps. Hardness holds for 5-local Hamiltonians with $\sup_\theta\|\dot H(\theta)\|,\sup_\theta\|\ddot H(\theta)\|=O(1)$ and a classically accessible guiding state of fidelity at least $1-1/\mathrm{poly}(n)$. A circuit-to-Hamiltonian construction couples the computation to an ancilla whose effective SSH loop encodes acceptance through its winding. An exact parameter-reversing symmetry quantizes the full Hamiltonian’s Berry phase. Symmetry-preserving perturbative gadgets extend hardness to nearest-neighbor square-lattice Hamiltonians from any fixed non-2SLD interaction set, including Heisenberg and XY interactions, allowing signed coefficients. For geometrically local Hamiltonians in fixed dimension, classical randomized algorithms combine spatially truncated quasi-adiabatic continuation with sparse time-dependent evolution simulation. With sampling-and-query access to the guide, constant gap, constant $B_1=\sup_\theta\|\dot H(\theta)\|$, and polynomially bounded second derivative, constant-precision estimation takes polynomial time given sufficiently high guide fidelity. For binary phases, fidelity $\gamma\geq1/2+\Omega(1)$ suffices for polynomial time; $\gamma\geq1/2$ gives quasipolynomial time using an energy filter. The results concern worst-case guided instances. Open regimes include constant gaps with growing $B_1$, lower guide overlap, and constant-precision estimation without a guide. The Berry invariant need not identify the ground-state phase of matter.
GPT-5.6 and GPT-6 were used to explore approaches to the proof of Theorem 2, Theorem 3 and Theorem 4, to check intermediate arguments, and to refine the text.
Central claim may not hold: The abstract claims polynomial-time classical estimation for constant-gap geometrically local Hamiltonians without stating the essential additional restriction B1 = O(1), while polynomially growing B1 remains open. The abstract's classical-algorithm claim omits efficient classical guiding-state access and overlap promises, including the distinction between polynomial time above squared overlap 1/2 by a constant and quasipolynomial time at overlap 1/2. The abstract's BQP-completeness statement does not explicitly specify guided input, although the proved containment requires a supplied efficient guiding-state preparation circuit and the unguided problem remains open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 24 pages, 1 figure