PaperlayerView exact revision on arXiv

Source-linked AI summary

QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis

Xin-Chuan Wu, Marc Grau Davis, Frederic T. Chong, Costin Iancu

arXiv:2012.09835v5quant-ph

TL;DR

NISQ devices make minimizing noisy two-qubit gates important, while quantum synthesis becomes intractable as circuit qubit counts grow. QGo partitions circuits into blocks, synthesizes each block, and stitches the results together. Across NISQ benchmarks, it reduces CNOT counts compared with t|ket⟩, and the paper reports optimization of circuits with 60+ qubits.

  • Problem

    Quantum synthesis scales exponentially with qubit count, making it intractable for circuits beyond a handful of qubits, while NISQ devices are especially sensitive to noisy two-qubit gates.

    Source: §I · p. 1

  • Method

    QGo partitions a circuit into independent blocks that synthesis can handle, re-synthesizes each block, and reassembles the optimized circuit.

    Source: §I · p. 1

  • Results

    QGo reduces CNOT gates by 29.9% on average and up to 50% compared with circuits optimized by t|ket⟩compiler.

    Source: §I · p. 2

  • Takeaways & Limitations

    QGo was demonstrated on circuits of 60+ qubits, suggesting a viable path toward higher fidelity for large-scale circuits.

    Source: §I · p. 2

Abstract

from arXiv · show

The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noise simulations, and large-size circuits on analytical models. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compilers such as t|ket>. When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits. Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains.

I. INTRODUCTION

NISQ devices make minimizing noisy two-qubit gates important, but quantum synthesis scales exponentially with qubit count. QGo combines circuit partitioning and synthesis to optimize larger circuits, evaluating circuit quality across device, simulation, and analytical settings.

I. INTRODUCTION

  • QGo partitions circuits into independent blocks, re-synthesizes each block, and reassembles them, replacing O(exp(n)) synthesis with calls to O(exp(k)) algorithms for k-qubit blocks.The time-to-solution grows linearly with the number of k-qubit blocks; Figure 1 illustrates partitioning a 5-qubit circuit into 3-qubit blocks.Source: §I · p. 1, Figure 1 · p. 2
  • QGo maps circuits to target hardware before partitioning and synthesis, then stitches the optimized blocks together.Its flow uses physical qubit mapping, circuit partitioning, quantum synthesis, and circuit composition.Source: §I · pp. 1–2
  • The evaluation uses NISQ benchmarks and compares partitioning strategies with 3- and 4-qubit blocks across IBM Athens, noisy simulations, and an analytical model.The settings cover small-, medium-, and large-size circuits, respectively.Source: §I · p. 2
  • Across NISQ benchmarks, QGo reduces CNOT gate counts by 29.9% on average and up to 50% compared with circuits optimized by t|ket⟩compiler, translating into direct fidelity improvements on IBM Athens.Source: §I · p. 2
  • 98% correlation between real-device and simulation results on small circuits, 78% correlation between CNOT reductions and real-device fidelity on small circuits, and 76% correlation with simulation on medium circuits.The evaluation uses real-device fidelity for small circuits, noisy simulation for medium circuits, and static CNOT reduction for large circuits.Source: §I · p. 2
  • QGo was demonstrated on circuits of 60+ qubits, extending synthesis-based optimization to large circuits.The paper describes this as the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuit optimization.Source: §I · p. 2

II. BACKGROUND

The background introduces quantum-computing principles and the circuit model. It also describes how qubit states and gates are represented.

A. Principles of Quantum Computation

  • A qubit is a two-level system represented by basis states |0⟩ and |1⟩, and an n-qubit system is represented by 2^n amplitudes.A single-qubit state is a normalized linear combination of the two basis states.Source: A. Principles of Quantum Computation · p. 3
  • A quantum circuit applies unitary gates to quantum states; CNOT gates and single-qubit rotations Rx, Ry, and Rz form a commonly used universal gate set.Two-qubit controlled gates and arbitrary single-qubit gates are universal.Source: A. Principles of Quantum Computation · p. 3

B. Quantum Circuit Synthesis

Quantum synthesis seeks short circuits but faces a scalability challenge; QGo combines synthesis with circuit partitioning to optimize larger circuits. Its overview maps the circuit before partitioning, synthesizing, and composing blocks.

B. Quantum Circuit Synthesis

  • Quantum synthesis decomposes a target unitary into gates, with short circuits—especially low-CNOT circuits—an important objective because CNOTs contribute more noise and runtime than single-qubit gates.Prior approaches include discrete-gate methods and methods using continuously variable gates; KAK decomposition can synthesize any two-qubit unitary with at most 3 CNOTs.Source: B. Quantum Circuit Synthesis · p. 3
  • QGo applies search-based numerical synthesis: A* searches for a short CNOT structure, while numerical optimization chooses parameters for its single-qubit gates.The method is selected for its ability to minimize CNOT count.Source: B. Quantum Circuit Synthesis · p. 3

III. SCALABLE CIRCUIT OPTIMIZATION USING SYNTHESIS

  • QGo maps a high-level program to hardware, partitions it into blocks, synthesizes each block, and composes the results into a topology-aware executable circuit.The block size trades synthesis time against CNOT reduction: larger blocks can yield fewer CNOTs but take exponentially longer to synthesize.Source: §III · p. 3, A. QGo Overview · pp. 3–4

B. Physical Qubit Mapping

QGo performs physical qubit mapping before synthesis so inserted swaps can be optimized with the circuit. Its partitioning heuristic then selects executable blocks of connected qubits, favoring blocks with more CNOT gates.

B. Physical Qubit Mapping

  • Physical mapping precedes synthesis so inserted swaps become part of the circuit that synthesis can optimize; mapping first can also preserve repeated CNOT patterns used by mapping algorithms.QGo uses the t|ket⟩ compiler for physical mapping, which produced shorter circuits than IBM Qiskit in the reported experiments.Source: B. Physical Qubit Mapping · p. 4

C. Circuit Partitioning

  • A valid qubit group maps to a connected component of the device graph; for a 3 × 3 grid, {q0, q3, q6} is valid, while {q2, q7, q8} is invalid.Only valid groups are considered during partitioning.Source: C. Circuit Partitioning · p. 4
  • The partitioning heuristic repeatedly selects the valid qubit group with the most executable CNOT gates, removes that block from the dependency graph, and continues until the graph is empty.It outputs the ordered blocks and their qubit-group mappings.Source: C. Circuit Partitioning · p. 5
  • The partitioning heuristic has time complexity O(nkg), where n is the original qubit count, k the block size, and g the total gate count; the authors describe it as scalable for large-scale partitioning.The passage contrasts this with dynamic-programming partitioning, which is limited by circuit depth.Source: C. Circuit Partitioning · pp. 4–6

D. Quantum Circuit Synthesis

QGo synthesizes each partitioned block using its unitary matrix, qubit group, and device connectivity. This block-based approach reduces the synthesis time-to-solution from O(exp(n)) to O(exp(k)).

D. Quantum Circuit Synthesis

  • O(exp(n)) to O(exp(k)): block-based synthesis reduces the time-to-solution for an n-qubit circuit by synthesizing blocks of size k.For each block, QGo supplies its unitary matrix, qubit group, and device connectivity to the synthesis tool.Source: D. Quantum Circuit Synthesis · p. 6
  • 10^-10 to 10^-15: the final unitary distance after synthesis falls in this range and is described as insignificant relative to device gate errors.The authors report that this distance has negligible impact on overall state fidelity.Source: D. Quantum Circuit Synthesis · p. 6

E. Circuit Composition

QGo stitches synthesized blocks using their qubit-group mappings, then combines adjacent single-qubit gates to produce the final optimized circuit.

E. Circuit Composition

  • QGo stitches blocks using their qubit-group mappings and keeps the original block when synthesis does not reduce its CNOT count, then combines adjacent single-qubit gates.Using the original block in that case avoids unnecessary synthesis distance from floating-point errors.Source: E. Circuit Composition · p. 6

IV. EXPERIMENTAL SETUP

The evaluation uses benchmark circuits grouped by size and applies different fidelity-evaluation regimes to small, medium, and large circuits. It compares 3- and 4-qubit synthesis blocks against t|ket⟩, the stated baseline.

A. Benchmarks

  • Benchmarks span small 4- and 5-qubit, medium 9- and 10-qubit, and large circuits beyond 60 qubits.The small circuits run on IBM’s 5-qubit Athens device.Source: A. Benchmarks · p. 6

B. Experimental Parameters

  • Fidelity is evaluated on Athens for small circuits, with noisy simulations for medium circuits and an analytical model for large circuits.The t|ket⟩ compiler at its highest optimization level is the baseline.Source: A. Benchmarks · p. 6, B. Experimental Parameters · p. 7

A. Benchmarks

  • The evaluation uses QAOA, TFIM, multiplier, adder, QFT, and Hidden Linear Function applications as benchmarks.The passages identify their application contexts, including MaxCut for QAOA and chemical-system time evolution for TFIM.Source: A. Benchmarks · p. 6

B. Experimental Parameters

  • QGo is tested with 3-qubit and 4-qubit blocks on a system with an Intel Xeon Silver 4110 CPU and 128 GB RAM.The reported setup uses Ubuntu 16.04.Source: B. Experimental Parameters · p. 6

V. EVALUATION

QGo reduces CNOT counts relative to t|ket⟩, with larger blocks generally producing greater reductions at longer synthesis times. Evaluation also examines synthesis-distance infidelity, real-device results, and noise simulations.

B. Impact of Synthesis Distance

  • Less than 10^-12 state infidelity is reported for each optimized circuit, negligible beside the stated NISQ gate-infidelity range of 10^-1 to 10^-6.QGo-4 has slightly larger synthesis-distance infidelity than QGo-3.Source: B. Impact of Synthesis Distance · p. 7, Figure 9 · p. 8

A. CNOT Reduction

  • 29.9% is the average CNOT reduction for QGo-4 versus t|ket⟩; QGo-4 reduces CNOT counts across all benchmarks.QGo-3 does not reduce counts for MUL5 and HLF5, while QGo-4 generally reduces more than QGo-3.Source: A. CNOT Reduction · p. 7, Figure 6 · p. 8

D. Running on Noise Simulation

  • With simulated two-qubit gate error probabilities from 0.1% to 2.5%, QGo reduces more total variation distance at larger gate errors.The analysis uses depolarizing noise.Source: D. Running on Noise Simulation · pp. 8–9

C. Running on Real Hardware

D. Running on Noise Simulation

  • 98% correlation links small-circuit total-variation results on Athens and noise simulation; for medium circuits, CNOT reduction correlates 76% with simulated improvement.Medium circuits are simulated because they are too deep for meaningful results on available devices.Source: D. Running on Noise Simulation · p. 7, Figure 12 · p. 9

E. Scalability

QGo scales to circuits beyond 60 qubits, with CNOT reductions measured statically and success rates estimated analytically. Larger blocks improve reductions but take longer to optimize.

E. Scalability

  • 22.8% for QGo-3 and 28.9% for QGo-4 are the average CNOT reductions on large circuits.The circuits are mapped to a 2D 8 × 8 physical-qubit lattice.Source: E. Scalability · p. 9
  • QGo-3 completes large-circuit optimization within minutes, while QGo-4 takes hours.QGo-4 achieves the larger CNOT reduction but has longer optimization time.Source: E. Scalability · p. 9
  • The small-circuit real-device and simulation results have 98% correlation, while medium-circuit CNOT reduction and simulated improvement have 76% correlation.These correlations provide context for interpreting simulated fidelity results alongside the large-circuit analytical estimates.Source: Figure 13 · p. 9, Figure 14 · p. 9
  • Large-circuit success rates are estimated with a worst-case analytical model that multiplies gate success rates; QGo-4 is projected to have the highest rates.The projected improvement is greater under larger gate error.Source: E. Scalability · p. 9

F. Discussion

The discussion characterizes QGo as applicable to large circuits even with 3-qubit blocks, while larger blocks offer more CNOT reduction at greater solving cost. It also identifies mapping quality as a potential factor in QGo’s efficacy.

F. Discussion

  • 3-qubit block synthesis already gives good optimization on large circuits, while larger blocks generally reduce more CNOTs and take longer to solve.Synthesis with 5-qubit blocks is possible, but its solving time is much longer.Source: F. Discussion · p. 9
  • Preliminary sensitivity analysis indicates a direct correlation between mapping quality and QGo efficacy; the authors conjecture that better mappings create opportunities for larger blocks.The passages identify highly interconnected components as a feature of the best-quality mappings.Source: F. Discussion · pp. 9–10
  • Figure 15 presents total variation distance under different gate-error levels, with lower distance indicating better results.The supplied caption identifies the metric and direction, but gives no specific outcome for the comparison.Source: Figure 15 · p. 10

VI. FUTURE WORK

The future-work discussion identifies approximate synthesis and pulse-level optimization as directions for extending QGo.

A. Approximate Synthesis

  • Relaxing the synthesis threshold to 10^-4 yielded no CNOT reduction because process infidelity is inflexible; useful accuracy–CNOT trade-offs need threshold-controllable synthesis.The authors suggest integrating a different synthesis tool or approximation-focused heuristic.Source: A. Approximate Synthesis · pp. 10–11
  • Fig. 19 compares circuit success rates under different gate-error levels; higher success rates are better.Source: Figure 19 · p. 11

B. Pulse-Level Optimization

  • Pulse-level optimization could replace QGo’s gate-sequence output with a synthesized sequence of pulses.The authors point to prior work on generating shorter pulses.Source: B. Pulse-Level Optimization · p. 11

C. QGo in Parallel

QGo partitions circuits into blocks for synthesis and reassembly, giving synthesis a role in large-scale optimization; the authors conclude it has practical value on current devices and is reliable in the NISQ era.

C. QGo in Parallel

  • Because blocks are independent during synthesis, QGo’s block synthesis can run in parallel and may reduce compilation time on a supercomputing system.Source: C. QGo in Parallel · p. 11

VII. RELATED WORK

  • Unlike mapping and swap heuristics that retain the original CNOT count, QGo can reduce both swap count and CNOT count.Source: §VII · p. 11
  • QGo targets general circuits, while its core synthesis tool can be changed to incorporate approaches tailored to specific circuit classes.Source: §VII · p. 11
  • Resynthesis depends on producing extremely short circuits; the search-based technique used here handles circuits up to 4 qubits, while another approach offers better runtime scaling but slightly longer circuits.Source: §VII · p. 11

VIII. CONCLUSION

  • QGo partitions circuits into blocks, re-synthesizes and stitches them, and the authors conclude it has practical value on current devices and is reliable in the NISQ era.They describe the work as offering insights for future compiler design.Source: §VIII · pp. 11–12
Loading 2012.09835v5…