POPQC: Parallel Optimization for Quantum Circuits
Abstract
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 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. In this paper, we present a parallel algorithm for local optimization of quantum circuits. To ensure efficiency, the algorithm operates by keeping a set of fingers into the circuit and maintains the invariant that a Ω-deep circuit needs to be optimized only if contains a finger. Operating in rounds, the algorithm selects a set of fingers, optimizes in parallel the segments containing the fingers, and updates the finger set to ensure the invariant. For constant Ω, we prove that the algorithm requires O(n lg n) work and O(r lg n) span, where n is the circuit size and r is the number of rounds. We prove that the optimized circuit returned by the algorithm is locally optimal in the sense that any Ω-segment of the circuit is optimal with respect to the oracle. To assess the algorithm’s effectiveness in practice, we implement it in the Rust programming language and evaluate it by considering a range of quantum benchmarks and several state-of-the-art optimizers. The evaluation shows that the algorithm is work efficient and scales well as the number of processors (cores) increases. On our benchmarks, the algorithm outperforms existing optimizers, which are all sequential, by as much as several orders of magnitude, without degrading the quality. Our code is available on GitHub at https://github.com/UmutAcarLab/popqc.
