Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the challenge of designing shallow quantum circuits for binary polynomial optimization problems, which offer better qubit scaling than quadratic formulations but require deeper circuits due to the absence of higher-order gates. The authors formulate circuit design as a classical binary linear problem, proving NP-completeness for a variant, and introduce Tempura, a scalable heuristic, alongside faster, near-optimal binary linear problem formulations. Empirical results demonstrate that these methods yield significantly shorter circuits compared to existing approaches.
A novel heuristic, Tempura, drastically reduces quantum circuit depth for polynomial optimization, overcoming a key hardware limitation.
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.