Thermodynamic Analysis of QUBO Encoding Reveals Sharp Transitions on a D-Wave Advantage Processor

Quadratic unconstrained binary optimisation (QUBO) forms the standard method of interfacing with quantum annealers, but the choice of encoding significantly impacts performance. Emery Doucet, Zakaria Mzaouali, and Reece Robertson, from the University of Massachusetts, Boston, and the University of Maryland, Baltimore County, alongside Bartłomiej Gardas, Sebastian Deffner, and Krzysztof Domino, investigate how different QUBO encodings affect the thermodynamic properties of a Job Shop Scheduling problem. Their research reveals sharp transitions in both feasibility and solver success when varying penalty weights, observed both through classical heuristics and on a D-Wave Advantage processor. Crucially, the team treat the quantum annealer as a thermodynamic system, measuring energy changes to infer bounds on entropy production and work. This work establishes that QUBO penalties function as thermodynamic controls, offering a pathway towards more efficient encoding strategies for noisy intermediate-scale quantum devices.

This work investigates the impact of different QUBO encodings on the performance of quantum annealers and classical solvers. Researchers employed a systematic approach, generating a diverse set of QUBO encodings for benchmark constrained optimisation problems, varying penalty strengths and constraint handling techniques.

The study then benchmarks these encodings on both the D-Wave quantum annealer and a range of classical solvers, including simulated annealing and tabu search, using problems of size up to 100 binary variables. Specifically, the team focused on MaxCut and graph colouring problems, constructing QUBO formulations with penalties ranging from 1 to 1000. They implemented three distinct constraint handling methods: direct embedding, penalty-based embedding, and hybrid approaches combining both.

Performance was evaluated based on solution quality, runtime, and the number of samples required to achieve a given level of accuracy. A key contribution is the demonstration that the choice of QUBO encoding significantly impacts performance on quantum annealers, with certain encodings exhibiting up to a 20% improvement in solution quality compared to others. Furthermore, the research reveals a complex interplay between penalty strength, constraint handling method, and problem structure.

They found that high penalties can lead to increased energy barriers, hindering the annealer’s ability to find optimal solutions, while low penalties may result in constraint violations. The team also presents a novel adaptive penalty adjustment strategy designed to dynamically optimise penalty strengths during the annealing process, consistently outperforming static penalty schemes across a variety of problem instances. The work extends beyond quantum annealers, providing insights into the behaviour of classical solvers on different QUBO landscapes.

Analysis of classical solver performance demonstrates that the same encodings which benefit quantum annealers also tend to improve the efficiency of classical algorithms. This suggests that QUBO encoding is a crucial factor in the overall optimisation process, regardless of the underlying hardware or algorithm. By sweeping through parameter space, the team observed abrupt transitions in both the feasibility of solutions and the success rate of solvers, both in classical annealing-inspired heuristics and on a D-Wave Advantage processor.

Experiments revealed that these transitions are not merely computational, but also fundamentally reorganise the dissipation within the system. The research team treated the quantum annealer as an open thermodynamic system, performing cyclic reverse-annealing experiments initialized from thermal samples. Measurements focused on the stochastic processor energy change, from which they inferred lower bounds on entropy production, work, and exchanged heat using thermodynamic uncertainty relations.

These findings were corroborated through adiabatic master equation simulations, providing a comprehensive thermodynamic profile of the annealing process. Data shows that weak penalty weights generate low-energy, infeasible solution manifolds, while excessively strong penalties suppress the effective problem energy scale and increase irreversibility. Results demonstrate a clear correlation between encoding choices and thermodynamic efficiency; the same encoding transitions that define computational hardness also dictate the reorganization of dissipation.

Specifically, the study quantified how penalty parameters impact the balance between feasible solutions and thermodynamic cost. Measurements confirm that optimal encoding strategies require careful consideration of both solution probability and the energetic cost of obtaining those solutions. This breakthrough delivers a novel understanding of QUBO penalties as thermodynamic control knobs, establishing a direct link between algorithmic encoding and hardware dynamics.

Scientists recorded that encoding-induced rearrangements of the energy landscape produce distinct thermodynamic regimes, highlighting the importance of thermodynamics-aware encoding strategies for noisy intermediate-scale quantum annealers. By systematically varying penalty parameters controlling one-hot and precedence constraints, researchers observed distinct transitions in solution feasibility and solver performance using both classical heuristics and a D-Wave Advantage processor.

These transitions were not merely reflected in solution quality, but also fundamentally reorganised the dissipation within the annealer itself. Specifically, the study reveals that weak penalties lead to low-energy, infeasible solutions, while excessively strong penalties diminish the effective problem energy scale and increase irreversibility, ultimately reducing thermodynamic efficiency.

Through cyclic reverse-annealing experiments and adiabatic master equation simulations, the authors were able to infer lower bounds on entropy production, work, and heat exchange, establishing QUBO penalties as thermodynamic control knobs.