Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.37199

Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms

Kazuki Sakamoto, Keisuke Fujii

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated textAI use disclosed
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

Related papers

Chern-number estimation: nearly optimal quantum algorithm and provable quantum speedup

Soichiro Imamura, Shintaro Ae, Kazuki Sakamoto +2 more

Topological phases of matter are characterized by global properties of quantum states beyond conventional local order parameters. The Chern number is a central invariant in this characterization, linking the geometry of quantum states to robust physical observables and making its determination key to understanding quantum matter. We construct a nearly optimal quantum algorithm for estimating the Chern number of a smooth Hamiltonian family over a two-dimensional parameter torus with a unique, gapped ground state, including interacting many-body systems. The algorithm transports and reuses two ground-state copies prepared at a single reference point and uses generalized quantum signal processing to coherently accumulate geometric phases. It achieves a Hamiltonian-oracle evolution time of $\tilde{O}(L_xL_y/Δ_{\min}^3)$, where $L_x,L_y$ bound the parameter derivatives of the Hamiltonian and $Δ_{\min}$ is a known spectral-gap lower bound. We prove a matching worst-case oracle lower bound, even when the Chern number is promised to be zero or one, establishing optimality up to polylogarithmic factors. For local Hamiltonian families with an inverse-polynomial gap and a supplied guiding state, exact Chern-number computation is in $\mathsf{FBQP}$ and is $\mathsf{BQP}$-hard, and merely deciding whether the Chern number is zero or one is already $\mathsf{BQP}$-complete. These results establish how efficiently quantum computers can estimate a quantized topological invariant and provide evidence for quantum advantage in characterizing topological phases.

quant-pharXiv:2609.35978•Sep 30, 2026•0 citations

On the Computational Complexity of Guided Berry Phase Estimation

Gabriel Waite

We prove that deciding the Berry phase for parameterised 2-local qubit Hamiltonians is BQP-complete when presented with a classical description of a guiding state, promised to overlap with the ground state of the system. Our results extend to systems with weighted Heisenberg interactions and when restricted to a 2D square or triangular lattice geometry. The techniques we develop leverage the Schrieffer--Wolff transformation, typically used in the construction of perturbative gadget reductions for local Hamiltonian problems, extending it to parameterised families of Hamiltonians. We demonstrate that there exists a choice of parameterised simulator Hamiltonians whose Berry phase well-approximates that of a parameterised target family. Using the perturbative gadget reduction framework of Oliveira and Terhal and of Schuch and Verstraete, we adapt the arguments to parameterised interactions and demonstrate the error bounds in the resulting simulation can be controlled. Additionally, we provide an explicit proof that families of 1-local Hamiltonians have a Berry phase that can be efficiently computed to inverse-polynomial precision. This establishes a complexity transition between 1-local and 2-local Hamiltonian families.

quant-pharXiv:2609.25929•Sep 23, 2026•1 citation

Computational complexity of Berry phase estimation in topological phases of matter

Hayakawa, Ryu, Kazuki Sakamoto, Chusei Kiumi

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

arXiv:2509.13423•Sep 16, 2025•6 citations

Hardness of recognizing phases of matter

Thomas Schuster, Dominik S. Kufel, Norman Y. Yao +1 more

We prove that recognizing the phase of matter of an unknown quantum state is quantum computationally hard. More specifically, we show that the quantum computational time of any phase recognition algorithm must grow exponentially in the range of correlations $ξ$ of the unknown state. This exponential growth renders the problem practically infeasible for even moderate correlation ranges, and leads to super-polynomial quantum computational time in the system size $n$ whenever $ξ= ω(\log n)$. Our results apply to a substantial portion of all known phases of matter, including symmetry-breaking phases and symmetry-protected topological phases for any discrete on-site symmetry group in any spatial dimension. To establish this hardness, we extend the study of pseudorandom unitaries (PRUs) to quantum systems with symmetries. We prove that symmetric PRUs exist under standard cryptographic conjectures, and can be constructed in extremely low circuit depths. We also establish hardness for systems with translation invariance and purely classical phases of matter. A key technical limitation is that the locality of the parent Hamiltonians of the states we consider is linear in $ξ$; the complexity of phase recognition for Hamiltonians with constant locality remains an important open question.

arXiv:2510.08503•Oct 9, 2025•8 citations

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality

Kazuki Sakamoto, Keisuke Fujii

The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of simulating such geometrically local systems on quantum computers. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that simulating short-time dynamics is at least as hard as polynomial-time and linear-space probabilistic classical computation. Third, we show that the computational complexity of simulating long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.

arXiv:2505.10445•Quantum•Aug 3, 2026•4 citations

Provable Quantum Advantage for Dynamical Phase Transition

Jue Xu, Xiao Yuan, Qi Zhao

The universal scaling of critical behavior in phase transitions is a cornerstone of physics. Dynamical quantum phase transitions (DQPTs) are their nonequilibrium analogues: abrupt nonanalyticities that emerge as a quantum system evolves in time. Yet the hardness and cost of detecting this phenomenon remain largely unexplored. We prove that estimating DQPT to a certain precision is intractable even for quantum computers, whereas deciding a subsystem variant of DQPT is as hard as simulating generic quantum circuits, implying a provable exponential quantum advantage. Furthermore, to search for critical times of local DQPTs, we show a quadratically faster quantum algorithm that estimates observables of Hamiltonian dynamics at multiple time points with Heisenberg-limited precision and sublinear scaling in the number of time points. Moreover, through encoding classical evolution into quantum dynamics, our framework enables broader quantum speedups for detecting anomalous phenomena in classical systems.

quant-pharXiv:2606.30396•Jun 30, 2026•0 citations
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 000 or πππ is BQP\mathsf{BQP}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\mathsf{BPP}\neq \mathsf{BQP}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 000 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.
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 000 from π\piπ is shown to be BQP\mathsf{BQP}BQP-complete for inverse-polynomial spectral gaps. Hardness holds for 5-local Hamiltonians with sup⁡θ∥H˙(θ)∥,sup⁡θ∥H¨(θ)∥=O(1)\sup_\theta\|\dot H(\theta)\|,\sup_\theta\|\ddot H(\theta)\|=O(1)supθ​∥H˙(θ)∥,supθ​∥H¨(θ)∥=O(1) and a classically accessible guiding state of fidelity at least 1−1/poly(n)1-1/\mathrm{poly}(n)1−1/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 B1=sup⁡θ∥H˙(θ)∥B_1=\sup_\theta\|\dot H(\theta)\|B1​=supθ​∥H˙(θ)∥, and polynomially bounded second derivative, constant-precision estimation takes polynomial time given sufficiently high guide fidelity. For binary phases, fidelity γ≥1/2+Ω(1)\gamma\geq1/2+\Omega(1)γ≥1/2+Ω(1) suffices for polynomial time; γ≥1/2\gamma\geq1/2γ≥1/2 gives quasipolynomial time using an energy filter.
The results concern worst-case guided instances. Open regimes include constant gaps with growing B1B_1B1​, lower guide overlap, and constant-precision estimation without a guide. The Berry invariant need not identify the ground-state phase of matter.
Topological phases of matter are characterized by global properties of quantum states beyond conventional local order parameters. The Chern number is a central invariant in this characterization, linking the geometry of quantum states to robust physical observables and making its determination key to understanding quantum matter. We construct a nearly optimal quantum algorithm for estimating the Chern number of a smooth Hamiltonian family over a two-dimensional parameter torus with a unique, gapped ground state, including interacting many-body systems. The algorithm transports and reuses two ground-state copies prepared at a single reference point and uses generalized quantum signal processing to coherently accumulate geometric phases. It achieves a Hamiltonian-oracle evolution time of O~(LxLy/Δmin⁡3)\tilde{O}(L_xL_y/Δ_{\min}^3)O~(Lx​Ly​/Δmin3​), where Lx,LyL_x,L_yLx​,Ly​ bound the parameter derivatives of the Hamiltonian and Δmin⁡Δ_{\min}Δmin​ is a known spectral-gap lower bound. We prove a matching worst-case oracle lower bound, even when the Chern number is promised to be zero or one, establishing optimality up to polylogarithmic factors. For local Hamiltonian families with an inverse-polynomial gap and a supplied guiding state, exact Chern-number computation is in FBQP\mathsf{FBQP}FBQP and is BQP\mathsf{BQP}BQP-hard, and merely deciding whether the Chern number is zero or one is already BQP\mathsf{BQP}BQP-complete. These results establish how efficiently quantum computers can estimate a quantized topological invariant and provide evidence for quantum advantage in characterizing topological phases.
We prove that deciding the Berry phase for parameterised 2-local qubit Hamiltonians is BQP-complete when presented with a classical description of a guiding state, promised to overlap with the ground state of the system. Our results extend to systems with weighted Heisenberg interactions and when restricted to a 2D square or triangular lattice geometry. The techniques we develop leverage the Schrieffer--Wolff transformation, typically used in the construction of perturbative gadget reductions for local Hamiltonian problems, extending it to parameterised families of Hamiltonians. We demonstrate that there exists a choice of parameterised simulator Hamiltonians whose Berry phase well-approximates that of a parameterised target family. Using the perturbative gadget reduction framework of Oliveira and Terhal and of Schuch and Verstraete, we adapt the arguments to parameterised interactions and demonstrate the error bounds in the resulting simulation can be controlled. Additionally, we provide an explicit proof that families of 1-local Hamiltonians have a Berry phase that can be efficiently computed to inverse-polynomial precision. This establishes a complexity transition between 1-local and 2-local Hamiltonian families.
The 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 BQP\mathsf{BQP}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 UQMA∩co\mathsf{UQMA} \cap \mathsf{co}UQMA∩co-UQMA\mathsf{UQMA}UQMA-completeness when we have an a priori\textit{a priori}a priori bound for the ground-state energy. Here, UQMA\mathsf{UQMA}UQMA is the unique witness version of QMA\mathsf{QMA}QMA, and UQMA∩co\mathsf{UQMA} \cap \mathsf{co}UQMA∩co-UQMA\mathsf{UQMA}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 UQMA∩co\mathsf{UQMA} \cap \mathsf{co}UQMA∩co-UQMA\mathsf{UQMA}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.
We prove that recognizing the phase of matter of an unknown quantum state is quantum computationally hard. More specifically, we show that the quantum computational time of any phase recognition algorithm must grow exponentially in the range of correlations ξξξ of the unknown state. This exponential growth renders the problem practically infeasible for even moderate correlation ranges, and leads to super-polynomial quantum computational time in the system size nnn whenever ξ=ω(log⁡n)ξ= ω(\log n)ξ=ω(logn). Our results apply to a substantial portion of all known phases of matter, including symmetry-breaking phases and symmetry-protected topological phases for any discrete on-site symmetry group in any spatial dimension. To establish this hardness, we extend the study of pseudorandom unitaries (PRUs) to quantum systems with symmetries. We prove that symmetric PRUs exist under standard cryptographic conjectures, and can be constructed in extremely low circuit depths. We also establish hardness for systems with translation invariance and purely classical phases of matter. A key technical limitation is that the locality of the parent Hamiltonians of the states we consider is linear in ξξξ; the complexity of phase recognition for Hamiltonians with constant locality remains an important open question.
The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of simulating such geometrically local systems on quantum computers. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that simulating short-time dynamics is at least as hard as polynomial-time and linear-space probabilistic classical computation. Third, we show that the computational complexity of simulating long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.
The universal scaling of critical behavior in phase transitions is a cornerstone of physics. Dynamical quantum phase transitions (DQPTs) are their nonequilibrium analogues: abrupt nonanalyticities that emerge as a quantum system evolves in time. Yet the hardness and cost of detecting this phenomenon remain largely unexplored. We prove that estimating DQPT to a certain precision is intractable even for quantum computers, whereas deciding a subsystem variant of DQPT is as hard as simulating generic quantum circuits, implying a provable exponential quantum advantage. Furthermore, to search for critical times of local DQPTs, we show a quadratically faster quantum algorithm that estimates observables of Hamiltonian dynamics at multiple time points with Heisenberg-limited precision and sublinear scaling in the number of time points. Moreover, through encoding classical evolution into quantum dynamics, our framework enables broader quantum speedups for detecting anomalous phenomena in classical systems.