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:2009.07309 · npj Quantum Information

Space-efficient binary optimization for variational quantum computing

Adam Glos, Aleksandra Krawiec, Zoltán Zimborás

Published Apr 19, 2022• 103 citations
arXivHTMLPDF

Abstract

Abstract In the era of Noisy Intermediate-Scale Quantum (NISQ) computers it is crucial to design quantum algorithms which do not require many qubits or deep circuits. Unfortunately, most of the well-known quantum algorithms are too demanding to be run on currently available quantum devices. Moreover, even the state-of-the-art algorithms developed for the NISQ era often suffer from high space complexity requirements for particular problem classes. In this paper, we show that it is possible to greatly reduce the number of qubits needed for the Travelling Salesman Problem (TSP), a paradigmatic optimization task, at the cost of having deeper variational circuits. While the focus is on this particular problem, we claim that the approach can be generalized for other problems where the standard bit-encoding is highly inefficient. Finally, we also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models. All the proposed encodings have the same volume up to polylogarithmic factors and remain efficient to implement within the Quantum Approximate Optimization Algorithm framework.

DOI
10.1038/s41534-022-00546-y

Related papers

Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables

Simon Garhofer, Oliver Bringmann

The Quantum Approximate Optimization Algorithm (QAOA) and its derived variants are widely in use for approximating combinatorial optimization problem instances on gate-based Noisy Intermediate Scale Quantum (NISQ) computers. Commonly, circuits required for QAOA are constructed by first reformulating a given problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. It is then straightforward to synthesize a QAOA circuit from QUBO equations. In this work, we illustrate a more qubit-efficient circuit construction for combinatorial optimization problems by the example of the Traveling Salesperson Problem (TSP). Conventionally, the qubit encoding in QAOA for the TSP describes a tour using a sequence of nodes, where each node is written as a 1-hot binary vector. We propose to encode TSP tours by selecting edges included in the tour. Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding. We examined implementations of both QAOA encoding variants in terms of their approximation quality and runtime. Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical optimizer iterations increases only slightly.

arXiv:2412.07450•Dec 10, 2024•1 citation

Reducing the Number of Qubits from $n^2$ to $n\log_{2} (n)$ to Solve the Traveling Salesman Problem with Quantum Computers: A Proposal for Demonstrating Quantum Supremacy in the NISQ Era

Mehdi Ramezani, Sadegh Salami, Mehdi Shokhmkar +2 more

In our pursuit of quantum supremacy during the NISQ era, this research introduces a novel approach rooted in the Quantum Approximate Optimization Algorithm (QAOA) framework to address the Traveling Salesman Problem (TSP). By strategically reducing the requisite qubit count from $n^2$ to $n\log_{2} (n)$, our QAOA-based algorithm not only contributes to the ongoing discourse on qubit efficiency but also demonstrates improved performance based on established metrics, underscoring its potential for achieving NISQ-era supremacy in solving real-world optimization challenges.

arXiv:2402.18530•Feb 28, 2024•13 citations

Combinatorial optimization using quantum computing

Gloria Oppong

This thesis explores quantum computing for combinatorial optimization through the Traveling Salesman Problem (TSP), which aims to find a minimum-cost Hamiltonian cycle visiting each city exactly once. Using Qiskit, we implement the Quantum Approximate Optimization Algorithm (QAOA) on both simulators and quantum hardware, and compare its performance with that of classical exact optimization via the Gurobi solver. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with degree and subtour constraints embedded using quadratic penalties. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound solvers outperform it in both solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, the optimality gap grows with problem size, reflecting sensitivity to variational parameter tuning, penalty scaling, and hardware noise. Among classical optimizers for QAOA, COBYLA offers the most effective tradeoff between 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 1, 2026•0 citations

Variational Quantum Algorithms for Combinatorial Optimization

Daniel F. Pérez-Ramírez

The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.

arXiv:2407.06421•Jul 8, 2024•20 citations

A Resource-Efficient Variational Quantum Framework for the Traveling Salesman Problem

Yuefeng Lin, Chao Zheng, Cong Guo

The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.

quant-pharXiv:2605.00739•May 4, 2026•0 citations

Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs

Bence Bakó, Adam Glos, Özlem Salehi +1 more

Current state-of-the-art quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent cost Hamiltonian suitable for the quantum device. Implementing each term of the cost Hamiltonian separately often results in high redundancy, significantly increasing the resources required. Instead, we propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits, eliminating the reliance on the binary optimization problem representation. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Program-based QAOA (Prog-QAOA). We exploit this idea for optimization tasks like the Travelling Salesman Problem and Max- K -Cut and obtain circuits that are near-optimal with respect to all relevant cost measures, e.g., number of qubits, gates, and circuit depth. While we demonstrate the power of Prog-QAOA only for a particular set of paradigmatic problems, our approach is conveniently applicable to generic optimization problems.

arXiv:2209.03386•Quantum•Mar 20, 2025•36 citations
Abstract In the era of Noisy Intermediate-Scale Quantum (NISQ) computers it is crucial to design quantum algorithms which do not require many qubits or deep circuits. Unfortunately, most of the well-known quantum algorithms are too demanding to be run on currently available quantum devices. Moreover, even the state-of-the-art algorithms developed for the NISQ era often suffer from high space complexity requirements for particular problem classes. In this paper, we show that it is possible to greatly reduce the number of qubits needed for the Travelling Salesman Problem (TSP), a paradigmatic optimization task, at the cost of having deeper variational circuits. While the focus is on this particular problem, we claim that the approach can be generalized for other problems where the standard bit-encoding is highly inefficient. Finally, we also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models. All the proposed encodings have the same volume up to polylogarithmic factors and remain efficient to implement within the Quantum Approximate Optimization Algorithm framework.
The Quantum Approximate Optimization Algorithm (QAOA) and its derived variants are widely in use for approximating combinatorial optimization problem instances on gate-based Noisy Intermediate Scale Quantum (NISQ) computers. Commonly, circuits required for QAOA are constructed by first reformulating a given problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. It is then straightforward to synthesize a QAOA circuit from QUBO equations. In this work, we illustrate a more qubit-efficient circuit construction for combinatorial optimization problems by the example of the Traveling Salesperson Problem (TSP). Conventionally, the qubit encoding in QAOA for the TSP describes a tour using a sequence of nodes, where each node is written as a 1-hot binary vector. We propose to encode TSP tours by selecting edges included in the tour. Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding. We examined implementations of both QAOA encoding variants in terms of their approximation quality and runtime. Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical optimizer iterations increases only slightly.
Reducing the Number of Qubits from n2n^2n2 to nlog⁡2(n)n\log_{2} (n)nlog2​(n) to Solve the Traveling Salesman Problem with Quantum Computers: A Proposal for Demonstrating Quantum Supremacy in the NISQ Era
In our pursuit of quantum supremacy during the NISQ era, this research introduces a novel approach rooted in the Quantum Approximate Optimization Algorithm (QAOA) framework to address the Traveling Salesman Problem (TSP). By strategically reducing the requisite qubit count from n2n^2n2 to nlog⁡2(n)n\log_{2} (n)nlog2​(n), our QAOA-based algorithm not only contributes to the ongoing discourse on qubit efficiency but also demonstrates improved performance based on established metrics, underscoring its potential for achieving NISQ-era supremacy in solving real-world optimization challenges.
This thesis explores quantum computing for combinatorial optimization through the Traveling Salesman Problem (TSP), which aims to find a minimum-cost Hamiltonian cycle visiting each city exactly once. Using Qiskit, we implement the Quantum Approximate Optimization Algorithm (QAOA) on both simulators and quantum hardware, and compare its performance with that of classical exact optimization via the Gurobi solver. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with degree and subtour constraints embedded using quadratic penalties. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound solvers outperform it in both solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, the optimality gap grows with problem size, reflecting sensitivity to variational parameter tuning, penalty scaling, and hardware noise. Among classical optimizers for QAOA, COBYLA offers the most effective tradeoff between 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.
The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.
The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.
Current state-of-the-art quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent cost Hamiltonian suitable for the quantum device. Implementing each term of the cost Hamiltonian separately often results in high redundancy, significantly increasing the resources required. Instead, we propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits, eliminating the reliance on the binary optimization problem representation. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Program-based QAOA (Prog-QAOA). We exploit this idea for optimization tasks like the Travelling Salesman Problem and Max- K -Cut and obtain circuits that are near-optimal with respect to all relevant cost measures, e.g., number of qubits, gates, and circuit depth. While we demonstrate the power of Prog-QAOA only for a particular set of paradigmatic problems, our approach is conveniently applicable to generic optimization problems.