arXiv:2610.13283
Circuit Design Problems in Binary Polynomial Quantum Optimization
Dylan Laplace Mermoud, Dimitri Watel, Sourour Elloumi, Andrea Simonetto
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.
Written by gpt-6.1-sol from the abstract only. Automated: it can be wrong.
- Comments
- 26 pages