Simple Algorithm
Quantum Computing · Rydberg State · 26 min

Projectors & Resolutions of the Identity

Completeness relations, the workhorse identity of every calculation.

"Insert a complete set of states" is the most used sentence in quantum mechanics. Behind it sit orthogonal projectors, resolutions of the identity, and some surprisingly deep theorems about what a pair of projectors can look like.

What you’ll learn

  • Characterize orthogonal projectors algebraically (P2=P=P†P^2=P=P^\dagger), spectrally and metrically (∥P∥≤1\norm P\le1), and distinguish them from oblique idempotents.
  • Use orthogonal and overcomplete resolutions of the identity: PVMs, path sums, frames, POVMs and coherent states.
  • Prove ∫dψ ∣ψ⟩ ⁣⟨ψ∣⊗k=Πsym(k)/(d+k−1k)\int d\psi\,\dyad\psi^{\otimes k}=\Pi^{(k)}_{\mathrm{sym}}/\binom{d+k-1}{k} with Schur's lemma and derive the average-fidelity formula.
  • State Jordan's lemma for two projectors and apply it to products of reflections.

Projectors, precisely

Oblique idempotents are the warning case. E=(1100)E=\begin{pmatrix}1&1\\0&0\end{pmatrix} satisfies E2=EE^2=E but projects along the slanted direction ker⁡E=span⁡{(1,−1)T}\ker E=\operatorname{span}\{(1,-1)^T\}, and ∥E∥∞=2\norm E_\infty=\sqrt2. It is not a measurement: ⟨ψ∣E∣ψ⟩\bra\psi E\ket\psi can be complex, or exceed 11 (it reaches 12+12\tfrac12+\tfrac1{\sqrt2} for real unit vectors).

Projectors form a lattice: P≤QP\le Q iff PQ=PPQ=P iff ran⁡P⊆ran⁡Q\operatorname{ran}P\subseteq\operatorname{ran}Q. If PP and QQ commute, PQPQ projects onto ran⁡P∩ran⁡Q\operatorname{ran}P\cap\operatorname{ran}Q. If they do not, PQPQ is not even Hermitian, but von Neumann's alternating-projection theorem recovers the intersection: (PQ)n→P∧Q(PQ)^n\to P\wedge Q, the projector onto ran⁡P∩ran⁡Q\operatorname{ran}P\cap\operatorname{ran}Q.

Think first How fast does (PQ)n(PQ)^n converge? Try two lines in R2\R^2 at angle θ\theta: P=∣u⟩ ⁣⟨u∣P=\dyad u, Q=∣v⟩ ⁣⟨v∣Q=\dyad v with ⟨u∣v⟩=cos⁡θ\braket{u|v}=\cos\theta.

PQ=cos⁡θ ∣u⟩ ⁣⟨v∣PQ=\cos\theta\,\ketbra{u}{v} and (PQ)n=cos⁡2n−1θ ∣u⟩ ⁣⟨v∣(PQ)^n=\cos^{2n-1}\theta\,\ketbra{u}{v}, so ∥(PQ)n−0∥=cos⁡2n−1θ\norm{(PQ)^n-0}=\cos^{2n-1}\theta. Convergence is geometric at a rate set by the angle between the subspaces; in general the exact rate is c2n−1c^{2n-1} with cc the cosine of the Friedrichs angle (Kayalar–Weinert). Nearly parallel subspaces converge slowly.

Resolutions of the identity

An orthogonal resolution of the identity is a family of projectors with PkPl=δklPkP_kP_l=\delta_{kl}P_k and ∑kPk=I\sum_kP_k=\id. One object, three names: a projection-valued measure (PVM), a projective measurement with Pr⁡(k)=Tr⁡(Pkρ)\Pr(k)=\Tr(P_k\rho), and the spectral decomposition of the observable A=∑kakPkA=\sum_ka_kP_k. Inserting resolutions is how almost every calculation proceeds:

  • ⟨ϕ|AB|ψ⟩=∑k⟨ϕ|A|k⟩⟨k|B|ψ⟩\mel{\phi}{AB}{\psi}=\sum_k\mel{\phi}{A}{k}\mel{k}{B}{\psi}: matrix multiplication.
  • Tr⁡A=∑k⟨k|A|k⟩\Tr A=\sum_k\mel{k}{A}{k}, and Tr⁡(∣ψ⟩ ⁣⟨ϕ∣)=⟨ϕ∣ψ⟩\Tr\big(\ketbra{\psi}{\phi}\big)=\braket{\phi|\psi}.
  • ⟨x∣ψ⟩=∑k⟨x∣k⟩⟨k∣ψ⟩\braket{x|\psi}=\sum_k\braket{x|k}\braket{k|\psi}: change of basis; in infinite dimensions ψ(x)=∫⟨x∣p⟩ψ~(p) dp\psi(x)=\int\braket{x|p}\tilde\psi(p)\,dp is the Fourier transform.
DerivationFeynman's path sum for circuits
  1. ⟨x|UT⋯U1|y⟩=∑z1,…,zT−1⟨x|UT|zT−1⟩⋯⟨z2|U2|z1⟩⟨z1|U1|y⟩\mel{x}{U_T\cdots U_1}{y}=\sum_{z_1,\dots,z_{T-1}}\mel{x}{U_T}{z_{T-1}}\cdots\mel{z_2}{U_2}{z_1}\mel{z_1}{U_1}{y}

    Insert a computational-basis resolution ∑z∣z⟩ ⁣⟨z∣\sum_z\dyad z between consecutive layers of an nn-qubit circuit U=UT⋯U1U=U_T\cdots U_1:

  2. amplitude=∑paths ∏t(local amplitude)⟹BQP⊆PSPACE\text{amplitude}=\sum_{\text{paths}}\ \prod_t\big(\text{local amplitude}\big)\quad\Longrightarrow\quad\mathsf{BQP}\subseteq\mathsf{PSPACE}

    Each term is a product of gate matrix elements along one computational path. There are 2n(T−1)2^{n(T-1)} paths, but each term takes polynomial time and the sum can be accumulated term by term in polynomial space:

  3. BQP⊆PP⊆PSPACE\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}

    A finer counting version of the same sum gives BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP} (Adleman, DeMarrais & Huang, 1997). Interference, the cancellation among exponentially many paths, is what classical samplers cannot easily reproduce.

Resolutions need not be orthogonal. Any family of positive operators summing to I\id is a POVM, and rank-one families {ck∣ψk⟩ ⁣⟨ψk∣}\{c_k\dyad{\psi_k}\} are tight frames: overcomplete "bases" that still come with a reconstruction formula.

ResolutionIdentityNotes
Orthonormal basis∑k=1d∣k⟩ ⁣⟨k∣=I\sum_{k=1}^d\dyad{k}=\ida PVM with dd outcomes
Trine (qubit)23∑k=02∣ψk⟩ ⁣⟨ψk∣=I\tfrac23\sum_{k=0}^2\dyad{\psi_k}=\id∣ψk⟩=cos⁡2πk3∣0⟩+sin⁡2πk3∣1⟩\ket{\psi_k}=\cos\tfrac{2\pi k}3\ket0+\sin\tfrac{2\pi k}3\ket1: Bloch vectors 120∘120^\circ apart on a great circle
SIC-POVM1d∑j=1d2∣ψj⟩ ⁣⟨ψj∣=I\tfrac1d\sum_{j=1}^{d^2}\dyad{\psi_j}=\id∣⟨ψj∣ψk⟩∣2=1d+1\abs{\braket{\psi_j|\psi_k}}^2=\tfrac1{d+1} for j≠kj\neq k; for a qubit, a regular tetrahedron
Coherent states1π∫C∣α⟩ ⁣⟨α∣ d2α=I\tfrac1\pi\int_\C\dyad{\alpha}\,d^2\alpha=\idovercomplete in infinite dimensions; ∣⟨α∣β⟩∣2=e−∣α−β∣2\abs{\braket{\alpha|\beta}}^2=e^{-\abs{\alpha-\beta}^2}
Think first The three trine states satisfy ∑k∣ψk⟩ ⁣⟨ψk∣=c I\sum_k\dyad{\psi_k}=c\,\id. Without computing any matrix, find cc.

Take traces: ∑kTr⁡∣ψk⟩ ⁣⟨ψk∣=3=c Tr⁡I=2c\sum_k\Tr\dyad{\psi_k}=3=c\,\Tr\id=2c, so c=32c=\tfrac32 and the POVM elements are Ek=23∣ψk⟩ ⁣⟨ψk∣E_k=\tfrac23\dyad{\psi_k}. That the sum is proportional to I\id at all is because ∣ψk⟩ ⁣⟨ψk∣=12(I+r⃗k⋅σ⃗)\dyad{\psi_k}=\tfrac12\big(\id+\vec r_k\cdot\vec\sigma\big) and the three Bloch vectors, 120∘120^\circ apart, add up to zero.

The identity from symmetry: Haar averages

Average ∣ψ⟩ ⁣⟨ψ∣\dyad\psi over all pure states with the unitarily invariant (Haar) measure. The result commutes with every unitary, so by Schur's lemma it is a multiple of I\id; its trace is 11, so ∫dψ ∣ψ⟩ ⁣⟨ψ∣=I/d\int d\psi\,\dyad\psi=\id/d. A uniformly random state is a resolution of the identity. The same argument on kk copies is a workhorse for designs, de Finetti theorems and benchmarking:

DerivationProof sketch, and a payoff
  1. [M,U⊗k]=0∀ U∈U(d)\comm{M}{U^{\otimes k}}=0\qquad\forall\,U\in U(d)

    Call the left side MM. Each ∣ψ⟩⊗k\ket\psi^{\otimes k} lies in Sym⁡k\operatorname{Sym}^k, so M=ΠsymMΠsymM=\Pi_{\mathrm{sym}}M\Pi_{\mathrm{sym}}, and Haar invariance gives U⊗kMU†⊗k=MU^{\otimes k}MU^{\dagger\otimes k}=M for all U∈U(d)U\in U(d):

  2. 1=Tr⁡M=c(d+k−1k)1=\Tr M=c\binom{d+k-1}{k}

    Sym⁡k(Cd)\operatorname{Sym}^k(\C^d) is an irreducible representation of U(d)U(d), so Schur's lemma gives M=c ΠsymM=c\,\Pi_{\mathrm{sym}}. Fix cc by traces; dim⁡Sym⁡k(Cd)=(d+k−1k)\dim\operatorname{Sym}^k(\C^d)=\binom{d+k-1}{k} counts multisets of size kk from dd labels.

  3. ∫dψ ∣⟨ψ|U|ψ⟩∣2=Tr⁡[(U⊗U†) I+SWAPd(d+1)]=∣Tr⁡U∣2+dd(d+1)\int d\psi\,\abs{\mel{\psi}{U}{\psi}}^2=\Tr\Big[(U\otimes U^\dagger)\,\frac{\id+\mathrm{SWAP}}{d(d+1)}\Big]=\frac{\abs{\Tr U}^2+d}{d(d+1)}

    Payoff (k=2k=2): the average fidelity of a unitary error UU over Haar-random inputs, using Tr⁡[(A⊗B) SWAP]=Tr⁡(AB)\Tr\big[(A\otimes B)\,\mathrm{SWAP}\big]=\Tr(AB):

Predict before you look

A qubit suffers an unwanted ZZ. Averaged over Haar-random pure inputs, what is ∫dψ ∣⟨ψ|Z|ψ⟩∣2\int d\psi\,\abs{\mel{\psi}{Z}{\psi}}^2, in percent?

Show the answer

33 %

Tr⁡Z=0\Tr Z=0, so the formula gives 0+22⋅3=13\frac{0+2}{2\cdot3}=\tfrac13. Check on the Bloch sphere: ⟨ψ|Z|ψ⟩=z\mel{\psi}{Z}{\psi}=z, and the average of z2z^2 over the unit sphere is 13\tfrac13. Even a full Pauli error leaves average fidelity 13\tfrac13, not 00: states near the zz-axis are barely affected.

Two projectors: Jordan's lemma

DerivationProof sketch
  1. PQP∣vj⟩=cj2∣vj⟩,0≤cj≤1PQP\ket{v_j}=c_j^2\ket{v_j},\qquad 0\le c_j\le1

    PQPPQP is Hermitian and maps ran⁡P\operatorname{ran}P to itself. Diagonalize it there with orthonormal ∣vj⟩∈ran⁡P\ket{v_j}\in\operatorname{ran}P:

  2. Q∣vj⟩=cj∣wj⟩,Q∣wj⟩=∣wj⟩,P∣wj⟩=1cjPQP∣vj⟩=cj∣vj⟩Q\ket{v_j}=c_j\ket{w_j},\qquad Q\ket{w_j}=\ket{w_j},\qquad P\ket{w_j}=\tfrac1{c_j}PQP\ket{v_j}=c_j\ket{v_j}

    If 0<cj<10<c_j<1, set ∣wj⟩=Q∣vj⟩/cj\ket{w_j}=Q\ket{v_j}/c_j, a unit vector since ∥Qvj∥2=⟨vj|PQP|vj⟩=cj2\norm{Qv_j}^2=\mel{v_j}{PQP}{v_j}=c_j^2. Then Bj=span⁡{∣vj⟩,∣wj⟩}B_j=\operatorname{span}\{\ket{v_j},\ket{w_j}\} is two-dimensional and invariant:

  3. ⟨vi∣vj⟩=δij,⟨vi∣wj⟩=cjδij,⟨wi∣wj⟩=⟨vi|PQP|vj⟩cicj=δij\braket{v_i|v_j}=\delta_{ij},\qquad \braket{v_i|w_j}=c_j\delta_{ij},\qquad \braket{w_i|w_j}=\frac{\mel{v_i}{PQP}{v_j}}{c_ic_j}=\delta_{ij}

    Different blocks are orthogonal, because every overlap reduces to a matrix element of PQPPQP:

  4. H=⨁jBj ⊕ (common eigenvectors of P and Q)\Hil=\bigoplus_jB_j\ \oplus\ \big(\text{common eigenvectors of }P\text{ and }Q\big)

    Vectors with cj∈{0,1}c_j\in\{0,1\}, and the part of ker⁡P\ker P orthogonal to all blocks (where QQ restricts to a projector), split into common eigenvectors. Writing cj=cos⁡θjc_j=\cos\theta_j gives the normal form.

Jordan's lemma turns any problem about two projectors into many independent qubit problems. The reflections RP=2P−IR_P=2P-\id and RQ=2Q−IR_Q=2Q-\id act on block jj as reflections about two lines at angle θj\theta_j, so their product is a rotation by 2θj2\theta_j, with eigenvalues e±2iθje^{\pm2i\theta_j}. That single fact drives:

  • Grover search and amplitude amplification: one block, a rotation by 2θ2\theta per iteration;
  • Szegedy quantum walks: walk spectra from principal angles, and quadratically faster hitting times;
  • Marriott–Watrous in-place amplification of QMA verifiers, using a single copy of the witness;
  • QSVT, which applies polynomials to exactly the numbers cos⁡θj\cos\theta_j, the singular values of PQPQ.
Check your understanding

P=∣u⟩ ⁣⟨u∣P=\dyad u and Q=∣v⟩ ⁣⟨v∣Q=\dyad v with ∣⟨u∣v⟩∣=cos⁡θ\abs{\braket{u|v}}=\cos\theta. What is ∥P−Q∥∞\norm{P-Q}_\infty?

  1. sin⁡θ\sin\theta
  2. 1−cos⁡θ1-\cos\theta
  3. 2sin⁡θ2\sin\theta
  4. cos⁡θ\cos\theta
Show the answer

A. sin⁡θ\sin\theta

On their two-dimensional block, P−QP-Q is traceless Hermitian with Tr⁡(P−Q)2=2−2cos⁡2θ\Tr(P-Q)^2=2-2\cos^2\theta, so its eigenvalues are ±sin⁡θ\pm\sin\theta. Hence also the trace distance between the pure states, 12∥P−Q∥1=sin⁡θ=1−∣⟨u∣v⟩∣2\tfrac12\norm{P-Q}_1=\sin\theta=\sqrt{1-\abs{\braket{u|v}}^2}.

Key takeaways

  • Orthogonal projectors: P2=P=P†P^2=P=P^\dagger, equivalently idempotent with ∥P∥∞≤1\norm P_\infty\le1; oblique idempotents are not measurements.
  • Orthogonal resolutions are PVMs and spectral decompositions; inserting them gives matrix products, traces, basis changes and Feynman path sums (BQP⊆PSPACE\mathsf{BQP}\subseteq\mathsf{PSPACE}).
  • Overcomplete resolutions (trine, SIC, coherent states) are POVMs and tight frames; SIC existence in every dimension is open.
  • Haar averages: ∫dψ ∣ψ⟩ ⁣⟨ψ∣⊗k=Πsym/(d+k−1k)\int d\psi\,\dyad\psi^{\otimes k}=\Pi_{\mathrm{sym}}/\binom{d+k-1}{k}, so the average fidelity of UU is (∣Tr⁡U∣2+d)/(d(d+1))(\abs{\Tr U}^2+d)/(d(d+1)).
  • Jordan's lemma: two projectors split into 1- and 2-dimensional blocks, and products of reflections rotate by twice the principal angles.

Check yourself

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

Question 1

Which of these is an orthogonal projector?

  1. (1100)\begin{pmatrix}1&1\\0&0\end{pmatrix}
  2. XX
  3. 12(I+X)\tfrac12(\id+X)
  4. 12(I+Z)\tfrac1{\sqrt2}(\id+Z)
Show the answer

C. 12(I+X)\tfrac12(\id+X)

12(I+X)=∣+⟩ ⁣⟨+∣\tfrac12(\id+X)=\dyad+: it is Hermitian, and (12(I+X))2=14(I+2X+I)=12(I+X)\big(\tfrac12(\id+X)\big)^2=\tfrac14(\id+2X+\id)=\tfrac12(\id+X).

Question 2

For a Haar-random pure state in Cd\C^d and any operator AA, what is ∫dψ ⟨ψ|A|ψ⟩\int d\psi\,\mel{\psi}{A}{\psi}?

  1. Tr⁡A\Tr A
  2. Tr⁡(A)/d\Tr(A)/d
  3. ∥A∥∞\norm A_\infty
  4. Tr⁡(A)2/d2\Tr(A)^2/d^2
Show the answer

B. Tr⁡(A)/d\Tr(A)/d

∫dψ ⟨ψ|A|ψ⟩=Tr⁡(A∫dψ ∣ψ⟩ ⁣⟨ψ∣)=Tr⁡(A I/d)=Tr⁡(A)/d\int d\psi\,\mel{\psi}{A}{\psi}=\Tr\big(A\int d\psi\,\dyad\psi\big)=\Tr(A\,\id/d)=\Tr(A)/d.

Question 3

In a Jordan block where PP and QQ project onto lines at angle θ\theta, what is (2Q−I)(2P−I)(2Q-\id)(2P-\id)?

  1. A reflection about the bisector
  2. A rotation by θ\theta
  3. A rotation by 4θ4\theta
  4. A rotation by 2θ2\theta
Show the answer

D. A rotation by 2θ2\theta

Composing reflections about two lines at angle θ\theta gives a rotation by 2θ2\theta, with eigenvalues e±2iθe^{\pm2i\theta}. In Grover search sin⁡θ=1/N\sin\theta=1/\sqrt N, so about π4N\tfrac\pi4\sqrt N iterations rotate the start state onto the marked one.

Question 4

Inserting a computational-basis resolution of the identity between each pair of consecutive layers of an nn-qubit, TT-layer circuit writes one amplitude as a sum of how many terms, in general?

  1. nTnT
  2. 2n(T−1)2^{n(T-1)}
  3. 2n2^n
  4. TnT^n
Show the answer

B. 2n(T−1)2^{n(T-1)}

Each of the T−1T-1 insertions sums over 2n2^n basis states independently: (2n)T−1(2^n)^{T-1} paths. Exponentially many terms, each cheap to compute, which is exactly why the path sum proves BQP⊆PSPACE\mathsf{BQP}\subseteq\mathsf{PSPACE} rather than giving an efficient simulation.

Further reading

  • P. R. Halmos, "Two subspaces," Trans. Amer. Math. Soc. 144, 381 (1969).
  • A. W. Harrow, "The church of the symmetric subspace," arXiv:1308.6595 (2013).
  • J. M. Renes, R. Blume-Kohout, A. J. Scott & C. M. Caves, "Symmetric informationally complete quantum measurements," J. Math. Phys. 45, 2171 (2004).
  • C. Marriott & J. Watrous, "Quantum Arthur–Merlin games," Computational Complexity (2005).
  • L. M. Adleman, J. DeMarrais & M.-D. A. Huang, "Quantum computability," SIAM J. Comput. (1997).