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.

arXiv comment17 pages, 8 figures

References in corpus (26)

• Stochastic thermodynamics, fluctuation theorems, and molecular machines
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Equilibrium free energy differences from nonequilibrium measurements: a master equation approach
• Thermodynamic uncertainty relation for biomolecular processes
• Dissipation bounds all steady-state current fluctuations
• Defining and detecting quantum speedup
• Perspectives of quantum annealing: Methods and implementations
• Quantum Adiabatic Markovian Master Equations
• 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
• Flight Gate Assignment with a Quantum Annealer
• Necessary Condition for the Quantum Adiabatic Approximation
• Reexamination of the evidence for entanglement in the D-Wave processor
• Quantum fluctuation theorem to benchmark quantum annealers
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Work statistics and symmetry breaking in an excited state quantum phase transition
• Improved bound on entropy production in a quantum annealer
• 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