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.

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•0 citations

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 three 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}$. Third, we show $\mathsf{P}^{\mathsf{UQMA} \cap \mathsf{co}\text{-}\mathsf{UQMA}\mathsf{[log]}}$-hardness and containment in $\mathsf{P}^{\mathsf{PGQMA[log]}}$ when we have no additional assumption. 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•0 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•0 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

DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians

Zhengfeng Ji, Tongyang Li, Changpeng Shao +2 more

We study the computational complexity of estimating the normalized trace $2^{-n}\mathrm{Tr}[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$. We show that if $f(x)$ is a continuous function with approximate degree $Ω(\mathrm{poly}(n))$, then estimating $2^{-n}\mathrm{Tr}[f(A)]$ up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of $f(x)$. This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when $A$ is sparse, the classical query complexity of this problem is exponential in the approximate degree. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.

quant-pharXiv:2604.01519•Apr 3, 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.
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 three 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. Third, we show PUQMA∩co-UQMA[log]\mathsf{P}^{\mathsf{UQMA} \cap \mathsf{co}\text{-}\mathsf{UQMA}\mathsf{[log]}}PUQMA∩co-UQMA[log]-hardness and containment in PPGQMA[log]\mathsf{P}^{\mathsf{PGQMA[log]}}PPGQMA[log] when we have no additional assumption. 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 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.
We study the computational complexity of estimating the normalized trace 2−nTr[f(A)]2^{-n}\mathrm{Tr}[f(A)]2−nTr[f(A)] for a log-local Hamiltonian AAA acting on nnn qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions f(x)f(x)f(x). We show that if f(x)f(x)f(x) is a continuous function with approximate degree Ω(poly(n))Ω(\mathrm{poly}(n))Ω(poly(n)), then estimating 2−nTr[f(A)]2^{-n}\mathrm{Tr}[f(A)]2−nTr[f(A)] up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of f(x)f(x)f(x). This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when AAA is sparse, the classical query complexity of this problem is exponential in the approximate degree. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.