PaperlayerView exact revision on arXiv

Source-linked AI summary

An Efficient Quantum Compiler that reduces $T$ count

Luke Heyfron, Earl T. Campbell

arXiv:1712.01557v3quant-ph

TL;DR

T-OPT seeks a minimum-T decomposition of a diagonal CNOT+T unitary, while its equivalent order-3 tensor-rank problem is difficult to solve optimally. The compilers adapt Lempel’s order-2 factoring ideas to order-3 tensor optimization, with TODD iteratively reducing columns of an input gate-synthesis matrix. TODD slightly outperforms TOOL without feedback on random circuits and yields positive savings over the best previous algorithm on all benchmarks except Mod 54, averaging 20%.

Abstract

from arXiv · show

Before executing a quantum algorithm, one must first decompose the algorithm into machine-level instructions compatible with the architecture of the quantum computer, a process known as quantum compiling. There are many different quantum circuit decompositions for the same algorithm but it is desirable to compile leaner circuits. A fundamentally important cost metric is the $T$ count -- the number of $T$ gates in a circuit. For the single qubit case, optimal compiling is essentially a solved problem. However, multi-qubit compiling is a harder problem with optimal algorithms requiring classical runtime exponential in the number of qubits. Here, we present and compare several efficient quantum compilers for multi-qubit Clifford + $T$ circuits. We implemented our compilers in C++ and benchmarked them on random circuits, from which we determine that our TODD compiler yields the lowest $T$ counts on average. We also benchmarked TODD on a library of reversible logic circuits that appear in quantum algorithms and found that it reduced the $T$ count for 97\% of the circuits with an average $T$-count saving of 20\% when compared against the best of all previous circuit decompositions.

I. PRELIMINARIES

The paper frames T-count optimization for Clifford+T circuits as a compilation problem and develops a workflow that isolates non-Clifford behavior for optimization. Its algebraic framework connects diagonal CNOT+T synthesis to symmetric tensor rank, enabling efficient approximate solutions.

I. PRELIMINARIES

  • The preliminaries define the Pauli group, the Clifford group as its normalizer, and the CNOT+T gate set as {CNOT, S, T}.S is included separately because of the magic-states cost model.Source: §I · p. 2

II. WORK-FLOW OVERVIEW

  • Stages 1–3 preprocess a Clifford+T circuit to isolate its non-Clifford behavior in a diagonal CNOT+T gate, and stages 4–6 optimize and reconstruct the circuit.The workflow’s output implements the original circuit with reduced T count.Source: Figure 1 · p. 2, §II · p. 3

A. Circuit preprocessing

  • Hadamard-gadgetization replaces each Hadamard with a CNOT+T block and a measured ancilla, moving classically controlled Pauli-X corrections to the circuit’s end.This converts most of the input into the optimizer-compatible gate set.Source: A. Circuit preprocessing · p. 3

B. Diagonal CNOT+T Framework

  • A diagonal circuit’s phase function yields a symmetric signature tensor from the parities of its weighted-polynomial coefficients; matching tensors identify Clifford-equivalent unitaries.A gate-synthesis matrix represents the phase polynomial, and removing zero or repeated columns strips Clifford behavior.Source: B. Diagonal CNOT+T Framework · pp. 4–5
  • T-OPT is reduced to the order-3 symmetric tensor-rank problem, and Lempel’s efficient order-2 factoring algorithm inspires approximate, rather than guaranteed optimal, compilers.The tensor-rank problem is also linked to Reed–Muller decoding, which imposes a practical limit on optimal synthesis.Source: B. Diagonal CNOT+T Framework · pp. 5–6

III. T-OPTIMISER

The section introduces the T-optimiser subroutine as the step that converts a signature tensor into a gate-synthesis matrix with few columns.

III. T-OPTIMISER

  • The T-optimiser takes a signature tensor as input and returns a gate-synthesis matrix with few columns.The paper implements several variants of this subroutine.Source: §III · p. 6

A. Reed-Muller decoder (RM)

The brute-force Reed–Muller decoder is limited to small qubit counts, motivating heuristic approaches.

A. Reed-Muller decoder (RM)

  • The implemented brute-force Reed–Muller decoder reaches its limit at nRM = 6 qubits.The authors report that exhaustive search for n = 7 would take over 91 years under their generous one-codeword-per-clock-cycle estimate, while n = 6 takes about 7 × 10^-4 seconds by that estimate.Source: A. Reed-Muller decoder (RM) · p. 6
  • In practice, the brute-force decoder takes around 10 minutes for n = 6, leading the authors to conclude that heuristics are needed.Source: A. Reed-Muller decoder (RM) · p. 6

B. Recursive Expansion (RE)

The section develops efficient approaches to reducing T counts in CNOT+T circuits, progressing from recursive expansion to order lowering and third-order tensor factoring. TOOL uses Lempel factoring on reduced subcircuits, while TODD iteratively removes matrix columns while preserving the signature tensor.

B. Recursive Expansion (RE)

  • Recursive Expansion (RE) converts each cubic monomial using a modulo identity to obtain a gate-synthesis matrix.The resulting matrix may contain columns of Hamming weight three or less, yielding a worst-case T-count of O(n^3).Source: B. Recursive Expansion (RE) · p. 6

C. Target Optimal by Order Lowering (TOOL)

  • TOOL lowers the order of a CNOT+T circuit by extracting quadratic controlled subcircuits that Lempel’s algorithm can synthesize efficiently and optimally.It repeats the extraction until the remaining circuit is small enough for the RM algorithm; one account specifies brute-force compilation at six qubits.Source: C. Target Optimal by Order Lowering… · pp. 6–7
  • TOOL is presented as a concrete version of the Campbell and Howard approach, and this paper reports its first numerical results from an implementation.The paper describes both plain TOOL and a variant with feedback.Source: C. Target Optimal by Order Lowering… · pp. 6–7

D. Third Order Duplicate and Destroy (TODD)

  • TODD extends Lempel’s factoring algorithm to order-3 tensors and iteratively reduces an input gate-synthesis matrix by removing columns while preserving its signature tensor.The algorithm searches column pairs for transformations that create duplicates, then destroys duplicate pairs to reduce the matrix and the circuit’s T count.Source: D. Third Order Duplicate and Destroy… · pp. 7–9
  • TODD’s duplication transformation creates duplicate columns, and removing such a pair preserves the signature tensor of the gate-synthesis matrix.The transformation must satisfy the stated conditions for signature preservation.Source: D. Third Order Duplicate and Destroy… · p. 8
  • TODD tests column pairs and searches a null-space basis for a vector that enables a signature-preserving duplication transformation.The algorithm then destroys duplicate pairs and repeats on the reduced matrix; at least one column is removed in the odd-parity case and at least two in the even-parity case.Source: D. Third Order Duplicate and Destroy… · p. 9

IV. RESULTS & DISCUSSION

The evaluation implements the compiler TOpt in C++ and tests it on random inputs and a library of reversible-logic circuits used in quantum algorithms.

  • TOpt implements RE, TOOL with feedback, TOOL without feedback, and TODD in C++.Source: §IV · p. 9
  • The random benchmark samples signature tensors uniformly across a range of qubit counts and tests all four T-optimiser variants.Source: §IV · p. 9
  • The algorithm benchmark draws reversible-logic circuits from three libraries, including examples such as Galois Field multipliers, integer addition, and hidden weighted bit functions.Results are listed in Table I; the benchmarks ran on the University of Sheffield’s Iceberg HPC cluster.Source: §IV · p. 9

A. Random Circuit Benchmark

On random-circuit benchmarks, TODD has the lowest average T count, while TOOL offers a runtime advantage and both scale better than RE. The tested circuits are diagonal CNOT+T circuits in the IQP class.

  • Both TOOL variants follow O(n^2) T-count scaling, compared with O(n^3) for RE; TODD slightly outperforms TOOL (without feedback) in the reported numerical results.T-count distributions for fixed n concentrate around their means, and TODD performs better on the vast majority of tested random circuits.Source: A. Random Circuit Benchmark · p. 10
  • TOOL runs faster than TODD, while TODD can partition very large circuits into smaller circuits at some cost to T-count reduction.For very large circuits, the authors say it is unclear which compiler works best and recommend running both.Source: A. Random Circuit Benchmark · p. 10
  • The random benchmark uses commuting gates {T, CS, CCZ}, so its circuits lie in the IQP complexity class and are not universal.The passage notes that low-cost IQP designs may be an asset for quantum-supremacy experiments.Source: A. Random Circuit Benchmark · p. 10
  • TODD produces the smallest average T counts and scales like TOOL (Feedback); both outperform RE by a factor n.For large n, the T-count difference between TODD and TOOL (Feedback) approaches 5.5 ± 0.7.Source: Figure 4 · p. 10, A. Random Circuit Benchmark · p. 10

B. Quantum Algorithms Benchmark

TODD led the benchmark comparisons, while TOOL’s weaker performance on algorithm circuits was linked to its control-qubit selection. The section also qualifies T-count optimization with ancilla and CNOT costs and notes that T count alone omits full space-time cost.

B. Quantum Algorithms Benchmark

  • Hadamard gadgets often require considerable ancilla space, though hcap can bound the register by partitioning circuits at no more than hcap Hadamard gates.More Hadamard gates generally increase TODD compilation time and the T count for TODD-part.Source: B. Quantum Algorithms Benchmark · p. 10
  • TOOL reduced T counts below the best previous result on 18% of benchmark circuits with feedback and 30% without; its naive random control-qubit selector was cited as a cause of poorer performance.Source: B. Quantum Algorithms Benchmark · pp. 10–11

C. The T Count and Other Metrics

  • T count does not capture full space-time cost, which is architecture-sensitive; for surface code, the T-to-Clifford cost ratio is estimated at 50 to 1000.The cited range depends on architectural assumptions.Source: C. The T Count and Other Metrics · p. 11
  • The protocol often increases CNOT count, and the paper leaves CNOT optimization for future work despite its importance for large n.The increase is largely attributed to naively mapping the phase polynomial back to a circuit.Source: C. The T Count and Other Metrics · p. 11

V. CONCLUSIONS & ACKNOWLEDGEMENTS

  • The authors conclude that TODD with Hadamard gadgets performs best in practice among their compiler variants for quantum-algorithm circuits.They report that each variant produced lower T counts than previous attempts known to them.Source: §V · p. 11

B. Quantum Algorithms Benchmark

  • 20% average and 51% maximum T-count savings over the best previous algorithm were reported for TODD, with positive savings on every benchmark except Mod 54.TODD reduced or preserved T count for every tested input circuit.Source: B. Quantum Algorithms Benchmark · p. 10, Table I · p. 12

Appendix A CLIFFORD + T BENCHMARKS FOR TODD-PART AND TODD-hcap

The appendix compares Hadamard partitioning and ancilla-capped variants, finding a runtime–T-count trade-off and that relatively few Hadamard ancillas can yield positive savings. It also outlines Lempel’s iterative matrix-factor reduction.

Appendix A CLIFFORD + T BENCHMARKS FOR TODD-PART AND TODD-hcap

  • Table II reports T counts, savings, runtime, partition counts, and the hcap setting for TODD-part and TODD-hcap variants.The hcap experiment increased the cap until the first positive saving over the best previous algorithm.Source: Table II · p. 14
  • Hadamard-bounded partitioning significantly reduced compiler runtime but often produced higher T counts than the best previous result.The implementation did not optimize among the generally many possible partition choices.Source: Appendix A · p. 15
  • On average, 9 Hadamard ancillas were required for positive savings, and at most 23 sufficed for all but Cycle 173, which required 43.The benchmarks reached n = 36 qubits and T = 6671; the results suggest potential for an improved partitioning or preprocessing approach.Source: Appendix A · p. 15

Appendix B LEMPEL’S FACTORING ALGORITHM

  • Lempel’s algorithm iteratively reduces a factor matrix toward its minimal column count by finding a kernel vector, transforming paired columns, and removing them.It stops when the column count reaches μ(S).Source: Appendix B · p. 15

Appendix C TOOL ALGORITHM

TOOL iteratively extracts a target polynomial around a selected variable, factors its order-2 signature tensor with Lempel’s algorithm, and updates the remaining polynomial. It offers feedback and non-feedback variants before switching to brute-force optimization on a small remainder.

Appendix C TOOL ALGORITHM

  • Each TOOL round selects a variable x_c that occurs in f, and the selection order can affect the output.The reported implementation chose uniformly at random among eligible variables.Source: Appendix C · p. 16
  • The compiler recovers an order-3 gate-synthesis matrix, appends it to Aout, and subtracts its weighted term from f.Each round leaves f dependent on fewer variables; when it reaches nRM or fewer, TOOL switches to RM brute force.Source: Appendix C · p. 16
  • The target polynomial tilde f_c is quadratic and can therefore be synthesized optimally and efficiently.It is used as the target of a control-U2 operator with x_c as control.Source: Appendix C · p. 16
  • TOOL maps the target polynomial’s linear and quadratic coefficients into an order-2 signature tensor, then uses Lempel’s algorithm to find its minimal factor.The tensor entries are formed from the corresponding coefficients modulo 2.Source: Appendix C · p. 16
  • The feedback and non-feedback variants differ in whether the term |tilde A^T x| stays in f for later rounds or is sent to the output.Terms depending on x_c are sent to the output in either version.Source: Appendix C · p. 17

Appendix D CALCULATING CLIFFORD CORRECTION

The correction procedure compares the parity components of the input and output polynomials, identifies the resulting Clifford correction, and maps its polynomial difference back into a circuit.

Appendix D CALCULATING CLIFFORD CORRECTION

  • The input and output polynomials are split into odd- and even-coefficient parts, and their parity components are known to match.The resulting Clifford correction is identified as U(g2−f2), an element of D2.Source: Appendix D · p. 17
  • The polynomial difference f2−g2 is mapped to a phase polynomial and then to a quantum circuit for the correction.Source: Appendix D · p. 17

Appendix E TODD PSEUDOCODE

Appendix E presents TODD pseudocode and defines its matrix helpers, beginning by copying A into A′.

Appendix E TODD PSEUDOCODE

  • The appendix presents the Third Order Duplicate-then-Destroy (TODD) algorithm pseudocode.Its procedure begins by initializing A′ to A.Source: Appendix E · p. 18
  • nullspace(A) returns a matrix whose columns generate A’s right null space; colj(A) selects a column, and cols(A) counts columns.Source: Appendix E · p. 18
  • proper(A) removes every pair of identical columns and every all-zero column from A.Source: Appendix E · p. 18

Appendix F COMPUTATIONAL EFFICIENCY OF TODD

The appendix derives a worst-case computational bound for TODD and notes that measured runtimes are much lower and depend on circuit structure.

Appendix F COMPUTATIONAL EFFICIENCY OF TODD

  • The bound counts GF(2) arithmetic operations and assumes TODD, rather than preprocessing or representation mapping, is the computational bottleneck.Source: Appendix F · pp. 18–19
  • The column-pair loop takes at most O(m^2) iterations, with column addition, χ(A, z), nullspace calculation, and a nested loop inside.Source: Appendix F · p. 18
  • Calculating χ(A, z) takes O(n^3m) operations, yielding the same order for the E1 estimate.Source: Appendix F · p. 18
  • The outer loop runs at most m−m′ times (worst case m′=0); L2 contributes E2=m−n, while conditional, update, and proper steps cost m+n+1, n(m+1), and m.Source: Appendix F · p. 18
  • O((n+h)^3t^2) + O((n+h)t^3) upper-bounds expected compiler runtime for n qubits, h Hadamard gates, and t T gates.Source: Appendix F · p. 19
  • In practice, benchmark runtimes are much lower than the worst-case bound and show no simple relation to n, t, and h.The analysis assumes every row of χ(A, z) is calculated, although many rows are identical; calculating only unique rows may improve efficiency.Source: Appendix F · p. 19
Loading 1712.01557v3…