PaperlayerView exact revision on arXiv

Source-linked AI summary

Degeneracy Counting Quantum Algorithm using Decoherence

Malay Marut Das, Mark A. Novotny, Yaroslav Koshka

arXiv:2608.14941v1cs.LGquant-ph

TL;DR

Counting global optima is computationally difficult, yet their degeneracy can be useful for optimization and physical analysis. This paper develops a decoherence-based CTPQ algorithm that counts minima through a small probe, recovering tested degeneracies exactly at sufficiently low temperature.

  • Problem

    Counting or estimating global and near-optimal solutions can be computationally expensive, while degeneracy is relevant to optimization and physical systems.

  • Method

    The CTPQsd# algorithm uses perturbation theory to infer problem degeneracy from probe decoherence in a coupled CTPQ state.

  • Results

    Across simulated instances up to 20 problem qubits, recovered degeneracies matched the true values at sufficiently low temperature, with accuracy governed by a temperature threshold.

  • Takeaways & Limitations

    A fixed four-qubit probe makes the tomography dimension independent of problem size, avoiding full-register tomography for the demonstrated setting.

  • Takeaways & Limitations

    The evidence is limited to classical simulations of problem sizes up to 20 qubits and tested degeneracies from 1 through 16.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Exact degeneracy counting is computationally difficult, while existing classical and quantum approaches face scalability, coherence, optimization, and measurement bottlenecks. This work investigates counting global minima through probe decoherence in a CTPQ state, using numerical simulations of diagonal random-energy Hamiltonians.

  • Motivation: Exact counting is #P-complete in general and often intractable, motivating approximate methods that sacrifice absolute precision for scalability.The introduction contrasts computational hardness with the practical value of exact or approximate counts of global and near-optimal solutions.
  • Limitations: Existing quantum counting methods require deep, fully coherent circuits, while hybrid variational approaches face barren plateaus, NP-hard classical optimization, and exponentially costly tomography.Readout errors also accumulate multiplicatively across larger measured registers on noisy hardware.
  • Proposed approach: Probe decoherence in a canonical thermal pure quantum state can depend explicitly on the problem Hamiltonian’s ground-state degeneracy, enabling counting from a small probe’s reduced density matrix.The proposed mechanism targets a potentially large problem system using a probe such as N_S = 4 qubits.
  • Numerical testbed: The paper establishes a proof of concept by numerically testing the counting approach on arbitrary classical binary problems encoded by diagonal Hamiltonians with i.i.d. uniformly distributed energies.These models correspond to the Γ = 0 classical limit of the quantum random energy model and are simulated for composite systems S + P on a classical computer.

II. THEORY · B. Decoherence measure

The framework treats decoherence of a probe system S, coupled to a problem system P, as a resource for degeneracy counting. It quantifies decoherence through off-diagonal coherences of S in the energy eigenbasis, which coincides with the computational basis for the targeted classical optimization problems.

  • II. THEORY: Decoherence is treated as a resource in this approach, with probe S coupled to problem system P within a closed quantum system.The combined system evolves under H = H_S + H_P + λH_SP, where λ is the global coupling strength.
  • II. THEORY: The closed system contains N spin-1/2 particles and occupies a Hilbert space of dimension D = 2^N.The probe and problem dimensions are D_S = 2^N_S and D_P = 2^N_P.
  • II. THEORY: The total state is expanded in product basis states |i,p⟩, with coefficients c(i,p,t) describing probe-problem components.The basis states of S and P form a complete orthonormal basis for the entirety.
  • II. THEORY: The probe’s reduced density matrix ρ_S(t) is obtained by partially tracing the density matrix ρ_S+P(t) over the problem-system degrees of freedom.This reduction describes subsystem S within the larger closed system S + P.
  • B. Decoherence measure: The diagonal elements of ρ_S(t) give occupation probabilities, whereas its off-diagonal elements encode quantum coherences.Interaction with P causes phase coherence in S to decay toward a classical statistical mixture.
  • B. Decoherence measure: For the targeted classical optimization problems, the energy eigenbasis of H_S is the pointer basis and matches the computational basis of H_S and H_P.This basis corresponds to the states used in the classical optimization or degeneracy-counting problem.
  • B. Decoherence measure: The decoherence degree of S is quantified by σ_S(t), defined from the squared moduli of its off-diagonal density-matrix elements.The measure is evaluated relative to the energy eigenbasis of H_S.
  • B. Decoherence measure: σ_S(t) = 0 indicates that S is fully decohered relative to the energy eigenbasis of H_S.This condition denotes complete loss of coherence in that basis.

C. Quantum dynamics · D. Canonical thermal pure quantum state

Decoherence requires coupling the probe to an environment, driving it toward the thermal steady state needed by CTPQsd#. The CTPQ framework uses a single pure state to reproduce canonical thermal expectation values, with an infinite-temperature limit given by a uniformly random Hilbert-space state.

  • C. Quantum dynamics: Nonzero coupling λ between probe S and problem P enables environmental decoherence and drives S toward the thermal steady state required by CTPQsd#.An isolated system evolving unitarily under the TDSE cannot produce irreversible decay of density-matrix off-diagonal coherences.
  • C. Quantum dynamics: The resulting canonical steady state is termed the Canonical Thermal Pure Quantum (CTPQ) state, following prior scaling-state and canonical-thermal-state terminology.The terminology is attributed to prior literature and Sugiura and Shimizu.
  • D. Canonical thermal pure quantum state: A single CTPQ pure state can reproduce canonical ensemble predictions, providing a pure-state alternative to conventional mixed-state thermal descriptions.This framework is presented in quantum statistical mechanics as an alternative to the ensemble formulation.
  • D. Canonical thermal pure quantum state: In the thermodynamic limit N→∞, CTPQ expectation values converge in probability uniformly for every operator A.The supplied passages define convergence in probability through an error-dependent function η_ε(N) that vanishes as N grows.
  • D. Canonical thermal pure quantum state: For sufficiently large N, one CTPQ realization reproduces any observable’s thermal steady-state expectation value up to statistical or quantum fluctuations.The probability notation describes the convergence criterion for arbitrary ε>0.
  • D. Canonical thermal pure quantum state: At infinite temperature, equal weighting of all energy eigenstates reduces the CTPQ state to a random state |ψ0⟩ sampled from the D-dimensional Hilbert space.The state is represented using normalized random Gaussian coefficients.
  • D. Canonical thermal pure quantum state: The coefficients d_k are normalized so that their squared magnitudes sum to unity, ∑_k d_k* d_k = 1.The coefficients are described as random Gaussian variables.
  • D. Canonical thermal pure quantum state: The random Gaussian coefficients are generated with the Box-Muller method, while the underlying uniform variables are independent on [0,1).The resulting state is mathematically equivalent to a point sampled uniformly on the Hilbert-space hypersphere.

E. Preparation of a finite temperature CTPQ state

The study assumes the entirety reaches a finite-temperature CTPQ state, constructs it classically by imaginary-time projection, and analyzes the resulting state and its entanglement. This numerical approach avoids explicit real-time evolution but limits validation to 20 qubits.

  • State construction: The finite-temperature CTPQ state is constructed as e^−βH/2 applied to an infinite-temperature state, followed by normalization.This classical construction substitutes for real-time evolution or an equivalent quantum state-preparation protocol.
  • Temperature dependence: As temperature decreases, Boltzmann weighting biases the CTPQ state toward low-energy configurations.At β→0, the Boltzmann weights become uniform and the finite-temperature state reduces to the infinite-temperature state.
  • Entanglement: Even with no S–P Hamiltonian coupling (λ = 0), the CTPQ state is generally entangled rather than a product state.The joint-basis random coefficients are not factorizable as d_i d_p.
  • Numerical validation: The work assumes CTPQ-state preparation and uses classical imaginary-time projection for numerical validation, limiting the problem system size to 20 qubits.Efficient quantum circuits for CTPQ preparation are outside the study’s scope, while classical construction avoids explicit time evolution.

F. Relevant results of the perturbation theory analysis

Finite-temperature perturbation theory for CTPQ states gives decoherence expressions involving the problem’s free energy and ground-state degeneracy. In the low-temperature regime, probe-only measurements can reveal the problem’s ground-state degeneracy under specified conditions.

  • Perturbative framework: Finite-temperature perturbation theory in the probe–problem coupling strength λ provides analytical expressions for the probe’s decoherence measure.The perturbative results apply when the entirety S+P is prepared in a CTPQ state.
  • Temperature dependence: The infinite-temperature scaling relation does not include the ground-state degeneracy count, motivating the finite-temperature analysis.CTPQ states support analytical decoherence scaling relations at both infinite and finite temperatures.
  • Perturbative framework: The perturbation results hold for arbitrary probe and problem Hamiltonians, establishing a general framework for predicting decoherence in weakly coupled or uncoupled systems.The problem system P acts as a quantum environment for the probe S.
  • Low-temperature limit: At low temperature, the analytical expression connects the probe’s decoherence properties with the ground-state degeneracies g_S and g_P.The degeneracy symbols denote the ground-state degeneracies of S and P, respectively.
  • Low-temperature limit: When g_S > 1 and σ_S > 0, measurements performed solely on probe S can, in principle, reveal the problem’s ground-state degeneracy g_P.This connection forms the theoretical foundation of the degeneracy-counting algorithm.

G. Random-energy-model background

The study tests perturbation-theoretic degeneracy predictions on a structurally different, diagonal REM-like Hamiltonian. Its classical binary landscape is represented by a diagonal computational-basis Hamiltonian with random energy levels.

  • Motivation: The study applies perturbation-theoretic predictions from prior work to determine degeneracy in a structurally different class of diagonal, REM-like Hamiltonians.The target systems differ from the Heisenberg-type spin systems with ring topology examined previously.
  • REM background: In the REM limit p→∞, spin correlations vanish and the 2^N energy values form an i.i.d. Gaussian process over the hypercube {−1,1}^N.The p=2 case corresponds to the Sherrington-Kirkpatrick model, while p→∞ yields Derrida’s REM.
  • Hamiltonian representation: The framework restricts the QREM setting to zero transverse field, promoting the classical energy function to a diagonal Hamiltonian on a 2^N-dimensional Hilbert space.Ising configurations are eigenstates of the z-components of N spin-1/2 operators.
  • Model construction: The studied REM-like Hamiltonians use uniformly distributed energy levels rather than the canonical REM’s Gaussian distribution.The Hamiltonian is diagonal in the computational basis, and quantum spins encode binary classical variables.

III. METHOD · A. Overview of the CTPQsd# algorithm

The CTPQsd# algorithm uses a degenerate probe coupled with a classical problem Hamiltonian in a finite-temperature CTPQ state to infer problem degeneracy from probe decoherence. The protocol prepares, measures, and statistically averages the probe while exploiting uncoupled diagonal Hamiltonians for computational-basis operation and efficient imaginary-time projection.

  • A. Overview of the CTPQsd# algorithm: The probe Hamiltonian H_S is constructed with ground-state degeneracy g_S > 1, ensuring a nonzero low-temperature σ_S.The present work uses diagonal H_S.
  • A. Overview of the CTPQsd# algorithm: The problem Hamiltonian H_P encodes the target ground-state degeneracy g_P and is classical, hence diagonal, in this work.The problem degeneracy represents the quantity determined by the algorithm.
  • A. Overview of the CTPQsd# algorithm: The uncoupled system S + P is prepared at finite temperature in a CTPQ state |ψ_β⟩ by imaginary-time projection of a random infinite-temperature state |ψ_0⟩.Preparation uses λ = 0.
  • A. Overview of the CTPQsd# algorithm: The protocol traces out P to obtain ρ_S and computes the probe decoherence measure σ_S.For larger systems, a single measurement may suffice.
  • A. Overview of the CTPQsd# algorithm: Averaging σ_S over n independent CTPQ realizations yields a statistically robust estimate g_P,Meas from the low-temperature limit of equation (19).The required quantity is the expectation value E(σ_S) over independent CTPQ state realizations.
  • A. Overview of the CTPQsd# algorithm: Keeping the probe and problem uncoupled at λ = 0 preserves equation (19)'s validity and makes the probe energy eigenbasis the computational basis.This eliminates an additional basis transformation before computing σ_S.
  • A. Overview of the CTPQsd# algorithm: With λ = 0, the entirety Hamiltonian H = H_S ⊗ I_P + I_S ⊗ H_P is diagonal in the computational basis.Consequently, the imaginary-time projector e^−βH/2 simplifies operationally.

B. Construction of the Hamiltonian models · C. Finite-temperature CTPQ state preparation · D. Decoherence measurement and degeneracy extraction

The study constructs diagonal random-energy problem and probe Hamiltonians, prepares finite-temperature CTPQ states by imaginary-time projection, and extracts problem degeneracy from probe decoherence. Diagonal structure makes simulations tractable while low temperatures require arbitrary-precision arithmetic.

  • B. Construction of the Hamiltonian models: Problem instances use diagonal REM-like Hamiltonians with D_P=2^N_P basis states and uniformly drawn energies over a tunable spectral range R.The default range is R=2, with sweeps over R∈{0.01,0.1,1,10}.
  • B. Construction of the Hamiltonian models: The target ground-state degeneracy g_P is imposed by replacing the g_P lowest energies with their common minimum, with exact cases g_P∈{1,4,8,12,16}.Higher-energy entries remain unmodified, preserving their uniform-distribution statistics.
  • B. Construction of the Hamiltonian models: The probe contains N_S=4 qubits with D_S=16, and its four lowest diagonal energies are equalized to fix g_S=4.Probe and problem Hamiltonians use the same spectral range R.
  • C. Finite-temperature CTPQ state preparation: CTPQ states are classically prepared by imaginary-time projection of a random infinite-temperature state, whereas quantum implementations would require real-time evolution or thermalization protocols.The stated quantum approaches include VQT and VarQITE.
  • C. Finite-temperature CTPQ state preparation: Because the joint Hamiltonian is diagonal, applying e^-βH/2 requires element-wise multiplication, reducing projection cost to O(D) per realization.This enables simulations up to N_P=20, with D=2^24≈1.7×10^7 for N_S=4.
  • C. Finite-temperature CTPQ state preparation: At temperatures as low as T=10^-8, projector dynamic ranges exceed IEEE double precision, so arbitrary-precision arithmetic preserves relative magnitudes.Mathematica automatically promotes the projector and associated partition sums in this regime.
  • D. Decoherence measurement and degeneracy extraction: Probe decoherence is computed from the reduced density matrix after tracing out the problem, and its expectation is estimated by averaging independent CTPQ realizations.The simulations use n=100 realizations generally and n=350 at T=10^-8.
  • D. Decoherence measurement and degeneracy extraction: The measured decoherence average is inserted into the low-temperature perturbative relation, and the physically admissible quadratic root yields g_P,Meas.For quasi-degenerate cases, the estimate counts approximate minima when T2<T<T1.

E. Implementation, software, and computational resources · IV. RESULTS

The simulations were implemented in Mathematica on a single specified machine, with arbitrary-precision arithmetic and seeded randomness supporting low-temperature evaluation and reproducibility. Results examine decoherence’s temperature dependence across problem degeneracies, using the low-temperature plateau to calculate measured degeneracy.

  • E. Implementation, software, and computational resources: The simulations were implemented in Mathematica.
  • IV. RESULTS: For N_P = 20, decoherence curves were shown for degeneracies g_P = 1, 4, 8, 12, and 16.
  • IV. RESULTS: The low-temperature constant-σ_S region, where S+P approaches the ground state, was used to calculate g_P,Meas.
  • E. Implementation, software, and computational resources: They ran on a single machine with an Intel Core i7-12700H, 14 physical cores, 20 threads, and 64 GB RAM.
  • E. Implementation, software, and computational resources: Extended-precision evaluation used Mathematica’s built-in arbitrary-precision arithmetic, invoked automatically in the low-temperature regime.
  • E. Implementation, software, and computational resources: The random-number generator was seeded with SeedRandom[1234] at the beginning of each run for reproducibility.
  • E. Implementation, software, and computational resources: The largest simulated system had N_S = 4 and N_P = 20, requiring a complex-valued state vector of 224 entries, approximately 256 MB in machine precision.

A. Temperature dependence of decoherence and the low-temperature regime … D. Relative error of degeneracy determination at non-optimal temperatures

The CTPQsd# algorithm relies on low-temperature saturation of probe decoherence, with the required temperature decreasing as problem size grows. Simulations establish accuracy at T = 10^-8, quantify sampling and classical-simulation limits, and show relative-error sensitivity to temperature, size, and degeneracy.

  • A. Temperature dependence of decoherence and the low-temperature regime: The low-temperature operating window is constrained by exponentially growing Hilbert-space costs, limiting classical simulations to the investigated problem sizes.These time and memory costs are especially severe in the regime where CTPQsd# is effective.
  • A. Temperature dependence of decoherence and the low-temperature regime: Probe decoherence σ_S increases as temperature T decreases and saturates when S+P approaches the ground-state manifold.The curves correspond to g_P = 1, 4, 8, 12, and 16, with N_S = 4 and g_S = 4 fixed.
  • B. Scaling of the saturation temperature with problem size: The perturbative relation is valid when thermal occupation of the nearest excited level is negligible, requiring e^(-ΔE_P/k_BT_1) ≪ 1.For uniformly distributed energies, ΔE_P ~ R·2^-N_P.
  • C. Accuracy of the CTPQsd# algorithm: At T = 10^-8, CTPQsd# estimates g_P,Meas from probe decoherence for N_P = 16 and N_P = 20 across five problem systems.The estimates use 350 averages with different random Ψ_0; N_P = 20 error bars report SEM.
  • B. Scaling of the saturation temperature with problem size: Increasing problem-qubit count N_P requires progressively lower T to reach the constant-decoherence regime needed for degeneracy extraction.Figure 2 uses N_P = 8, 12, 16, and 20 at fixed degeneracies g_P = 1 and g_P = 16.
  • C. Accuracy of the CTPQsd# algorithm: 350 CTPQ-state realizations determine uncertainty using the standard error of the mean propagated through equation (23), rather than the standard deviation.This reflects that g_P,Meas is extracted from ensemble-averaged σ².
  • C. Accuracy of the CTPQsd# algorithm: Classical simulation limits prevent testing N_P > 20, while increasing the number of CTPQ-state preparations can improve degeneracy precision.The larger-size error behavior therefore remains unassessed in these simulations.
  • D. Relative error of degeneracy determination at non-optimal temperatures: Relative error increases at higher temperatures, and larger N_P requires lower T for correct determination of g_P; threshold T_1 depends only weakly on g_P.For fixed N_P = 20, lower degeneracies may require somewhat lower T than larger degeneracies.

E. CTPQsd# algorithm's dependence on the diagonal energy range parameter · F. Determination of quasi-degeneracy

The CTPQsd# algorithm requires lower operating temperatures as the Hamiltonian’s spectral range or variance decreases. For quasi-degeneracy, two temperature thresholds define a window for counting states within a user-specified energy tolerance, provided the energy gaps are sufficiently small.

  • E. CTPQsd# algorithm's dependence on the diagonal energy range parameter: For NP=20, lower degeneracies may require somewhat lower T for correct determination when other conditions are similar.The comparison uses gP=1, 4, 8, 12 and 16.
  • E. CTPQsd# algorithm's dependence on the diagonal energy range parameter: Lower spectral variance requires a lower threshold temperature T1 to reach the low-temperature regime of constant σS.This trend is reported for the diagonal REM-like Hamiltonian encoding and is expected to extend to other problem Hamiltonians.
  • E. CTPQsd# algorithm's dependence on the diagonal energy range parameter: For NP=20 and gP=8, decreasing R from 10 to 0.01 shifts the required temperature for correct degeneracy determination lower.The tested ranges are R = 10, 1, 0.1, and 0.01.
  • F. Determination of quasi-degeneracy: Quasi-degeneracy counts extrema whose energies fall within a small tolerance of the global optimum, rather than only states exactly matching the ground-state energy.The approximate count is denoted gP,Approx.
  • F. Determination of quasi-degeneracy: For gP,Approx=8 and NP=20, increasing ΔgP from 0 to 10−4 produces distinct σS-versus-T curves, with ΔgP=0 representing exact degeneracy.The tested gaps are ΔgP= 0, 10−8, 10−7, 10−6, 10−5, and 10−4.
  • F. Determination of quasi-degeneracy: Approximate degeneracy introduces a lower threshold T2 < T1, while smaller ΔgP broadens the temperature window for reflecting the near-degenerate count.Further lowering T below T1 incrementally excludes higher-energy states from the nearly-degenerate group.
  • F. Determination of quasi-degeneracy: If ΔgP is too large, no reliable temperature range exists; otherwise, choosing T2 < T < T1 can count all states within a user-specified tolerance ΔgP,Approx.The window is proposed for counting approximate-degenerate states meeting the user’s “good-enough” criterion.

V. CONCLUSION

The CTPQsd# algorithm determines global-solution degeneracy without enumerating solutions, using a small probe whose decoherence becomes degeneracy-sensitive below a threshold temperature. Simulations recovered tested degeneracies exactly through problem size N_P=20, while hardware realization still requires state preparation, encoding, noise control, and sampling studies.

  • Core contribution: CTPQsd# determines the global-solution degeneracy g_P of broad classical optimization problems without enumerating their solutions.The method builds on a perturbative relation between probe decoherence and degeneracy.
  • Numerical validation: 100% of tested simulated instances matched the true degeneracy for g_P∈{1,4,8,12,16} using a four-qubit probe and N_P≤20.Agreement occurred at sufficiently low temperature.
  • Temperature dependence: T_1 decreases with problem size N_P, and below T_1 the probe decoherence measure σ_S becomes sensitive to degeneracy.The passage reports that T_1 is not significantly sensitive to at least one additional tested setting, but the supplied text is truncated before specifying it.
  • Open questions: Future work must test whether canonical typicality reduces the required number of independent CTPQ preparations and assess readout noise and finite-sampling effects on g_P,Meas.These issues are identified as important questions for practical quantum-hardware realization.
  • Hardware challenges: Hardware implementation must encode the problem Hamiltonian, prepare CTPQ states in the low-temperature regime T<T_1, and control device noise through error mitigation.For diagonal cost Hamiltonians, the passage identifies Pauli-Z rotations in QAOA-type cost layers as one encoding route.
  • Measurement overhead: A four-qubit probe requires fixed 16 × 16 density-matrix tomography, unlike full-register tomography over the problem state space.The probe readout is described as relatively inexpensive and largely insulated from multiplicative accumulation of full-register readout errors.
Loading 2608.14941v1…