Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2004.14036

Insights on Training Neural Networks for QUBO Tasks

Thomas Gabor, Sebastian Feld, Hila Safi, Thomy Phan, Claudia Linnhoff–Popien

Published Jun 27, 2020• 3 citations
arXivHTMLPDF

Abstract

Current hardware limitations restrict the potential when solving quadratic unconstrained binary optimization (QUBO) problems via the quantum approximate optimization algorithm (QAOA) or quantum annealing (QA). Thus, we consider training neural networks in this context. We first discuss QUBO problems that originate from translated instances of the traveling salesman problem (TSP): Analyzing this representation via autoencoders shows that there is way more information included than necessary to solve the original TSP. Then we show that neural networks can be used to solve TSP instances from both QUBO input and autoencoders' hidden state representation. We finally generalize the approach and successfully train neural networks to solve arbitrary QUBO problems, sketching means to use neuromorphic hardware as a simulator or an additional co-processor for quantum computing.

DOI
10.1145/3387940.3391470

Related papers

ILP-Based QUBO Encodings of the Traveling Salesman Problem: Derivation and Benchmarking on Quantum Annealing Hardware

Katarzyna Nałęcz-Charkiewicz

The Traveling Salesman Problem (TSP) has been one of the most intensively studied problems in theoretical computer science for decades. Being NP-hard, it is unlikely to be solved in polynomial time; hence, despite numerous classical exact and approximate methods, quantum-inspired approaches are also explored. In this study, we analyze several formulations of the TSP suitable for quantum annealing, focusing not only on qubit requirements but also on practical performance, i.e., how frequently feasible and optimal solutions are obtained. We consider both complete and non-complete graphs, reflecting common real-world scenarios. One of the analyzed formulations corresponds to a previously established Quadratic Unconstrained Binary Optimization (QUBO) model, while the others originate from classical Integer Linear Programming (ILP) formulations. We provide a unified, step-by-step translation of selected compact ILP TSP formulations into QUBO models. We analytically show that for non-complete graphs these encodings are asymptotically smaller than the commonly used baseline formulation. We benchmark the formulations using simulated and quantum annealing to evaluate their feasibility and optimality rates. The results are discussed in the context of current quantum annealing hardware limitations, including QPU size and embedding overhead.

International Journal of Electronics and Telecommunications•Oct 29, 2026•0 citations

Solving the Traveling Salesman Problem Using Quantum Devices: QUBO and HOBO Formulations

G. V. Shuvalov, E. N. Krivtsova, M. A. Remnev +1 more

Abstract The traveling salesman problem (TSP) forms the foundation for many logistics and optimization tasks. At the same time, this problem is NP-hard and requires significant computational resources. Quantum computing promises to substantially accelerate computations or increase solution accuracy. The TSP can be conveniently mapped onto the quadratic unconstrained binary optimization (QUBO) formulation, which in turn can be solved using variational quantum eigensolver (VQE) and quantum approximate optimization algorithm (QAOA) methods, but this mapping requires a quadratic number of qubits. The higher-order binary optimization (HOBO) formulation requires significantly fewer qubits, but it contains higher-order terms. In our work, we thoroughly investigate both formulations and provide a practical recipe for solving the TSP. We give a comprehensive study and compare in detail QUBO and HOBO formulations.

Russian Microelectronics•Dec 1, 2025•0 citations

Quadratic Binary Optimization with Graph Neural Networks

Moshe Eliasof, Eldad Haber

We investigate a link between Graph Neural Networks (GNNs) and Quadratic Unconstrained Binary Optimization (QUBO) problems, laying the groundwork for GNNs to approximate solutions for these computationally challenging tasks. By analyzing the sensitivity of QUBO formulations, we frame the solution of QUBO problems as a heterophilic node classification task. We then propose QUBO-GNN, an architecture that integrates graph representation learning techniques with QUBO-aware features to approximate solutions efficiently. Additionally, we introduce a self-supervised data generation mechanism to enable efficient and scalable training data acquisition even for large-scale QUBO instances. Experimental evaluations of QUBO-GNN across diverse QUBO problem sizes demonstrate its superior performance compared to exhaustive search and heuristic methods. Finally, we discuss open challenges in the emerging intersection between QUBO optimization and GNN-based learning.

arXiv:2404.04874•Frontiers in artificial intelligence and applications•Oct 21, 2025•3 citations

Quantum Algorithms for Discrete and Combinatorial Optimization

Gloria Oppong

This study explores quantum computing for combinatorial optimization, focusing on the Traveling Salesman Problem (TSP). Using Qiskit, the Quantum Approximate Optimization Algorithm (QAOA) is implemented on simulators and quantum hardware, and compared with classical optimization using Gurobi. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with quadratic penalties enforcing degree and subtour constraints. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound methods achieve better solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, performance degrades with problem size due to sensitivity to parameter tuning, penalty scaling, and hardware noise. Among the tested classical optimizers, COBYLA provides the best balance of efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.

•May 5, 2026•0 citations

How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization

Thomas Gabor, Marian Lingsch-Rosenfeld, Claudia Linnhoff–Popien +1 more

Quadratic unconstrained binary optimization (QUBO) has become the standard format for optimization using quantum computers, i.e., for both the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). We present a toolkit of methods to transform almost arbitrary problems to QUBO by (i) approximating them as a polynomial and then (ii) translating any polynomial to QUBO. We showcase the usage of our approaches on two example problems (ratio cut and logistic regression).

arXiv:2204.11035•IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)•Mar 1, 2022•15 citations

Quantum Annealing Formulation for Binary Neural Networks

Michele Sasdelli, Tat-Jun Chin

Quantum annealing is a promising paradigm for building practical quantum computers. Compared to other approaches, quantum annealing technology has been scaled up to a larger number of qubits. On the other hand, deep learning has been profoundly successful in pushing the boundaries of AI. It is thus natural to investigate potentially game changing technologies such as quantum annealers to augment the capabilities of deep learning. In this work, we explore binary neural networks, which are lightweight yet powerful models typically intended for resource constrained devices. Departing from current training regimes for binary networks that smooth/approximate the activation functions to make the network differentiable, we devise a quadratic unconstrained binary optimization formulation for the training problem. While the problem is intractable, i.e., the cost to estimate the binary weights scales exponentially with network size, we show how the problem can be optimized directly on a quantum annealer, thereby opening up to the potential gains of quantum computing. We experimentally validated our formulation via simulation and testing on an actual quantum annealer (D-Wave Advantage), the latter to the extent allowable by the capacity of current technology.

arXiv:2107.02751•International Conference on Digital Image Computing: Techniques and Applications (DICTA)•Nov 1, 2021•18 citations
Current hardware limitations restrict the potential when solving quadratic unconstrained binary optimization (QUBO) problems via the quantum approximate optimization algorithm (QAOA) or quantum annealing (QA). Thus, we consider training neural networks in this context. We first discuss QUBO problems that originate from translated instances of the traveling salesman problem (TSP): Analyzing this representation via autoencoders shows that there is way more information included than necessary to solve the original TSP. Then we show that neural networks can be used to solve TSP instances from both QUBO input and autoencoders' hidden state representation. We finally generalize the approach and successfully train neural networks to solve arbitrary QUBO problems, sketching means to use neuromorphic hardware as a simulator or an additional co-processor for quantum computing.
The Traveling Salesman Problem (TSP) has been one of the most intensively studied problems in theoretical computer science for decades. Being NP-hard, it is unlikely to be solved in polynomial time; hence, despite numerous classical exact and approximate methods, quantum-inspired approaches are also explored. In this study, we analyze several formulations of the TSP suitable for quantum annealing, focusing not only on qubit requirements but also on practical performance, i.e., how frequently feasible and optimal solutions are obtained. We consider both complete and non-complete graphs, reflecting common real-world scenarios. One of the analyzed formulations corresponds to a previously established Quadratic Unconstrained Binary Optimization (QUBO) model, while the others originate from classical Integer Linear Programming (ILP) formulations. We provide a unified, step-by-step translation of selected compact ILP TSP formulations into QUBO models. We analytically show that for non-complete graphs these encodings are asymptotically smaller than the commonly used baseline formulation. We benchmark the formulations using simulated and quantum annealing to evaluate their feasibility and optimality rates. The results are discussed in the context of current quantum annealing hardware limitations, including QPU size and embedding overhead.
Abstract The traveling salesman problem (TSP) forms the foundation for many logistics and optimization tasks. At the same time, this problem is NP-hard and requires significant computational resources. Quantum computing promises to substantially accelerate computations or increase solution accuracy. The TSP can be conveniently mapped onto the quadratic unconstrained binary optimization (QUBO) formulation, which in turn can be solved using variational quantum eigensolver (VQE) and quantum approximate optimization algorithm (QAOA) methods, but this mapping requires a quadratic number of qubits. The higher-order binary optimization (HOBO) formulation requires significantly fewer qubits, but it contains higher-order terms. In our work, we thoroughly investigate both formulations and provide a practical recipe for solving the TSP. We give a comprehensive study and compare in detail QUBO and HOBO formulations.
We investigate a link between Graph Neural Networks (GNNs) and Quadratic Unconstrained Binary Optimization (QUBO) problems, laying the groundwork for GNNs to approximate solutions for these computationally challenging tasks. By analyzing the sensitivity of QUBO formulations, we frame the solution of QUBO problems as a heterophilic node classification task. We then propose QUBO-GNN, an architecture that integrates graph representation learning techniques with QUBO-aware features to approximate solutions efficiently. Additionally, we introduce a self-supervised data generation mechanism to enable efficient and scalable training data acquisition even for large-scale QUBO instances. Experimental evaluations of QUBO-GNN across diverse QUBO problem sizes demonstrate its superior performance compared to exhaustive search and heuristic methods. Finally, we discuss open challenges in the emerging intersection between QUBO optimization and GNN-based learning.
This study explores quantum computing for combinatorial optimization, focusing on the Traveling Salesman Problem (TSP). Using Qiskit, the Quantum Approximate Optimization Algorithm (QAOA) is implemented on simulators and quantum hardware, and compared with classical optimization using Gurobi. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with quadratic penalties enforcing degree and subtour constraints. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound methods achieve better solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, performance degrades with problem size due to sensitivity to parameter tuning, penalty scaling, and hardware noise. Among the tested classical optimizers, COBYLA provides the best balance of efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.
Quantum annealing is a promising paradigm for building practical quantum computers. Compared to other approaches, quantum annealing technology has been scaled up to a larger number of qubits. On the other hand, deep learning has been profoundly successful in pushing the boundaries of AI. It is thus natural to investigate potentially game changing technologies such as quantum annealers to augment the capabilities of deep learning. In this work, we explore binary neural networks, which are lightweight yet powerful models typically intended for resource constrained devices. Departing from current training regimes for binary networks that smooth/approximate the activation functions to make the network differentiable, we devise a quadratic unconstrained binary optimization formulation for the training problem. While the problem is intractable, i.e., the cost to estimate the binary weights scales exponentially with network size, we show how the problem can be optimized directly on a quantum annealer, thereby opening up to the potential gains of quantum computing. We experimentally validated our formulation via simulation and testing on an actual quantum annealer (D-Wave Advantage), the latter to the extent allowable by the capacity of current technology.