CS Paper Radar

On the Computational Complexity of Guided Berry Phase Estimation

Gabriel Waite

cs.CC quant-ph ·submitted 2026-09-22 09:34 UTC · v1
theory

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.

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

Closest papers

Nearest neighbours by meaning across the whole index.

Out-of-control Hamiltonian Learning

cs.IT quant-phcs.LGphysics.atom-ph ·2026-10-05 ·Weiyuan Gong, Muzhou Ma, Sitan Chen, Jordan Cotler, Hsin-Yuan Huang
similarity 0.60
Abstract · 87 pages, 7 figures

Learning the Hamiltonian of a many-body system from its dynamics is a central task in quantum science, yet the algorithms with the strongest provable guarantees assume some level of quantum control--fast, arbitrary single-qubit gates interleaved with time evolution, and measurements in arbitrary bases--that is beyond the capabilities of near-term analog quantum simulators. Motivated by analog atom- and ion-based platforms, we study Hamiltonian learning under minimal access models. Uniform state preparation and measurements: We first consider the setting where in every experiment, one can rotate each qubit to the same state, perform short-time evolution, and measure every qubit in the same basis. Surprisingly, we show that for generic 2-local Hamiltonians on any interaction graph, all of the parameters can be reconstructed from such experiments. Computational basis state preparation and measurements: We then consider a similarly constrained setting, but where state preparation and measurement are restricted to the computational basis. For nearest-neighbor Hamiltonians with only Pauli $X/Z$ interactions, a class which captures contemporary Rydberg atom platforms, we show that over 1D and 2D rectangular lattices, all of the parameters can be reconstructed from such experiments up to unavoidable gauges. Our protocols introduce new techniques for solving structured polynomial systems over an extensive number of parameters. Taken together, our results suggest that one can learn a great deal from the dynamics of quantum many-body systems even under the most stringent experimental constraints.

0.15

AI for Parameter Selection in Sample-based Quantum Diagonalization

cs.AI physics.chem-ph ·2026-11-13 ·Doriela Grabocka, Dimitrios Christofidellis, Federico Zipoli, Anna van Elst, Patrick Ruch +3 more
similarity 0.58
Abstract

Sample-based Quantum Diagonalization (SQD) methods provide a way to compute molecular ground-state energies, but their accuracy and runtime depend sensitively on configuration choices such as the subspace dimension, propagation timestep, and the allocation of a fixed sampling budget across circuits, for which no formal selection method exists. In this work, we explore whether oracle models can predict the quantum runtime and approximation error from the Hamiltonian and the candidate configuration. Using synthetic Hamiltonians with controllable spectral properties, we show that machine-learned models can map a Hamiltonian directly to the best-ranked configuration within a predefined grid for the SKQD algorithm, validated against classical Krylov propagation, achieving strong rank correlations between true and predicted error and runtime, Spearman $ρ= 0.969$ and $ρ= 0.905$, respectively. Extending the approach to 50 molecular Hamiltonians (20-50 qubits), with reference ground-state energies from classical calculations, we train regressors that predict the simulation error and runtime for a given molecule--configuration pair ahead of execution, and classifiers to distinguish, from 600 SqDRIFT quantum-hardware runs, whether a configuration achieves a ground-state energy within chemical accuracy ($1.6\times10^{-3}$ Ha $\approx 1$ kcal/mol). For the molecular Hamiltonians, the models additionally provide an a priori feasibility and resource estimate, predicting whether a molecule can reach chemical accuracy on current hardware and at what runtime, thus correctly classifying held-out molecules at the molecule level, achieving balanced accuracy 61.8% in-distribution and 100% for five larger held-out molecules.

0.21

Autonomous phase discovery

cs.LG quant-phcond-mat.str-el ·2026-09-27 ·Shiyu Zhou, Yuxuan Zhang, Sebastian Wetzel, Roger Melko, Xiu-Zhe Luo
benchmarkcode/data similarity 0.58
Abstract · 10 pages, 5 figures, https://github.com/shiyu-zhou-7/diff_phase

Understanding quantum phases of matter has long relied on physicists' intuition and mathematical tools such as symmetry and topology. Remarkably successful as these approaches have been, they provide no universal way to explore a Hamiltonian space whose organizing principle is not known in advance. In this work, we introduce a fully autonomous system combining differentiable programming and unsupervised learning for quantum phase discovery. The search evaluates ground-state data along an adaptive trajectory rather than on a predetermined parameter grid. We demonstrate the system with three different solvers and benchmark it against random sampling at equal ground-state-evaluation budgets. On a generalized cluster chain hosting up to $200$ distinct phases, the search finds up to $25$ more phases at the same budget, and matches random sampling given thirty times its budget. On a $50$-parameter Chern insulator, it reaches sectors not obtained by the simple harmonic constructions considered here, in a family whose inverse problem remains open, while recovering all sectors found by sampling. Our results establish autonomous, gradient-driven exploration of Hamiltonian space as a practical route to discovering quantum phases without phase labels or a prescribed target phase.

0.38

Local Relaxation Hierarchies for Quantum Ground State Energies: Convergence Guarantees and Message Passing Algorithms

cs.DC quant-ph ·2026-09-30 ·Sheng-Ku Lin, Ricardo Rivera Cardoso, Roberto Bondesan
benchmarkcode/datahot direction similarity 0.57
Abstract · 39 pages, 4 figures

Convex relaxation hierarchies provide lower bounds to the ground state energy of quantum many-body systems that can be computed in polynomial time on a classical computer, at any fixed hierarchy level. However, scaling these methods to large systems and accurate approximations remains challenging due to the computational cost of traditional solvers and the scarcity of efficiency guarantees. In this work, we develop local relaxation hierarchies and efficient, highly parallelisable message passing algorithms for estimating the relaxed ground state energies. We show that the first level of the hierarchy---based on local consistency of pairwise reduced density matrices---is exact for commuting Hamiltonians on trees. We further establish that another hierarchy, based on consistent intervals, converges exponentially fast in the interval size to the ground state energy for weak perturbations of separable Hamiltonians on a chain, thereby providing an efficient classical algorithm for these systems. Then, we introduce two variants of message passing algorithms that run in $\mathcal{O}(n/ε^2)$ and $\mathcal{O}(n/ε)$ time for any fixed level of the local hierarchy on bounded-degree graphs, where $ε$ is the precision for the relaxed ground state energy per site. This assumes that the optimal messages have $\mathcal{O}(1)$ norm---a condition we observe in practical settings in our experiments. These algorithms are based on the subgradient method and the Nesterov-type accelerated gradient descent method applied to an entropy-smoothed objective. Finally, we benchmark the message passing algorithms across different quantum Hamiltonians, lattice geometries, and relaxation levels, validating the theoretical predictions and their potential to surpass standard convex optimisation solvers for this problem. We release the resulting library at github.com/rick1924/gse-message-passing.

0.44

Fully quantum training of parametric circuits with Quantum Hamiltonian Descent

cs.LG quant-ph ·2026-10-23 ·Marco Burato, Leonardo Banchi
benchmarktheory similarity 0.57
Abstract

Parametric quantum circuits are usually trained by classical, local optimizers, which use the quantum computer only to evaluate the cost function, or its gradient, one point at a time. Quantum Hamiltonian Descent (QHD) takes a different route: in this quantum algorithm for continuous optimization, the parameters become the position of a quantum particle, with the cost function as its potential, and two time schedules control kinetic and potential energy so that the wavefunction explores the whole landscape and tunnels towards the global minimum. QHD, however, assumes a classically computable cost function, and its digital implementation is poorly understood: standard error bounds grow exponentially with the number of qubits per parameter, and the schedules are borrowed from classical optimization. Here we propose to train parametric circuits with QHD entirely on the quantum computer, through an online step in which the qubits encoding the parameters coherently control the circuit on a second register. We prove that, for cost functions with a smooth periodic extension, including those of parametric circuits, the simulation error admits a bound independent of the grid resolution, and that for circuits the bound grows at most linearly with the number of parameters. We also show that the ideal dynamics depends on the two schedules only through a single curve, which controls the adiabaticity of the search, and that the remaining freedom can be used to minimize the gate count. Simulations on benchmark functions and parametric circuits show that, at equal cost, schedules designed in this way markedly increase the probability of finding the global minimum.

0.05

Polynomial-time classical algorithms for mean-field models up to the glass transition

cs.DS quant-phcond-mat.dis-nnmath-ph ·2026-10-05 ·Alexander Schmidhuber, Alexander Zlokapa
highly cited similarity 0.56
Abstract · 63 + 107 pages, 4 figures

The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics. It is highly quantum: Gaussian states are far from the thermal state (Hastings and O'Donnell, STOC'22) and representing the thermal state requires large polynomial-size quantum circuits (Anschuetz et al., QIP'25). Very recently, it was nonetheless proven that classical algorithms can estimate local thermal expectations at sufficiently high temperature in quasipolynomial time (Zlokapa, FOCS'26). We show that classical algorithms can in fact estimate local observables at all constant temperatures in polynomial time. Our techniques also extend straightforwardly to classical systems: we resolve an open question about computing thermal expectations of a classical spin glass up to its phase transition (Bencs et al., STOC'26). Our proof develops a fully rigorous quantum cavity method. Due to the success of the classical cavity method in optimization, sampling, inference and learning, we expect the quantum cavity method to find further applications of independent interest. As an example, we give a quantum algorithm that learns SYK Hamiltonians from the Gibbs state at any constant temperature with polynomial time and sample complexity.

0.43

GadIR: A Spatial-Topology Preserving Compiler for Quantum Many-Body Systems Simulation

cs.AR quant-phcs.PL ·2026-09-01 ·Xiangyu Ren, Yuexun Huang, Zhaohui Yang, Yuchen Zhu, Tsung-Wei Huang +3 more
published similarity 0.56
Abstract · 59th IEEE/ACM International Symposium on Microarchitecture (MICRO 2026)

Simulating quantum many-body systems has been one of the most important applications of quantum computation. For simulation, the Hamiltonian of a physical system is compiled into quantum programs with native instructions for quantum hardware. In previous works, the Hamiltonian is represented as Pauli strings, then compiled and optimized based on the quantum circuit model. Such representation paradigm neglects the spatial topology of original physical models, which is vital information to reducing the overhead of compiling many-body systems Hamiltonians. To address such neglect, we introduce a spatial-topology preserving compiler for quantum many-body simulation. Using Pauli gadgets as the representations of the Hamiltonian, we introduce our intermediate representation -- GadIR, to preserve the spatial-topology information of original physical models. Our compiler frontend performs the group reduction algorithm based on Pauli gadget model, which is a hardware-independent optimization. Our compiler backend performs trotterization and scheduling on Pauli gadgets, then synthesizes the Pauli gadgets into hardware-native quantum programs. We evaluate our compiler on all the canonical quantum many-body system models, while achieving a significant reduction on compilation overhead regarding four major quantum architectures. Overall, our spatial-topology preserving IR exploits the compilation optimization space for quantum many-body systems Hamiltonian.

0.48

Learning angles for quantum approximate optimization

cs.LG quant-ph ·2026-10-16 ·Johannes Jakubik, Isabelle Wittmann, Zaheed Gaffoor, Gciniwe Simphiwe Baloyi, Craig Mahlasi +3 more
code/data similarity 0.56
Abstract

The Quantum Approximate Optimization Algorithm (QAOA) and its variants are leading algorithms to help solve challenging combinatorial optimization problems. QAOA maps these problems to Ising Hamiltonians such that their ground state is the desired solution. Candidate solutions are then drawn from a variational quantum circuit. The performance of QAOA hinges on a set of variational angles. However, finding good angles is an instance-specific and computationally expensive non-convex classical optimization task. Here, we learn the mapping from the problem instance to high-quality QAOA angles. Our learned models replace the per-instance optimization, that we call the solver, with a single forward pass that is several orders of magnitude faster than the solver with a near identical quality. Our models further generalize to unseen topologies such as Barabási-Albert and 2D grid graphs. Experiments on quantum hardware confirm that QAOA samples with angles produced by our open-source models are indistinguishable from solver angles. Crucially, models sensitive to the topology of the problem instance increase the quality of the QAOA angles. Our work amortizes a major bottleneck in QAOA by an up-front data generation and training cost. Importantly, this cost can be amortized over time in settings where many similar problems are optimized on a regular basis, as is often the case in applications for industry.

0.15