PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantifying magic for multi-qubit operations

James R. Seddon, Earl T. Campbell

arXiv:1901.03322v2quant-ph

TL;DR

Classical simulation of near-Clifford circuits and magic-state-based fault-tolerant computation motivate quantifying the non-stabiliserness of general quantum operations. The paper introduces channel robustness and magic capacity for general n-qubit channels, with all stabiliser-preserving CPTP maps free. It characterises complete stabiliser preservation and connects the measures to Monte Carlo simulation, where capacity can reduce sample complexity in some cases.

  • Problem

    Existing qubit approaches do not cleanly retain all multi-qubit stabiliser channels as free operations, limiting a general theory of channel non-stabiliserness.

    Source: §1 · p. 2

  • Method

    The paper defines channel robustness and magic capacity for general n-qubit channels, taking stabiliser-preserving CPTP maps as free operations.

    Source: §3 · pp. 4–6

  • Results

    Complete stabiliser preservation can be tested with an n-qubit ancilla and characterised by a stabiliser Choi state; capacity can require fewer samples than channel robustness when C(E) ≪ R*(E).

    Source: §3 · pp. 5, 7

  • Takeaways & Limitations

    The two monotones provide sample-complexity measures for Monte Carlo simulation of channels, including channels that preserve stabiliser states.

    Source: §3 · pp. 4, 7

    The robustness of the Choi state lacks submultiplicativity under composition because its decomposition can involve maps that are not trace-preserving.

    Source: §3 · p. 6

Abstract

from arXiv · show

The development of a framework for quantifying "non-stabiliserness" of quantum operations is motivated by the magic state model of fault-tolerant quantum computation, and by the need to estimate classical simulation cost for noisy intermediate-scale quantum (NISQ) devices. The robustness of magic was recently proposed as a well-behaved magic monotone for multi-qubit states and quantifies the simulation overhead of circuits composed of Clifford+T gates, or circuits using other gates from the Clifford hierarchy. Here we present a general theory of the "non-stabiliserness" of quantum operations rather than states, which are useful for classical simulation of more general circuits. We introduce two magic monotones, called channel robustness and magic capacity, which are well-defined for general n-qubit channels and treat all stabiliser-preserving CPTP maps as free operations. We present two complementary Monte Carlo-type classical simulation algorithms with sample complexity given by these quantities and provide examples of channels where the complexity of our algorithms is exponentially better than previous known simulators. We present additional techniques that ease the difficulty of calculating our monotones for special classes of channels.

1. INTRODUCTION

The paper extends magic-resource quantification from states to general quantum operations, motivated by classical simulation of near-Clifford circuits and magic-state-based fault-tolerant computation. It introduces channel robustness and magic capacity, treating all stabiliser-preserving CPTP maps as free and linking the measures to classical simulation algorithms.

1. INTRODUCTION

  • Near-Clifford circuits matter for NISQ benchmarking and verification, while magic-state distillation supports non-Clifford gates in fault-tolerant circuits.For qubits, discrete phase-space methods cannot cleanly retain all multi-qubit stabiliser channels as free operations, motivating alternative measures.Source: §1 · pp. 1–2

3. OVERVIEW OF MAIN RESULTS

  • Theorem 3.1 shows that complete stabiliser preservation can be tested with an n-qubit ancilla, and characterises it through the channel’s Choi state.The Choi state must itself be a stabiliser state.Source: §3 · p. 5
  • The channel robustness R* is faithful and submultiplicative under composition, and it does not increase when composed with stabiliser channels.Its decomposition uses completely stabiliser-preserving CPTP maps as free operations.Source: §3 · p. 5
  • The capacity C measures a channel’s maximum possible increase in robustness and is faithful, submultiplicative, and an upper bound on that increase.Its definition includes an identity channel, since the maximum increase may occur when the channel acts on part of a larger state.Source: §3 · p. 6
  • For every CPTP channel, the robustness of its Choi state is bounded above by C, which is bounded above by R*; the bounds coincide for third-level Clifford-hierarchy unitaries.The Choi-state robustness alone lacks submultiplicativity under composition because its decompositions can contain non-trace-preserving maps.Source: §3 · p. 6
  • Both channel measures give sample-complexity bounds for Monte Carlo simulation, and capacity can reduce the required samples when C(E) is much smaller than R*(E).The capacity-based algorithm solves a convex optimisation at each step, increasing runtime per sample.Source: §3 · pp. 5, 7

4. COMPLETELY STABILISER-PRESERVING OPERATIONS

The paper characterizes completely stabiliser-preserving channels and shows that testing preservation with an ancilla of the channel’s input size suffices. The robustness of the Choi state provides an equivalent test, though it is not itself a reliable monotone.

4. COMPLETELY STABILISER-PRESERVING OPERATIONS

  • Preserving stabiliser states without an ancilla is insufficient: ET maps single-qubit inputs to mixtures of |0⟩ and |1⟩, yet acting on a Bell pair can yield a recoverable magic state.A Z-measurement and conditional rotation recover a pure magic state using stabiliser operations.Source: §4 · p. 7
  • A channel is completely stabiliser-preserving exactly when it preserves stabiliser states after tensoring with an identity of the same dimension as the channel.The result also shows that checking larger ancillas is unnecessary.Source: §4 · pp. 7–8
  • The Choi-state robustness equals 1 for channels in SPn,n and is greater than 1 otherwise, giving a membership test for complete stabiliser preservation.The proof uses witnesses to establish the converse direction.Source: §4 · pp. 8–9
  • Although faithful, Choi-state robustness fails submultiplicativity under composition, so the paper uses it as a tool rather than as a reliable monotone.Its faithfulness supports the alternative channel-robustness definition.Source: §4 · p. 9

5. CHANNEL ROBUSTNESS

Channel robustness quantifies a channel’s non-stabiliserness through decompositions into completely stabiliser-preserving channels. It is faithful and obeys composition and tensor-product bounds, with a reduced optimization for diagonal channels.

5. CHANNEL ROBUSTNESS

  • Channel robustness is the minimum 2p + 1 over decompositions E = (1 + p)Λ+ − pΛ−, where Λ± are completely stabiliser-preserving channels and p ≥ 0.The definition extends the Bennink et al. approach by using SPn,n instead of CPR.Source: §5 · p. 9
  • For diagonal channels, the optimization reduces to decomposing E(|+⟩⟨+|⊗n) into stabiliser states with equal diagonal elements.This turns the general Choi-state problem into an n-qubit problem.Source: §5 · p. 10
  • Channel robustness is convex and faithful, and composition satisfies R∗(E2 ◦ E1) ≤ R∗(E1)R∗(E2).It is also submultiplicative under tensor products.Source: §5 · p. 10
  • The channel robustness is unchanged by tensoring with an identity: R∗(E) = R∗(E ⊗ 1).The proof establishes the reverse inequality in addition to submultiplicativity.Source: §5 · p. 11

6. MAGIC CAPACITY

Magic capacity measures the maximum robustness obtainable when a channel acts on a stabiliser input with an ancilla. It captures possible robustness increases for other inputs and obeys composition and tensor-product bounds.

6. MAGIC CAPACITY

  • Magic capacity can be optimized over pure stabiliser inputs while still capturing the possible increase in robustness for mixed or non-stabiliser inputs.The paper establishes this maximum-increase property using convexity of robustness.Source: A. Properties · pp. 11–12
  • Capacity is submultiplicative under composition: C(E1 ◦ E2) ≤ C(E1)C(E2).The proof bounds the robustness after the second channel using its capacity.Source: A. Properties · p. 12
  • Capacity is also submultiplicative under tensor products.The paper derives this from composition submultiplicativity and the ancilla in the capacity definition.Source: A. Properties · p. 12

B. Sandwich theorem

The sandwich theorem bounds channel capacity between Choi-state robustness and channel robustness, with all three equal for unitary operations in the third Clifford-hierarchy level. The section connects these quantities to static Monte Carlo simulation and shows how optimizing over all completely stabiliser-preserving maps can reduce sampling cost relative to CPR.

B. Sandwich theorem

  • For any CPTP channel E, R(Φ_E) ≤ C(E) ≤ R*(E), and for third-level unitary U, R(Φ_U) = C(U) = R*(U).For diagonal third-level gates, the equality also holds for decompositions of U(|+⟩⟨+|^n).Source: B. Sandwich theorem · pp. 12, 14

A. Static Monte Carlo

  • Static Monte Carlo optimizes over SP_m,m rather than CPR, representing completely stabiliser-preserving maps non-negatively and estimating Pauli expectations with an unbiased trajectory estimator.Its sample complexity depends on the product of the circuit elements’ channel robustness values squared; the intermediate sampling does not increase variance.Source: A. Static Monte Carlo · pp. 15, 17
  • Because CPR is a subset of the completely stabiliser-preserving maps, R*(E) ≤ R_CPR(E), and the static simulator’s sample complexity is never greater under these measures.If M elements each have R*(E_j)/R_CPR(E_j) ≤ k for a constant 0 < k < 1, the sample-complexity reduction factor is k^(2M); amplitude-damping noise is identified as a natural example.Source: A. Static Monte Carlo · pp. 17–18
  • For Λ_H, R*(Λ_H) = 1 while R_CPR(Λ_H) = 2, so M uses require 1 rather than 4^M samples under the respective simulators.Λ_H is a Z-measurement followed by a Hadamard conditioned on the −1 outcome; it is completely stabiliser-preserving.Source: A. Static Monte Carlo · p. 17
  • Diagonal-channel optimization makes monotone calculation tractable for operations on up to five qubits, enabling grouped decompositions when R(E^⊗n) < R(E)^n.The paper notes this strategy is useful for single-qubit Z-rotations.Source: A. Static Monte Carlo · p. 18

B. Dynamic Monte Carlo

The dynamic simulator uses magic capacity to set its sampling cost, adapting its quasiprobability decomposition to the state at each circuit step. This can reduce sample requirements when capacity is below channel robustness, at the cost of more computation per sample.

B. Dynamic Monte Carlo

  • When C(E) < R*(E), the dynamic simulator can use the lower output-state robustness to reduce sample complexity relative to the static simulator.For each step, it decomposes the channel output on the current stabiliser state and samples the next stabiliser state according to the absolute quasiprobability weights.Source: B. Dynamic Monte Carlo · p. 18
  • The dynamic estimator is unbiased, with sample complexity bounded by the product of the circuit elements’ magic capacities squared.It does not explicitly calculate the full trajectory distribution; the sample output is bounded by the product of per-step capacities.Source: B. Dynamic Monte Carlo · p. 19
  • Each sample requires L convex optimizations and L polynomial-runtime state-processing steps, trading higher per-sample cost for potentially exponential sample savings.When C(E) = R*(E), the paper recommends using the static method instead.Source: B. Dynamic Monte Carlo · p. 19

8. NUMERICAL RESULTS

The numerical results were produced using code and data files available from the paper’s public repository.

8. NUMERICAL RESULTS

  • The numerical results were produced with code and data files available from the public repository cited as Ref..Source: §8 · p. 20

A. Single-qubit rotation with amplitude damping

The paper compares magic measures and simulation costs for noisy single-qubit rotations and multiqubit diagonal gates. It finds that gate ordering, gate family, and grouping affect the relationships among the measures and the resulting simulation costs.

A. Single-qubit rotation with amplitude damping

  • For noisy X-rotations with amplitude damping, placing noise before the unitary lowers both C and R∗ but raises RCPR, favoring that ordering for the studied sample-complexity measures.With noise after the unitary at p=0.1, the three quantities show no difference; C(E) and R∗(E) agree up to solver precision for this operation class.Source: A. Single-qubit rotation with… · p. 20, Figure 3 · p. 21

B. Multiqubit phase gates

  • For multicontrol-Z gates (t=0), all three quantities agree through n=4, separate at n=5, and increase with each added qubit.More generally, the inequalities are tight for n=2 and n=3 but not for larger systems.Source: B. Multiqubit phase gates · pp. 21–22, Figure 4 · p. 22
  • For random diagonal gates, Choi robustness matched channel robustness for every tested 2-qubit gate but was typically lower at 3 and 4 qubits.Choi robustness equaled magic capacity for every random instance observed.Source: Figure 5 · p. 22, B. Multiqubit phase gates · p. 23
  • For nonzero t, capacity levels off as qubit count grows; the authors conjecture that it remains level for all n beyond a finite K.Their numerical investigation was limited to five-qubit gates.Source: B. Multiqubit phase gates · p. 22
  • Grouping Z-rotations yields strict submultiplicativity at every θ, with significant normalized-robustness reductions from n=2 to n=4 across many angles.The plotted quantities cover up to four qubits.Source: Figure 6 · p. 23, B. Multiqubit phase gates · p. 23

9. CONCLUSION

  • The channel-robustness static simulator can have exponentially lower sample complexity than Bennink et al. [3] for some channels, including amplitude-damped single-qubit rotation sequences.Submultiplicativity under tensor products and composition also lets the static simulator exploit circuit grouping.Source: §9 · pp. 23–24
  • For some multiqubit entangling gates, a capacity-based simulator can further reduce sample complexity, but on-the-fly convex optimization makes each sample harder to obtain.The capacity is strictly below channel robustness for some such gates.Source: §9 · p. 24

Appendix A: Properties of robustness of the Choi state

The appendix establishes convexity and tensor-product submultiplicativity for Choi-state robustness, but gives a counterexample to submultiplicativity under channel composition. It also proves faithfulness and identity-extension invariance for channel robustness.

Appendix A: Properties of robustness of the Choi state

  • Choi-state robustness is convex in the channel and submultiplicative under tensor products.The tensor-product result follows from factoring the maximally entangled state and applying state robustness submultiplicativity.Source: Appendix A · p. 26
  • Choi-state robustness is not submultiplicative under composition: the example has R(ΦE2◦E1) ≈1.414, exceeding R(ΦE2)R(ΦE1).The appendix attributes such counterexamples to cases where the input maximizing output robustness is not maximally entangled.Source: Appendix A · p. 26

Appendix B: Properties of channel robustness

  • Channel robustness is faithful: it equals 1 for stabiliser-preserving channels and is greater than 1 otherwise.The proof uses the Choi state's robustness as a lower bound on channel robustness.Source: Appendix B · p. 27
  • Channel robustness is unchanged when the channel is tensored with an identity map.The proof traces out the identity-system registers to construct a valid stabiliser decomposition.Source: Appendix B · p. 28

Appendix C: Optimisation problem for channel robustness

The appendix formulates channel robustness as a linear program over stabiliser-state decompositions. It enforces trace preservation through linear constraints on Pauli-vector components and implements the resulting program in MATLAB with CVX.

Appendix C: Optimisation problem for channel robustness

  • The channel-robustness program uses nonnegative variables for the positive and negative parts of stabiliser-state quasiprobabilities.It retains the stabiliser-state matrix while modifying constraints to require trace-preserving component channels.Source: Appendix C · pp. 28–29
  • Trace preservation is imposed by setting nontrivial reduced Pauli expectations ⟨1 ⊗Pj⟩ to zero, yielding the linear constraint MA+⃗p = 0.For an n-qubit output subsystem, the matrix M selects 4^n − 1 such expectations.Source: Appendix C · pp. 29–31
  • The resulting linear program was implemented in MATLAB using CVX, with code made available in the cited repository.The construction of M must match the chosen ordering of Pauli operators.Source: Appendix C · p. 31

Appendix D: Properties of magic capacity

Magic capacity equals one for stabiliser-preserving channels and exceeds one for any non-stabiliser-preserving CPTP channel. For diagonal channels, the section reduces the calculation burden and establishes conditions for valid trace-preserving decompositions.

Appendix D: Properties of magic capacity

  • C(Λ)=1 for every stabiliser-preserving CPTP channel, whereas C(E)>1 for any non-stabiliser-preserving CPTP channel E.The latter follows because some stabiliser input is mapped to a normalised non-stabiliser state.Source: Appendix D · p. 31

1. Reducing the problem size

  • For diagonal channels, channel robustness and magic capacity are tractable up to five qubits, reducing the general calculation burden.The direct optimisation is impractical above two-qubit channels because it generally ranges over 2n-qubit stabiliser states; diagonal channels permit a reduction using commuting Cliffords.Source: §1 · pp. 31–32

2. Trace condition for diagonal channels

  • For any diagonal channel, an optimal decomposition can satisfy the trace condition and use Choi states of diagonal channels.The construction maps a decomposition of the full Choi state to one whose terms are Choi states for diagonal channels, without changing its ℓ1-norm.Source: §2 · p. 33
  • A stabiliser-preserving parity-measurement-and-correction channel leaves diagonal-channel Choi states invariant while bringing general Choi states into the required trace-condition form.For each paired qubit, measure Z⊗Z and apply X to the first qubit on an odd-parity outcome.Source: §2 · p. 33

3. Magic capacity in the affine space picture

The affine-space formalism yields a reduction for calculating the magic capacity of diagonal channels. It replaces optimisation over all 2n-qubit stabiliser inputs with a restricted set of n-qubit representatives.

3. Magic capacity in the affine space picture

  • For diagonal E_D, magic capacity can be calculated by optimising over the n-qubit representative states |K⟩ rather than all 2n-qubit stabiliser states.Equivalent stabiliser inputs with the same affine space K give the same final robustness.Source: §3 · pp. 34–35
  • The affine-space formalism labels computational basis states by binary vectors and represents stabiliser states using affine spaces and quadratic forms over binary vectors.An affine space is specified by a shift vector and generators for its associated linear subspace.Source: §3 · p. 34
  • For diagonal channels, Clifford transformations commuting with the channel establish equivalent inputs and reduce 2n-qubit stabiliser states to representatives that preserve the robustness calculation.The proof uses diagonal Cliffords to relate phase and shift parameters, and CNOTs targeted on the last n qubits to factor off a stabiliser state.Source: §3 · pp. 35–37

B. But G′

For diagonal ED, the capacity maximization can be reduced to representative affine-space states. This reduction makes cases up to five qubits tractable.

B. But G′

  • When A has full column rank m, a left-inverse G′−1 exists.Source: B. But G′ · p. 37
  • The construction puts G′ = CGS in form (A31), yielding UC |K⟩ = |K′.Source: B. But G′ · p. 37
  • For a two-qubit channel, the reduction cuts the check from 36,720 four-qubit stabiliser states to one state for each of 7 non-trivial affine spaces.The passage reports that cases up to five qubits become tractable using this method.Source: B. But G′ · p. 37
  • Table III compares counts of stabiliser states and affine spaces; trivial affine spaces are singletons corresponding to computational basis states, on which diagonal CPTP channels act as identity.Source: Table III · p. 37, B. But G′ · p. 37

4. Dimension of affine space

The dimension of an input affine space bounds the robustness achievable after a diagonal unitary, enabling further reductions for multi-control phase gates. For multi-control-T gates, robustness is constant across n at fixed input dimension, but the five-qubit calculation limit leaves its behavior at larger dimensions unresolved.

4. Dimension of affine space

  • R(U|K⟩) is bounded by the maximum robustness achievable for a k-qubit state when K has dimension k.The output is Clifford-equivalent to a k-qubit state acted on by a diagonal unitary, tensored with a stabiliser state.Source: §4 · p. 38
  • For M_t,n, only n robustness calculations are needed: one representative linear subspace for each possible dimension.If the affine space excludes the zero vector, the gate acts as identity; otherwise it is a linear subspace, and equal-dimensional subspaces are equivalent for this calculation.Source: §4 · p. 39
  • For multicontrol-T gates, robustness at fixed k is constant with n when k≤n; the reported values rise through k=4 and then drop at k=5.The authors relate the drop to the limitation of their techniques to five-qubit operations and explain that the altered phase on the all-zero term becomes small as k grows.Source: §4 · p. 40, Table IV · p. 40
  • The five-qubit calculation limit prevents confirming whether robustness continues to decrease as the input-space dimension increases.Source: §4 · p. 40
Loading 1901.03322v2…