PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient synthesis of universal Repeat-Until-Success circuits

Alex Bocharov, Martin Roetteler, Krysta M. Svore

arXiv:1404.5320v2quant-phcs.ET

TL;DR

RUS synthesis must control circuit-design costs and hardware-relevant overheads while retaining efficient implementations. The paper uses measured ancilla-assisted constructions and reports low expected T-cost for an approximated rotation, with broader depth and synthesis bounds.

  • Problem

    RUS designs may contain many controlled-Pauli gates, creating hardware concerns despite their zero T-count.

    Source: Appendix F · p. 10

  • Method

    The constructions use one measured ancilla for RUS operation, correcting failure at zero T-count, and route data through V or V† using Bell-state ancillas.

    Source: Appendix E · p. 10, §3 · p. 15

  • Results

    58 T gates achieve an expected T-count below 58.7 and trace distance 1.056 × 10^-12 for Rz(π/64).

    Source: Appendix G · p. 11

  • Takeaways & Limitations

    The reported construction combines high-fidelity single-qubit rotation synthesis with low expected T-cost and controlled-Pauli reduction opportunities.

    Source: Appendix F · p. 10, Appendix G · p. 11

    The analysis guarantees the asymptotic expected T-count bound only below a precision threshold that may be impractically small for small δ.

    Source: Appendix A · p. 6

Abstract

from arXiv · show

Recently, it was shown that Repeat-Until-Success (RUS) circuits can achieve a $2.5$ times reduction in expected $T$-count over ancilla-free techniques for single-qubit unitary decomposition. However, the previously best known algorithm to synthesize RUS circuits requires exponential classical runtime. In this paper we present an algorithm to synthesize an RUS circuit to approximate any given single-qubit unitary within precision $\varepsilon$ in probabilistically polynomial classical runtime. Our synthesis approach uses the Clifford+$T$ basis, plus one ancilla qubit and measurement. We provide numerical evidence that our RUS circuits have an expected $T$-count on average $2.5$ times lower than the theoretical lower bound of $3 \log_2 (1/\varepsilon)$ for ancilla-free single-qubit circuit decomposition.

Appendix A: Information-Theoretic Bounds

The appendix derives an information-theoretic lower bound on the design cost of these RUS circuits and states that the bound is specific to this design. It also identifies a probabilistic asymptotic limit and an impractically tight precision threshold for approaching it.

Appendix A: Information-Theoretic Bounds

  • The counting argument bounds the number of eligible cyclotomic integers by O(2^t), using |z|^2 = O(2^(t/2)) and |z|^4 = O(2^t).This establishes the finite density needed for the arc argument.Source: Appendix A · p. 5
  • O(2^t) cyclotomic rationals imply that some axial rotations cannot be implemented with design cost t or less when ε < K × 2^-t.The argument uses an empty arc on the unit circumference containing no eligible cyclotomic rational.Source: Appendix A · p. 5
  • The necessary condition ε ≥ K × 2^-t yields a lower bound on the design cost for implementing axial rotations with these RUS circuits.The supplied passages state that this condition is equivalent to the specific lower bound for the authors’ solution.Source: Appendix A · pp. 5–6
  • For any fixed δ > 0, the method guarantees expected T-count at most (1 + δ) log2(1/ε) plus a constant below a threshold ε_δ.The threshold may be impractically tight for small δ because the one-round success rate is strictly below one.Source: Appendix A · p. 6
  • A uniform lower bound under assumptions broader than this RUS design remains an open problem for future research.The appendix explicitly limits its derivation to the particular design considered.Source: Appendix A · p. 6

Appendix C: Details on Cyclotomic Rational Approximation

This appendix reduces axial-rotation approximation to finding small-norm cyclotomic integers whose phase ratio approximates the target phase. It uses approximate integer-relation bounds to obtain a cyclotomic-integer magnitude scaling of O(ε^-1/4).

Appendix C: Details on Cyclotomic Rational Approximation

  • The phase ratio z*/z approximates e^iθ when a specified integer-linear expression involving θ is smaller than ε|z|.The same expression vanishing exactly characterizes exact representability.Source: Appendix C · p. 6
  • O(ε^-1/4) bounds the magnitude of cyclotomic integers z_ε whose phase ratios ε-approximate e^iθ.This follows from the stated multivariate Diophantine-approximation result.Source: Appendix C · p. 6
  • The approximation is constructed by choosing integer coefficients that make the relevant linear form small while controlling their maximum magnitude by a power of the requested error.The appendix applies a multivariate integer-relation theorem to the trigonometric quantities determined by θ.Source: Appendix C · p. 6
  • The customized PSLQ algorithm finds approximate integer relations with norm O(m_ε), and therefore O(ε^-1/4) under the appendix’s observation.Here m_ε is the minimum norm of an approximate relation at precision ε.Source: Appendix C · p. 7

Appendix D: Details on the Norm Equation in Z[ω]

The appendix explains how norm equations over the cyclotomic ring are solved efficiently in favorable factorization cases and how randomized normalization addresses solvability. It relies on a conjecture that favorable multipliers occur with sufficient density.

Appendix D: Details on the Norm Equation in Z[ω]

  • Norm equations are constructively solvable in three stated factorization situations, and primes in those classes are called “good” primes.The supplied passages specify two of the prime conditions and identify the resulting classification.Source: Appendix D · p. 7
  • For composite right-hand sides, the algorithm precomputes small prime elements and searches limited factorizations whose residual factor passes a primality test.Efficiency is retained when the residual and selected factors satisfy the good-prime or even-exponent conditions.Source: Appendix D · p. 7
  • Randomized normalization samples a multiplier because the norm equation can change substantially even when the phase ratio remains unchanged.Multiplying z by a real-valued ring element r preserves (rz)*/(rz) but changes the norm equation’s right-hand side.Source: Appendix D · p. 7
  • The method relies on the conjecture that “lucky” multipliers making the norm equation solvable are reasonably dense in the ring.The appendix describes estimating this density as an open and likely very hard number-theory problem.Source: Appendix D · p. 7

1. Random Search Normalization

  • The second randomized-normalization version uses sampling radius and a minimum one-round success rate to generate near-deterministic RUS circuits.The Tcount function supplies minimal Clifford+T costs without necessarily performing the decomposition.Source: §1 · p. 7

Appendix E: Details on RUS Circuit Synthesis

The appendix develops constructive normal-form and lifting results that synthesize RUS designs from single-qubit Clifford+T representations, with bounded T-count overhead and a one-ancilla implementation.

Normal forms

  • Circuits with equal minimal T-count can be related through decorated T codes, differing only by Clifford wrappers and Pauli insertions.The construction motivates lifting equivalent single-qubit representations into a two-qubit RUS design.Source: Appendix E · pp. 7–9
  • Any single-qubit Clifford+T circuit can be constructively rewritten as Clifford gates surrounding a T code, enabling subsequent synthesis transformations.A T code is generated by T H and T† H syllables.Source: Appendix E · p. 8

Lifting

  • The Lift procedure maps Pauli gates to controlled-Pauli gates and other gates to ancilla-local operations, producing a two-qubit Clifford+T circuit.The primary qubit acts as control while single-qubit gates are placed on the ancilla in the described implementation.Source: Appendix E · p. 9
  • A lifted representation of a unitary with T-count t requires either t or t + 1 T gates in the key two-qubit construction.The possible increase arises from at most two non-Pauli Clifford gates introduced during lifting.Source: Appendix E · pp. 8–9

RUS construction

  • The synthesis algorithm takes V as input, decomposes V and V† into related T-code forms, lifts the decorated code, and returns the RUS design circuit.The algorithm is summarized in Figure 8 and outputs the constructed RUS circuit.Source: Appendix E · p. 9, Figure 8 · p. 9
  • A single-qubit unitary with minimum T-count t yields a two-qubit RUS circuit using at most t + 9 T gates and success probability |u|^2.On failure, the target acquires a Z correction that can be reversed at zero T-count; on success, the target implements the desired rotation.Source: Appendix E · p. 10

Appendix F: Reducing controlled-Pauli Gates in an RUS design

The appendix reduces controlled-Pauli overhead by rewriting decorated T codes while preserving their signatures, yielding a systematic bound on the remaining Pauli gates.

Overhead

  • Worst-case synthesis can introduce up to 2t controlled-Pauli gates, which may concern hardware despite their zero T-count.Here t denotes the circuit T-count.Source: Appendix F · p. 10

Reduction strategy

  • Signature-preserving rewrite rules eliminate half of the Pauli gates in a decorated T code.The optimization targets controlled-Pauli overhead without changing the circuit signature.Source: Appendix F · p. 10
  • A decorated T code of T-count t can be systematically rewritten to an equivalent form with no more than t + 1 Pauli gates and the same signature.The bound follows from commuting Pauli gates through Hadamards and applying a minimality argument.Source: Appendix F · p. 10

Appendix G: An Example

The worked example synthesizes an RUS circuit for Rz(π/64) at precision 10^-11, achieving better-than-requested accuracy and substantially lower expected T-count than the ancilla-free bound.

Example setup

  • The example targets Rz(π/64) with precision ε = 10^-11 and uses randomized norm-equation search to obtain one-round success probability 0.9885.The integer-relation stage first achieves approximately 3 × 10^-12 precision before the randomized search modifies the representation.Source: Appendix G · p. 10

Cost and accuracy

  • The synthesized circuit has design cost 58 T gates and expected T-count below 58.7 at success probability 0.9885.An alternative construction using Λ(H) has expected T-cost 54.6.Source: Appendix G · p. 11
  • The final trace distance is 1.056 × 10^-12, better than the requested precision.The displayed circuit is generated in the final synthesis stage.Source: Appendix G · pp. 10–11

Comparison

  • The example’s expected T-count is roughly 2.4 times smaller than the ancilla-free theoretical bound at ε = 1.056 × 10^-12.The paper notes that reductions reliably exceed 2.5 at finer precisions, whereas this coarser example is easier to parse.Source: Appendix G · p. 11

Appendix H: Cost and Performance Evaluation

The evaluation examines T-count versus precision for random axial rotations and separately considers Fourier rotations and runtime performance.

Evaluation scope

  • The evaluation covers T-count-versus-precision performance on random axial rotations, Fourier rotations, and algorithm runtime.The supplied passage introduces these evaluation dimensions without reporting their numerical outcomes.Source: Appendix H · p. 11

1. Cost Evaluation on Fourier angles

For 40 Fourier angles across precisions from 10^-11 to 10^-40, the synthesized RUS circuits show expected T-count scaling with precision. The mean follows 1.08 log2(1/ε) + 17.5, with plateaus attributed to overclocking.

Cost Evaluation on Fourier angles

  • 40 angles of the form π/2^k were evaluated at 30 target precisions from 10^-11 through 10^-40.For each angle and precision, the algorithm generated a two-qubit RUS circuit and recorded expected T-count and runtime.Source: §1 · p. 11
  • 1.08 log2(1/ε) + 17.5 is the regression for mean expected T-count across 40 Fourier angles.The equivalent base-10 form is 3.59 log10(1/ε) + 17.5.Source: §1 · p. 11
  • Plateaus arise when the algorithm produces precision better than requested, such as approximately 10^-23 for a 10^-21 target.This overclocking occurs more frequently for π/2^k angles than for completely random angles.Source: §1 · p. 11

2. Runtime Performance Evaluation

The runtime analysis finds probabilistically polynomial dependence on log(1/ε), supported by norm-equation complexity and empirical PSLQ scaling. Although PSLQ iterations grow linearly in log(1/ε), variable-precision arithmetic makes elementary big-digit cost quadratic in that quantity.

Runtime Performance Evaluation

  • PSLQ and norm-equation solving are the algorithm’s only intensive computational blocks; other steps have trivial combined runtime.The implementation used Mathematica and assessed PSLQ iterations rather than wall-clock speed because the code was not optimized for clock speed.Source: §2 · p. 11
  • 3.86 log10(1/ε) − 6.77 is the empirical regression for PSLQ iterations, confirming linear growth in log(1/ε).Figure 10 reports mean expected iterations to PSLQ termination.Source: §2 · p. 11, Figure 10 · p. 12
  • Variable-precision arithmetic raises the practical cost of PSLQ to quadratic in log(1/ε) elementary big-digit operations.The mantissa size grows linearly with log(1/ε).Source: §2 · pp. 11–12
  • The overall synthesis runtime is probabilistically polynomial in log(1/ε).The norm-equation cost is probabilistically polynomial in the right-hand-side bit size, and the randomized modifier search solves polynomially many equations per target and precision level.Source: §2 · p. 12

Appendix I: Generalizations

The appendix extends RUS constructions beyond the single-ancilla single-qubit setting. It gives exact implementation results with two ancillas, a conjectural one-ancilla strengthening, and a specialized two-ancilla alternative for xy-plane rotations.

Appendix I: Generalizations

  • An arbitrary unitary can be implemented exactly by an RUS circuit using at most two additional qubits under the stated pre-multiplier ring condition.The condition is always met for unitaries defined over Q(ω).Source: Appendix I · p. 12
  • For unitaries over Q(ω), the two-ancilla exact implementation result applies generally.This follows because the required pre-multiplier condition is always satisfied over that field.Source: Appendix I · p. 12
  • With at most one additional qubit, the same class of unitaries can be implemented only assuming a number-theory conjecture.The conjectural strengthening saves one ancilla relative to the two-ancilla construction.Source: Appendix I · p. 12
  • A specialized Jack-of-Daggers implementation uses two ancillas, triples T-count, and applies when V is a rotation around an xy-plane axis.It avoids additional entangling gates and tightly controls T-depth in terms of the T-depth of V.Source: Appendix I · p. 12

1. Exact implementations with 2 ancillas

The exact-implementation construction embeds suitable scaled unitaries into larger unitaries and uses arithmetic conditions to realize them as RUS circuits. For Q(ω)-defined unitaries, this yields exact implementations with at most two ancillas and identity failure behavior.

1. Exact implementations with 2 ancillas

  • More generally, if a scaled version of V has entries in Z[i,1/√2] and |α|^2 is an integer, V admits an RUS circuit with at most n + 2 qubits.The two ancillas are initialized to |0⟩, and failure implements the identity on the n-qubit target.Source: §1 · p. 12
  • The proof reduces the embedding problem to quadratic Diophantine equations and applies a unitary-embedding lemma twice.The extra degrees of freedom allow the equations to be solved using the four squares theorem.Source: §1 · pp. 12–13
  • Scaling V to a contraction enables successive embeddings into a unitary of four times the matrix size.The construction chooses ℓ so that α2^-ℓ/2 has norm at most one, then builds the embedding using β and γ coefficients.Source: §1 · p. 13
  • The resulting embedding has coefficients in Z[i,1/√2] and can be implemented exactly over Clifford+T.Its determinant condition removes the otherwise required additional ancilla qubit.Source: §1 · p. 13
  • Any exact RUS design with at least two ancillas and Clifford corrections can be replaced by one with at most two ancillas and no failure correction.This follows because an existing RUS circuit supplies a scalar α satisfying the exact-implementation theorem’s assumption.Source: §1 · p. 13
  • A unitary V over Q(ω) can be implemented exactly by an RUS circuit using at most two ancilla qubits.The ancillas can be initialized to |0⟩, and failure applies only the identity operation.Source: §1 · p. 13

2. Exact implementations with 1 ancilla

The one-ancilla construction embeds the target operation through cyclotomic norm equations, but its exact solvability relies on unresolved number-theoretic assumptions.

Exact embeddings

  • The proposed embedding imposes |θ|^2|α|^2+|λ|^2 = 1, with θ and λ chosen from Q[ω] under additional assumptions on V.For V over Q(ω), α can be chosen as an odd integer, reducing the condition to a norm-form equation.Source: §2 · p. 13
  • The construction reduces solvability to norm equations whose coefficients are represented through arithmetic progressions and primes constrained modulo 8.The ansatz uses N(θ) = 8k + 3 and seeks primes satisfying p ≡ 5 mod 8 for the corresponding equation N(λ) = p.Source: §2 · p. 13

Number-theoretic limitation

  • Exact solvability ultimately depends on Dickson’s unproven conjecture about simultaneous primes in arithmetic progressions.Even establishing one such simultaneous prime is described as a long-standing open problem.Source: §2 · p. 14

Heuristic evidence

  • A heuristic based on Chebotarev’s density theorem suggests suitable prime pairs are likely and are found quickly in practice, but does not guarantee them.The relevant primality events are not independent, so the heuristic cannot establish universal solvability.Source: §2 · p. 14

Alternative approach

  • Restricting the variables to Gaussian integers does not resolve the issue because the resulting quadratic form has an infinite set of exceptions.The form falls into a case known not to have a finite exception set.Source: §2 · p. 14

3. Low-depth implementations with 3 ancillas

The three-ancilla implementation realizes a controlled choice between V and V† using Bell-state eigenstates, preserving V’s T-depth up to a constant additive term for V in Sxy.

Resource trade-off

  • A related ancilla-free realization can require a number of entangling operations that grows linearly with the T-count of V.The three-ancilla alternative trades additional ancillas for controlled-SWAP-based depth control.Source: §3 · p. 14

Bell-state construction

  • The circuit uses Bell states as efficiently prepared eigenstates to route the data qubit through either V or V†.The singlet handles V⊗V, while the relevant symmetric Bell state handles V†⊗V for V ∈ Sxy.Source: §3 · pp. 14–15

Low-depth implementation

  • The alternative implementation applies to V ∈ Sxy and achieves T-depth at most t + 8 when V has T-count t.Its applicability is limited to rotations around axes in the xy-plane.Source: §3 · p. 14

Depth and resources

  • The central V, V†, V gates run in parallel, so the circuit retains V’s T-depth apart from controlled-SWAP overhead.Two controlled-SWAP gates each use 7 T gates with T-depth 4; the remaining gates are Clifford gates.Source: Figure 11 · p. 15, §3 · p. 15

Controlled transformation

  • The input control bit determines whether the transformation applied to the data qubit is V or V†, after which the ancillas are returned to |0⟩.For b = 0 the circuit applies V, and for b = 1 it applies V†.Source: §3 · p. 15

Depth and resources

  • The construction adds two ancillas beyond the one ancilla already required by the RUS design.The additional ancillas are initialized in |0⟩.Source: §3 · p. 15
Loading 1404.5320v2…