POPQC: Parallel Optimization for Quantum Circuits
Pengyu Liu, Jatin Arora, Mingkuan Xu, Umut A. Acar · 2025
Optimization of quantum programs or circuits is a fundamental problem in quantum computing and remains a major challenge. State-of-the-art quantum circuit optimizers rely on heuristics and typically require superlinear, and even exponential, time. Recent work [8] proposed a new approach that pursues a weaker form of optimality called local optimality. Parameterized by a natural number Ω, local optimality insists that each and every Ω-segment of the circuit is optimal with respect to an external optimizer, called the oracle. Local optimization can be performed using only a linear number of calls to the oracle but still incurs quadratic computational overheads in addition to oracle calls. Perhaps most importantly, the algorithm is sequential.