CS Paper Radar

Degeneracy Counting Quantum Algorithm using Decoherence

Malay Marut Das, Mark A. Novotny, Yaroslav Koshka

cs.LG quant-ph ·submitted 2026-08-14 23:41 UTC · v1

Abstract

Counting the global optima of a classical optimization problem is a #P-hard task. We develop the canonical thermal pure quantum (CTPQ) state-based degeneracy counting (CTPQsd#) algorithm that determines the number of global optima of a classical optimization problem P by measuring only a small probe S, without finding individual minima. The method exploits a perturbative relation between the decoherence measure of S and the degeneracy of P when S and P are together in a CTPQ state. We provide the first numerical demonstration that this relation can be used to count the global minima, applying it to problems encoded by diagonal random-energy Hamiltonians as a maximally unstructured testbed for classical binary optimization problems. Classical simulations of up to 20 problem qubits quantify the algorithm's sensitivity to variations in the temperature of the CTPQ state, the Hamiltonian energy range, the problem size, and degeneracy. We establish the temperature threshold for determining the exact degeneracy and identify a second, lower threshold that provides a temperature window to count near-degenerate minima within a user-defined energy tolerance. By confining measurement to S, the protocol replaces tomography over the exponentially large problem Hilbert space with tomography over a small probe represented by only four qubits.

Closest papers

Nearest neighbours by meaning across the whole index.

No Exponential Quantum Advantage for Decoded Quantum Interferometry with Local Quantum Decoders

cs.DS quant-ph ·2026-11-09 ·Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana, Dylan Herman, Guneykan Ozgul +3 more
theory similarity 0.67
Abstract

Decoded quantum interferometry (DQI) reduces optimization of sparse linear constraint problems, and sampling from their Gibbs measures, to decoding a linear code from a quantum state. We study DQI on random $D$-regular $k$-sparse instances with $k\ge3$, for which local decoders such as belief propagation with quantum messages (BPQM) are commonly used. Such decoders estimate a typical codeword symbol using only the qudits within logarithmic distance of it. Our main insight is that the thresholds of the decoding problem induced by DQI correspond to phase transitions of the Gibbs measure that are well studied in statistical physics: tree reconstruction for local decoders and, for Max-$k$-XORSAT, condensation for the optimal decoder. This insight allows us to prove two main results. First, we prove an information-theoretic obstruction: no local decoder can recover the codeword with high probability above the tree reconstruction threshold. Conversely, we show that a decoder based on BPQM reaches this threshold. Since the cavity method predicts that local Markov chains equilibrate rapidly up to the same threshold, we expect DQI with local decoders to give no exponential speedup for sampling and no advantage in approximate optimization with amplitude functions that depend only on the number of violated constraints. Second, we consider the optimal decoder (the pretty-good measurement, for which no efficient implementation is known) and show that it succeeds exactly below the condensation threshold. The condensation threshold thus provides a tight upper bound on the performance of DQI with these amplitude functions, providing a strict refinement of the limit that Jordan et al.\ derived from the Holevo bound. Our results point to efficient nonlocal decoders that succeed between the two thresholds as the only viable path to a quantum advantage with DQI on these instances.

0.36

Complexity Barriers to State Preparation in Quantum Approximate Optimization

cs.CC quant-ph ·2026-09-25 ·Stuart Hadfield
theoryhighly cited similarity 0.66
Abstract

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

0.39

Measurement-Efficient Differentiable Quantum Architecture Search for Combinatorial Optimization

cs.LG quant-ph ·2026-10-07 ·Lukas Theißinger, Thore Gerlach, Christian Bauckhage
top venuebenchmarkcode/data similarity 0.65
Abstract · 6 pages, 2 figures. Accepted at the 2026 IEEE 2nd International Conference on Quantum Artificial Intelligence (QAI). Code and data: https://…

Differentiable quantum architecture search (DQAS) is a promising framework for the automated design of quantum circuits, particularly for variational quantum optimization algorithms. However, its practical deployment on quantum hardware is limited by the large number of circuit measurements required during optimization, making hardware execution costly. In this work, we show that for a broad class of combinatorial optimization problems and commonly used rotational gate parameterizations, the measurement cost of DQAS can be significantly reduced without changing the optimization objective. We derive the proposed measurement reduction scheme theoretically and validate it experimentally on 3-SAT and MaxCut benchmark problems. Our approach reduces the requested gradient measurement cost by about 39 to 41% while introducing only negligible classical post-processing overhead, lowering the practical cost of executing DQAS on quantum hardware.

0.43

Optimal Quantum Algorithm for Ground-State Energy Estimation with a Guiding State

cs.CC quant-phcs.DS ·2026-08-25 ·Stacey Jeffery, Freek Witteveen
theoryhighly cited similarity 0.65
Abstract · 25 pages

In the problem of ground-state energy estimation, one aims to estimate the smallest eigenvalue of a Hamiltonian, often given a guiding state, with some promised overlap $γ$ with the ground space. The main approach to this problem is to simulate its evolution, and estimate the smallest (or equivalently, largest) eigenphase of the resulting unitary $U$. We give a quantum algorithm that estimates the largest eigenphase of a unitary $U$ in this guided setting using a factor of $\log\frac{1}γ$ fewer queries to $U$ than the previous best approach. The result matches an existing lower bound, and answers an open question from Mande and de Wolf. The algorithm is based on transducers, which often allow composition of quantum algorithms without overhead from error reduction.

0.51

Optimization Geometry of QAOA and Variational Quantum Algorithms

cs.NE quant-ph ·2026-10-04 ·Vojtěch Novák, Ivan Zelinka, Silvie Illésová, Swagatam Das, Martin Beseda
similarity 0.65
Abstract

Variational quantum algorithms turn choices of Hamiltonian, ansatz, and parameterization into a classical nonconvex optimization problem. We study how this objective function can be visualized and characterized in ways that help explain optimizer behavior. We distinguish two properties of the objective: the number of local minima encountered along sampled directions and the differences in quality among local-search endpoints. We then ask how a local optimizer, represented by BFGS, compares with adaptive differential evolution, represented by jSO. Rather than comparing jSO with a single local run, we allow BFGS multiple starts within the same function-evaluation budget. This gives local search repeated opportunities to explore different basins and provides a stronger baseline for asking when a global evolutionary solver is useful. We study these questions using VQE and QAOA, focusing on how frustra- tion, circuit depth, parameter tying, mixed locality, and nonlinear repa- rameterization change the Hamiltonian expectation-value objective seen by the classical optimizer. Increasing independent circuit depth raises the sampled local-minimum count without making global search more effective. Parameter tying, by contrast, produces both more repeated local structure and much larger differences in quality among local-search endpoints, and in this regime adaptive differential evolution outperforms function-evaluation-matched multistart BFGS. The comparison shows that the number of local minima alone does not determine whether global search is advantageous: the important distinction is whether different basins lead to similarly good solutions or to substantially different objective values. These results provide a practical workflow for connecting model construction, objective- function geometry, empirical diagnostics, and optimizer choice.

0.08

Regev's Reduction Reaches Reconstruction

cs.DS quant-phcond-mat.dis-nn ·2026-11-06 ·Stephen P. Jordan, Quynh T. Nguyen, Leo Zhou
similarity 0.64
Abstract · 30 pages, 4 figures

Regev's reduction uses a quantum Fourier transform to carry out reductions between various problems related to lattices and codes. We apply it to the problem of sampling from Gibbs distributions of certain classical spin glass Hamiltonians, which can equivalently be thought of as cost functions for average-case instances of an optimization problem called $D$-regular max-$k$-LINSAT. This problem becomes hard at low temperature. Here, we use a quantum decoding algorithm called Belief Propagation with Quantum Messages (BPQM) to solve the decoding problem arising from Regev's reduction. Our main contribution is a proof that the minimum temperature reachable using Regev+BPQM is exactly equal to the reconstruction threshold temperature for noisy channels transmitting signals on a tree network. This equality can be understood via Renes' duality between classical and quantum channels, which we use to show that quantum decoding is possible exactly when classical reconstruction on the dual problem is impossible. M{é}zard and Montanari identified this reconstruction temperature with a dynamical glass transition predicted by the one-step replica-symmetry breaking (1RSB) cavity equation. It is conjectured that local samplers such as Metropolis Monte Carlo and Glauber dynamics cannot equilibrate efficiently below this reconstruction temperature but may do so above it; our large numerical experiments show close agreement with this prediction across hundreds of different problem parameters. Therefore, our results rigorously show that Regev+BPQM reaches a temperature for which, to our knowledge, there is no matching classical guarantee, and brings Regev+BPQM to the conjectured limit of efficient Gibbs sampling by classical local dynamics.

0.18

Programming Quantum Circuit Parameters with Large Language Models

cs.LG quant-ph ·2026-11-12 ·Tiago de Souza Farias, Caio Moraes Porto, Matheus da Silva Fonseca, Nicolas Armando Cabrera Carpi, Anderson de Araujo Oliveira +1 more
theoryhot direction similarity 0.64
Abstract · 31 pages

Large language models (LLMs) have recently demonstrated the ability to generate parameters for variational quantum circuits without conventional optimization. However, the conditions under which this approach is effective remain unclear. Here, we investigate a frozen, general-purpose LLM that generates complete circuit parameter vectors from symbolic circuit and Hamiltonian descriptions, with optional iterative energy feedback. We evaluate the approach on general random Hamiltonians, structured parent Hamiltonians, and molecular systems. For general Hamiltonians, LLM-generated parameters exhibit larger energy errors than conventional Adam optimization, while additional feedback generally provides limited improvement. In contrast, for structured Hamiltonians, the LLM can generate promising low-energy parameter configurations, suggesting that identifiable physical and mathematical structure facilitates parameter inference. We also show that direct LLM predictions of minimum energies can violate the Hamiltonian spectral lower bound, whereas generated circuit parameters allow independent evaluation of physically realizable energy expectation values. Finally, we investigate blind circuit interpretation and find that the LLM can predict measurement outcomes even when it fails to identify the underlying quantum algorithm. These findings highlight the role of problem structure, the limitations of iterative LLM optimization, and the importance of independently verifiable predictions in quantum parameter programming.

0.27

Fully quantum training of parametric circuits with Quantum Hamiltonian Descent

cs.LG quant-ph ·2026-10-23 ·Marco Burato, Leonardo Banchi
benchmarktheory similarity 0.64
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