Circuit Design Problems in Binary Polynomial Quantum Optimization
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≥ 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.
Related
- Quantum estimates for classical polynomial optimization
- Certified bounds on optimization problems in quantum theory
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Local Shellings of Broken-Circuit Complexes via Boundary States and the Chromatic Specialization of the Negami Polynomial
- The Negami Polynomial and Broken-Circuit Stanley--Reisner Rings
BibTeX
@misc{mermoud2026circuit,
title = {{Circuit Design Problems in Binary Polynomial Quantum Optimization}},
author = {Dylan Laplace Mermoud and Dimitri Watel and Sourour Elloumi and Andrea Simonetto},
howpublished = {HAL},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13283},
eprint = {2610.13283},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05797947v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Circuit Design Problems in Binary Polynomial Quantum Optimization
AU - Dylan Laplace Mermoud
AU - Dimitri Watel
AU - Sourour Elloumi
AU - Andrea Simonetto
PY - 2026
DA - 2026/10/09
PB - HAL
DO - 10.48550/arxiv.2610.13283
UR - https://hal.science/hal-05797947v1
AB - 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 \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.
ER -