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

IEEE Transactions on Quantum Engineering

A Comparative Study on Solving Optimization Problems With Exponentially Fewer Qubits

David Winderl, Nicola Franco, Jeanette Miriam Lorenz

Published Jan 1, 2024• 5 citations
Publisher

Abstract

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.

DOI
10.1109/tqe.2024.3392834

Related papers

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

Towards Solving Large QUBO Problems Using Quantum Algorithms: Improving the LogQ Scheme

Yagnik Chatterjee, J. Messud

The LogQ algorithm encodes Quadratic Unconstrained Binary Optimization (QUBO) problems with exponentially fewer qubits than the Quantum Approximate Optimization Algorithm (QAOA). The advantages of conventional LogQ are accompanied by a challenge related to the optimization of its free parameters, which requires the usage of resourceintensive evolutionary or even global optimization algorithms. We propose a new$\log Q$parameterization that can be optimized with a gradient-inspired method, which is less resource-intensive and thus strengthens the advantage of LogQ over QAOA for large/industrial problems. We illustrate the features of our method on an analytical model and present larger scale numerical results on MaxCut problems.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

An exponentially more efficient optimization algorithm for noisy quantum computers

Marko J. Rančić

Quantum computers are devices which allow the solution of problems unsolvable to their classical counterparts. As an error-corrected quantum computer is still a decade away the quantum computing community has dedicated much attention to developing algorithms for currently available Noisy Intermediate-Scale Quantum computers (NISQ). Thus far, within NISQ, optimization problems are one of the most commonly studied and are exclusively tackled with the Quantum Approximate Optimization Algorithm (QAOA). This algorithm predominantly computes graph partitions with a maximal separation of edges (MaxCut), but can also be modified to calculate other properties of graphs. Here, I present a novel quantum optimization algorithm which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem. Such an improved performance allowed me to partition a graphs 32 nodes on publicly available 5 qubit gate-based solid state quantum devices without any preprocessing such as division of the graph into smaller subgraphs. This results represent a 40% increase in graph size as compared to state-of-art experiments on solid state devices such as Google Sycamore. The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal quantum simulators. Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with quantum simulators, again without any pre-division into smaller subproblems and a lower solution bound of 67.9% is achieved.

•Oct 22, 2021•3 citations

Solving Constrained Optimization Problems Using Hybrid Qubit-Qumode Quantum Devices

Rishab Dutta, Brandon Allen, Chuzhi Xu +8 more

Variational Quantum Algorithms (VQAs) provide a promising framework for tackling complex optimization problems on near-term quantum hardware. Here, we demonstrate that hybrid qubit-qumode quantum devices offer an efficient route to solving Quadratic Unconstrained Binary Optimization (QUBO) problems using the Echoed Conditional Displacement Variational Quantum Eigensolver (ECD-VQE). Leveraging circuit quantum electrodynamics (cQED) architectures, we encode QUBO instances across multiple qumodes weakly coupled to a single qubit and extract binary solutions directly from photon-number measurements. We apply ECD-VQE to the Binary Knapsack Problem and show that it outperforms the Quantum Approximate Optimization Algorithm (QAOA) implemented on conventional qubit circuits, achieving higher-quality solutions with dramatically fewer resources. We also demonstrate that ECD-VQE can be extended to chemically motivated tasks such as active-space selection for multireference electronic structure methods. These results highlight the utility of hybrid qubit-qumode platforms for a broad class of NP-hard and chemistry-related optimization problems and demonstrate that variational ECD ansatz can realize expressive state preparation with significantly shallower circuits than qubit-only architectures, positioning qubit-qumode gates as compelling candidates for constrained optimization in early fault-tolerant quantum computing.

arXiv:2501.11735•Journal of Chemical Theory and Computation•May 14, 2026•0 citations

Variational Ansatz preparation to avoid CNOT-gates on noisy quantum devices for combinatorial optimizations

Tsukasa Miki, Ryo Okita, Moe Shimada +2 more

The variational quantum eigensolver (VQE), which is a quantum–classical hybrid approach, has latent powers to leverage near-term quantum devices by effectively managing a limited number of qubits with finite coherent lifetimes. While it is generally argued that the quantum approximate optimization algorithm (QAOA), which is a special case of VQE with a variational Ansatz based on the adiabatic theorem, may enable practical applications of noisy quantum devices for classical combinatorial optimizations, the strategy to improve the performance of this algorithm by increasing the circuit depth conflicts with the limited coherence time of near-term quantum devices. Here, we introduce strategies involving the VQE to reduce the circuit resources required for solving combinatorial optimizations. Our concept of a parameterized quantum circuit allows the Ansatz preparation to be achieved by only single-qubit operation. We find that the variational Ansatz without controlled X-gates leads to quick convergence in a classical subroutine used to determine the variational parameters. In addition, the variational Ansatz with optimized parameters maintains performance over the problem sizes both on the numerical simulation and IBM 27-qubit processor “ibm_kawasaki.” Therefore, the variational Ansatz introduced in this study has several advantages considering the total calculation time and performance scaling over the problem sizes. We also show that the variational Ansatz consisting of a lower number of gate operations than that of QAOA can approximate the eigenstates of diagonal Hamiltonians with high accuracy. We illustrate our ideas with a maximum-cut problem and show that near-term quantum applications may be feasible using short-depth circuits.

AIP Advances•Mar 1, 2022•16 citations

A Variational Qubit-Efficient MaxCut Heuristic Algorithm

Yovav Tene-Cohen, Tomer Kelman, Ohad Lev +1 more

Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only $$O(\log N)$$ O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.

arXiv:2308.10383•npj Quantum Information•Feb 16, 2026•3 citations
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.
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.
The LogQ algorithm encodes Quadratic Unconstrained Binary Optimization (QUBO) problems with exponentially fewer qubits than the Quantum Approximate Optimization Algorithm (QAOA). The advantages of conventional LogQ are accompanied by a challenge related to the optimization of its free parameters, which requires the usage of resourceintensive evolutionary or even global optimization algorithms. We propose a newlog⁡Q\log QlogQparameterization that can be optimized with a gradient-inspired method, which is less resource-intensive and thus strengthens the advantage of LogQ over QAOA for large/industrial problems. We illustrate the features of our method on an analytical model and present larger scale numerical results on MaxCut problems.
Quantum computers are devices which allow the solution of problems unsolvable to their classical counterparts. As an error-corrected quantum computer is still a decade away the quantum computing community has dedicated much attention to developing algorithms for currently available Noisy Intermediate-Scale Quantum computers (NISQ). Thus far, within NISQ, optimization problems are one of the most commonly studied and are exclusively tackled with the Quantum Approximate Optimization Algorithm (QAOA). This algorithm predominantly computes graph partitions with a maximal separation of edges (MaxCut), but can also be modified to calculate other properties of graphs. Here, I present a novel quantum optimization algorithm which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem. Such an improved performance allowed me to partition a graphs 32 nodes on publicly available 5 qubit gate-based solid state quantum devices without any preprocessing such as division of the graph into smaller subgraphs. This results represent a 40% increase in graph size as compared to state-of-art experiments on solid state devices such as Google Sycamore. The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal quantum simulators. Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with quantum simulators, again without any pre-division into smaller subproblems and a lower solution bound of 67.9% is achieved.
Variational Quantum Algorithms (VQAs) provide a promising framework for tackling complex optimization problems on near-term quantum hardware. Here, we demonstrate that hybrid qubit-qumode quantum devices offer an efficient route to solving Quadratic Unconstrained Binary Optimization (QUBO) problems using the Echoed Conditional Displacement Variational Quantum Eigensolver (ECD-VQE). Leveraging circuit quantum electrodynamics (cQED) architectures, we encode QUBO instances across multiple qumodes weakly coupled to a single qubit and extract binary solutions directly from photon-number measurements. We apply ECD-VQE to the Binary Knapsack Problem and show that it outperforms the Quantum Approximate Optimization Algorithm (QAOA) implemented on conventional qubit circuits, achieving higher-quality solutions with dramatically fewer resources. We also demonstrate that ECD-VQE can be extended to chemically motivated tasks such as active-space selection for multireference electronic structure methods. These results highlight the utility of hybrid qubit-qumode platforms for a broad class of NP-hard and chemistry-related optimization problems and demonstrate that variational ECD ansatz can realize expressive state preparation with significantly shallower circuits than qubit-only architectures, positioning qubit-qumode gates as compelling candidates for constrained optimization in early fault-tolerant quantum computing.
The variational quantum eigensolver (VQE), which is a quantum–classical hybrid approach, has latent powers to leverage near-term quantum devices by effectively managing a limited number of qubits with finite coherent lifetimes. While it is generally argued that the quantum approximate optimization algorithm (QAOA), which is a special case of VQE with a variational Ansatz based on the adiabatic theorem, may enable practical applications of noisy quantum devices for classical combinatorial optimizations, the strategy to improve the performance of this algorithm by increasing the circuit depth conflicts with the limited coherence time of near-term quantum devices. Here, we introduce strategies involving the VQE to reduce the circuit resources required for solving combinatorial optimizations. Our concept of a parameterized quantum circuit allows the Ansatz preparation to be achieved by only single-qubit operation. We find that the variational Ansatz without controlled X-gates leads to quick convergence in a classical subroutine used to determine the variational parameters. In addition, the variational Ansatz with optimized parameters maintains performance over the problem sizes both on the numerical simulation and IBM 27-qubit processor “ibm_kawasaki.” Therefore, the variational Ansatz introduced in this study has several advantages considering the total calculation time and performance scaling over the problem sizes. We also show that the variational Ansatz consisting of a lower number of gate operations than that of QAOA can approximate the eigenstates of diagonal Hamiltonians with high accuracy. We illustrate our ideas with a maximum-cut problem and show that near-term quantum applications may be feasible using short-depth circuits.
Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only O(log⁡N)O(\log N)O(logN) O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.