QUBO encoding effects on quantum annealing efficiency
Dr. Sebastian Deffner, Physics Department (2025)
Quantum annealing is an important paradigm of quantum computing which can be used to solve a wide range of problems. This is done by transforming any given problem into the form of a quadratic unconstrained binary optimization (QUBO) problem. Unfortunately, any given problem can typically be encoded in QUBO form in a huge variety of ways, none of which are obviously superior to any other. While each QUBO formulation produces a problem which encodes the correct solution, the imperfections of current NISQ-era devices mean that some encodings are more likely to yield correct results than others. Selecting optimal encodings is extremely difficult, and so in practice heuristics are used to construct encodings which are hoped to perform reasonably well. In this work, we focus on a specific job shop scheduling problem and examine how different encodings of this problem in QUBO form lead to different behavior when solved with quantum annealing. Through a combination of experiments on a D-Wave device and numerical simulations of the annealing process, we study the connection between the accuracy of the solution and the efficiency of the annealer itself interpreted as a thermodynamic machine. In doing so, we shed light on the question of what it means for a specific QUBO encoding to be easier or harder to solve with quantum annealing.
Thermodynamics of Quantum Computation
Josey Stevens, Sebastian Deffner (2017)
We will present a minimal model of a continuous quantum Maxwell demon obeying Hamiltonian dynamics. Our model will be solved via semi-exact computational methods to study its steady-state behavior. Study of this model will also lead to quantification of the thermodynamic advantage of quantum information processing as compared to classical information processing. The new model serves as a significant generalization of previous work and serves as the starting point for studying open quantum Maxwell demons.