POPQC: Parallel Optimization for Quantum Circuits (Extended Version)

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 $\Omega$, local optimality insists that each and every $\Omega$-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 $\Omega$-deep circuit needs to be optimized only if it 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 $\Omega$, 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 $\Omega$-segment of the circuit is optimal with respect to the oracle.

SPAA25

References in corpus (22)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• Superconducting Qubits: Current State of Play
• An introduction to quantum machine learning
• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Programmable Quantum Simulations of Spin Systems with Trapped Ions
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• A Race Track Trapped-Ion Quantum Processor
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• QuantumNAS: Noise-Adaptive Search for Robust Quantum Circuits
• Optimized Compilation of Aggregated Instructions for Realistic Quantum Computers
• A Verified Optimizer for Quantum Circuits
• QIRAL: A High Level Language for Lattice QCD Code Generation
• Adaptive pruning-based optimization of parameterized quantum circuits
• Reinforcement learning for optimization of variational quantum circuit architectures
• Exact and practical pattern matching for quantum circuit optimization
• Synthesizing Quantum-Circuit Optimizers
• Beyond NISQ: The Megaquop Machine
• QFAST: Conflating Search and Numerical Optimization for Scalable Quantum Circuit Synthesis