Source-linked AI summary
Automated optimization of large quantum circuits with continuous parameters
Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, Dmitri Maslov
TL;DR
Large quantum circuits need automated optimization because quantum hardware remains limited and expensive, while manual gate-level optimization becomes impractical. The paper develops heuristic Light and Heavy optimizers, including methods for continuous gate parameters, and reports substantial gate-count reductions, often improving on prior approaches in less time. Its scope includes benchmark circuits relevant to computations intended to outperform classical computers, with some comparison and circuit-validity limitations.
Problem
Limited, expensive quantum hardware and the complexity of large circuits create a need for automated resource reduction beyond practical manual optimization.
Method
The paper implements Light and Heavy optimizers that apply carefully ordered basic and special-purpose subroutines to large quantum circuits.
Results
Across the benchmarks, the algorithms achieve substantial gate-count reductions, typically producing smaller circuits in less time than prior approaches.
Takeaways & Limitations
Automated optimization can improve large quantum-circuit implementations while preserving the underlying algorithms’ basic circuit structure.
Takeaways & Limitations
One comparison used a corrected original circuit because the circuit used by a prior optimizer was incorrect; cost comparisons also depend on fault-tolerant gate-cost assumptions.
Abstract
from arXiv · showhide
We develop and implement automated methods for optimizing quantum circuits of the size and type expected in quantum computations that outperform classical computers. We show how to handle continuous gate parameters and report a collection of fast algorithms capable of optimizing large-scale quantum circuits. For the suite of benchmarks considered, we obtain substantial reductions in gate counts. In particular, we provide better optimization in significantly less time than previous approaches, while making minimal structural changes so as to preserve the basic layout of the underlying quantum algorithms. Our results help bridge the gap between the computations that can be run on existing hardware and those that are expected to outperform classical computers.
1 Introduction
Quantum computing may enable important applications, but current hardware is limited and expensive, making efficient implementation essential. This work develops automated optimization for large circuits and compares favorably with prior approaches.
- Motivation: Tens to hundreds of qubits may become available on programmable superconducting-circuit and trapped-ion devices.
- Motivation: Limited and expensive quantum-computing resources make efficient implementations of quantum algorithms essential.
- Problem: Quantum circuits admit many implementations, so automated optimization can reduce resources when circuit complexity exceeds practical manual optimization.
- Contribution: The authors develop heuristic software tools to reduce gate counts where manual gate-level optimization is no longer practical.
- Evaluation: Benchmarks cover arithmetic, factoring and discrete-logarithm components, quantum Fourier transforms, and product-formula Hamiltonian simulation.
- Contribution: The approach targets large-scale circuits, typically finding smaller circuits in less time than prior software and addressing continuous gate parameters.
2 Results
The optimizer was tested on QFTs, adders, product-formula algorithms, arithmetic circuits, Toffoli gates, and Galois-field multipliers at scales relevant to classically difficult quantum computations. Across these benchmarks, it reduced important gate counts, handled continuous parameters and composite gates, and preserved the original interaction structure.
- QFT and adders: 36% or more savings were obtained for approximate QFTs with 512 or more qubits by reducing rz gates.The paper identifies rz gates as the most expensive resource in a fault-tolerant implementation.
- QFT and adders: A factor of up to 5.2 reduction in t gates was achieved for Quipper library adders, entirely through automated optimization.The optimized Quipper library adder also outperformed the QFA by a wide margin.
- QFT and adders: A factor-of-more-than-5 reduction was reported for the overall factoring algorithm implemented with the optimized Quipper library adder.The paper attributes this to factoring’s reliance on modular exponentiation and integer addition.
- QFT and adders: 2.7-fold cnot reduction was obtained with Heavy optimization for Quipper adders, compared with 1.7-fold reduction using Light optimization.Heavy optimization did not improve QFT or QFA gate counts.
- Quantum simulation: The 2nd-, 4th-, and 6th-order product formulas showed approximately 33.3% cnot and 28.5% rz reductions, while Phase and Hadamard counts fell by roughly 3 to 6 times.The 1st-order formula showed no cnot or rz optimization, and Heavy optimization added no improvement.
- Comparison with prior approaches: For benchmark arithmetic circuits, the optimizer matched or improved t counts while reducing cnot counts; RC-Adder6 aggregate cost fell from 71.91 to 49.70.For Galois-field multipliers, GF(2^64) cnot count fell from 180,892 to 24,765 and aggregate cost from 30,168.59 to 18,326.42, about 39%.
3 Discussion
The paper's Light and Heavy optimizers reduce gate counts quickly through carefully chosen basic optimizations, while preserving circuit structure. The discussion also identifies comparison caveats and several directions for further improvement.
- Light and Heavy optimization algorithms achieve substantial gate-count reductions using a carefully chosen sequence of basic optimizations.The approach improves over more mathematically sophisticated t-par optimization while retaining a simple design.
- Table 4 labels standard Light and Heavy optimizations as “(L)” and “(H)” in the t-par comparison.
- The comparison includes an incorrect circuit optimized by t-par, identified by simulation and contrasted with the intended mapping.The reported optimization used the correct original circuit for that case.
- Very fast runtimes, especially for Light optimization, reflect the simplicity of the approach.
- Further improvements could use more computationally demanding rz-composition routines, template-based and peephole optimizations, expanded rewriting rules, and resource-aware trade-offs.
4 Methods
The methods combine multiple circuit representations, preprocessing, optimization subroutines, and specialized routines to reduce both cnot and rz counts while preserving practical scalability. Two optimizer variants and an LCR procedure tailor the optimization to circuit structure and runtime demands.
- Representations: The optimizer uses netlists, directed acyclic graphs, and phase polynomials to represent circuits and support different transformations.Netlists encode gate order, DAGs expose gate adjacency, and phase polynomials compactly represent circuits made of not, cnot, and rz gates.
- Representations: The phase polynomial representation expresses a circuit as an affine reversible transformation combined with a diagonal phase transformation.The phase polynomial is a linear combination of affine Boolean functions with coefficients reduced modulo 2π.
- Preprocessing: Preprocessing propagates not gates rightward through Toffoli and cnot gates, cancels adjacent not gates when possible, and otherwise restores the original changes.The procedure applies to inputs containing only not, cnot, and Toffoli gates and prepares them for later optimization.
- Optimization strategy: Light and Heavy optimizers apply subroutines in a chosen order, with Heavy using more routines for better optimization at higher runtime cost.Both versions use the preprocessing step.
- Special-purpose optimizations: The LCR optimizer handles circuits formed by repeated blocks by optimizing one, two, and three-block instances to identify simplifications across block boundaries.It is designed for repeated-block algorithms such as product formula simulation algorithms.