Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Randomized Benchmarking

Robust average gate fidelities from random sequences.

Randomized benchmarking is the most widely reported number in experimental quantum computing, and one of the most misunderstood. Under clean assumptions it provably measures an average gate fidelity, immune to state-preparation and measurement errors. This lesson proves that theorem, then examines what happens when its assumptions fail.

What you’ll learn

  • State and prove the Magesan–Gambetta–Emerson decay theorem F(m)=A pm+BF(m) = A\,p^m+B for gate-independent noise.
  • Prove the twirling lemma for unitary 2-designs and derive r=(d−1)(1−p)/dr = (d-1)(1-p)/d.
  • Explain gate-dependent noise, the gauge problem and leakage, and quantify the gap between average and worst-case error for coherent errors.
  • Compare interleaved, simultaneous, character, direct, mirror and cycle benchmarking, and layer fidelity.

The protocol and the decay theorem

Fix a gate set G\mathsf G that forms a group, here the nn-qubit Clifford group Cn\mathcal C_n (modulo phases), and write G(ρ)=GρG†\mathcal G(\rho) = G\rho G^\dagger for the ideal channel of GG. Each implemented gate is noisy, G~=ΛG∘G\tilde{\mathcal G} = \Lambda_G\circ\mathcal G. A length-mm sequence draws G1,…,GmG_1,\ldots,G_m independently and uniformly, and appends Gm+1=(Gm⋯G1)−1G_{m+1} = (G_m\cdots G_1)^{-1}.

DerivationProof: telescoping the sequence
  1. Sm=Λ∘Gm+1∘Λ∘Gm∘⋯∘Λ∘G1\mathcal S_m = \Lambda\circ\mathcal G_{m+1}\circ\Lambda\circ\mathcal G_m\circ\cdots\circ\Lambda\circ\mathcal G_1

    The implemented sequence of m+1m+1 noisy gates.

  2. Dj:=Gj∘⋯∘G1,Gj=Dj∘Dj−1†,Gm+1=Dm†\mathcal D_j := \mathcal G_j\circ\cdots\circ\mathcal G_1,\qquad\mathcal G_j = \mathcal D_j\circ\mathcal D_{j-1}^\dagger,\qquad\mathcal G_{m+1} = \mathcal D_m^\dagger

    Introduce cumulative products, with D0=I\mathcal D_0 = \mathcal I. Because the map (G1,…,Gm)↦(D1,…,Dm)(G_1,\ldots,G_m)\mapsto(D_1,\ldots,D_m) is a bijection of Gm\mathsf G^m, the DjD_j are also independent and uniformly distributed.

  3. Sm=Λ∘(Dm†∘Λ∘Dm)∘(Dm−1†∘Λ∘Dm−1)∘⋯∘(D1†∘Λ∘D1)\mathcal S_m = \Lambda\circ\big(\mathcal D_m^\dagger\circ\Lambda\circ\mathcal D_m\big)\circ\big(\mathcal D_{m-1}^\dagger\circ\Lambda\circ\mathcal D_{m-1}\big)\circ\cdots\circ\big(\mathcal D_1^\dagger\circ\Lambda\circ\mathcal D_1\big)

    Substitute and regroup: every noise map is now sandwiched by its own independent, uniformly random Clifford.

  4. E Sm=Λ∘(ΛC)m,ΛC(ρ)=p ρ+(1−p)Tr⁡(ρ)Id\mathbb E\,\mathcal S_m = \Lambda\circ\big(\Lambda^{\mathcal C}\big)^m,\qquad\Lambda^{\mathcal C}(\rho) = p\,\rho+(1-p)\Tr(\rho)\frac{\id}{d}

    Average over the independent DjD_j. By the twirling lemma (next step) each factor becomes depolarizing.

  5. F(m)=Tr⁡[E Λ(pmρ+(1−pm)Id)]=A pm+BF(m) = \Tr\Big[E\,\Lambda\Big(p^m\rho+(1-p^m)\frac{\id}{d}\Big)\Big] = A\,p^m+B

    Since (ΛC)m(ρ)=pmρ+(1−pm)I/d(\Lambda^{\mathcal C})^m(\rho) = p^m\rho+(1-p^m)\id/d. SPAM enters only through ρ\rho, EE and the final Λ\Lambda, that is, only through AA and BB. □\square

Twirling and the error rate

DerivationFrom p to the average error
  1. Fpro(Λ)=Fpro(ΛG)=p+1−pd2F_{\text{pro}}(\Lambda) = F_{\text{pro}}(\Lambda^{\mathsf G}) = p+\frac{1-p}{d^2}

    Conjugating by unitaries leaves Tr⁡RΛ\Tr R_\Lambda, hence FproF_{\text{pro}}, unchanged, so twirling preserves the process fidelity.

  2. Favg=d Fpro+1d+1=p+1−pdF_{\text{avg}} = \frac{d\,F_{\text{pro}}+1}{d+1} = p+\frac{1-p}{d}

    Apply the Horodecki–Nielsen formula.

  3. r=1−Favg=(d−1)(1−p)dr = 1-F_{\text{avg}} = \frac{(d-1)(1-p)}{d}

    The RB error per Clifford: r=(1−p)/2r = (1-p)/2 for one qubit and r=3(1−p)/4r = 3(1-p)/4 for two.

Predict before you look

Two-qubit Clifford RB gives p=0.98p = 0.98. What is the average error per two-qubit Clifford, in percent?

Show the answer

1.5 %

r=(d−1)(1−p)d=34×0.02=1.5%r = \tfrac{(d-1)(1-p)}{d} = \tfrac34\times0.02 = 1.5\%. A random two-qubit Clifford needs 1.5 CNOT-type gates on average, plus single-qubit gates, so if the entangling gates dominate, each one errs at most about 1%1\% of the time.

Standard RB gets expensive fast. The Clifford group modulo phases has ∣Cn∣=2n2+2n∏j=1n(4j−1)\abs{\mathcal C_n} = 2^{n^2+2n}\prod_{j=1}^n(4^j-1) elements: 24 for one qubit, 11 520 for two, about 9.3×1079.3\times10^7 for three. The 11 520 two-qubit Cliffords fall into classes needing 0, 1, 2 and 3 CNOTs, of sizes 576, 5184, 5184 and 576, an average of exactly 1.5. A random nn-qubit Clifford needs O(n2/log⁡n)\order{n^2/\log n} two-qubit gates (Aaronson & Gottesman 2004), so standard RB is rarely used beyond two or three qubits.

When the assumptions fail

Real noise depends on which gate is applied: G~=ΛG∘G\tilde{\mathcal G} = \Lambda_G\circ\mathcal G with ΛG\Lambda_G varying. Magesan, Gambetta and Emerson (2012) expanded around the average noise and found first-order corrections to the single exponential. A deeper issue was pointed out later:

Other violations change the shape of the decay. Leakage out of the computational subspace adds a second decay constant (Wood & Gambetta 2018). Time-correlated (non-Markovian) noise and drift inflate the sequence-to-sequence fluctuations and can bend the curve. A decay that is not a clean single exponential is a diagnostic in its own right.

DerivationAverage versus worst-case error
  1. Uθ=e−iθZ/2:Fpro=∣Tr⁡Uθ2∣2=cos⁡2θ2U_\theta = e^{-i\theta Z/2}:\qquad F_{\text{pro}} = \Big|\frac{\Tr U_\theta}{2}\Big|^2 = \cos^2\frac\theta2

    A coherent over-rotation by θ\theta on one qubit.

  2. r=dd+1(1−Fpro)=23sin⁡2θ2r = \frac{d}{d+1}\big(1-F_{\text{pro}}\big) = \frac23\sin^2\frac\theta2

    Its average error.

  3. ε⋄:=12∥Uθ−I∥⋄=sin⁡θ2=32 r\varepsilon_\diamond := \tfrac12\norm{\mathcal U_\theta-\mathcal I}_\diamond = \sin\frac\theta2 = \sqrt{\tfrac32\,r}

    Its worst-case (diamond-norm) error. For a unitary, ε⋄=1−δ2\varepsilon_\diamond = \sqrt{1-\delta^2} with δ\delta the distance from the origin to the numerical range of UθU_\theta, here the chord between e∓iθ/2e^{\mp i\theta/2}, so δ=cos⁡θ2\delta = \cos\frac\theta2.

  4. E(ρ)=(1−q)ρ+∑P≠IqPPρP:ε⋄=q=d+1d r\mathcal E(\rho) = (1-q)\rho+\sum_{P\ne\id}q_PP\rho P:\qquad\varepsilon_\diamond = q = \frac{d+1}{d}\,r

    By contrast, for stochastic Pauli noise with total error probability qq the worst case is linear in rr.

Check your understanding

RB reports r=10−4r = 10^{-4} on a qubit whose only error is a small systematic over-rotation. Roughly what is the worst-case error ε⋄\varepsilon_\diamond?

  1. 10−410^{-4}
  2. 1.5×10−41.5\times10^{-4}
  3. 5×10−55\times10^{-5}
  4. about 1.2×10−21.2\times10^{-2}
Show the answer

D. about 1.2×10−21.2\times10^{-2}

ε⋄=3r/2=1.5×10−4≈1.2×10−2\varepsilon_\diamond = \sqrt{3r/2} = \sqrt{1.5\times10^{-4}}\approx1.2\times10^{-2}: two orders of magnitude worse than the average. Coherent errors can add up in amplitude rather than in probability, which is why fault-tolerance analyses care, and why randomized compiling (Wallman & Emerson 2016) inserts random Pauli frames to turn them into stochastic Pauli noise.

The unitarity of the noise, measurable with a purity-benchmarking variant of RB (Wallman, Granade, Harper & Flammia 2015), separates coherent from incoherent contributions to rr and tightens the bounds on ε⋄\varepsilon_\diamond.

Variants, scalability and the frontier

VariantIdeaReports
Interleaved RB (Magesan et al. 2012)insert a fixed gate CC after every random Clifford and fit its decay pCp_CrC≈(d−1)(1−pC/p)dr_C\approx\frac{(d-1)(1-p_C/p)}{d}, with rigorous systematic-error bounds that are often loose
Simultaneous RB (Gambetta et al. 2012)run RB on several qubits or pairs at once and compare with isolated RBcrosstalk and addressability errors
Character RB (Helsen et al. 2019)representation theory extends RB to gate groups that are not 2-designsdecay rates for non-Clifford gate sets
Direct and mirror RB (Proctor et al. 2019, 2022)random layers of native gates, or a circuit followed by its mirror imageerrors per layer on many qubits without compiling global Cliffords
Cycle benchmarking (Erhard et al. 2019)Pauli-twirled repetitions of a fixed cycle of gates on many qubitsprocess fidelity of a whole cycle
Layer fidelity (McKay et al. 2023)product of simultaneous direct-RB fidelities that cover a layer of two-qubit gatesfidelity of full layers on 100 or more qubits
python
import numpy as np
from qiskit.circuit.library import CZGate
from qiskit_experiments.library import StandardRB, InterleavedRB

lengths = np.arange(1, 200, 20)

# Two-qubit standard RB on physical qubits 0 and 1
rb = StandardRB(physical_qubits=(0, 1), lengths=lengths, num_samples=20, seed=7)

# Interleaved RB for the CZ gate on the same pair
irb = InterleavedRB(CZGate(), physical_qubits=(0, 1), lengths=lengths, num_samples=20, seed=7)

# data = rb.run(backend).block_for_results()
# print(data.analysis_results("EPC"))

A sketch using the Qiskit Experiments library (details vary between versions). The analysis fits A pm+BA\,p^m+B and reports the error per Clifford, "EPC".

Key takeaways

  • For gate-independent Markovian noise, Clifford RB gives F(m)=A pm+BF(m) = A\,p^m+B with SPAM confined to AA and BB; r=(d−1)(1−p)/dr = (d-1)(1-p)/d is the average error of the noise.
  • The proof is a telescoping substitution plus the twirling lemma: over a unitary 2-design every channel averages to a depolarizing one, by Schur's lemma.
  • Gate-dependent noise raises a gauge problem: the RB decay is observable, individual gate fidelities are not. Leakage and non-Markovian noise distort the decay's shape.
  • Average error can hide worst-case error: a coherent over-rotation has ε⋄=3r/2\varepsilon_\diamond = \sqrt{3r/2}, while Pauli noise has ε⋄=d+1d r\varepsilon_\diamond = \tfrac{d+1}{d}\,r.
  • Interleaved, simultaneous, character, direct, mirror and cycle benchmarking, and layer fidelity, extend RB to specific gates, crosstalk, other gate sets and many qubits.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In the decay F(m)=A pm+BF(m) = A\,p^m+B of standard RB with gate-independent noise, which statement is correct?

  1. AA and BB absorb state-preparation and measurement errors, while pp depends only on the gate noise
  2. pp absorbs the SPAM errors, while AA is the gate fidelity
  3. BB equals the average gate fidelity
  4. All three depend only on the gate noise
Show the answer

A. AA and BB absorb state-preparation and measurement errors, while pp depends only on the gate noise

From the proof, A=Tr⁡[EΛ(ρ−I/d)]A = \Tr[E\Lambda(\rho-\id/d)] and B=Tr⁡[EΛ(I/d)]B = \Tr[E\Lambda(\id/d)] depend on ρ\rho and EE, while pp is the depolarizing parameter of the twirled noise.

Question 2

Two-qubit RB gives p=0.99p = 0.99. The average error per Clifford is

  1. 1%1\%
  2. 0.5%0.5\%
  3. 0.75%0.75\%
  4. 1.33%1.33\%
Show the answer

C. 0.75%0.75\%

r=(d−1)(1−p)/d=34×1%=0.75%r = (d-1)(1-p)/d = \tfrac34\times1\% = 0.75\%, with d=4d = 4.

Question 3

Why can the RB error rate differ from the average infidelity of the individual gates reported by tomography, even with perfect statistics?

  1. Because RB uses Cliffords while tomography uses Paulis
  2. Because tomography is biased by shot noise
  3. Because RB averages over sequences while tomography averages over states
  4. Because the infidelity of an individual gate is gauge-dependent, while the RB decay is a gauge-invariant property of the whole gate set
Show the answer

D. Because the infidelity of an individual gate is gauge-dependent, while the RB decay is a gauge-invariant property of the whole gate set

A similarity transformation of the gate set leaves every observable probability unchanged but changes individual gate fidelities. The RB decay rate is invariant; "the" fidelity of one gate depends on the representation (Proctor et al. 2017).

Question 4

You suspect that driving one qubit disturbs its neighbor. Which RB variant is designed to detect this?

  1. Interleaved RB
  2. Simultaneous RB
  3. Purity (unitarity) RB
  4. Standard single-qubit RB on each qubit separately
Show the answer

B. Simultaneous RB

Simultaneous RB compares error rates measured with neighbors idle and with neighbors driven at the same time; the difference quantifies crosstalk and addressability errors (Gambetta et al. 2012).

Further reading

  • J. Emerson, R. Alicki & K. Życzkowski, "Scalable noise estimation with random unitary operators", Journal of Optics B 7, S347 (2005); E. Knill et al., "Randomized benchmarking of quantum gates", Physical Review A 77, 012307 (2008).
  • E. Magesan, J. M. Gambetta & J. Emerson, "Scalable and robust randomized benchmarking of quantum processes", Physical Review Letters 106, 180504 (2011).
  • E. Magesan et al., "Efficient measurement of quantum gate error by interleaved randomized benchmarking", Physical Review Letters 109, 080505 (2012).
  • T. Proctor, K. Rudinger, K. Young, M. Sarovar & R. Blume-Kohout, "What randomized benchmarking actually measures", Physical Review Letters 119, 130502 (2017); J. J. Wallman, "Randomized benchmarking with gate-dependent noise", Quantum 2, 47 (2018).
  • J. Helsen, I. Roth, E. Onorati, A. H. Werner & J. Eisert, "General framework for randomized benchmarking", PRX Quantum 3, 020357 (2022).