REVIEW 36 cited by
A Tutorial on Formulating and Using QUBO Models
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.
Forward citations
Cited by 36 Pith papers
-
Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization
BloGDiT introduces blocked Gibbs-style denoising in diffusion transformers to enable large targeted edits for constraint satisfaction and optimization, matching or exceeding prior methods on Sudoku, graph coloring, MI...
-
Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning
CRiSP uses neural-guided MCTS and curriculum learning to insert Clifford prefixes before parameterized rotations in VQAs, yielding mean 3.17x and max 45x gains in energy accuracy on 22-qubit QAOA benchmarks versus pri...
-
Quantum Optimisation for Transport Vulnerability Identification
Reformulating bi-level MINLP transport vulnerability analysis into QUBO form allows D-Wave quantum annealing to solve disruption scenarios on networks up to 6018 links in minutes, one to two orders of magnitude faster...
-
A Geometric Theory of Fermion-to-Qubit Encodings
The paper proposes that Bravyi–Kitaev and Xia–Bian–Kais encoded Hamiltonians carry geometric structure whose spectral and transport descriptors reflect interaction-driven reorganization, but the strongest "exact" clai...
-
Feasibility-driven QAOA with penalty scheduling
Introduces Λ-lr-QAOA and piecewise-ramp QAOA that promote penalty schedules to variational parameters and use a feasibility-driven loss on budget-constrained MWIS satellite planning instances.
-
Pauli Correlation Encoding for mRNA Secondary Structure Prediction: Problem-Aware Decoding for Dense-Constraint QUBOs
Pauli Correlation Encoding with a trained problem-aware decoder achieves 75-100% near-optimal recovery on mRNA QUBO instances up to 152 variables and matches or exceeds simulator performance on IBM Heron processors fo...
-
Solving Classical and Quantum Spin Glasses with Deep Boltzmann Quantum States
Deep Boltzmann Quantum States with natural-gradient optimization and annealing-like training match exact or best-known solutions for large infinite-range Ising spin glasses and solve job shop scheduling instances.
-
Qubit-Scalable CVRP via Lagrangian Knapsack Decomposition and Noise-Aware Quantum Execution
A hybrid quantum framework decomposes CVRP into bounded-width knapsack subproblems, trains a reinforcement learning controller for Lagrangian multipliers, and uses a contextual bandit to adapt quantum hardware executi...
-
Improving Feasibility in Quantum Approximate Optimization Algorithm for Vehicle Routing via Constraint-Aware Initialization and Hybrid XY-X Mixing
Constraint-aware initialization and hybrid XY-X mixer in QAOA for VRP yield lower average energies and higher feasible-solution ratios than standard QAOA across ideal, finite-shot, and noisy simulations.
-
Thermodynamic significance of QUBO encoding on quantum annealers
Penalty weights in a QUBO encoding act as thermodynamic control knobs, changing both solver success and irreversibility on a quantum annealer.
-
Mitigating the barren plateau problem in linear optics
A dual-valued phase shifter in linear optics creates variational cost landscapes with fewer local minima and outperforms prior linear-optical variational algorithms by mitigating barren plateaus.
-
Performance-Driven QUBO for Recommender Systems on Quantum Annealers
PDQUBO is a new performance-driven QUBO method for feature selection in recommender systems that incorporates counterfactual performance impacts of features and pairs, is model-agnostic, and outperforms prior quantum ...
-
A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions
A compact QUBO encoding derived via ILP reduces logical variables by thousands in AES, MD5, SHA1 and SHA256, with over 8x reduction for AES-256.
-
COMET: Combinatorial Optimization for Multiplex Editing Targets Via Constraint-Preserving QAOA
On a three-gene CRISPR gRNA selection QUBO, XY-mixer QAOA reaches >95% optimum probability by depth 3 in simulation and keeps sim–hardware energy gap within |0.8| on ibm_kingston, while penalty variants stay below 6% ...
-
Principles of Quantum Optimization for Constrained Problems
Computational slowdown in constrained quantum optimization is attributed to the speed of entanglement restructuring, and the paper shows how constraints create (or avoid) the narrow spectral gaps where this restructur...
-
A Distributed Quantum Approximate Optimization Algorithm Simulator for Engineering Design Optimization
This paper presents a new open-source distributed QAOA simulator for QUBO problems that includes variable allocation across QPUs, runtime optimizations, a Streamlit GUI, and demonstrations of consistent results with m...
-
A Distributed Quantum Approximate Optimization Algorithm Simulator for Engineering Design Optimization
The authors built and released a distributed QAOA simulator supporting monolithic and multi-QPU modes, runtime optimizations, a GUI, and demonstrations on benchmarks plus a power unit commitment problem where all mode...
-
A Distributed Quantum Approximate Optimization Algorithm Simulator for Engineering Design Optimization
Develops and demonstrates a distributed QAOA simulator that produces solution bitstrings and costs matching classical monolithic QAOA and brute force on tested QUBO instances including unit commitment.
-
Performance Gains in Quantum SAT Solvers Using ESOP Encoding
ESOP-based e-CNF encoding for quantum SAT oracles yields lower qubit counts, T-gate complexity, and circuit depth than standard CNF.
-
A Quantum Inspired Variational Kernel and Explainable AI Framework for Cross Region Solar and Wind Energy Forecasting
A hybrid classical-plus-quantum-inspired framework for cross-region renewable energy forecasting matches top baselines within 1% accuracy and separates calm versus stormy conditions with a 15-fold higher Fisher discri...
-
Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems
Neural networks transform initial embeddings into feasible unit disk configurations for QUBO problems on Rydberg qubits and outperform the Gurobi solver in experiments.
-
Neural optimization for quantum architectures: graph embedding problems with Distance Encoder Networks
A modified autoencoder with a custom embedding loss learns spatial mappings to solve the constrained unit disk problem for qubit embedding on neutral-atom quantum processors and outperforms classical solvers under fix...
-
BBQ-mIS: a parallel quantum algorithm for graph coloring problems
BBQ-mIS decomposes graph coloring into parallel maximum independent set instances on Rydberg quantum hardware combined with classical branch-and-bound to produce proper colorings with few colors.
-
A penalty-free quantum algorithm to find energy eigenstates
A penalty-free, fully quantum algorithm is proposed for finding ground and excited states of many-body Hamiltonians.
-
EPIC-CIM: Training Convolutional Neural Networks on a Coherent Ising Machine via Equilibrium Propagation
An energy-based CIM training scheme with equilibrium propagation reportedly reaches 92.3% MNIST test accuracy, but lacks a valid derivation and reproducible details.
-
A Unified Local Light-shifts Encoding For Solving Optimization Problems on a Rydberg Annealer
A unified local light-shifts encoding maps QUBO instances of SAT variants, set packing, quadratic assignment, clustering, and protein folding onto Rydberg annealers and solves them via optimized quantum annealing.
-
Impact-Driven Quantum Decomposition for Traffic Zone Partitioning: A Hybrid Gate-Model Framework
Hybrid impact-guided quantum decomposition for QUBO traffic zone partitioning evaluated on IBM Quantum System One, showing improved convergence over classical refinement but not outperforming direct quantum solutions.
-
Impact-Driven Quantum Decomposition for Traffic Zone Partitioning: A Hybrid Gate-Model Framework
Impact-guided hybrid quantum decomposition for traffic zone partitioning improves convergence and spatial coherence over classical refinement but does not outperform direct quantum optimization on IBM hardware.
-
Solve Crude Oil Scheduling Problems by Using Quantum-Classical Hybrid Algorithms
Hybrid quantum-classical solver using Benders decomposition and QUBO reduces crude oil scheduling costs by 73-80% versus metaheuristics on 15 test instances while matching commercial solver speed.
-
Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing
QAOA and QWOA are applied to set balancing via an L2 QUBO formulation, and a scaled-exponential Pauli-string mixer decomposition is claimed to outperform conventional circuits, but the benchmark evidence is not reproducible.
-
Quantum-based QoE Optimization in Advanced Cellular Networks: Integration and Cloud Gaming Use Case
Quantum-inspired regressors match classical ML for cloud gaming KQI prediction on a controlled testbed, and a tensor-network optimizer matches brute-force with a modest speedup.
-
A Distributed Quantum Approximate Optimization Algorithm Simulator for Engineering Design Optimization
The authors release a distributed QAOA simulator package that supports monolithic and multi-QPU execution modes for QUBO instances and demonstrates consistent results with classical references on benchmarks and a unit...
-
An Empirical Evaluation of Quantum-Inspired QUBO Methods for Heterogeneous HPC Workflow Mapping and Scheduling
Empirical tests show QUBO-SA and QAOA-inspired schedulers lose feasibility beyond 10-15 tasks while MILP, CP-SAT, GA and HEFT remain robust on the same instances.
-
Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem
Iterative cutting-plane generation and arc preprocessing reduce TSP model size and yield performance gains on classical, direct quantum, and hybrid D-Wave solvers.
-
Feedback-Based Quantum Control for Safe and Synergistic Drug Combination Design
A quantum feedback algorithm finds ground-state drug combinations from Ising-encoded interaction data, but the problems are tiny and the interaction weights are hand-assigned.
-
Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games
The paper reviews QUDO, T-QUDO and HOBO formulations, provides explicit encodings between them, discusses limitations, and gives examples for knapsack, TSP and games including N-Queens and Peg Solitaire.
Discussion (0). Sign in to comment.