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:2610.13283

Circuit Design Problems in Binary Polynomial Quantum Optimization

Dylan Laplace Mermoud, Dimitri Watel, Sourour Elloumi, Andrea Simonetto

quant-phSubmitted Oct 9, 2026• Announced Oct 12, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper studies how to design minimum-depth quantum circuits for binary polynomial optimization objectives. Higher-degree binary formulations can require fewer qubits than quadratic formulations, but implementing their interactions introduces circuit-depth overhead when native $d$-qubit gates are unavailable for $d\geq 3$. The central question is how to minimize this overhead for a given polynomial objective. The circuit-design task is formulated as a classical binary linear optimization problem, and a variant of the task is proved to be $\mathsf{NP}$-complete. On the algorithmic side, the paper introduces Tempura, a heuristic intended to scale to larger instances, together with alternative binary linear formulations that trade optimality for computational feasibility. The reported performance evaluation finds that these methods produce substantially shorter circuits than the state-of-the-art approaches used for comparison, while Tempura has mostly comparable runtime. The abstract identifies an explicit optimality-versus-computational-cost trade-off, but does not specify the circuit model, hardware-connectivity assumptions, precise variant covered by the complexity result, or any approximation guarantees. It also gives no numerical depth reductions, benchmark sizes, or runtime measurements. Since the full text is unavailable, the scope of the complexity proof and the empirical comparisons cannot be assessed beyond these abstract-level claims.

No sign of AI-generated textUnclear novelty

Written by gpt-6.1-sol from the abstract only. Automated: it can be wrong.

Comments
26 pages

Related papers

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

Optimizing Variational Circuits for Higher-Order Binary Optimization

Zoé Verchère, Sourour Elloumi, Andrea Simonetto

Variational quantum algorithms have been advo-cated as promising candidates to solve combinatorial optimization problems on near-term quantum computers. Their methodology involves transforming the optimization problem into a quadratic unconstrained binary optimization (QUBO) problem. While this transformation offers flexibility and a ready-to-implement circuit involving only two-qubit gates, it has been shown to be less than optimal in the number of employed qubits and circuit depth, especially for polynomial optimization. On the other hand, strategies based on higher-order binary optimization (HOBO) could save qubits, but they would introduce additional circuit layers, given the presence of higher-than-two-qubit gates. In this paper, we study HOBO problems and propose new approaches to encode their Hamiltonian into a ready-to-implement circuit involving only two-qubit gates. Our methodology relies on formulating the circuit design as a combinatorial optimization problem, in which we seek to minimize circuit depth. We also propose handy simplifications and heuristics that can solve the circuit design problem in polynomial time. We evaluate our approaches by comparing them with the state of the art, showcasing clear gains in terms of circuit depth.

arXiv:2307.16756•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•11 citations

Towards large-scale quantum optimization solvers with few qubits

Marco Sciorilli, Lucas Borges, Taylor L. Patti +4 more

Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over $$m={{\mathcal{O}}}({n}^{k})$$ binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.

arXiv:2401.09421•Nature Communications•Jan 8, 2025•72 citations

Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Friedrich Wagner, Jonas Nüßlein, Frauke Liers

To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.

arXiv:2302.05493•ACM Transactions on Quantum Computing•Jan 13, 2025•13 citations

Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling

Grange, Camille, Marion Lavignac, Valentina Pozzoli +1 more

Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.

arXiv:2411.10062•Nov 15, 2024•4 citations

A QUBO Formulation for Qubit Allocation

Bryan Dury, Olivia Di Matteo

To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.

arXiv:2009.00140•Aug 31, 2020•17 citations
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.
The paper studies how to design minimum-depth quantum circuits for binary polynomial optimization objectives. Higher-degree binary formulations can require fewer qubits than quadratic formulations, but implementing their interactions introduces circuit-depth overhead when native ddd-qubit gates are unavailable for d≥3d\geq 3d≥3. The central question is how to minimize this overhead for a given polynomial objective.
The circuit-design task is formulated as a classical binary linear optimization problem, and a variant of the task is proved to be NP\mathsf{NP}NP-complete. On the algorithmic side, the paper introduces Tempura, a heuristic intended to scale to larger instances, together with alternative binary linear formulations that trade optimality for computational feasibility. The reported performance evaluation finds that these methods produce substantially shorter circuits than the state-of-the-art approaches used for comparison, while Tempura has mostly comparable runtime.
The abstract identifies an explicit optimality-versus-computational-cost trade-off, but does not specify the circuit model, hardware-connectivity assumptions, precise variant covered by the complexity result, or any approximation guarantees. It also gives no numerical depth reductions, benchmark sizes, or runtime measurements. Since the full text is unavailable, the scope of the complexity proof and the empirical comparisons cannot be assessed beyond these abstract-level claims.
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
Variational quantum algorithms have been advo-cated as promising candidates to solve combinatorial optimization problems on near-term quantum computers. Their methodology involves transforming the optimization problem into a quadratic unconstrained binary optimization (QUBO) problem. While this transformation offers flexibility and a ready-to-implement circuit involving only two-qubit gates, it has been shown to be less than optimal in the number of employed qubits and circuit depth, especially for polynomial optimization. On the other hand, strategies based on higher-order binary optimization (HOBO) could save qubits, but they would introduce additional circuit layers, given the presence of higher-than-two-qubit gates. In this paper, we study HOBO problems and propose new approaches to encode their Hamiltonian into a ready-to-implement circuit involving only two-qubit gates. Our methodology relies on formulating the circuit design as a combinatorial optimization problem, in which we seek to minimize circuit depth. We also propose handy simplifications and heuristics that can solve the circuit design problem in polynomial time. We evaluate our approaches by comparing them with the state of the art, showcasing clear gains in terms of circuit depth.
Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over m=O(nk)m={{\mathcal{O}}}({n}^{k})m=O(nk) binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.
To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.
Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.
To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.