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

A Review of Quantum Algorithms for the Unconstrained Shortest Path Problem

Theodorakopoulos, Panagiotis, Ani Anciaux‐Sedrakian, Ibtihel Ben Gharbia, Hamza Jaffali, Abdel Lisser, Quang Huy Tran

Published Apr 24, 2026• 0 citations
OpenAlex

Abstract

We investigate the relevance of variational algorithms for the single-source single-destination shortest path problem, within the application framework of eco-routing. The problem is formulated via a Quadratic Unconstrained Binary Optimization (QUBO) model, which is solved using VQE and QAOA algorithms. For QAOA two different initialization schemes are tested, based on a heuristic strategy, whereas for VQE we test two different ansatzes. The results highlight both the feasibility and scalability issues of solving the shortest path problem with quantum optimization approaches, while providing a simple yet interesting comparison between VQE and QAOA. This work aims to establish an initial direction towards addressing more challenging constrained variants of the problem.

Related papers

Solving the Network Shortest Path Problem on a Quantum Annealer

Thomas Krauss, Joey McCollum

This article addresses the formulation for implementing a single source, single-destination shortest path algorithm on a quantum annealing computer. Three distinct approaches are presented. In all the three cases, the shortest path problem is formulated as a quadratic unconstrained binary optimization problem amenable to quantum annealing. The first implementation builds on existing quantum annealing solutions to the traveling salesman problem, and requires the anticipated maximum number of vertices on the solution path |P| to be provided as an input. For a graph with |V| vertices, |E| edges, and no self-loops, it encodes the problem instance using |V||P| qubits. The second implementation adapts the linear programming formulation of the shortest path problem, and encodes the problem instance using |E| qubits for directed graphs or 2|E| qubits for undirected graphs. The third implementation, designed exclusively for undirected graphs, encodes the problem in |E| + |V| qubits. Scaling factors for penalty terms, complexity of coupling matrix construction, and numerical estimates of the annealing time required to find the shortest path are made explicit in the article.

IEEE Transactions on Quantum Engineering•Jan 1, 2020•34 citations

A Comparative Study On Solving Optimization Problems With Exponentially Fewer Qubits

David Winderl, Nicola Franco, Jeanette Miriam Lorenz

Variational Quantum optimization algorithms, such as the Variational Quantum Eigensolver (VQE) or the Quantum Approximate Optimization Algorithm (QAOA), are among the most studied quantum algorithms. In our work, we evaluate and improve an algorithm based on VQE, which uses exponentially fewer qubits compared to the QAOA. We highlight the numerical instabilities generated by encoding the problem into the variational ansatz and propose a classical optimization procedure to find the ground-state of the ansatz in less iterations with a better or similar objective. Furthermore, we compare classical optimizers for this variational ansatz on quadratic unconstrained binary optimization and graph partitioning problems.

arXiv:2210.11823•Oct 21, 2022•1 citation

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

Energy Internet Routing using Quantum Optimization Algorithms

Alireza Alamgir Tehrani, Mehrdad Boroushaki, Abbas Rajabi

The Energy Internet (EI) is a new concept aimed at enhancing the integration of renewable energy sources with the energy grid. Energy-efficient path selection in EI is NP-hard. This research presents an innovative Quadratic Unconstrained Binary Optimization (QUBO) and Ising Hamiltonian formulation for energy routing. The validation and scalability of the proposed formulation were evaluated by applying quantum-inspired annealing and quantum gate optimization to two case studies, a 9-node and a 30-node EI network. A comparative analysis was presented between classical optimization using the Dijkstra algorithm, optimization-based methods, and QAOA using the Qiskit Sampler Primitive, NumpyEigenSolver, and quantum-inspired annealing using the Ocean exact Solver, D-Wave Tabu Sampler, and D-Wave Simulated Annealing. Simulation results based on the proposed formulation agree with the exact solution, while the runtime of classical approaches is less than that of quantum approaches. However, the Simulated Annealing sampler offers the shortest runtime among all quantum methods.

quant-pharXiv:2608.28401•Aug 31, 2026•0 citations

A Comparative Study on Solving Optimization Problems With Exponentially Fewer Qubits

David Winderl, Nicola Franco, Jeanette Miriam Lorenz

Variational quantum optimization algorithms, such as the Variational Quantum Eigensolver (VQE) or the Quantum Approximate Optimization Algorithm (QAOA), are among the most studied quantum algorithms. In our work, we evaluate and improve an algorithm based on VQE, which uses exponentially fewer qubits compared to the QAOA. We highlight the numerical instabilities generated by encoding the problem into the variational ansatz and propose a classical optimization procedure to find the ground-state of the ansatz in less iterations with a better or similar objective. Additionally, we propose a method to embed the linear interpolation of the MaxCut problem on a quantum device. Furthermore, we compare classical optimizers for this variational ansatz on quadratic unconstrained binary optimization and graph partitioning problems.

IEEE Transactions on Quantum Engineering•Jan 1, 2024•5 citations

Quantum Optimization in Loc(Q)ation Science: QUBO Formulations, Benchmark Problems, and a Computational Study

Felix P. Broesamle, Stefan Nickel

Recent advances in quantum computing and the increasing availability of quantum hardware have substantially enhanced the practical relevance of quantum approaches to discrete optimization. Among these, the Quadratic Unconstrained Binary Optimization (QUBO) formulation provides a unifying modeling framework for a broad class of $\mathbf{NP}$-hard problems and is naturally suited to quantum computing and quantum-inspired algorithms. Location science, network design, and logistics represent core application domains of discrete optimization, combining high practical impact with substantial computational challenges. In this work, we develop QUBO formulations for several fundamental problems in these domains, including a nonlinear integer formulation of the Discrete Ordered Median Problem (DOMP). Beyond their modeling relevance, these QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware. We further derive a tight bound for the penalty parameter ensuring equivalence between the QUBO formulation and its underlying integer program. Finally, we conduct a comprehensive computational study using QAOA, WS-QAOA, and classical heuristics for QUBO instances of the $p$-Median Problem and the Fixed-Charge Facility Location Problem (FCFLP), and introduce two effective warm-start strategies for WS-QAOA based on its linear programming relaxation.

quant-pharXiv:2602.10951•Feb 12, 2026•0 citations
We investigate the relevance of variational algorithms for the single-source single-destination shortest path problem, within the application framework of eco-routing. The problem is formulated via a Quadratic Unconstrained Binary Optimization (QUBO) model, which is solved using VQE and QAOA algorithms. For QAOA two different initialization schemes are tested, based on a heuristic strategy, whereas for VQE we test two different ansatzes. The results highlight both the feasibility and scalability issues of solving the shortest path problem with quantum optimization approaches, while providing a simple yet interesting comparison between VQE and QAOA. This work aims to establish an initial direction towards addressing more challenging constrained variants of the problem.
This article addresses the formulation for implementing a single source, single-destination shortest path algorithm on a quantum annealing computer. Three distinct approaches are presented. In all the three cases, the shortest path problem is formulated as a quadratic unconstrained binary optimization problem amenable to quantum annealing. The first implementation builds on existing quantum annealing solutions to the traveling salesman problem, and requires the anticipated maximum number of vertices on the solution path |P| to be provided as an input. For a graph with |V| vertices, |E| edges, and no self-loops, it encodes the problem instance using |V||P| qubits. The second implementation adapts the linear programming formulation of the shortest path problem, and encodes the problem instance using |E| qubits for directed graphs or 2|E| qubits for undirected graphs. The third implementation, designed exclusively for undirected graphs, encodes the problem in |E| + |V| qubits. Scaling factors for penalty terms, complexity of coupling matrix construction, and numerical estimates of the annealing time required to find the shortest path are made explicit in the article.
Variational Quantum optimization algorithms, such as the Variational Quantum Eigensolver (VQE) or the Quantum Approximate Optimization Algorithm (QAOA), are among the most studied quantum algorithms. In our work, we evaluate and improve an algorithm based on VQE, which uses exponentially fewer qubits compared to the QAOA. We highlight the numerical instabilities generated by encoding the problem into the variational ansatz and propose a classical optimization procedure to find the ground-state of the ansatz in less iterations with a better or similar objective. Furthermore, we compare classical optimizers for this variational ansatz on quadratic unconstrained binary optimization and graph partitioning problems.
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.
The Energy Internet (EI) is a new concept aimed at enhancing the integration of renewable energy sources with the energy grid. Energy-efficient path selection in EI is NP-hard. This research presents an innovative Quadratic Unconstrained Binary Optimization (QUBO) and Ising Hamiltonian formulation for energy routing. The validation and scalability of the proposed formulation were evaluated by applying quantum-inspired annealing and quantum gate optimization to two case studies, a 9-node and a 30-node EI network. A comparative analysis was presented between classical optimization using the Dijkstra algorithm, optimization-based methods, and QAOA using the Qiskit Sampler Primitive, NumpyEigenSolver, and quantum-inspired annealing using the Ocean exact Solver, D-Wave Tabu Sampler, and D-Wave Simulated Annealing. Simulation results based on the proposed formulation agree with the exact solution, while the runtime of classical approaches is less than that of quantum approaches. However, the Simulated Annealing sampler offers the shortest runtime among all quantum methods.
Variational quantum optimization algorithms, such as the Variational Quantum Eigensolver (VQE) or the Quantum Approximate Optimization Algorithm (QAOA), are among the most studied quantum algorithms. In our work, we evaluate and improve an algorithm based on VQE, which uses exponentially fewer qubits compared to the QAOA. We highlight the numerical instabilities generated by encoding the problem into the variational ansatz and propose a classical optimization procedure to find the ground-state of the ansatz in less iterations with a better or similar objective. Additionally, we propose a method to embed the linear interpolation of the MaxCut problem on a quantum device. Furthermore, we compare classical optimizers for this variational ansatz on quadratic unconstrained binary optimization and graph partitioning problems.
Recent advances in quantum computing and the increasing availability of quantum hardware have substantially enhanced the practical relevance of quantum approaches to discrete optimization. Among these, the Quadratic Unconstrained Binary Optimization (QUBO) formulation provides a unifying modeling framework for a broad class of NP\mathbf{NP}NP-hard problems and is naturally suited to quantum computing and quantum-inspired algorithms. Location science, network design, and logistics represent core application domains of discrete optimization, combining high practical impact with substantial computational challenges. In this work, we develop QUBO formulations for several fundamental problems in these domains, including a nonlinear integer formulation of the Discrete Ordered Median Problem (DOMP). Beyond their modeling relevance, these QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware. We further derive a tight bound for the penalty parameter ensuring equivalence between the QUBO formulation and its underlying integer program. Finally, we conduct a comprehensive computational study using QAOA, WS-QAOA, and classical heuristics for QUBO instances of the ppp-Median Problem and the Fixed-Charge Facility Location Problem (FCFLP), and introduce two effective warm-start strategies for WS-QAOA based on its linear programming relaxation.