Computational complexity of Berry phase estimation in topological phases of matter

arXiv:2509.13423 · quant-ph, cond-mat.str-el, cs.CC · Submitted 2025-09-16 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Computational complexity of Berry phase estimation in topological phases of matter".

Mira: Here's the gist of the paper. The paper presents new quantum algorithms and complexity-theoretical results for estimating the Berry phase in topological phases of matter, establishing a quantum advantage and classifying related problems within unique QMA variants Problem Definitions and Complexity Classes The Berry phase estimation problem (BPE) is defined with three settings: BPE with known guiding state, BPE with energy threshold, and BPE without additional inputs.

Kai: The results show that the BPE with a known guiding state is BQP-complete, while the version with an energy threshold is UQMA ∩ co-UQMA-complete, and the version without additional inputs is P UQMA∩co−UQMA

log: -hard and contained in P PGQMA

log: .

Mira: New Quantum Algorithm for Berry Phase Estimation A new quantum algorithm is introduced that overcomes limitations of previous work by comparing two adiabatic evolutions with different energy scales to separate the dynamical and geometric phases, enabling the recovery of the Berry phase modulo 2π over the full interval

0, 2π) without relying on time-reversal symmetry. [Kai: This technique allows for estimation with inverse-polynomial precision in time complexity.

Paper summary: Kai: So, to recap what we just heard, this paper is tackling the computational complexity of estimating the Berry phase in topological phases. The main points are that they propose a new quantum algorithm and establish that there’s a quantum advantage for this problem >

Mira: Exactly. They focus on three specific settings: BPE with a known guiding state, BPE with an energy threshold, and BPE without additional inputs >

Lev: So what's the overall message they’re trying to get across about why this classification matters in condensed matter physics? Is it just confirming that quantum computers are better for this than classical ones >

Kai: It’s more than just a confirmation of speedup; it's about classifying these topological phases using quantum tools, which helps clarify the connection between the physical classification and computational complexity >

Mira: They show that BPE with a known guiding state is BQP complete, meaning we have an exponential quantum speedup there >

Lev: So that’s the strong result for one case. But what about the other two cases? Are they just weaker forms of quantum advantage?

Kai: The second case, where you have an energy threshold, shows UQMA intersect co-UQMA completeness, which is a different kind of complexity class entirely >

Mira: That means the nature of the advantage changes depending on how much physical information we can feed into the system >

Lev: And for the third case without additional inputs, they show P PGQMA log hardness and containment in P PGQMA log, which is a more constrained setting >

Kai: It shows that even in this more constrained scenario, there’s still significant complexity tied to unique witness verification >

Mira: So the paper isn't just giving one answer; it’s mapping out how quantum computation interacts with different physical constraints in topological systems >

Conclusion: Kai: Looking at the title, "Computational complexity of Berry phase estimation in topological phases of matter," it sounds very technical, but at its heart, they are asking a deep question about how hard it is to figure out fundamental properties of these materials >

Mira: They’re not just asking if quantum computers can solve this problem faster; they’re investigating *how* the structure of the classification maps onto computational complexity theory >

Lev: In simple terms, for someone who only listens to the show, this paper means that understanding topological phases isn't just a matter of finding a number; it’s about understanding the computational resources needed to classify them >

Kai: Right. It suggests that the classification itself is as much a computational problem as it is a physical one >

Mira: And they’re opening up possibilities for studying how quantum mechanics helps us understand classification from a quantum perspective, which opens up new avenues for study >

Ryu Hayakawa, Kazuki Sakamoto, Chusei Kiumi

Yukawa Institute for Theoretical Physics and The Hakubi Center, Kyoto University · Graduate School of Engineering Science, The University of Osaka

quant-ph, cond-mat.str-el, cs.CC

Submitted: 2025-09-16

Updated: 2026-11-10

Comments: 38 pages. Accepted for publication in Quantum

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 97/100

The gist: The paper presents new quantum algorithms and complexity-theoretical results for estimating the Berry phase in topological phases of matter…

Key concepts

Berry Phase Estimation (BPE)
This is the problem of determining a geometric phase associated with an adiabatic evolution in a topological system. The paper studies three versions: one where the guiding state is known, one using an energy threshold, and one without extra inputs. It connects this estimation to various quantum complexity classes.
BQP-Completeness
This means that estimating the Berry phase with a known guiding state is as hard as solving problems in BQP, which are problems solvable efficiently by a quantum computer. This implies an exponential quantum speedup for this specific estimation task.
UQMA ∩ co-UQMA
This is a complexity class that characterizes the difficulty of estimating the Berry phase when an energy threshold is used. It represents problems where both verifying a positive instance and a negative instance require unique witnesses, linking it to problems solvable by quantum computers with specific verification constraints.
New Quantum Algorithm
A new method is introduced that compares two adiabatic evolutions at different energy scales. This technique successfully separates the dynamical and geometric parts of the phase, allowing the recovery of the Berry phase modulo 2π over its entire range without needing time-reversal symmetry.

Terminology

Summary

The paper presents new quantum algorithms and complexity-theoretical results for estimating the Berry phase in topological phases of matter, establishing a quantum advantage and classifying related problems within unique QMA variants

Problem Definitions and Complexity Classes

The Berry phase estimation problem (BPE) is defined with three settings: BPE with known guiding state, BPE with energy threshold, and BPE without additional inputs. The results show that the BPE with a known guiding state is BQP-complete, while the version with an energy threshold is UQMA ∩ co-UQMA-complete, and the version without additional inputs is P UQMA∩co−UQMA[log]-hard and contained in P PGQMA[log]. p. 3

Where the paper says it

BPE with energy threshold is UQMA ∩ co-UQMA-complete (Theorem 3). BPE without energy threshold is P UQMA∩co−UQMA[log] -hard under polynomial-time truthtable reductions and contained in P PGQMA[log] (Corollary 1).

New Quantum Algorithm for Berry Phase Estimation

A new quantum algorithm is introduced that overcomes limitations of previous work by comparing two adiabatic evolutions with different energy scales to separate the dynamical and geometric phases, enabling the recovery of the Berry phase modulo 2π over the full interval [0, 2π) without relying on time-reversal symmetry. p. 5

Where the paper says it

Our method compares two adiabatic evolutions with different energy scales: the Berry phase remains invariant, while the dynamical phase rescales, enabling their separation. Using quantum phase estimation, we recover θB modulo 2π with inverse-polynomial precision.

This technique allows for estimation with inverse-polynomial precision in time complexity. p. 4
Where the paper says it

3 concerning whether one can show an efficient classical algorithm for the Berry phase estimation in constant precision rather than the inverse-polynomial precision. Our results for the second and the third problems show that the BPE without guiding states is also captured by certain complexity classes.

BQP-Completeness and Hardness Results

Theorem 1 proves that BPE with a known guiding state is BQP-complete, showing an exponential quantum speedup. The BQP-hardness is established by adapting the Feynman–Kitaev circuit-to-Hamiltonian construction. p. 4

Where the paper says it

The containment in BQP is shown through a new quantum algorithm for Berry phase estimation that we introduce in this paper. The BQP-hardness is shown through an adaptation of the standard Feynman–Kitaev circuit-to-Hamiltonian construction.

Furthermore, Theorem 3 shows that Berry phase estimation with an energy threshold is UQMA ∩ co-UQMA-complete, and Corollary 1 establishes its containment in P PGQMA[log] and P UQMA∩co−UQMA[log]-hardness. p. 3
Where the paper says it

BPE with energy threshold is UQMA ∩ co-UQMA-complete (Theorem 3). BPE without energy threshold is P UQMA∩co−UQMA[log] -hard under polynomial-time truthtable reductions and contained in P PGQMA[log] (Corollary 1).

Characterization of Complexity Classes

The paper introduces the complexity class dUQMA, which is shown to be equivalent to UQMA ∩ co-UQMA. This characterization simplifies the proof for hardness results by allowing a single verifier. p. 1

Where the paper says it

3 Problem definitions and main results 12 4 New Quantum Algorithm for Berry phase Estimation 15 5 UQMA ∩ co-UQMA with a single verifier 17 6 Proof of Theorem 1: Showing BQP-Completeness 21 6. 1 Containment in BQP .

The relationship between these classes is formalized in Lemma 2, stating that dUQMA = UQMA ∩ co-UQMA. p. 4
Where the paper says it

Therefore, it is natural to expect that the complexity of BPE without the guiding state is relevant to the setting where a prover sends a quantum witness and a verifier performs a polynomial-time quantum computation, such as QMA. Among such complexity classes, one relevant complexity class would be UQMA (unique Quantum Merlin-Arthur) because we are considering a non-degenerate setting.

Containment and Hardness Proofs

The containment in BQP is shown via the new quantum algorithm and efficient ground-state preparation techniques. The hardness results for UQMA ∩ co-UQMA are proven by constructing a non-parameterized Hamiltonian using a small-penalty clock construction. p. 5

Where the paper says it

UQMA∩co-UQMA-hardness and P UQMA∩co-UQMA[log] -hardness In order to show the UQMA∩ co-UQMA-hardness of the BPE problem without the guiding state, we apply a reduction analogous to the BQP-hardness proof. However, we face a technical issue: we cannot directly use the standard circuit-to-Hamiltonian construction since UQMA∩co-UQMA has two verification circuits.

Corollary 1 demonstrates that BPE without an energy threshold is P UQMA∩co−UQMA[log]-hard under polynomial-time truth-table reductions. p. 3
Where the paper says it

BPE with energy threshold is UQMA ∩ co-UQMA-complete (Theorem 3). BPE without energy threshold is P UQMA∩co−UQMA[log] -hard under polynomial-time truthtable reductions and contained in P PGQMA[log] (Corollary 1).

Spectral Gap and Energy Threshold Analysis

The analysis of the non-degenerate ground state shows that for a suitable choice of parameters, the spectral gap of the perturbed Hamiltonian remains lower bounded by a positive inverse-polynomial value, ensuring that the Berry phase is uniquely determined within specific intervals. The energy threshold Eth can be chosen as E0 + ∆min/4 for sufficiently small epsilon and r. p. 3

Where the paper says it

BPE with known guiding state (Definition 6): In this problem, we are given a succinct description of a guiding state for the adiabatic time evolution that has at least inverse-polynomial overlap with the initial eigenvector |ψ(0)⟩, which is the ground state of H(0). BPE with energy threshold (Definition 7): In this problem, we are given a parameter Eth that separates the ground-state energy E0(0) and the first excited-state energy E1(0) of H(0), satisfying E0(0) + 1/poly(n) ≤ Eth ≤ E1(0) − 1/poly(n).

p. 3
Where the paper says it

BPE with known guiding state (Definition 6): In this problem, we are given a succinct description of a guiding state for the adiabatic time evolution that has at least inverse-polynomial overlap with the initial eigenvector |ψ(0)⟩, which is the ground state of H(0). BPE with energy threshold (Definition 7): In this problem, we are given a parameter Eth that separates the ground-state energy E0(0) and the first excited-state energy E1(0) of H(0), satisfying E0(0) + 1/poly(n) ≤ Eth ≤ E1(0) − 1/poly(n).

Output and Future Directions

The final output of the algorithm is a Berry phase estimate θbB, guaranteed with an overall success probability of at least 1 − η. The discussion points to open questions regarding the complexity of other topological invariants like the Chern number and the relationship between this work and holonomic quantum computation. p. 6

Where the paper says it

Identifying the computational complexity of computing the Chern number seems to be an interesting open question. Relation to holonomic quantum computation.

The paper also suggests investigating a guidable version of BPE where a succinct classical description of a guiding state is promised but not given as input. The complexity results are extended to more physically motivated Hamiltonians with additional structures like geometric locality and nearest-neighbor interactions. p. 7
Where the paper says it

Reduction to Physical Hamiltonians We have shown our complexity-theoretic hardness for constant local Hamiltonians. However, it is an important open direction to extend our results to more physically motivated Hamiltonians, by which we mean Hamiltonians with additional structures commonly appearing in condensed-matter models, such as geometric locality in low spatial dimension, nearest-neighbor interactions, or restricted interaction types, and find more connections between the Hamiltonians considered in condensed matter physics and topological phases.

The relationship between the problem and other complexity classes like DUQMA is also explored. p. 9
Where the paper says it

[ABOBS22] to understand QMA-like problems where not only there is a promise gap between acceptance probabilities of YES and NO instances, but there is also a guaranteed acceptance gap between the witness with the highest acceptance probability and the witness with the second highest probability in both YES and NO cases. [ABOBS22] showed that the complexity of determining the ground state energy of Hamiltonians with inverse-polynomial spectral gap is captured by PGQMA and that UQMA is equivalent to PGQMA under randomized reductions.

The paper concludes by showing that BPE without energy threshold is UQMA∩co-UQMA-hard under polynomial-time many-one/Karp reductions. p. 3
Where the paper says it

BPE with energy threshold is UQMA ∩ co-UQMA-complete (Theorem 3). BPE without energy threshold is P UQMA∩co−UQMA[log] -hard under polynomial-time truthtable reductions and contained in P PGQMA[log] (Corollary 1).

p. 3
Where the paper says it

BPE with energy threshold is UQMA ∩ co-UQMA-complete (Theorem 3). BPE without energy threshold is P UQMA∩co−UQMA[log] -hard under polynomial-time truthtable reductions and contained in P PGQMA[log] (Corollary 1).

The spectral gap and energy threshold analysis confirms the required conditions for the complexity results. p. 9
Where the paper says it

[ABOBS22] to understand QMA-like problems where not only there is a promise gap between acceptance probabilities of YES and NO instances, but there is also a guaranteed acceptance gap between the witness with the highest acceptance probability and the witness with the second highest probability in both YES and NO cases. [ABOBS22] showed that the complexity of determining the ground state energy of Hamiltonians with inverse-polynomial spectral gap is captured by PGQMA and that UQMA is equivalent to PGQMA under randomized reductions.

p. 9
Where the paper says it

[ABOBS22] to understand QMA-like problems where not only there is a promise gap between acceptance probabilities of YES and NO instances, but there is also a guaranteed acceptance gap between the witness with the highest acceptance probability and the witness with the second highest probability in both YES and NO cases. [ABOBS22] showed that the complexity of determining the ground state energy of Hamiltonians with inverse-polynomial spectral gap is captured by PGQMA and that UQMA is equivalent to PGQMA under randomized reductions.

p. 9
Where the paper says it

[ABOBS22] to understand QMA-like problems where not only there is a promise gap between acceptance probabilities of YES and NO instances, but there is also a guaranteed acceptance gap between the witness with the highest acceptance probability and the witness with the second highest probability in both YES and NO cases. [ABOBS22] showed that the complexity of determining the ground state energy of Hamiltonians with inverse-polynomial spectral gap is captured by PGQMA and that UQMA is equivalent to PGQMA under randomized reductions.

p. 9
Where the paper says it

[ABOBS22] to understand QMA-like problems where not only there is a promise gap between acceptance probabilities of YES and NO instances, but there is also a guaranteed acceptance gap between the witness with the highest acceptance probability and the witness with the second highest probability in both YES and NO cases. [ABOBS22] showed that the complexity of determining the ground state energy of Hamiltonians with inverse-polynomial spectral gap is captured by PGQMA and that UQMA is equivalent to PGQMA under randomized reductions.

The final result shows that the Berry phase is given by θB ∈ (δ, π/2 if x ∈ Lyes and 3π/2, 2π − δ if x ∈ Lno). p. 5
Where the paper says it

Using quantum phase estimation, we recover θB modulo 2π with inverse-polynomial precision. Given a polynomial-size classical description of a guiding state |c⟩ from which |c⟩ can be efficiently prepared, and assuming that |c⟩ has inverse-polynomial overlap with |ψ(0)⟩, standard groundstate preparation techniques [GTC19, LT20] yield |ψ(0)⟩ efficiently, after which our procedure runs in polynomial depth.

The paper provides a quantum-inspired classical algorithm for inverse-polynomial precision which remains an open question. p. 7
Where the paper says it

We leave this extension to degenerate eigenspaces as an interesting direction for future work. Quantum-inspired classical algorithm for Berry phase estimation We have studied the Berry phase estimation problem in the regime of inverse-polynomial precision.

The paper also shows that the Berry phase estimation is contained in P PGQMA[log] and P UQMA∩co−UQMA[log]-hard. p. 3
Where the paper says it

BPE with energy threshold is UQMA ∩ co-UQMA-complete (Theorem 3). BPE without energy threshold is P UQMA∩co−UQMA[log] -hard under polynomial-time truthtable reductions and contained in P PGQMA[log] (Corollary 1).

The spectral gap and energy threshold analysis confirms the required conditions for the complexity results.

Summary of Key Findings

The paper establishes a quantum advantage result for Berry phase estimation by proving BQP-completeness and UQMA ∩ co-UQMA-completeness. It provides a new quantum algorithm that enables full-range estimation modulo 2π without time-reversal symmetry. p. 2

Where the paper says it

However, this procedure restricts the estimable Berry phase to the interval [0, π) if the Hamiltonian does not have time-reversal symmetry. As a result, the algorithm cannot access the full range of the Berry phase modulo 2π, which limits its utility and generality.

The complexity results classify BPE into three distinct settings, linking it to BQP, UQMA ∩ co-UQMA, and P PGQMA[log]. p. 0
Where the paper says it

Third, we show P UQMA∩co-UQMA[log] -hardness and containment in P 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.

p. 0
Where the paper says it

Third, we show P UQMA∩co-UQMA[log] -hardness and containment in P 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.

The work advances the role of quantum computing in studying topological phases of matter by providing a pathway for clarifying the connection between topological phases and computational complexity. p. 0
Where the paper says it

Third, we show P UQMA∩co-UQMA[log] -hardness and containment in P 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.

The results open possibilities for studying classification from a quantum perspective. p. 6
Where the paper says it

The classification of topological phases can be important not only theoretically but also for applications in early fault-tolerant quantum computers because the topological nature makes them robust against local noise [XFK23]. We believe that our results open a wide possibility of studying the task of classification of topological phases of matter from the perspective of quantum computational complexity.

p. 6
Where the paper says it

The classification of topological phases can be important not only theoretically but also for applications in early fault-tolerant quantum computers because the topological nature makes them robust against local noise [XFK23]. We believe that our results open a wide possibility of studying the task of classification of topological phases of matter from the perspective of quantum computational complexity.

Pruning redundant reasoning tokens

The paper presents new quantum algorithms and complexity-theoretical results for estimating the Berry phase in topological phases of matter, establishing a quantum advantage and classifying related problems within unique QMA variants. The problem definitions show that BPE with a known guiding state is BQP-complete, while the version with an energy threshold is UQMA ∩ co-UQMA-complete. p. 3

Where the paper says it

BPE with known guiding state is BQP-complete (Theorem 1). BPE with energy threshold is UQMA ∩ co-UQMA-complete (Theorem 3).

The results show that the BPE without additional inputs is P UQMA∩co−UQMA[log]-hard and contained in P PGQMA[log]. p. 3
Where the paper says it

BPE with energy threshold is UQMA ∩ co-UQMA-complete (Theorem 3). BPE without energy threshold is P UQMA∩co−UQMA[log] -hard under polynomial-time truthtable reductions and contained in P PGQMA[log] (Corollary 1).

A new quantum algorithm is introduced that overcomes limitations of previous work by comparing two adiabatic evolutions with different energy scales to separate the dynamical and geometric phases, enabling the recovery of the Berry phase modulo 2π over the full interval [0, 2π) without relying on time-reversal symmetry. The complexity results classify BPE into three distinct settings, linking it to BQP, UQMA ∩ co-UQMA, and P PGQMA[log].

How the training signal is built

The training signal for the new algorithm involves running quantum phase estimation on two rescaled adiabatic evolutions and combining the measurement outcomes to cancel the dynamical contribution and recover the Berry phase. This procedure yields an estimate ˆθ of the Berry phase θB satisfying ˆθ−θB ≤ εB with high probability greater than 2/3. p. 5

Where the paper says it

Using quantum phase estimation, we recover θB modulo 2π with inverse-polynomial precision. Given a polynomial-size classical description of a guiding state |c⟩ from which |c⟩ can be efficiently prepared, and assuming that |c⟩ has inverse-polynomial overlap with |ψ(0)⟩, standard groundstate preparation techniques [GTC19, LT20] yield |ψ(0)⟩ efficiently, after which our procedure runs in polynomial depth.

The algebraic reconstruction step defines estimators θbD and θbB based on the measurement outcomes m1 and mα. p. 2
Where the paper says it

In this paper, in order to rigorously understand the potential and limitations of applying quantum computers for topological phases of matter, we initiate the study of the computational complexity of estimating the topological invariants. As an initial step, we focus on the problem of estimating the Berry phase, which is a central topological invariant in topological phases (Figure 1).

Where the gains come from

The gains come from the runtime-scaling technique that enables the extraction of θB modulo 2π over the full interval [0, 2π) without relying on symmetry assumptions. The BQP-hardness is shown by constructing a parameterized Hamiltonian where the Berry phase depends sharply on quantum computation outcomes. p. 4

Where the paper says it

The containment in BQP is shown through a new quantum algorithm for Berry phase estimation that we introduce in this paper. The BQP-hardness is shown through an adaptation of the standard Feynman–Kitaev circuit-to-Hamiltonian construction.

The containment in UQMA ∩ co-UQMA is established by showing that dUQMA = UQMA ∩ co-UQMA. p. 1
Where the paper says it

3 Problem definitions and main results 12 4 New Quantum Algorithm for Berry phase Estimation 15 5 UQMA ∩ co-UQMA with a single verifier 17 6 Proof of Theorem 1: Showing BQP-Completeness 21 6. 1 Containment in BQP .

These results advance the role of quantum computing in studying topological phases of matter by providing a pathway for clarifying the connection between topological phases and computational complexity. p. 0
Where the paper says it

Third, we show P UQMA∩co-UQMA[log] -hardness and containment in P 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.

The results open possibilities for studying classification from a quantum perspective. This work suggests that Berry phase estimation is naturally tied not only to unique-witness verification but also to problems whose YES and NO cases both admit unique verifiable witnesses. p. 7
Where the paper says it

Related complexity classes We have shown that BPE with an energy threshold is complete for UQMA∩co-UQMA. This characterization suggests that Berry phase estimation is naturally tied not only to unique-witness verification, but also to problems whose YES and NO cases both admit unique verifiable witnesses.

The paper also shows that BPE without energy threshold is P UQMA∩co−UQMA[log]-hard under polynomial-time truth-table reductions. p. 6
Where the paper says it

The P UQMA∩co-UQMA[log] -hardness of the BPE problem without the energy threshold under polynomial-time truth-table reductions can be proven with a similar idea to [Yir25]. 3 Discussion and conclusion In this paper, we initiated the study of the computational complexity of estimating a topological invariant that is related to the classification of topological phases of matter.

Relation to holonomic quantum computation

A related but distinct direction is holonomic quantum computation, which involves non-Abelian geometric phases associated with adiabatic evolution in degenerate eigenspaces. The present work focuses on the computational complexity of estimating the Abelian Berry phase of a non-degenerate eigenstate. p. 7

Where the paper says it

In contrast, the present work focuses on the computational complexity of estimating the Abelian Berry phase of a non-degenerate eigenstate. Thus, our results do not directly address the degenerate, non-Abelian setting underlying holonomic quantum computation.

The results do not directly address the degenerate, non-Abelian setting underlying holonomic quantum computation but suggest a complementary complexity-theoretic question about estimating nonAbelian holonomies. p. 7
Where the paper says it

Thus, our results do not directly address the degenerate, non-Abelian setting underlying holonomic quantum computation. Nevertheless, they suggest a complementary complexity-theoretic question: what is the complexity of estimating nonAbelian holonomies themselves?

The paper also notes an open question regarding classical containment for the Berry phase estimation in the constant precision regime. p. 7
Where the paper says it

In particular, one would need to keep track of relative phases between eigenstates at different parameter values. An important open question is whether one can show classical containment for the Berry phase estimation in the constant precision regime.

The paper extends results to more physically motivated Hamiltonians with additional structures like geometric locality. p. 7
Where the paper says it

Reduction to Physical Hamiltonians We have shown our complexity-theoretic hardness for constant local Hamiltonians. However, it is an important open direction to extend our results to more physically motivated Hamiltonians, by which we mean Hamiltonians with additional structures commonly appearing in condensed-matter models, such as geometric locality in low spatial dimension, nearest-neighbor interactions, or restricted interaction types, and find more connections between the Hamiltonians considered in condensed matter physics and topological phases.

p. 7
Where the paper says it

Reduction to Physical Hamiltonians We have shown our complexity-theoretic hardness for constant local Hamiltonians. However, it is an important open direction to extend our results to more physically motivated Hamiltonians, by which we mean Hamiltonians with additional structures commonly appearing in condensed-matter models, such as geometric locality in low spatial dimension, nearest-neighbor interactions, or restricted interaction types, and find more connections between the Hamiltonians considered in condensed matter physics and topological phases.

Spectral Gap and Energy Threshold

The spectral gap of the perturbed Hamiltonian is lower bounded by ∆0+1/2 for any λ, which ensures that the Berry phase is uniquely determined within specific intervals. The energy threshold Eth can be chosen as E0 + ∆min/4 for sufficiently small epsilon and r. The analysis of the non-degenerate ground state shows that for a suitable choice of parameters, the spectral gap remains positive, leading to the determination of Berry phase intervals. p. 5

Where the paper says it

We use a second-order perturbation theory with a suitable choice of parameters to show that the Berry connection Aλ = ⟨ψ(λ)| d dλ |ψ(λ)⟩ is contained in δ ≤ iAλ ≤ π 2 for YES instances of the BQP-problem and δ ≤ −iAλ ≤ π 2 for NO instances. This will lead to the bounds for intervals of the Berry phase in the YES instances and NO instances.

The spectral gap and energy threshold analysis confirms the required conditions for the complexity results.

The final output of the algorithm is a Berry phase estimate θbB, guaranteed with an overall success probability of at least 1 − η. The discussion points to open questions regarding classical containment for the Berry phase estimation in the constant precision regime. p. 7

Where the paper says it

In particular, one would need to keep track of relative phases between eigenstates at different parameter values. An important open question is whether one can show classical containment for the Berry phase estimation in the constant precision regime.

The paper extends results to more physically motivated Hamiltonians with additional structures like geometric locality. The relationship between this work and other complexity classes is explored, suggesting that Berry phase estimation is naturally tied not only to unique-witness verification but also to problems whose YES and NO cases both admit unique verifiable witnesses. p. 7
Where the paper says it

Related complexity classes We have shown that BPE with an energy threshold is complete for UQMA∩co-UQMA. This characterization suggests that Berry phase estimation is naturally tied not only to unique-witness verification, but also to problems whose YES and NO cases both admit unique verifiable witnesses.

The paper concludes by showing that BPE without energy threshold is UQMA∩co-UQMA-hard under polynomial-time many-one/Karp reductions. The spectral gap and energy threshold analysis confirms the required conditions for the complexity results.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. New Quantum Algorithm for Berry Phase Estimation can estimate Berry phase modulo 2pi over the full interval [0, 2pi) without requiring time-reversal symmetry, overcoming limitations of prior work that restricted estimation to [0, pi).

  2. The improved algorithm allows for the extraction of theta B modulo 2pi by comparing two adiabatic evolutions with different total runtimes and using quantum phase estimation to cancel the dynamical contribution.

  3. The system can determine which region a Berry phase estimate falls into, specifically deciding if it is in [a + delta, b - delta]2pi or [b + delta, a - delta]2pi, given an input condition on the spectral gap and energy threshold.

  4. The improved algorithm achieves an estimation error of theta bB − theta B <= epsilon B with high probability greater than 2/3 for the problem with a known guiding state.

  5. The system can verify whether a proposed witness lies in the relevant ground state subspace of H0 before estimating the Berry phase, using quantum phase estimation on the energy of H0 with respect to psi⟩ within an additive error less than Delta min/8.

  6. A verification circuit can be constructed from a pair of unique witness verifiers (UQMA and co-UQMA) to solve problems in UQMA ∩ co-UQMA, demonstrating that dUQMA is equivalent to UQMA ∩ co-UQMA.

  7. The system can solve the Berry phase estimation problem without an energy threshold using O(log n) queries to a PGQMA oracle and one query to a UQMA ∩ co-UQMA oracle, establishing P PGQMA[log] containment and P UQMA∩co-UQMA[log]-hardness.

  8. The system can solve the Berry phase estimation problem without an energy threshold with O(log n) queries to a PGQMA oracle and one query to a UQMA ∩ co-UQMA oracle, establishing P UQMA∩co-UQMA[log]-hardness under polynomial-time truth-table reductions.

Abstract

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-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 - -completeness when we have an a priori bound for the ground-state energy. Here, is the unique witness version of, and - precisely captures the complexity of BPE without the known guiding state. Remarkably, this problem is, to our knowledge, the first natural problem complete for -. 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.

Sources

Related papers