Computational complexity of Berry phase estimation in topological phases of matter

• URL: http://arxiv.org/abs/2509.13423v1
• Date: Tue, 16 Sep 2025 18:01:20 GMT
• Title: Computational complexity of Berry phase estimation in topological phases of matter
• Abstract summary: We present a new quantum algorithm for the Berry phase estimation problems.<n>For the complexity-theoretic results, we consider three cases.<n>Remarkably, this problem turned out to be the first natural problem contained in both $mathsfUQMA$ and $mathsfUQMA$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 three cases. First, we prove $\mathsf{BQP}$-completeness when we are given a guiding state that has a large overlap with the ground state. This result establishes an exponential quantum speedup for estimating the Berry phase. Second, we prove $\mathsf{dUQMA}$-completeness when we have \textit{a priori} bound for ground state energy. Here, $\mathsf{dUQMA}$ is a variant of the unique witness version of $\mathsf{QMA}$ (i.e., $\mathsf{UQMA}$), which we introduce in this paper, and this class precisely captures the complexity of BPE without the known guiding state. Remarkably, this problem turned out to be the first natural problem contained in both $\mathsf{UQMA}$ and $\mathsf{co}$-$\mathsf{UQMA}$. Third, we show $\mathsf{P}^{\mathsf{dUQMA[log]}}$-hardness and containment in $\mathsf{P}^{\mathsf{PGQMA[log]}}$ when we have no additional assumption. These results advance the role of quantum computing in the study of topological phases of matter and provide a pathway for clarifying the connection between topological phases of matter and computational complexity.

Related papers

• An Optimal Analysis of the Product Test [42.29010058743949]
  Product testing decides whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition.<n>Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined.<n>As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from $mathsfQMA(k)$ to $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2026-07-23T16:17:44Z)
• Efficient Complex-Valued State Preparation on Bucket Brigade QRAM [47.72095699729477]
  Efficient quantum state preparation is a critical component in quantum algorithms that process large classical data.<n>We present two improvements within the same architecture-aware framework.
  arXiv  Detail & Related papers  (2026-04-28T13:43:29Z)
• IQP circuits for 2-Forrelation [2.5782420501870296]
  2-Forrelation problem provides optimal separation between classical and quantum query complexity.<n>We show that 2-Forrelation can be solved using Instantaneous Quantum Polynomial-time ($mathsfIQP$) circuits.
  arXiv  Detail & Related papers  (2026-04-16T17:24:25Z)
• Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness [0.0]
  We introduce a broad class of quadratic bosonic problems for which we prove that they are $mathsfBQP$-complete.<n>We show that extending the aforementioned class to even more general quadratic Hamiltonians results in a $mathsfPostBQP$-hard problem.<n>This reveals a sharp transition in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.
  arXiv  Detail & Related papers  (2026-03-27T16:25:41Z)
• Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy [0.7321157455672144]
  We show that restricting quantum-classical PCPs unique to proofs does not reduce their power.<n>We also prove a non-uniform quantum analogue of the Karp-Lipton theorem.<n>These results offer new insights into the structure of quantum proof systems.
  arXiv  Detail & Related papers  (2025-06-24T16:59:50Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
  This work studies three quantum-verifier based generalizations of $mathsfPH$. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for $mathsfQCPH$. We show one-sided error reduction for $mathsfpureQPH$, as well as the first bounds relating these quantum variants of $mathsfPH$.
  arXiv  Detail & Related papers  (2024-01-03T09:12:25Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations. We show that there exist (efficient) local producing measurements that cannot be reproduced through randomness and quantum-time computation.
  arXiv  Detail & Related papers  (2023-03-03T16:53:30Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
  We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with $mathcal N=2 $ supersymmetry. Our main motivation for studying this is the fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial.
  arXiv  Detail & Related papers  (2021-06-30T18:00:01Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)
• Quantum aspects of chaos and complexity from bouncing cosmology: A study with two-mode single field squeezed state formalism [0.0]
  This paper is devoted to the study of out-of-equilibrium aspects and quantum chaos appearing in the universe. We use the $Out-of-Time Ordered correlation (OTOC)$ functions for probing the random behaviour of the universe both at early and the late times.
  arXiv  Detail & Related papers  (2020-09-08T16:10:52Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.