PaperlayerView exact revision on arXiv

Source-linked AI summary

Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries

Adam Paetznick, Krysta M. Svore

arXiv:1311.1074v2quant-ph

TL;DR

Fault-tolerant single-qubit decomposition seeks accurate approximations with fewer costly non-Clifford gates. The paper develops measurement-conditioned Repeat-Until-Success circuits and shows improved T-count scaling for Z-axis rotations and arbitrary single-qubit unitaries, while its database limits accuracy to 10^-6 unless expanded or supplemented algorithmically.

  • Problem

    Fault-tolerant decomposition needs accurate single-qubit approximations while minimizing the costly non-Clifford-gate count.

  • Method

    The paper develops non-deterministic Repeat-Until-Success circuits that condition on measurement outcomes, recover from failure, and repeat using few non-Clifford gates and ancillas.

  • Results

    For random Z-axis rotations, the technique can use as little as one-third as many T gates as prior methods, while arbitrary single-qubit unitaries can be approximated within 10^-6.

  • Takeaways & Limitations

    RUS circuits extend lower-T-count non-deterministic decomposition from small Z-axis rotations to arbitrary single-qubit unitaries.

  • Takeaways & Limitations

    The Z-axis database supports accuracy only up to 10^-6; higher accuracy requires expanding the database or using an algorithmic decomposition.

Abstract

from arXiv · show

We present a decomposition technique that uses non-deterministic circuits to approximate an arbitrary single-qubit unitary to within distance $ε$ and requires significantly fewer non-Clifford gates than existing techniques. We develop "Repeat-Until-Success" (RUS) circuits and characterize unitaries that can be exactly represented as an RUS circuit. Our RUS circuits operate by conditioning on a given measurement outcome and using only a small number of non-Clifford gates and ancilla qubits. We construct an algorithm based on RUS circuits that approximates an arbitrary single-qubit $Z$-axis rotation to within distance $ε$, where the number of $T$ gates scales as $1.26\log_2(1/ε) - 3.53$, an improvement of roughly three-fold over state-of-the-art techniques. We then extend our algorithm and show that a scaling of $2.4\log_2(1/ε) - 3.28$ can be achieved for arbitrary unitaries and a small range of $ε$, which is roughly twice as good as optimal deterministic decomposition methods.

1 Introduction

The paper targets resource-efficient fault-tolerant decomposition of single-qubit unitaries, where T gates dominate the cost. It introduces non-deterministic RUS circuits using measurements and ancillas to reduce expected T counts while retaining exact conditional implementations.

  • Motivation: T gates define the cost of {H, T} circuits because fault-tolerant T gates can cost up to an order of magnitude more than H gates.
  • Results: The method reduces expected T gates for random Z-axis rotations by roughly three-fold over prior techniques and improves arbitrary-unitary scaling by roughly 50 percent relative to composing three Z rotations.
  • Method: RUS circuits condition on measurement outcomes, implement the desired unitary on success, and reverse failure outcomes before repeating.This repeat-until-success structure uses non-determinism rather than a fixed deterministic gate sequence.
  • Method: The framework characterizes exactly representable RUS unitaries, searches for low-T-count circuits, builds a database, and composes circuits for approximation.

2 Existing methods for single-qubit unitary decomposition

Prior single-qubit decomposition methods include phase kickback, programmable ancilla rotations, alternate gate sets, and hierarchical RUS circuits. This paper improves RUS-based decomposition and characterizes its broader applicability.

  • Existing approaches: Earlier approaches used phase kickback with Fourier-transform ancillas and phase estimation, or programmable ancilla rotations with cascading ancillas and gate teleportation.These methods represent alternative non-deterministic strategies for single-qubit unitary decomposition.
  • Alternate gate sets: BGS approximated arbitrary single-qubit unitaries over {H, S, V3} with typical cost 3 log5(1/ε) V3 gates.Their fault-tolerant V3 implementation initially required eight T gates, later reduced to one Toffoli by Jones.
  • Alternate gate sets: Four T gates implement V3 exactly with the improved RUS circuit, compared with 67 T gates for KMM approximation at ε = 10^-6.The resulting {H, S, V3}-decomposition also has lower average T count than {H, T}-decomposition methods.
  • RUS circuits: RUS circuits extend beyond small-angle Z rotations to large- and small-angle rotations and rotations about arbitrary axes.The paper also provides a general characterization and construction framework for RUS circuits.
  • RUS circuits: Earlier RUS work proposed hierarchical tree-like circuits that outperform Selinger and KMM for small-angle Z-axis rotations.The present work distinguishes itself by targeting a wider range of rotation angles and axes.
  • Cost comparisons: The paper summarizes T-count costs for its RUS method and prior algorithms in separate tables for non-axial and axial rotations.The supplied passage identifies the tables' scopes but does not provide their cell values.

3 Repeat-Until-Success circuits

RUS circuits use ancilla measurements to implement a target single-qubit unitary on success and inexpensive recoverable operations on failure, enabling repetition until success. The framework characterizes exact implementability, searches low-T circuits, and analyzes success probability, expected cost, and amplitude amplification.

  • 3 Repeat-Until-Success circuits: For V3, zero outcomes on two X-basis measurements implement V3 exactly, while other outcomes implement identity; success probability is 5/8.The protocol therefore repeats until the all-zero outcome occurs, with a geometrically distributed repetition count.
  • 3 Repeat-Until-Success circuits: RUS circuits prepare ancillas, apply a {Clifford, T} unitary, measure them, and repeat after low-cost recovery operations when the outcome indicates failure.Success outcomes implement the desired operation; failure outcomes implement undesired operations that are reversed before repetition.
  • 3 Repeat-Until-Success circuits: The framework represents the success branch as U and other measurement branches as recoverable unitaries, with ancilla preparation and a joint unitary W defining the circuit.The all-zero ancilla outcome can be selected as the success outcome without loss of generality because measurement outcomes may be permuted.
  • 3 Repeat-Until-Success circuits: Exact {Clifford, T} implementation requires the relevant scaled unitary matrices and coefficients to lie in the ring Z[i, 1/√2], with normalization constraints on the construction.When α0 is an integer, Lagrange’s four-square theorem permits satisfying the normalization with at most two ancilla qubits.
  • 3.2 Success probability and expected cost: The expected repetition count is 1/p, so an RUS circuit with implementation cost C(W) has expected cost C(W)/p and variance C(W)(1−p)/p^2.T count is used because fault-tolerant resources are often dominated by T gates, although circuit volume may be more complete for some architectures.
  • 3.3 Amplifying the success probability: Amplitude amplification can increase success probability and reduce expected T count for some RUS circuits, particularly when p < 1/3.For circuits with more than two ancillas, the non-Clifford cost of the reflection operator makes the analysis more complicated.

4 Direct search algorithm

The authors develop an optimized direct-search procedure for synthesizing low-T-count RUS circuits, focusing on one-ancilla, two-CZ circuit structures and canonical single-qubit sequences.

  • Search procedure: The search retains circuits whose non-Clifford matrix blocks are all proportional to one unitary, identifying RUS circuits implementing that unitary on success.The procedure constructs a {Clifford, T} circuit, partitions W's first two columns into 2 × 2 matrices, removes Clifford-proportional blocks, and tests the remainder.
  • Circuit family: The study focuses on circuits with one ancilla qubit and two CZ gates interleaved with single-qubit Clifford gates.A preliminary random search found many results for small ancilla counts, larger T counts, and one or two entangling gates.
  • Search optimization: Canonical-form representations and Clifford simplifications reduce the direct-search space while preserving the relevant single-qubit gate sequences.Canonical sequences use Clifford factors around products of TH and SHTH syllables, and diagonal or absorbable Clifford gates can be eliminated in the target circuit structure.
  • Computational cost: The direct search remains exponential in the number of T gates, so the authors partition it across many parallel computations and collect results in a central database.Circuits of the Fig. 3 form were exhaustively synthesized up to raw T count 15 in roughly one week on hundreds of cores.

5 Direct search results

The search produces a database of exact, measurement-conditioned RUS implementations with low expected T counts and substantial advantages over deterministic approximation for axial and non-axial rotations.

  • Database results: The database contains 2194 minimum-expected-T-count circuits with at most 15 T gates, including 1659 axial and 535 non-axial rotations.Each circuit exactly implements a unique non-Clifford single-qubit unitary on success and otherwise implements a single-qubit Clifford operation.
  • Amplification: Amplitude amplification improves circuits with relatively high expected T counts but does not improve circuits with expected T count 30 or less.The database statistics compare raw T count and success probability with expected T count before and after amplification.
  • Axial rotations: The database demonstrates that many axial rotations can be implemented exactly conditioned on measurement, although only T is nontrivially exactly synthesizable without measurement in the Clifford-T setting.Of the database circuits, 1659 are axial rotations modulo Clifford conjugation.
  • Database comparisons: Typical RUS improvements are about three-fold for axial rotations and about twelve-fold for non-axial rotations versus KMM expected T counts at distance 10^-6.The larger non-axial advantage arises because KMM decomposes such unitaries into three axial rotations.
  • Representative example: A four-T-gate RUS circuit succeeds with probability 7/8 and implements a non-axial rotation exactly, whereas KMM requires 182 T gates for distance 10^-6.The RUS circuit therefore uses over 40 times fewer T gates than the cited approximation method for this example.
  • Further constructions: The database also contains higher-order V-basis gates with normalization factors 1/√p for p ∈ {13, 17, 29}, providing fault-tolerant implementations for these gates.These gates are presented as possible ingredients for more efficient future decomposition algorithms.

6 Applications

RUS circuits are used to reduce the T-gate cost of approximating single-qubit rotations and arbitrary unitaries. Database composition achieves high-accuracy axial approximations and improved non-axial scaling, subject to computational and database-size limits.

  • 6 Applications: RUS circuits provide exact, fault-tolerant implementations and can therefore serve as components for universal gate sets and approximate decomposition.The circuits condition the desired unitary on a measurement outcome and repeat after reversible failure outcomes.
  • 6.2 Decomposition by composition of RUS circuits: The composition approach exhaustively searches RUS-circuit combinations, retaining circuits below a fixed expected T-count threshold and using Clifford-conjugation equivalence classes.This reduces database growth and computational cost while preserving candidates with low expected cost.
  • 6.2.1 Results: decomposition with axial rotations: 1.26 log2(1/ε) − 3.53 T gates approximate arbitrary Z-axis rotations, with 95% probability for randomly chosen angles.The database supports approximation of any Z-axis rotation to ε = 10^-6.
  • 6.2.1 Results: decomposition with axial rotations: Approximation accuracy is limited by computation time, memory, and database size, with the reported construction requiring roughly 20 hours and 41 GB of memory.The authors state that more efficient implementations or database expansion could improve worst-case accuracy.
  • 6.2.2 More accurate axial rotations using gearbox circuits: Gearbox circuits improve direct methods for large angles, while their best scaling applies when the angle and required relative precision are small.The database described permits at most six significant digits; higher precision requires a larger database.
  • 6.2.3 Results: Decomposition with non-axial rotations: 2.4 log2(1/ε) − 3.28 expected T gates approximate arbitrary single-qubit unitaries over ε ≥ 8 × 10^-3.The result uses a database of 45,526 RUS circuits with expected T count at most 18 and is roughly twice as efficient for modest accuracies.

7 Conclusions and future work

The paper establishes RUS circuits as a general non-deterministic framework for exact representation and low-T-count approximation of single-qubit unitaries. Its conclusions include strong T-count reductions, while accuracy, circuit scope, and online execution impose boundaries for future work.

  • Conclusions: RUS circuits provide a general non-deterministic framework and characterize which unitaries can be represented exactly.The circuits condition on measurement outcomes and can be repeated when the desired outcome is not obtained.
  • Results: For random Z-axis rotations, RUS methods can require as little as one-third the T gates of several deterministic techniques, while arbitrary-unitary accuracy reaches 10^-6.Composing axial and non-axial RUS circuits yields larger T-count improvements, with accuracy limited by database size.
  • Future work: The current circuit family is only a subset of possible RUS circuits, and incomplete number-theoretic understanding limits efficient decomposition and approximation to smaller ε.Expanding the search could improve database density.
  • Future work: The framework is restricted to Clifford recovery operations and has not yet been extended to multi-qubit unitaries or non-unitary channels.The paper suggests considering larger or alternative recovery-operation classes.
  • Architectural constraints: Online RUS execution makes completion time unpredictable, requiring placement, routing, and classical-control techniques that must be assessed for each architecture.Architecture-specific analysis is needed to evaluate practical benefits.
Loading 1311.1074v2…