Thermodynamic significance of QUBO encoding on quantum annealers

Abstract

Quadratic unconstrained binary optimization (QUBO) is the standard interface to quantum annealers, yet a single constrained task admits many QUBO encodings whose penalty choices reshape the energy landscape experienced by hardware. We study a Job Shop Scheduling instance using a two-parameter family of encodings controlled by penalty weights $p_{\mathrm{sum}}$ (one-hot/sum constraints) and $p_{\mathrm{pair}}$ (precedence constraints). Sweeping $(p_{\mathrm{sum}},p_{\mathrm{pair}})$, we observe sharp transitions in feasibility and solver success across classical annealing-inspired heuristics and on a D-Wave Advantage processor. Going beyond solution probability, we treat the annealer as an open thermodynamic system and perform cyclic reverse-annealing experiments initialized from thermal samples, measuring the stochastic processor energy change. From the first two moments of this energy change we infer lower bounds on entropy production, work, and exchanged heat via thermodynamic uncertainty relations, and corroborate the observed trends with adiabatic master equation simulations. We find that the same encoding transitions that govern computational hardness also reorganize dissipation: weak penalties generate low-energy infeasible manifolds, while overly strong penalties suppress the effective problem energy scale and increase irreversibility, reducing the thermodynamic efficiency. Our results establish QUBO penalties as thermodynamic control knobs and motivate thermodynamics-aware encoding strategies for noisy intermediate-scale quantum annealers.

17 pages, 8 figures

References in corpus (13)

• Thermodynamic uncertainty relation for biomolecular processes
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Quantum technologies need a Quantum Energy Initiative
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Work statistics and symmetry breaking in an excited state quantum phase transition
• Efficiency Optimization in Quantum Computing: Balancing Thermodynamics and Computational Performance
• Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
• Two-dimensional Parallel Tempering for Constrained Optimization
• On the Baltimore Light RailLink into the quantum future
• Hamiltonian quantum gates -- energetic advantage from entangleability
• Quantum-inspired dynamical models on quantum and classical annealers