PaperlayerView exact revision on arXiv

Source-linked AI summary

Lower bounds on the non-Clifford resources for quantum computations

Michael Beverland, Earl Campbell, Mark Howard, Vadym Kliuchnikov

arXiv:1904.01124v2quant-ph

TL;DR

Magic-state distillation dominates the overhead of stabilizer-based fault-tolerant quantum computing, motivating sharper resource lower bounds. This paper develops monotones and a canonical form for stabilizer computations, establishing stronger bounds for state conversion, unitary synthesis, and key computational tasks.

  • Problem

    Magic-state production can dominate fault-tolerant quantum-computing overhead, motivating lower bounds on resources needed for conversions, unitary synthesis, and computational tasks.

    Source: §1 · p. 3

  • Method

    The paper introduces stabilizer nullity and the dyadic monotone, uses stabilizer extent, and derives a canonical form for post-selected stabilizer circuits.

    Source: §1.1 · p. 3, §1.2 · p. 4, §7 · p. 33

  • Results

    The paper establishes stronger lower bounds for resource conversion, arbitrary single-qubit unitary approximation, modular addition, and multiply-controlled phase operations.

    Source: §1 · p. 3, §7 · p. 32

  • Takeaways & Limitations

    The results provide resource-cost bounds across state conversion, synthesis, and computational tasks, including catalytic conversions that are impossible without catalysts.

    Source: §1 · p. 3, §2.3 · p. 9

    Not all inter-conversion bounds apply with arbitrary catalysts because stabilizer extent multiplicativity is unknown for all states.

    Source: §7 · p. 33

Abstract

from arXiv · show

We establish lower-bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks, treating stabilizer operations as free. Our bounds apply to adaptive computations using measurements and an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational tasks. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are close to optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision $\varepsilon$ requires at least $1/7\cdot\log_2(1/\varepsilon) - 4/3$ $T$-states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on $\varepsilon$. Up to multiplicative factors, we optimally lower bound the number of $T$ or $CCZ$ states needed to implement the ubiquitous modular adder and multiply-controlled-$Z$ operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.

1 Introduction and high-level overview

The paper develops monotones and canonical-form techniques to lower-bound magic-state resources for state conversion, important quantum subroutines, and approximate unitary synthesis. It also identifies catalytic conversion gaps and near-optimal costs under restricted measurement outcomes.

1.1 Monotones under stabilizer operations

  • The paper introduces stabilizer nullity and uses it, together with stabilizer extent, to prove resource-state lower bounds under stabilizer operations.Stabilizer nullity is the number of hosted qubits minus independent stabilizing Pauli operators, and it is non-increasing under stabilizer operations.Source: §1.1 · p. 3
  • Catalysis is necessary and sufficient for several resource-state conversions, establishing a general no-go theorem and new catalytic examples.Catalyst states are borrowed during computation and returned unchanged at the end.Source: §1.1 · p. 4

1.2 Resource state conversion

  • Stabilizer nullity rules out some catalyzed conversions and reveals an asymptotic conversion gap between T-states and CCZ-states.Starting with n copies of |T⟩, optimal conversion through |CCZ⟩ yields fewer than n |T⟩ copies, even asymptotically.Source: §1.2 · p. 4

1.3 Computational tasks

  • For n ≥ 3, implementing Cn−1Z requires at least n |T⟩, n/2 |CS⟩, or n/3 |CCZ⟩ states, while the best known algorithm uses n − 2 |CCZ⟩ states.The bounds follow by lower-bounding the resource cost of producing the corresponding target state.Source: §1.3 · p. 5

1.4 Unitary synthesis

  • The unitary-synthesis bounds apply despite measurements, classical feed-forward, and ancillas, using canonical stabilizer-circuit forms and discrete measurement probabilities.The analysis must also handle catalyst states and random resource consumption determined by measurement outcomes.Source: §1.4 · p. 6

1.5 Measurement with probability 1/2

  • With only probability-one-half Pauli measurements, the dyadic monotone proves that n − 2 |CCZ⟩ states optimally implement Cn−1Z and are required for modular addition.The best known modular-adder circuit uses one additional |CCZ⟩ state.Source: §1.5 · pp. 6–7

2 Some basic techniques

This section introduces stabilizer nullity and reviews stabilizer extent as monotones under stabilizer operations, then shows that catalysts can enable conversions otherwise impossible. These techniques support the paper’s later resource-conversion bounds.

2.1 Stabilizer nullity

  • The stabilizer nullity ν(|ψ⟩) = n − log2 |Stab|ψ⟩| is invariant under Clifford unitaries, non-increasing under Pauli measurements, additive under tensor products, and unchanged by stabilizer states.After a Pauli measurement, the stabilizer size either stays the same or increases by at least a factor of two.Source: §2.1 · pp. 7–8

2.2 Stabilizer extent

  • The stabilizer extent ξ is another monotone under stabilizer operations [4] [42], defined through minimization over complex linear combinations of stabilizer states and multiplicative for specified state sets.Its multiplicativity holds when each state in the set satisfies at least one stated condition, although broader multiplicativity remains unproven.Source: §2.2 · pp. 8–9

2.3 Catalysis

  • Catalysts—resource states returned unchanged—enable conversions forbidden without them, while number-field closure proves that stabilizer circuits preserve density-matrix entries within the field.In particular, |CS⟩ or |CCZ⟩ states cannot produce |T⟩ without catalysis, whereas |CS⟩ can produce |T⟩ using an additional unconsumed |T⟩ catalyst.Source: §2.3 · pp. 9–10, Figure 2 · p. 11

3 Conversion between resource states

This section develops catalytic protocols and monotone-based bounds for converting quantum resource states. It shows that catalysis enables otherwise impossible conversions, while conversion rates can remain lossy even asymptotically.

3 Conversion between resource states

  • Catalytic conversions generalize prior constructions [8] [21] [44], and monotones show that exactly interconvertible resource states may still require asymptotic loss.The section develops phase-polynomial and adder-based catalytic protocols, then uses monotones to bound optimal conversion rates.Source: §3 · p. 11

3.1 Phase polynomial protocols

  • For W_n states, catalysis converts |W_n⟩ to |T⟩⊗n−1, whereas no T-states can be derived without a catalyst; W_n can also be reduced to W_n−1 by measurement and Clifford correction.The |W_n⟩→|T⟩⊗n−1 conversion matches the phase-polynomial theorem, and reduction succeeds for either computational-basis measurement outcome.Source: §3.1 · pp. 12–13

3.2 One-bit adder conversion protocols

  • Recursive one-bit-adder protocols implement higher-level rotations using Clifford magic states and catalysis, amortizing correction costs and achieving asymptotically optimal |CCZ⟩ consumption under 50% measurement outcomes.For exp(πij/2^d|1⟩⟨1|) gates, the protocol uses (2^d−1−1)(k−1)+d−1 copies of |CCZ⟩, while the lower bound requires asymptotically 1−1/2^(d−1) copies per produced state.Source: §3.2 · pp. 13–16

3.3 Conversion bounds

  • For |T⟩ and |CCZ⟩ conversions, stabilizer nullity gives r≥3 and r′≤3, while stabilizer extent strengthens the consumption bound to r≥3.63356.The resulting gap means producing a |CCZ⟩-related CSS state requires at least 3.63 |T⟩ states, but conversion back yields at most 3 |T⟩ states.Source: §3.3 · pp. 16–17, Table 1 · p. 17

4 Computational task lower bounds

The section lower bounds non-stabilizer resources for multiply controlled-Z gates and modular adders by reducing gate implementation to resource-state production, including catalytic conversions. It obtains linear lower bounds in n for T, CS, and CCZ resources, and also for the n-qubit Quantum Fourier Transform.

4 Computational task lower bounds

  • The resource-state strategy lower bounds implementing a unitary by the copies needed to produce its output state, including catalytically produced non-stabilizer states.The approach bootstraps state-production bounds to computational tasks and permits catalyst states that are returned after the computation.Source: §4 · pp. 17–18

4.1 Lower bounds for the CnZ gate

  • For n ≥ 3, implementing Cn−1Z requires at least n |T⟩ states, n/2 |CS⟩ states, or n/3 |CCZ⟩ states.These bounds follow from stabilizer nullity values ν(|T⟩) = 1, ν(|CS⟩) = 2, and ν(|CCZ⟩) = 3.Source: §4.1 · p. 18

4.2 Lower bounds for the modular adder

  • Modular addition on two n-qubit registers requires at least n − 2 |T⟩ states, (n − 2)/2 |CS⟩ states, or (n − 2)/3 |CCZ⟩ states.The same nullity calculation also shows that an n-qubit Quantum Fourier Transform requires at least n−2 copies of |T⟩.Source: §4.2 · pp. 19–20

5 Lower bounds for approximate unitary synthesis

This section derives resource-state lower bounds for approximate single-qubit unitary synthesis that allow adaptive Pauli measurements and arbitrary stabilizer ancillas. It connects diamond-norm unitary approximation to post-selected state approximation and obtains logarithmic lower bounds for |CS⟩, |CCZ⟩, and |T⟩ resources.

5 Lower bounds for approximate unitary synthesis

  • The bounds apply to adaptive Clifford-and-Pauli-measurement protocols and do not depend on the number of ancillary qubits.A canonical form for post-selected stabilizer circuits reduces the analysis to commuting measurements without ancillary qubits.Source: §5 · pp. 21–22

5.1 Approximate unitary synthesis with and without post-selection

  • For any C > 1, the protocol satisfies the Cε condition with probability at least (C −1)/C, and therefore N|Ψ⟩(U, ε) ≥ N, under Definition 5.1.Source: §5.1 · pp. 22–23

5.2 Lower bounds with |CS⟩and |CCZ⟩resource states

  • |CS⟩ resources require at least 1/3·log2(1/ε)− 2/3 copies for some states when ε < 1/8, while |CCZ⟩ resources require at least 1/4 · log2(1/ε) −1/2.The |CS⟩ bound applies, for example, when ε < |⟨ψ|0⟩|2 < 3ε; the |CCZ⟩ result assumes post-selection probability p.Source: §5.2 · pp. 24–25

5.3 Lower bounds with |T⟩resource states

  • |T⟩ resources require at least 1/3 · log2(1/ε) −2/3 copies for some states when ε < 1/8.The bound applies, for example, to states satisfying ε < |⟨ψ|0⟩|2 < 3ε, and follows from a lower bound on nonzero joint Pauli-measurement probabilities.Source: §5.3 · pp. 25–26

6 Tighter lower bounds with measurement probabilities one half

For stabilizer protocols whose Pauli measurement outcomes each have probability one half, the dyadic monotone yields tighter resource lower bounds. It proves optimality for multiply-controlled-Z, puts the modular-adder bound one |CCZ⟩ short of the best construction, and gives optimal asymptotic catalytic conversion rates.

6 Tighter lower bounds with measurement probabilities one half

  • The dyadic monotone extends the stabilizer-nullity approach by tracking the largest power of two in denominators of Pauli expectations and remains applicable to the half-probability measurement setting.It is additive under tensor products, invariant under Clifford unitaries, nonnegative with equality exactly for stabilizer states, and monotone under the specified measurements.Source: §6.1 · pp. 28–29, §6.2 · p. 30

6.1 Lower bound with CCZ gates for CnZ gate

  • n−2 |CCZ⟩ states are necessary and sufficient to implement the n-qubit multiply-controlled-Z gate Cn−1Z with measurement probabilities one half, making the construction in [32] optimal.The dyadic monotone is invariant under Clifford operations and non-increasing under these measurements, while vanishing exactly on stabilizer states.Source: §6.1 · pp. 28–29

6.2 Lower bounds for the modular adder

  • The n-qubit modular adder requires at least n−2 |CCZ⟩ states and 2n−5 |T⟩ states for n≥3; the best-known [21] construction uses n−1 |CCZ⟩ states.Thus the |CCZ⟩ lower bound is one state short of the best-known construction, while the T-state bound has half its multiplicative constant.Source: §6.2 · p. 31

6.3 Lower bounds for resource state conversion

  • Catalytic conversion of |CCZ⟩ states into n copies of |πj/2^d⟩ for odd j and d≥2 requires at least n(1−1/2^(d−1)) |CCZ⟩ states, making the asymptotic rate optimal.The bound applies to stabilizer protocols with 50% measurement probabilities and catalysts whose entries lie in the relevant ring Rd′.Source: §6.3 · pp. 31–32

7 Conclusion and open problems

The paper establishes resource lower bounds for resource conversion, unitary synthesis, and computational tasks, enabled by new monotones and a canonical post-selected stabilizer-circuit form. It identifies applications to additional circuits and open problems concerning multiplicativity, approximate conversion, algorithmic efficiency, and monotone classification.

Contributions

  • The work derives resource lower bounds across resource-state conversion, unitary synthesis, and computational tasks using stabilizer nullity, the dyadic monotone, and a canonical post-selected stabilizer-circuit form.The authors expect these tools to have broader applications.Source: §7 · pp. 32–33

Future applications

  • Future applications include lower bounds for multiply-controlled adders, Hamming-weight-one preparation, Hamming-weight computation, and small circuits such as small-qubit quantum Fourier transforms.Source: §7 · p. 33

Open problems

  • It remains unknown for which states stabilizer extent is multiplicative, limiting inter-conversion bounds when arbitrary catalysts are present.Source: §7 · p. 33
  • Exact inter-conversion of stabilizer states is unavoidably lossy even asymptotically; extending these results to inexact qubit conversion remains open.The analogous inexact extension has been achieved for odd-prime qudits [48], but not for qubits.Source: §7 · p. 33
  • Whether more efficient quantum adders and multiply-controlled-Z circuits exist outside probability 1/2 measurements remains open.Source: §7 · p. 33
  • A further open problem is classifying all monotones for non-Clifford states satisfying properties such as additivity, faithfulness, and strong convexity.Source: §7 · p. 33

A Appendices · A.1 Generic circuits for injecting diagonal gates

This appendix gives a generic half-teleportation protocol that applies any diagonal n-qubit unitary U using its resource state |U⟩=U|+⟩^⊗n, with measurement-dependent corrections. It proves correctness and shows that level-k diagonal gates require corrections from at most level k−1 of the Clifford hierarchy.

A.1 Generic circuits for injecting diagonal gates

  • The protocol applies any diagonal n-qubit unitary U to an arbitrary input |α⟩ using one resource state |U⟩.It takes 2n qubits, with |U⟩ on the first n and |α⟩ on the last n.Source: §A.1 · p. 37
  • The appendix makes the previously noted third-level half-teleportation construction explicit and slightly more general, with explicit corrections listed afterward.The construction is presented as an elaboration of the resource-state implementation pointed out in [30].Source: §A.1 · pp. 37–38
  • It applies pairwise CNOT gates, measures the resource qubits, and records outcomes m(1), ..., m(n).The CNOTs run from each resource qubit to the corresponding input qubit before measurement.Source: §A.1 · p. 37
  • For every measurement outcome equal to 1, the protocol applies X corrections followed by UX_kU† corrections on the corresponding input qubit.All X corrections are completed before proceeding to the UX_kU† corrections.Source: §A.1 · p. 37
  • The output leaves the first n qubits in a known computational-basis state and produces U|α⟩ on the remaining n qubits.This establishes the intended action of the injection circuit on the arbitrary input state.Source: §A.1 · p. 37
  • If U lies at level k of the Clifford hierarchy, every correction UX_kU† lies at most at level k−1.This follows directly from the hierarchy definition for conjugation by U.Source: §A.1 · pp. 37–38

A.2 Reducing the cost of unitary synthesis using T gates

The section reduces approximate single-qubit synthesis cost by using larger non-Clifford gate sets and optimized T-gate injection protocols. These methods achieve average- and worst-case reductions relative to Clifford+T synthesis.

A.2 Reducing the cost of unitary synthesis using T gates

  • The conversion protocols reduce each T-gate application to 3 + 1/(4k) T gates on average and 3.5 + 1/(2k) in the worst case.These costs improve on the four-T-gate consumption of the basic injection approach.Source: §A.2 · pp. 39–40
  • A Figure 10 circuit applies T gates for arbitrary-angle single-qubit Z rotations using three T gates on average.The protocol also requires fewer ancillary qubits than the conversion protocols in the comparison.Source: §A.2 · p. 39
  • Clifford+T synthesis uses fewer than 3 log2(1/ε)+O(log(log2(1/ε))) T gates typically and fewer than 4 log2(1/ε)+O(1) in the worst case.Expanding the gate set and applying the described algorithm reaches a break-even point with Clifford+T synthesis.Source: §A.2 · pp. 39–40
  • 20% average and 10% worst-case reductions in T gates are achieved for single-qubit rotation synthesis.The best protocol consumes three T gates per applied gate on average and 3.5 T gates in the worst case.Source: §A.2 · p. 40

A.3 Explicit circuits for some common resource conversions

This section presents explicit circuits establishing upper bounds for several resource-state conversions, including CCZ implementation, bidirectional resource conversions, and measurement-based conversions involving controlled unitaries and C_nS states.

A.3 Explicit circuits for some common resource conversions

  • Together, these constructions supply conversion upper bounds reported in Tables 1 and 2.Source: §A.3 · p. 40
  • Known circuits implement the CCZ gate using four T gates, providing an explicit resource conversion construction.Source: Figure 11 · p. 40
  • The section also gives explicit two-way conversions between resource states, including |CCZ⟩↔|CS⟩ and |CCZ⟩↔|CCZ123,145⟩.These circuits serve as subroutines for some of the paper’s conversion results.Source: Figure 12 · p. 41, Figure 13 · p. 41, Figure 14 · p. 41
  • Measuring the control qubit of |CU⟩ in the Z basis produces |U⟩ with probability 1/2 and |+⟩^n otherwise for diagonal U.This follows because the Z projectors commute with CU, so the measurement selects the |0⟩ or |1⟩ control branch.Source: §A.3 · p. 41
  • Measuring Y on the first qubit of the relevant construction yields |C_nS_m⟩ with probability 1/2 for either eigenvalue m = ±1.The proposition establishes both the uniform measurement probability and the resulting post-measurement state.Source: §A.3 · p. 42

A.4 Extent values

This section tabulates extent values for common resource states used in the paper’s bounds and outlines a procedure for rigorously certifying exact values. Some multi-qubit entries are instead reconstructed from numerical approximations, and equal extent does not imply Clifford equivalence.

A.4 Extent values

  • Exact extent certification compares primal and dual linear programs after reconstructing candidate algebraic expressions from approximate numerical solutions.The procedure confirms the result when the primal minimum and dual maximum agree.Source: §A.4 · p. 42
  • For some multi-qubit states, the authors did not perform rigorous certification and instead reconstructed expressions matching extent estimates to eight digits of precision.These entries therefore rely on numerical precision and expression reconstruction rather than a completed primal–dual proof.Source: §A.4 · p. 42
  • Table 4 lists exact extent expressions for resource states used in the bounds of Tables 1 and 2, with values accurate to eight digits.The table also notes that some states share an extent without being Clifford-equivalent.Source: §A.4 · p. 42, Table 4 · p. 43
  • States can have the same extent without being Clifford-equivalent, with Y-basis measurement on the last qubit producing an additional distinction.The supplied passage introduces this measurement-based distinction without stating its resulting value.Source: §A.4 · p. 43

A.5 Further details on phase polynomial protocols

This section proves phase-polynomial resource-conversion results for third-level diagonal unitaries and develops catalytic examples based on their matrix structure. It also connects the construction to known CS and CCZ catalysis protocols.

A.5 Further details on phase polynomial protocols

  • The phase-polynomial formalism shows that a diagonal third-level unitary’s T-count equals the number of odd-valued coefficients, while even coefficients contribute only Clifford operations.Splitting f into its odd and even parts isolates the non-Clifford unitary; optimizing over equivalent phase polynomials gives the relevant minimum T-count.Source: §A.5 · p. 44
  • Row reduction of the phase-polynomial matrix enables conversion to rank(P) copies of T states, with additional T states accounting for removable columns.If rank(P) exceeds the stabilizer nullity, the resulting protocol is stronger than the theorem’s stated bound.Source: §A.5 · p. 45
  • When every row of the phase-polynomial matrix has even Hamming weight, the associated magic state cannot convert directly to a T state, necessitating catalytic protocols.Such unitaries are products of CS and CCZ gates up to Cliffords and have amplitudes in Q(i), which obstructs the conversion.Source: §A.5 · p. 45
  • The family W_n has τ(W_n)=n+1, stabilizer nullity n, and achieves the strongest catalysis examples when τ(U)=µ(U)+1.W_2 is Clifford-equivalent to CS and reproduces Campbell’s protocol [8], while W_3 is Clifford-equivalent to CCZ and yields the Gidney–Fowler protocol [23].Source: §A.5 · pp. 45–46

A.6 Lower bound reduction from the modular adder to the multiply-controlled Z state

The section reduces production of the n-controlled-Z state to implementing a controlled modular increment, then realizes that increment using the modular adder. Applying the increment to a stabilizer state yields a state Clifford-equivalent to |CnZ⟩.

Reduction overview

  • The reduction proceeds in two steps: construct |CnZ⟩ from CIncn using Clifford operations, then implement CIncn with the modular adder.Thus any implementation of the modular adder supplies a route to producing the n-controlled-Z state from a stabilizer input.Source: §A.6 · p. 46

Producing the multiply-controlled-Z state

  • Applying CIncn to |+⟩^n|0⟩ removes controlled-X gates targeting |+⟩ qubits, leaving an n-controlled-NOT whose output is Clifford-equivalent to |CnZ⟩.The construction first uses CIncn’s action |j⟩|a + j⟩ → |j⟩|a + j mod 2^n⟩ for j = 0, 1 and n-qubit a.Source: §A.6 · p. 46

Reduction to the modular adder

  • The controlled modular increment circuit CIncn can be implemented with the modular adder by using the first input’s last qubit as control and setting its other qubits to |0⟩.This establishes the reduction from modular-adder implementation to controlled modular increment.Source: §A.6 · p. 46

A.7 Canonical form for post-selected stabilizer computations

This section reduces post-selected stabilizer computations to a canonical form involving commuting Pauli measurements and a final Clifford, after removing trivial stabilizer components. It also proves a decoupling lemma showing that ancillary stabilizer qubits can be separated from the nonstabilizer states.

A.7 Canonical form for post-selected stabilizer computations

  • Proposition A.6 factors any state with 2^r stabilizers into r Clifford-mapped |0⟩ qubits and a state with trivial stabilizer.A Clifford conjugates the state’s stabilizer subgroup to the subgroup generated by Z_1, ..., Z_r.Source: §A.7 · pp. 46–47
  • Theorem A.7 represents any post-selected stabilizer computation between nullity-matched states using independent commuting Pauli operators and a Clifford unitary.For n-qubit input and m-qubit output with m ≤ n, the theorem uses k = n − m Pauli operators; the output also includes a stabilizer state and a projector onto their +1 eigenspaces.Source: §A.7 · p. 47
  • When input and output have equal nullity, they are Clifford-equivalent, and enumerating stabilizer circuits requires considering only mutually commuting Pauli measurements.The commuting-measurement structure follows from replacing measurements that anticommute with an input stabilizer by equally likely Clifford corrections.Source: §A.7 · pp. 47–48
  • Lemma A.9 rewrites Clifford gates and post-selected Pauli measurements as a final Clifford followed by a commuting Pauli subgroup compatible with the input stabilizer.Measurements anticommuting with an input stabilizer are converted into Clifford operations, while stabilizer-compatible measurements are retained or removed according to their outcomes.Source: §A.7 · pp. 48–49
  • The proof of Theorem A.7 removes ancillary |0⟩ qubits by replacing the relevant Pauli operators with operators supported only on the remaining input qubits.Lemma A.10 supplies the decoupling step, after which additional stabilizer generators can be included to obtain the required number of measurements.Source: §A.7 · p. 49

A.7.1 Decoupling stabilizer states

  • Lemma A.10 proves that stabilizer ancillas can be decoupled by reducing to trivial-stabilizer states and inductively constraining a Clifford to commute with the ancilla Z operators.The resulting states with appended |0⟩ ancillas are Clifford-equivalent, completing the induction.Source: §A.7.1 · p. 50
  • The decoupling argument uses block decomposition: a unitary commuting with first-qubit Z is controlled on that qubit, and its branch unitary is Clifford because it preserves stabilizer states.Proposition A.11 gives the block form, while Lemma A.13 establishes the stabilizer-preservation criterion for Cliffordness.Source: §A.7.1 · pp. 50–51

A.8 Conversion protocols for dyadic rational powers of T gate √ … A.11 General lower bounds for approximate unitary synthesis

This section develops catalytic conversion protocols and a number-theoretic framework for dyadic rational powers of the T gate, while establishing properties of the dyadic monotone. It then applies these properties to derive lower bounds for approximate single-qubit unitary synthesis, including logarithmic T-state requirements in the approximation precision.

A.8 Conversion protocols for dyadic rational powers of T gate √

  • For odd j and positive k,d, 2^k rotations R(πj/2^d) use |πj/2^d⟩ catalytically, k CCZ gates, and k+1 lower-angle rotations.The protocol has measurement outcomes with probability 50% and recursively yields the family of conversions in Theorem A.16.Source: §A.8 · pp. 51–52
  • Asymptotically, producing |πj/2d⟩ requires 1 − 1/2^(d−1) CCZ states per state, using dyadic resource states as catalysts.Theorem A.16 uses ad,k = 2^(d−1)(k−1)+2 output gates and bd,k = (2^(d−1)−1)(k−1)+d−1 CCZ states.Source: §A.8 · p. 52

A.9 Overview of some definitions and results from Number Theory

  • The appendix extends v2 from rationals to nested cyclotomic fields using multiplicative norm functions Nd, with Nd(x)^2 = Nd+1(x), ensuring v2 is well-defined and additive.The construction uses rational-valued norms and their multiplicativity to preserve consistency across the nested field extensions.Source: §A.9.1 · pp. 53–54

A.9.2 Certain values of v2

  • Under |σk(x)| ≤ 1 for every odd k, v2(x) ≤ 0, with equality only when x = ±1, supporting positivity of the dyadic monotone.This condition is identified as key to showing that the dyadic monotone vanishes exactly for stabilizer states.Source: §A.9.2 · p. 57

A.9.3 Inequality v2(x + y) ≥min(v2(x), v2(y))

  • The number-theoretic development establishes v2(x + y) ≥ min(v2(x), v2(y)) by reducing the general case to divisibility properties of cyclotomic integers.The proof introduces cyclotomic integers and factors involving 1−exp(iπ/2^d) to control the valuation.Source: §A.9.3 · p. 57
  • The valuation v2 is grounded in arithmetic properties of nested cyclotomic number fields and their unique ramified prime of norm 2.The argument uses prime norms and divisibility properties to establish the valuation framework.Source: §A.9.3 · p. 58

A.10 Some properties of dyadic monotone µ2

  • The dyadic monotone µ2 is nonnegative and vanishes exactly on stabilizer states, while post-selecting a Pauli outcome with a dyadic state preserves the non-increasing property.For a nonzero-probability +1 outcome, if the post-selected state remains in the relevant ring up to global phase, then µ2 does not increase.Source: §A.10 · p. 59
  • Post-selecting on two commuting Pauli measurements can increase µ2, with the supplied example changing its value from 3 to 4.Thus, the monotonicity result does not extend generally to multiple post-selected commuting measurements.Source: §A.10 · p. 60

A.11 General lower bounds for approximate unitary synthesis

  • µ2|Ψ⟩ + ν|Ψ⟩ ≥ 1/2^(d−1) log2(1/ε) − 1/2^(d−2) for trace-distance approximation of a qubit state under the stated ε and amplitude conditions.The bound applies to states with entries in R_d and stabilizer-operation protocols with post-selection.Source: §A.11 · p. 61
  • For approximation using NT copies of |T⟩, the cited result gives 7NT ≥ 1/7 log2(1/ε) − 1/14, establishing a logarithmic lower bound in approximation precision.Source: §A.11 · p. 62

Related papers

Loading 1904.01124v2…