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 International Conference on Quantum Computing and Engineering (QCE)

Space-Efficient Embedding of the Clique Cover Problem for Quantum Optimization

Bence Bakó, Dániel Nagy, Péter Hága, Zsófia Kallus, Zoltán Zimborás

Published Sep 17, 2023• 0 citations
Publisher

Abstract

Current quantum computer prototypes exhibit various strengths and weaknesses based on their individual architectures. Consequently, the development of flexible circuit design approaches becomes a critical tool. To tackle this challenge in the case of clique cover optimization, we propose a novel embedding method of this problem, efficiently reducing the width of the required quantum circuit exponentially in the number of cliques. We compare this new embedding based on a Polynomial Unconstrained Binary Optimization reformulation to the traditional one-hot encoded quadratic problem and present numerical simulations of the Quantum Approximate Optimization Algorithm for both methods, studying in particular the solution quality. The results obtained from the numerical experiments provide valuable insights into the performance gains achieved by employing our space-efficient embedding method, verified through both analytical and stochastic simulation benchmarks. Our results highlight the effectiveness of the space-efficient embedding method for the clique cover problem and extend the set of problems formulated with this technique.

DOI
10.1109/qce57702.2023.10306

Related papers

Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding

Zsolt Tabi, Kareem H. El-Safty, Zsofia Kallus +4 more

Current quantum computing devices have different strengths and weaknesses depending on their architectures. This means that flexible approaches to circuit design are necessary. We address this task by introducing a novel space-efficient quantum optimization algorithm for the graph coloring problem. Our circuits are deeper than the ones of the standard approach. However, the number of required qubits is exponentially reduced in the number of colors. We present extensive numerical simulations demonstrating the performance of our approach. Furthermore, to explore currently available alternatives, we also perform a study of random graph coloring on a quantum annealer to test the limiting factors of that approach, too.

arXiv:2009.07314•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•68 citations

Circuit Design Problems in Binary Polynomial Quantum Optimization

Dylan Laplace Mermoud, Dimitri Watel, Sourour Elloumi +1 more

Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree $d$ incur in circuit depth overheads, due to the lack of $d$-qubit gates, for $d\geq 3$, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the \textsf{NP}-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime.

quant-pharXiv:2610.13283•Oct 12, 2026•0 citations

Efficient Hamiltonian Reduction for Quantum Annealing on SatCom Beam Placement Problem

Thinh Q. Dinh, Son Hoang Dau, Eva Lagunas +1 more

Beam Placement (BP) is a well-known problem in Low-Earth Orbit (LEO) satellite communication (SatCom) systems, which can be modelled as an NP-hard clique cover problem. Recently, quantum computing has emerged as a novel technology which revolutionizes how to solve challenging optimization problems by formulating Quadratic Unconstrained Binary Optimization (QUBO), then preparing Hamiltonians as inputs for quantum computers. In this paper, we study how to use quantum computing to solve BP problems. However, due to limited hardware resources, existing quantum computers are unable to tackle large optimization spaces. Therefore, we propose an efficient Hamiltonian Reduction method that allows quantum processors to solve large BP instances encountered in LEO systems. We conduct our simulations on real quantum computers (D-Wave Advantage) using a real dataset of vessel locations in the US. Numerical results show that our algorithm outperforms commercialized solutions of D-Wave by allowing existing quantum annealers to solve 17.5 times larger BP instances while maintaining high solution quality. Although quantum computing cannot theoretically overcome the hardness of BP problems, this work contributes early efforts to applying quantum computing in satellite optimization problems, especially applications formulated as clique cover/graph coloring problems.

arXiv:2210.06042•International Conference on Communications•May 28, 2023•9 citations

Circuit Design Problems in Binary Polynomial Quantum Optimization

Dylan Laplace Mermoud, Dimitri Watel, Sourour Elloumi +1 more

Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree d incur in circuit depth overheads, due to the lack of d-qubit gates, for d≥3, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the NP-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime

•Oct 13, 2026•0 citations

A Quantum Approach for Stochastic Constrained Binary Optimization

Sarthak Gupta, Vassilis Kekatos

Analytical and practical evidence indicates the advantage of quantum computing solutions over classical alternatives. Quantum-based heuristics relying on the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) have been shown numerically to generate high-quality solutions to hard combinatorial problems, yet incorporating constraints to such problems has been elusive. To this end, this work puts forth a quantum heuristic to cope with stochastic binary quadratically constrained quadratic programs (QCQP). Identifying the strength of quantum circuits to efficiently generate samples from probability distributions that are otherwise hard to sample from, the variational quantum circuit is trained to generate binaryvalued vectors to approximately solve the aforesaid stochastic program. The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks. Tests on several synthetic problem instances using a quantum simulator corroborate the near-optimality and feasibility of the method, and its potential to generate feasible solutions for the deterministic QCQP too.

arXiv:2301.01443•IEEE International Conference on Acoustics Speech and Signal Processing•May 5, 2023•4 citations

Lagrangian duality in quantum optimization: Overcoming QUBO limitations for constrained problems

Einar Gabbassov, Gili Rosenberg, Artur Scherer

We propose an approach to solving constrained combinatorial optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width in contrast with the prevalent approach of solving constrained problems via reformulations based on the quadratic unconstrained binary optimization (QUBO) framework. In this study, we include a detailed review of the limitations encountered when using QUBO for constrained optimization. We show that the proposed method overcomes these limitations by encoding the optimal solution at an energetically elevated level of a simpler problem Hamiltonian, which results in substantially more resource-efficient quantum circuits. We consolidate our strategy with a detailed analysis on how the concepts of Lagrangian duality such as duality gap and complementary slackness relate to the success probability of sampling the optimal solution. Our findings are illustrated by benchmarking the Lagrangian dual approach against the QUBO approach using the NP-complete binary knapsack problem.

arXiv:2310.04542•Physical Review Research•May 23, 2025•5 citations
Current quantum computer prototypes exhibit various strengths and weaknesses based on their individual architectures. Consequently, the development of flexible circuit design approaches becomes a critical tool. To tackle this challenge in the case of clique cover optimization, we propose a novel embedding method of this problem, efficiently reducing the width of the required quantum circuit exponentially in the number of cliques. We compare this new embedding based on a Polynomial Unconstrained Binary Optimization reformulation to the traditional one-hot encoded quadratic problem and present numerical simulations of the Quantum Approximate Optimization Algorithm for both methods, studying in particular the solution quality. The results obtained from the numerical experiments provide valuable insights into the performance gains achieved by employing our space-efficient embedding method, verified through both analytical and stochastic simulation benchmarks. Our results highlight the effectiveness of the space-efficient embedding method for the clique cover problem and extend the set of problems formulated with this technique.
Current quantum computing devices have different strengths and weaknesses depending on their architectures. This means that flexible approaches to circuit design are necessary. We address this task by introducing a novel space-efficient quantum optimization algorithm for the graph coloring problem. Our circuits are deeper than the ones of the standard approach. However, the number of required qubits is exponentially reduced in the number of colors. We present extensive numerical simulations demonstrating the performance of our approach. Furthermore, to explore currently available alternatives, we also perform a study of random graph coloring on a quantum annealer to test the limiting factors of that approach, too.
Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree ddd incur in circuit depth overheads, due to the lack of ddd-qubit gates, for d≥3d\geq 3d≥3, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the \textsf{NP}-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime.
Beam Placement (BP) is a well-known problem in Low-Earth Orbit (LEO) satellite communication (SatCom) systems, which can be modelled as an NP-hard clique cover problem. Recently, quantum computing has emerged as a novel technology which revolutionizes how to solve challenging optimization problems by formulating Quadratic Unconstrained Binary Optimization (QUBO), then preparing Hamiltonians as inputs for quantum computers. In this paper, we study how to use quantum computing to solve BP problems. However, due to limited hardware resources, existing quantum computers are unable to tackle large optimization spaces. Therefore, we propose an efficient Hamiltonian Reduction method that allows quantum processors to solve large BP instances encountered in LEO systems. We conduct our simulations on real quantum computers (D-Wave Advantage) using a real dataset of vessel locations in the US. Numerical results show that our algorithm outperforms commercialized solutions of D-Wave by allowing existing quantum annealers to solve 17.5 times larger BP instances while maintaining high solution quality. Although quantum computing cannot theoretically overcome the hardness of BP problems, this work contributes early efforts to applying quantum computing in satellite optimization problems, especially applications formulated as clique cover/graph coloring problems.
Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree d incur in circuit depth overheads, due to the lack of d-qubit gates, for d≥3, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the NP-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime
Analytical and practical evidence indicates the advantage of quantum computing solutions over classical alternatives. Quantum-based heuristics relying on the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) have been shown numerically to generate high-quality solutions to hard combinatorial problems, yet incorporating constraints to such problems has been elusive. To this end, this work puts forth a quantum heuristic to cope with stochastic binary quadratically constrained quadratic programs (QCQP). Identifying the strength of quantum circuits to efficiently generate samples from probability distributions that are otherwise hard to sample from, the variational quantum circuit is trained to generate binaryvalued vectors to approximately solve the aforesaid stochastic program. The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks. Tests on several synthetic problem instances using a quantum simulator corroborate the near-optimality and feasibility of the method, and its potential to generate feasible solutions for the deterministic QCQP too.
We propose an approach to solving constrained combinatorial optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width in contrast with the prevalent approach of solving constrained problems via reformulations based on the quadratic unconstrained binary optimization (QUBO) framework. In this study, we include a detailed review of the limitations encountered when using QUBO for constrained optimization. We show that the proposed method overcomes these limitations by encoding the optimal solution at an energetically elevated level of a simpler problem Hamiltonian, which results in substantially more resource-efficient quantum circuits. We consolidate our strategy with a detailed analysis on how the concepts of Lagrangian duality such as duality gap and complementary slackness relate to the success probability of sampling the optimal solution. Our findings are illustrated by benchmarking the Lagrangian dual approach against the QUBO approach using the NP-complete binary knapsack problem.