Computational complexity of Berry phase estimation in topological phases of matter
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 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).Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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).Where the paper says it
Where the paper says it
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 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 . 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.Where the paper says it
Where the paper says it
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 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. 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).Where the paper says it
Where the paper says it
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 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). 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).Where the paper says it
Where the paper says it
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 Identifying the computational complexity of computing the
Chern number seems to be an interesting open question. Relation to holonomic quantum computation. 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. [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. 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). 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). [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. [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. [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. [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. 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. 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. 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).Where the paper says it
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. 7Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 BPE with known guiding state is BQP-complete (Theorem 1). BPE with energy threshold is UQMA ∩ co-UQMA-complete (Theorem 3). 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).Where the paper says it
Where the paper says it
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 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. 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 paper says it
Where the paper says it
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 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. 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 . 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. 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 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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? 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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
-
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).
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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
- On the complexity of unique quantum witnesses and quantum approximate counting
- An Elementary Proof of the Quantum Adiabatic Theorem
- Improved Hardness Results for the Guided Local Hamiltonian Problem
- Efficient Berry Phase Calculation via Adaptive Variational Quantum Computing Approach
- Quantum computing topological invariants of two-dimensional quantum matter
- The complexity of antiferromagnetic interactions and 2D lattices
- An Information-Theoretic Proof of the Constructive Commutative Quantum Lov'asz Local Lemma
- A Note on the Complexity of the Spectral Gap Problem
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements