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

On the Computational Complexity of Guided Berry Phase Estimation

Gabriel Waite

quant-phcs.CCSubmitted Sep 22, 2026• Announced Sep 23, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks whether the known BQP-completeness of guided Berry-phase estimation for $5$-local Hamiltonian paths persists with two-body interactions and geometric restrictions. The problem supplies a classical description of an efficiently preparable guiding state with inverse-polynomial ground-state overlap and asks which of two separated arcs contains the ground-state Berry phase. It establishes BQP-completeness for $2$-local qubit Hamiltonians on square or triangular lattices, including weighted Heisenberg interactions with local fields. The promises include closed $C^2$ paths, unique ground states, inverse-polynomial spectral gaps, polynomially bounded Hamiltonian norms and first two derivatives, and inverse-polynomial phase resolution. For $1$-local paths, it gives a classical polynomial-time algorithm requiring no guiding state, establishing a locality boundary between membership in P and BQP-completeness. The reductions extend perturbative-gadget simulation to parameter-dependent families using Schrieffer–Wolff transformations and Kato parallel transport. Besides pointwise simulation error $\varepsilon$, Berry-phase control tracks the error derivative $\|\partial_s E\|_\infty$ and the derivative $\kappa$ of a closed low-energy identification isometry. The phase-error bound is $O(\gamma_*^{-2}L\varepsilon+\gamma_*^{-1}\|\partial_sE\|_\infty+\gamma_*^{-1}\varepsilon+\kappa)$, where $L$ bounds target and pulled-back simulator derivatives. Polynomial penalty strengths control these errors through a constant-depth gadget chain while preserving guiding-state overlap. The one-local algorithm uses cyclic products of single-qubit projectors with discretisation error $O(1/N)$ up to polynomial factors. The results retain the gap, regularity, nondegeneracy, and guiding-state promises. Extensions to other Berry-phase estimation variants, Fermi–Hubbard models, degenerate low-energy encodings, and exponential precision remain open.

Little sign of AI-generated textAI use disclosed
were used to assist with language and formatting, this included: grammar correction, sentence/statement restructuring, ensuring consistency in terminology throughout the manuscript, and assistance with summarising mathematical content.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
41 + 30 pages; 8 figures. v1: comments welcome

Related papers

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

Kazuki Sakamoto, Keisuke Fujii

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.

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

Physically motivated guiding states for local Hamiltonians

Gabriel Waite, Karl Lin, Samuel J. Elman +1 more

We study the computational complexity of the Guided Local Hamiltonian problem: given a local Hamiltonian $H$ together with a classical description of a guiding state that has non-negligible overlap with the ground state of $H$, estimate the ground-state energy within inverse-polynomial precision. This setting captures real-world scenarios in quantum chemistry and many-body physics, where trial states derived from classical heuristics can be used to guide quantum algorithms. We identify families of physically-motivated guiding states for which the computational hardness of ground-state energy estimation persists in the guided setting. Extending prior results for semi-classical subset states, we prove BQP-hardness for classes including fixed-weight states, matrix product states, Gaussian states, and Fendley states. Our hardness results are obtained via refined Feynman-Kitaev circuit-to-Hamiltonian constructions that explicitly expose the structural role of the guiding state in the reduction. Complementing these results, we give a constructive proof of BQP containment when the guiding state admits a polynomial-size classical description, establishing BQP-completeness for the canonical formulation of the problem. Our results show that quantum advantage persists for the newly introduced state classes, and classical methods also remain viable when said guiding states admit appropriate descriptions. Together, our results identify a Goldilocks zone of guiding states that are efficiently preparable, succinctly described, and sample-query accessible, within which quantum advantage for ground-state estimation can be meaningfully assessed. We additionally formalise the Guided Fermi-Hubbard Hamiltonian problem and prove BQP-completeness on 2D square and triangular lattices, both with and without magnetic fields, when provided with an appropriate fermionic guiding state.

arXiv:2509.25815•Physical Review A•Jun 8, 2026•6 citations

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States

Chris Cade, Marten Folkertsma, Gharibian, Sevag +4 more

Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.

arXiv:2207.10097•Leibniz international proceedings in informatics•Jul 20, 2022•19 citations

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

Improved Hardness Results for the Guided Local Hamiltonian Problem

Chris Cade, Marten Folkertsma, Sevag Gharibian +4 more

Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with $6$-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to $1/2$ with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.

arXiv:2207.10250•Jul 21, 2022•36 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 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
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 paper asks whether the known BQP-completeness of guided Berry-phase estimation for 555-local Hamiltonian paths persists with two-body interactions and geometric restrictions. The problem supplies a classical description of an efficiently preparable guiding state with inverse-polynomial ground-state overlap and asks which of two separated arcs contains the ground-state Berry phase.
It establishes BQP-completeness for 222-local qubit Hamiltonians on square or triangular lattices, including weighted Heisenberg interactions with local fields. The promises include closed C2C^2C2 paths, unique ground states, inverse-polynomial spectral gaps, polynomially bounded Hamiltonian norms and first two derivatives, and inverse-polynomial phase resolution. For 111-local paths, it gives a classical polynomial-time algorithm requiring no guiding state, establishing a locality boundary between membership in P and BQP-completeness.
The reductions extend perturbative-gadget simulation to parameter-dependent families using Schrieffer–Wolff transformations and Kato parallel transport. Besides pointwise simulation error ε\varepsilonε, Berry-phase control tracks the error derivative ∥∂sE∥∞\|\partial_s E\|_\infty∥∂s​E∥∞​ and the derivative κ\kappaκ of a closed low-energy identification isometry. The phase-error bound is O(γ∗−2Lε+γ∗−1∥∂sE∥∞+γ∗−1ε+κ)O(\gamma_*^{-2}L\varepsilon+\gamma_*^{-1}\|\partial_sE\|_\infty+\gamma_*^{-1}\varepsilon+\kappa)O(γ∗−2​Lε+γ∗−1​∥∂s​E∥∞​+γ∗−1​ε+κ), where LLL bounds target and pulled-back simulator derivatives. Polynomial penalty strengths control these errors through a constant-depth gadget chain while preserving guiding-state overlap. The one-local algorithm uses cyclic products of single-qubit projectors with discretisation error O(1/N)O(1/N)O(1/N) up to polynomial factors.
The results retain the gap, regularity, nondegeneracy, and guiding-state promises. Extensions to other Berry-phase estimation variants, Fermi–Hubbard models, degenerate low-energy encodings, and exponential precision remain open.
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.
We study the computational complexity of the Guided Local Hamiltonian problem: given a local Hamiltonian HHH together with a classical description of a guiding state that has non-negligible overlap with the ground state of HHH, estimate the ground-state energy within inverse-polynomial precision. This setting captures real-world scenarios in quantum chemistry and many-body physics, where trial states derived from classical heuristics can be used to guide quantum algorithms. We identify families of physically-motivated guiding states for which the computational hardness of ground-state energy estimation persists in the guided setting. Extending prior results for semi-classical subset states, we prove BQP-hardness for classes including fixed-weight states, matrix product states, Gaussian states, and Fendley states. Our hardness results are obtained via refined Feynman-Kitaev circuit-to-Hamiltonian constructions that explicitly expose the structural role of the guiding state in the reduction. Complementing these results, we give a constructive proof of BQP containment when the guiding state admits a polynomial-size classical description, establishing BQP-completeness for the canonical formulation of the problem. Our results show that quantum advantage persists for the newly introduced state classes, and classical methods also remain viable when said guiding states admit appropriate descriptions. Together, our results identify a Goldilocks zone of guiding states that are efficiently preparable, succinctly described, and sample-query accessible, within which quantum advantage for ground-state estimation can be meaningfully assessed. We additionally formalise the Guided Fermi-Hubbard Hamiltonian problem and prove BQP-completeness on 2D square and triangular lattices, both with and without magnetic fields, when provided with an appropriate fermionic guiding state.
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.
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.
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 666-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/21/21/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.
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.