Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Trace, Norms & Operator Distances

Hilbert–Schmidt, trace norm and operator norm: how we measure errors.

Your gate is "almost" a TT gate. How almost? Error budgets, thresholds and approximation theorems all need distances, and in quantum information three matrix norms do nearly all of the work.

What you’ll learn

  • Use the trace, its cyclicity and the Hilbert–Schmidt inner product, including Pauli expansions.
  • Define Schatten pp-norms via singular values and relate the trace, Frobenius and operator norms.
  • Derive the pure-state trace distance and state its operational meaning (Helstrom).
  • Bound accumulated gate error by telescoping, accounting for global phase.
  • Explain what the diamond norm adds, and why average fidelity can understate worst-case error.

Trace and the Hilbert–Schmidt inner product

The trace Tr⁡A=∑i⟨i|A|i⟩=∑iλi\Tr A=\sum_i\mel{i}{A}{i}=\sum_i\lambda_i is basis-independent and cyclic: Tr⁡(AB)=Tr⁡(BA)\Tr(AB)=\Tr(BA), hence Tr⁡(ABC)=Tr⁡(CAB)=Tr⁡(BCA)\Tr(ABC)=\Tr(CAB)=\Tr(BCA). Cyclic is not the same as symmetric: in general Tr⁡(ABC)≠Tr⁡(BAC)\Tr(ABC)\neq\Tr(BAC).

The d×dd\times d matrices form a d2d^2-dimensional Hilbert space under the Hilbert–Schmidt inner product ⟨A,B⟩HS=Tr⁡(A†B)=∑ijAij∗Bij\langle A,B\rangle_{HS}=\Tr(A^\dagger B)=\sum_{ij}A_{ij}^*B_{ij}. The 4n4^n Pauli strings P∈{I,X,Y,Z}⊗nP\in\{\id,X,Y,Z\}^{\otimes n} are orthogonal, Tr⁡(P†Q)=2nδPQ\Tr(P^\dagger Q)=2^n\delta_{PQ}, so they form a basis:

A=12n∑PTr⁡(PA) P,ρ=12(I+rxX+ryY+rzZ),rj=Tr⁡(ρ σj)A=\frac{1}{2^n}\sum_P\Tr(PA)\,P,\qquad \rho=\tfrac12\big(\id+r_xX+r_yY+r_zZ\big),\quad r_j=\Tr(\rho\,\sigma_j)
The Pauli expansion. For one qubit it is the Bloch-vector form of a density matrix.
Think first Is Tr⁡(ABC)=Tr⁡(ACB)\Tr(ABC)=\Tr(ACB)? Try A=XA=X, B=YB=Y, C=ZC=Z.

XYZ=(iZ)Z=iIXYZ=(iZ)Z=i\id, so Tr⁡(XYZ)=2i\Tr(XYZ)=2i. But XZY=(−iY)Y=−iIXZY=(-iY)Y=-i\id, so Tr⁡(XZY)=−2i\Tr(XZY)=-2i. Only cyclic permutations preserve the trace.

Schatten norms: one family, three workhorses

Every AA has a singular value decomposition A=UΣV†A=U\Sigma V^\dagger; the singular values s1≥⋯≥sd≥0s_1\ge\dots\ge s_d\ge0 are the eigenvalues of ∣A∣=A†A\abs A=\sqrt{A^\dagger A}. The Schatten pp-norm is the ℓp\ell_p norm of the singular values:

∥A∥p=(∑isip)1/p,∥A∥1=Tr⁡∣A∣,∥A∥2=Tr⁡A†A,∥A∥∞=s1=max⁡∥v∥=1∥Av∥\norm{A}_p=\Big(\sum_is_i^p\Big)^{1/p},\qquad \norm{A}_1=\Tr\abs{A},\quad \norm{A}_2=\sqrt{\Tr A^\dagger A},\quad \norm{A}_\infty=s_1=\max_{\norm{v}=1}\norm{Av}
NormAlso calledNatural use
∥⋅∥1\norm{\cdot}_1trace norm, nuclear normdistances between states: 12∥ρ−σ∥1\tfrac12\norm{\rho-\sigma}_1
∥⋅∥2\norm{\cdot}_2Hilbert–Schmidt, Frobeniuseasy algebra, least-squares tomography, average-case errors
∥⋅∥∞\norm{\cdot}_\inftyoperator, spectral normworst-case error of an operation on any input; Hamiltonian bounds
Check your understanding

PP is an orthogonal projector of rank kk on Cd\C^d. What is (∥P∥1,∥P∥2,∥P∥∞)\big(\norm P_1,\norm P_2,\norm P_\infty\big)?

  1. (k, k, k)(k,\,k,\,k)
  2. (k, k, 1)(k,\,\sqrt k,\,1)
  3. (1, 1, 1)(1,\,1,\,1)
  4. (d, d, 1)(d,\,\sqrt d,\,1)
Show the answer

B. (k, k, 1)(k,\,\sqrt k,\,1)

The singular values of PP are kk ones and d−kd-k zeros, so ∥P∥1=k\norm P_1=k, ∥P∥2=k\norm P_2=\sqrt k and ∥P∥∞=1\norm P_\infty=1. The chain ∥P∥1=k∥P∥2=k∥P∥∞\norm P_1=\sqrt k\norm P_2=k\norm P_\infty shows the ordering inequalities are tight.

Distances between states

The trace distance D(ρ,σ)=12∥ρ−σ∥1D(\rho,\sigma)=\tfrac12\norm{\rho-\sigma}_1 is the operationally right distance between states. By duality, D(ρ,σ)=max⁡0≤M≤ITr⁡(M(ρ−σ))D(\rho,\sigma)=\max_{0\le M\le\id}\Tr\big(M(\rho-\sigma)\big): the largest possible difference in the probability of any measurement outcome.

DerivationPure states, and qubits
  1. Δ=∣ψ⟩ ⁣⟨ψ∣−∣ϕ⟩ ⁣⟨ϕ∣,spec⁡(Δ)⊆{λ,−λ,0}\Delta=\dyad{\psi}-\dyad{\phi},\qquad \operatorname{spec}(\Delta)\subseteq\{\lambda,-\lambda,0\}

    Let Δ=∣ψ⟩ ⁣⟨ψ∣−∣ϕ⟩ ⁣⟨ϕ∣\Delta=\dyad\psi-\dyad\phi. It has rank at most 22 and trace 00, so its non-zero eigenvalues are ±λ\pm\lambda.

  2. 2λ2=Tr⁡Δ2=1+1−2∣⟨ψ∣ϕ⟩∣22\lambda^2=\Tr\Delta^2=1+1-2\abs{\braket{\psi|\phi}}^2

    Compute Tr⁡Δ2\Tr\Delta^2 two ways:

  3. D(ψ,ϕ)=1−∣⟨ψ∣ϕ⟩∣2D(\psi,\phi)=\sqrt{1-\abs{\braket{\psi|\phi}}^2}

    So ∥Δ∥1=2λ\norm\Delta_1=2\lambda and

  4. D(ρ,σ)=12 ∣r⃗−s⃗∣D(\rho,\sigma)=\tfrac12\,\abs{\vec r-\vec s}

    For qubits, ρ−σ=12(r⃗−s⃗)⋅σ⃗\rho-\sigma=\tfrac12(\vec r-\vec s)\cdot\vec\sigma has eigenvalues ±12∣r⃗−s⃗∣\pm\tfrac12\abs{\vec r-\vec s}, so the trace distance is half the Euclidean distance between Bloch vectors, pure or mixed.

The Fuchs–van de Graaf inequalities 1−F≤D≤1−F1-\sqrt F\le D\le\sqrt{1-F} tie DD to the fidelity F(ρ,σ)=(Tr⁡∣ρσ∣)2F(\rho,\sigma)=\big(\Tr\abs{\sqrt\rho\sqrt\sigma}\big)^2, with equality on the right for pure states. And DD is contractive: D(Φ(ρ),Φ(σ))≤D(ρ,σ)D(\Phi(\rho),\Phi(\sigma))\le D(\rho,\sigma) for every channel Φ\Phi. Processing never makes states more distinguishable.

Predict before you look

You receive ∣0⟩\ket0 or ∣+⟩\ket+ with equal probability. What is the best possible probability, in percent, of identifying which one you got?

Show the answer

85 %

∣⟨0∣+⟩∣2=12\abs{\braket{0|+}}^2=\tfrac12, so D=1−12=12D=\sqrt{1-\tfrac12}=\tfrac1{\sqrt2} and pmax⁡=12+122≈0.854=cos⁡2π8p^{\max}=\tfrac12+\tfrac1{2\sqrt2}\approx0.854=\cos^2\tfrac\pi8. The optimal measurement is along the Bloch axis (z^−x^)/2(\hat z-\hat x)/\sqrt2, at 45∘45^\circ from each state.

Distances between operations

For unitaries the operator norm gives the worst case over inputs, ∥(U−V)∣ψ⟩∥≤∥U−V∥∞\norm{(U-V)\ket\psi}\le\norm{U-V}_\infty, and it is unchanged by tensoring with an identity on an ancilla. Errors then accumulate at most additively:

DerivationThe telescoping (hybrid) argument
  1. UT⋯U1−VT⋯V1=∑t=1TVT⋯Vt+1 (Ut−Vt) Ut−1⋯U1U_T\cdots U_1-V_T\cdots V_1=\sum_{t=1}^TV_T\cdots V_{t+1}\,(U_t-V_t)\,U_{t-1}\cdots U_1

    Compare TT ideal gates UtU_t with implementations VtV_t (all unitary). Insert and subtract hybrid products:

  2. ∥UT⋯U1−VT⋯V1∥∞≤∑t=1T∥Ut−Vt∥∞\norm{U_T\cdots U_1-V_T\cdots V_1}_\infty\le\sum_{t=1}^T\norm{U_t-V_t}_\infty

    Each term has the error in one slot and unitaries (norm 11) elsewhere. Use the triangle inequality and submultiplicativity:

  3. ∣Pr⁡U(x)−Pr⁡V(x)∣≤2 ∥U−V∥∞\abs{\Pr_U(x)-\Pr_V(x)}\le2\,\norm{U-V}_\infty

    So TT gates, each ϵ\epsilon-accurate, give a TϵT\epsilon-accurate circuit, and every outcome probability moves by at most 2Tϵ2T\epsilon. This is why O(log⁡T)\order{\log T} bits of precision per gate suffice (Bernstein–Vazirani).

Global phase. UU and eiγUe^{i\gamma}U are the same gate, so compare min⁡γ∥U−eiγV∥∞\min_\gamma\norm{U-e^{i\gamma}V}_\infty. For T=diag⁡(1,eiπ/4)T=\diag(1,e^{i\pi/4}) versus I\id: ∥T−I∥∞=2sin⁡π8≈0.77\norm{T-\id}_\infty=2\sin\tfrac\pi8\approx0.77, but with the optimal phase γ=−π/8\gamma=-\pi/8 the distance drops to 2sin⁡π16≈0.392\sin\tfrac\pi{16}\approx0.39.

Channels. Noisy operations are channels, not unitaries. The right worst-case distance is the diamond norm, which lets the input be entangled with an ancilla:

∥Φ−Ψ∥⋄=max⁡ρ∥(Φ⊗idd)(ρ)−(Ψ⊗idd)(ρ)∥1.\norm{\Phi-\Psi}_\diamond=\max_\rho\norm{(\Phi\otimes\mathrm{id}_d)(\rho)-(\Psi\otimes\mathrm{id}_d)(\rho)}_1.

An ancilla of the same dimension always suffices, and for general channels it can be strictly necessary. The optimal probability of telling Φ\Phi from Ψ\Psi in one use is 12+14∥Φ−Ψ∥⋄\tfrac12+\tfrac14\norm{\Phi-\Psi}_\diamond, and rigorous fault-tolerance thresholds are typically stated in this norm.

Key takeaways

  • The trace is cyclic, not symmetric; Tr⁡(A†B)\Tr(A^\dagger B) makes matrices a Hilbert space with the Pauli strings as an orthogonal basis.
  • Schatten norms: ∥⋅∥1\norm\cdot_1 for states, ∥⋅∥2\norm\cdot_2 for algebra and averages, ∥⋅∥∞\norm\cdot_\infty for worst-case operations, with ∥A∥∞≤∥A∥2≤∥A∥1≤r∥A∥2\norm A_\infty\le\norm A_2\le\norm A_1\le\sqrt r\norm A_2.
  • D=12∥ρ−σ∥1D=\tfrac12\norm{\rho-\sigma}_1 sets the optimal guessing probability 12+12D\tfrac12+\tfrac12D (Helstrom); for pure states D=1−∣⟨ψ∣ϕ⟩∣2D=\sqrt{1-\abs{\braket{\psi|\phi}}^2}, for qubits half the Bloch distance.
  • Gate errors add at most linearly (telescoping); compare unitaries up to global phase, and channels in the diamond norm.
  • For coherent errors the diamond distance scales like the square root of the average infidelity.

Check yourself

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

Question 1

Which quantity bounds the error of an implemented unitary VV (intended UU) on every input, including when it acts on part of an entangled state?

  1. 1−∣Tr⁡(U†V)∣2/d21-\abs{\Tr(U^\dagger V)}^2/d^2
  2. ∥U−V∥∞\norm{U-V}_\infty
  3. ∣Tr⁡(U†V)∣/d\abs{\Tr(U^\dagger V)}/d
  4. ∥U−V∥2/d\norm{U-V}_2/\sqrt d
Show the answer

B. ∥U−V∥∞\norm{U-V}_\infty

∥(U−V)⊗I∥∞=∥U−V∥∞\norm{(U-V)\otimes\id}_\infty=\norm{U-V}_\infty and ∥(U−V)∣ψ⟩∥≤∥U−V∥∞\norm{(U-V)\ket\psi}\le\norm{U-V}_\infty for every unit vector, so it is a worst-case bound that survives adding ancillas. The trace-based quantities measure average behavior.

Question 2

A circuit has 10001000 gates, each within operator-norm distance 10−410^{-4} of ideal. What is the best general upper bound on the whole circuit's operator-norm error?

  1. 10−410^{-4}
  2. 1000×10−4≈3×10−3\sqrt{1000}\times10^{-4}\approx3\times10^{-3}
  3. 0.10.1
  4. 22; no better general bound exists
Show the answer

C. 0.10.1

Telescoping gives ∑t∥Ut−Vt∥≤1000×10−4=0.1\sum_t\norm{U_t-V_t}\le1000\times10^{-4}=0.1, and coherent errors that all push the same way essentially reach it. T\sqrt T growth is typical for random, incoherent errors but is not a worst-case guarantee.

Question 3

What is the trace distance between ∣0⟩ ⁣⟨0∣\dyad0 and the maximally mixed state I/2\id/2?

  1. 11
  2. 12\tfrac1{\sqrt2}
  3. 00
  4. 12\tfrac12
Show the answer

D. 12\tfrac12

ρ−σ=diag⁡(12,−12)\rho-\sigma=\diag(\tfrac12,-\tfrac12), so 12∥ρ−σ∥1=12\tfrac12\norm{\rho-\sigma}_1=\tfrac12. Equivalently, half the Bloch distance from the north pole to the center: 12∣z^−0⃗∣=12\tfrac12\abs{\hat z-\vec0}=\tfrac12.

Question 4

Which expression equals Tr⁡(ABC)\Tr(ABC) for all d×dd\times d matrices A,B,CA,B,C?

  1. Tr⁡(CAB)\Tr(CAB)
  2. Tr⁡(BAC)\Tr(BAC)
  3. Tr⁡(CBA)\Tr(CBA)
  4. Tr⁡(A) Tr⁡(BC)\Tr(A)\,\Tr(BC)
Show the answer

A. Tr⁡(CAB)\Tr(CAB)

Cyclicity: Tr⁡(MN)=Tr⁡(NM)\Tr(MN)=\Tr(NM) with M=ABM=AB, N=CN=C. Non-cyclic reorderings fail: Tr⁡(XYZ)=2i\Tr(XYZ)=2i but Tr⁡(YXZ)=−2i\Tr(YXZ)=-2i.

Further reading

  • J. Watrous, The Theory of Quantum Information, chs. 1 and 3 (Cambridge, 2018).
  • C. W. Helstrom, Quantum Detection and Estimation Theory (Academic Press, 1976).
  • C. A. Fuchs & J. van de Graaf, "Cryptographic distinguishability measures for quantum-mechanical states," IEEE Trans. Inf. Theory (1999).
  • A. Yu. Kitaev, "Quantum computations: algorithms and error correction," Russian Math. Surveys (1997).
  • R. Kueng, D. M. Long, A. C. Doherty & S. T. Flammia, "Comparing experiments to the fault-tolerance threshold," Phys. Rev. Lett. (2016).