Approximate Randomized Benchmarking for Finite Groups

• The work concerns randomized benchmarking, quantum gates, Clifford gates, monomial unitaries, random walks on groups, and fidelity estimation.Source: D S Fran¸ca and A K Hashagen · p. 1

• Randomized benchmarking estimates average gate fidelity while avoiding the exponential measurement cost of complete noise tomography.Source: §1 · p. 2
• The protocol applies to finite-group representations that need not be irreducible or form a 2-design, using channel covariance and spectral structure.Source: §1 · p. 2
• Approximate Haar-distributed gate sequences can replace exact samples, enabling potentially more efficient Markov chain Monte Carlo sampling and stability against small sampling errors.Source: §1 · pp. 2–3
• The study restricts its formal development to finite groups although most results can be extended to compact groups.Source: §1 · p. 2
• A generator-based protocol uses group generators plus one additional random element, but assumes approximately covariant, gate-independent noise.Source: §1 · pp. 2–3
• The monomial-unitary application includes T gates, requires estimating two parameters, supports O(d) multiplication and inversion, and reliably estimates average gate fidelity numerically.Source: §1 · p. 3

2. Notation and Preliminaries

• Quantum channels are trace-preserving completely positive maps, and the paper uses POVMs, Choi-Jamiolkowski channel-state duality, trace distance, and channel expectations.Source: §2 · p. 4
• Finite-group unitary representations decompose into irreducible representations with multiplicities, whose commutant structure organizes covariant-channel analysis.Source: §2 · pp. 4–5

2.1. Covariant Quantum Channels and Twirls

• A channel is covariant when it respects the group representation, equivalently commuting with the adjoint representation or with the corresponding Choi representation.Source: §2.1 · pp. 5–6
• Covariant channels admit decompositions controlled by irreducible components and multiplicities, while irreducibly covariant channels have a simpler structure with channel eigenvalues exposed.Source: §2.1 · p. 6
• The twirl of a channel is covariant with respect to the chosen group representation.Source: §2.1 · pp. 6–7

2.2. Random Walks on Groups

• A random walk generated by an inversion-closed generating set converges to the group’s Haar distribution, providing approximate samples after sufficient steps.Source: §2.2 · p. 7
• Mixing time measures convergence in total variation, and the paper notes that it commonly scales logarithmically with inverse accuracy and group size.Source: §2.2 · p. 8

• Average fidelity can be determined from entanglement fidelity, which equals d^-2 times the trace of the channel as a linear operator.Source: §3 · pp. 8–9
• The randomized-benchmarking protocol fits experimental decay data to estimate eigenvalues and then uses their multiplicities to recover the trace and average fidelity.Source: §3 · p. 9
• Covariance imposes spectral structure and degeneracy, so when few irreducible components occur only a few spectral values are needed to estimate the trace.Source: §3 · p. 10
• For suitable powers of a covariant channel, measurement probabilities become sums of exponential terms determined by distinct channel eigenvalues.Source: §3 · pp. 10–11
• Twirling preserves entanglement fidelity and therefore average fidelity, allowing estimation through the more structured twirled channel.Source: §3 · p. 11

4. Randomized benchmarking protocol

• The protocol samples m independent Haar-distributed gates, appends an inverse-completing gate, measures sequence fidelity, and averages over repeated sequences for different m.The implemented gates are noisy channels of the form U_g ◦ T, while preparation and measurement errors are included in the initial state and POVM effect.Source: §4 · pp. 11–12

4.1. Analysis of the Protocol

• The sequence analysis follows from independently Haar-distributed transformed gates and structural results for covariant quantum channels.The first error channel is absorbed into state-preparation-and-measurement error, after which the averaged sequence is expressed through powers of the twirled channel.Source: §4.1 · pp. 12–13
• Fitting the measured decay curve estimates eigenvalues of the twirled noise channel, whose known irreducible multiplicities determine the channel trace and average fidelity.Theorem 13 and Corollary 14 establish the general-group decay structure, with coefficients and eigenvalues determined by the representation and channel.Source: §4.1 · pp. 12–13
• When fitted eigenvalues cannot be assigned to irreducible representations, pairing them with irreducible dimensions yields minimum and maximum fidelity estimates.These bounds correspond to the most pessimistic and optimistic pairings, respectively, but the ambiguity creates numerical difficulties.Source: §4.1 · pp. 13–14

5. Approximate Twirls

• Approximate Haar samples can replace exact Haar samples in randomized benchmarking while preserving measurement statistics up to a controlled error.The samples are independent and drawn from probability measures ν_k that approximate the Haar measure.Source: §5 · pp. 14, 16
• The approximate twirl to the power m is defined for a probability measure on G^m and reduces to the regular twirl when the measure is the m-fold Haar distribution.The paper uses this construction to compare approximate and exact channel twirls for arbitrary finite groups.Source: §5 · p. 14
• The approximate-twirl error is bounded by the total-variation distance between the sampling distribution and the m-fold Haar measure in norms contractive under quantum channels.The result applies to the 1→1 norm and the diamond norm, and is designed to remain well behaved when channel twirls are raised to powers.Source: §5 · pp. 14–15
• Theorem 17 derives a bound on the discrepancy between approximate and exact sequence distributions from per-round sampling errors, with the proof using relative entropy and Pinsker-type inequalities.The same result extends to any norm that contracts under quantum channels, including the diamond norm.Source: §5 · p. 15
• For random-walk sampling, the total runtime is efficient when the chain mixes rapidly and the sequence length is at most on the order of the dimension.The required chain length is tied to the mixing time and the desired closeness δ of the measurement statistics.Source: §5 · p. 16

• Generator-based RB implements gates from an inversion-closed generating set plus one arbitrary group element, rather than arbitrary group gates.This addresses the practical need to decompose gates into generators while requiring approximately covariant noise.Source: §6 · pp. 16–17
• Random walks generated by A approach Haar sampling after a mixing time, although successive intermediate group elements are generally dependent.Elements separated by roughly the mixing time have joint distributions close to Haar.Source: §6 · p. 17
• The protocol samples b+m+1 gates, measures sequence fidelity, averages over M realizations, and varies m to estimate average survival probabilities.The initial b generator applications serve as an initialization before fitting the decay curve.Source: §6 · pp. 17–18
• The procedure reproduces Haar-sampled statistics up to O(δ^2), provided the covariance and mixing errors remain sufficiently small.Reliability requires δ^2bm ≪1; for rapidly mixing groups of polynomial size in dimension, b scales polylogarithmically with system size and sequence parameters.Source: §6 · p. 18
• Under δ-covariant noise and b=t_1(m−1ϵ) with m≥b, the generator protocol satisfies the theorem’s randomized-benchmarking guarantee.The associated corollary applies the result to arbitrary POVM elements and initial states.Source: §6 · p. 18

7. Numerics and Examples

• The numerical section leaves open how to fit multi-parameter decay curves and choose protocol sizes or derive confidence intervals for the estimates.Appendices A and B discuss proposed fitting approaches and preliminary statistical results.Source: §7 · p. 19

7.1. Monomial Unitary Matrices

• MU(d, 8) supports two-parameter randomized benchmarking, with multiplication, inversion, and sampling scaling linearly in dimension d.The resulting classical RB cost is O(Mmd), which is less favorable than Clifford scaling in qubits but remains applicable at high dimensions.Source: §7.1 · p. 20
• For MU(d, 8), simulations with depolarizing and unitary noise report small estimation errors across tested dimensions and sequence counts.The depolarizing-noise study uses p = 0.9 and m = 40, while the unitary-noise study uses 10 qubits, 1000 sequences, and m = 20.Source: Table 1 · p. 21, Table 2 · p. 21, §7.1 · p. 21

7.2. Clifford Group

• The Clifford generator random walk lacks a rigorous mixing-time estimate; its rapid mixing with tmix = O(n^2 log(n)) remains conjectural.The conjectured scaling would improve on an algorithm requiring O(n^3) operations, but the paper provides no rigorous bound.Source: §7.2 · p. 22
• Clifford protocols estimate average fidelity effectively for high-fidelity channels under less restrictive gate assumptions, but become unreliable when fidelity is low.The numerical results indicate that lower-Kraus-rank channels may remain reliable at lower fidelities than higher-Kraus-rank channels.Source: §7.2 · p. 23, Table 3 · p. 23, Table 4 · p. 23
• Approximate and exact Haar samples produce virtually indistinguishable estimates, while generator randomized benchmarking has similar performance for p close to 1.The comparison uses average and mean error versus p for the Clifford group under the random quantum-channel noise model.Source: §7.2 · pp. 23, 25, Figure 1 · p. 24

8. Conclusion and Open Problems

• The protocol estimates average gate fidelity for arbitrary finite-group unitary representations and can use approximate Haar samples or generators plus one additional gate under suitable noise assumptions.These extensions may make randomized benchmarking more practical when full group descriptions or implementations are unavailable.Source: §8 · p. 25
• The assumption of gate-independent noise is only a 0-order approximation, so extending the results to noise that depends weakly on the gate remains desirable.The paper also identifies interleaved benchmarking, variance estimation, and confidence intervals as open problems.Source: §8 · pp. 25–26

A. Numerical Considerations

• Numerical fitting becomes difficult when randomized benchmarking data contain several exponential parameters, motivating improved fitting schemes and confidence intervals.The paper points to appendix A for numerical proposals and notes that statistical questions remain open.Source: §8 · p. 25, A. Numerical Considerations · p. 27

A.1. Fitting the Data to Several Parameters

• Fitting noisy data to exponential curves is numerically unstable for large numbers of parameters, with reliability depending on initialization and spectral separation.Closely spaced eigenvalues or absent eigenspace support can prevent some parameters from being estimated.Source: §A.1 · p. 27
• The representation determines the maximum model size, 2n + 1, while stable algorithms are available for n = 2 and for moderate parameter counts.The authors note that good initial decay-rate estimates can improve practical fitting.Source: §A.1 · p. 27
• Unknown correspondence between fitted parameters and irreducible representations can widen fidelity bounds, motivating examples with few parameters and similarly sized irreducible components.This avoids numerical instability and overly broad optimistic–pessimistic fidelity intervals.Source: §A.1 · pp. 27–28
• Better multi-parameter fitting is needed to obtain useful confidence intervals, with Bayesian approaches suggested as a possible direction.The appendix also describes parameter isolation as a way to address the fitting problem.Source: §A.1 · p. 28, §A.2 · p. 28

A.2. Isolating the parameters

• For a simply covariant irreducible representation, suitable initial states can isolate individual channel eigenvalues and thereby estimate each irreducible component separately.For monomial unitary matrices, off-diagonal states isolate one parameter while non-maximally mixed diagonal states isolate another.Source: §A.2 · pp. 28–29

B. Statistical Considerations

• Deriving useful confidence intervals for arbitrary finite groups remains open because suitable choices of sequence count M and sequence length m depend on the fitting algorithm and group.The Clifford case can use existing results, but the general case lacks an equally clear prescription.Source: B. Statistical Considerations · p. 29
• Hoeffding’s inequality bounds the deviation between the empirical average fidelity from M sequences and its expected value.The argument uses only that each observed survival-probability variable lies in [0, 1].Source: B. Statistical Considerations · p. 29
• 6 × 10^8 sequences are needed to be 10^-4 from the expectation with probability 0.95 under the general bound, making it infeasible for applications.The bound is deliberately group-independent and therefore not expected to perform well in specific settings.Source: B. Statistical Considerations · p. 29

C. Proof of Theorem 17

• Relative-entropy bounds and Pinsker-type estimates control the distance between the approximate and Haar-induced sequence distributions.The proof combines these estimates with the theorem’s per-step sampling conditions.Source: C. Proof of Theorem 17 · p. 30
• The 1 →1 norm contracts under quantum channels, while the sampled U_g elements are independent.Source: C. Proof of Theorem 17 · p. 30
• The proof rewrites the distribution of cumulative products in terms of the independently sampled measures ν_k and compares it with the Haar-product distribution.The map σ rearranges group tuples, while Haar invariance preserves the relevant reference distribution.Source: C. Proof of Theorem 17 · p. 30

D. Proof of Theorem 20

• Theorem 20 assumes δ-covariant noise, an inversion-closed generating set, and a protocol length chosen from the chain-mixing time.The proof uses b = t1(m−1ϵ) with m ≥ b and controls errors through the stochastic matrix generated by the gate set.Source: D. Proof of Theorem 20 · pp. 31–32
• The channel comparison separates a covariant component from a noise component, with the covariant part supplying the zeroth-order contribution and higher-order terms controlled by δ.The argument compares first- and second-order terms and uses the distribution bound ∥ν_j − µ∥_1 ≤ ϵ m.Source: D. Proof of Theorem 20 · pp. 31–32
• The proof bounds the deviation between the relevant gate distributions and Haar measure using total variation distance after sufficiently many Markov-chain steps.For shorter intervals, it applies a trivial estimate; combining both cases yields the theorem’s claim.Source: D. Proof of Theorem 20 · p. 32

E. Proof of Lemma 24

• For monomial-unitary covariance, the proof translates channel covariance into commutation of the Choi state with U ⊗ Ū for every monomial unitary U.Restricting to diagonal unitaries constrains matrix elements, while the n > 2 condition excludes additional off-diagonal possibilities.Source: E. Proof of Lemma 24 · pp. 33–34
• Permutation invariance reduces the channel’s coefficients to one independent off-diagonal parameter for each of A and B, plus a diagonal-sector parameter.The resulting terms are projections with ranks 1, d^2 − d, and d − 1; the diagonal-sector term is a difference of projections.Source: E. Proof of Lemma 24 · pp. 33–34