Lesson 40 · 90 min · advanced

The SWAP Test

Loading progress…

\lvert\langle\psi\vert\phi\rangle\rvert^2

Prerequisites: Quantum Kernels & Fidelity Kernels, Toffoli, Reversible Logic & Universality

Objectives and key results

$8\times8$
$P(0)=\frac12\big(1+\lvert\langle\psi\vert\phi\rangle\rvert^2\big)$
$n$
$\mathrm{Tr}\big[\mathrm{SWAP}(\rho\otimes\sigma)\big]=\mathrm{Tr}(\rho\sigma)$
$\hat F=2\hat P(0)-1$
$\mathrm{CSWAP}_{0;1,2}=\mathrm{CNOT}_{2\to1}\,\mathrm{CCX}_{0,1\to2}\,\mathrm{CNOT}_{2\to1}$
$\mathrm{Re}\langle\psi\vert U\vert\psi\rangle$

formula · SWAP-test acceptance probability: $P(0)=\tfrac14\big\lVert\lvert\psi\phi\rangle+\lvert\phi\psi\rangle\big\rVert^2=\tfrac12\big(1+\lvert\langle\psi\vert\phi\rangle\rvert^2\big),\qquad P(1)=\tfrac12\big(1-\lvert\langle\psi\vert\phi\rangle\rvert^2\big)$
identity · The SWAP trick: $\mathrm{Tr}\big[\mathrm{SWAP}\,(\rho\otimes\sigma)\big]=\mathrm{Tr}(\rho\sigma)\ \Rightarrow\ P(0)=\tfrac12\big(1+\mathrm{Tr}(\rho\sigma)\big)$
theorem · Estimator and shot budget: $\hat F=2\hat P(0)-1,\quad\mathbb E[\hat F]=F,\quad\mathrm{Var}[\hat F]=\frac{4P_0(1-P_0)}N=\frac{1-F^2}N,\qquad N\ge\frac{2\ln(2/\delta)}{\varepsilon^2}\Rightarrow P\big(\lvert\hat F-F\rvert\le\varepsilon\big)\ge1-\delta$
identity · Fredkin decomposition: $\mathrm{CSWAP}_{0;1,2}=\mathrm{CNOT}_{2\to1}\,\mathrm{CCX}_{0,1\to2}\,\mathrm{CNOT}_{2\to1}\qquad(8\ \text{CNOTs with a 6-CNOT Toffoli})$
formula · Hadamard test: $P(0)=\tfrac12\big(1+\mathrm{Re}\langle\psi\vert U\vert\psi\rangle\big),\qquad P(0)\big\vert_{S^\dagger}=\tfrac12\big(1+\mathrm{Im}\langle\psi\vert U\vert\psi\rangle\big)$

Why a second overlap test?#

K(x,x')=\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2

Definition

The overlap-estimation task

n

Intuition

\lvert0\rangle

Quick check

10^4

The controlled-SWAP (Fredkin) gate#

Definition

Controlled-SWAP (Fredkin) gate

\mathrm{CSWAP}_{c;a,b}

\mathrm{CSWAP}_{0;1,2}=\begin{pmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\end{pmatrix}=\begin{pmatrix}I_4&0\\0&\mathrm{SWAP}\end{pmatrix},\qquad\mathrm{SWAP}=\begin{pmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{pmatrix}

CSWAP in the basis |c a b⟩ with qubit 0 = control8×8

Unitary verified: $U^\dagger U = I$ (max deviation 0.0e+0)

Proposition

The Fredkin gate is a self-inverse permutation matrix

\mathrm{CSWAP}

Proof (8 steps)

Step 1:
$\mathrm{CSWAP}\lvert k\rangle=\lvert\pi(k)\rangle,\qquad\pi(5)=6,\ \ \pi(6)=5,\ \ \pi(k)=k\ \ (k\notin\{5,6\})$
Apply the definition to the eight basis states: for $c=0$ (indices $0$ – $3$ ) nothing moves; for $c=1$ the states $\lvert100\rangle$ and $\lvert111\rangle$ have $a=b$ and are fixed, while $\lvert101\rangle\mapsto\lvert110\rangle$ and $\lvert110\rangle\mapsto\lvert101\rangle$ .
Step 2:
$(P_\pi)_{jk}=\langle j\vert P_\pi\vert k\rangle=\delta_{j,\pi(k)}$
Column $k$ of a matrix is the image of the basis vector $\lvert k\rangle$ , here the basis vector $\lvert\pi(k)\rangle$ : every column and every row contains exactly one entry $1$ , which is the definition of a permutation matrix. This reproduces the displayed matrix: $I_8$ with rows $5$ and $6$ exchanged.
Step 3:
$(P_\pi^{\top}P_\pi)_{kl}=\sum_{j=0}^{7}\delta_{j,\pi(k)}\,\delta_{j,\pi(l)}=\delta_{\pi(k),\pi(l)}=\delta_{kl}$
The sum over $j$ picks out $j=\pi(k)$ ; the last equality holds because $\pi$ is injective. So $P_\pi^\top P_\pi=I_8$ .
Step 4:
$P_\pi\in\mathbb R^{8\times8}\ \Rightarrow\ P_\pi^\dagger=\overline{P_\pi}^{\,\top}=P_\pi^\top\ \Rightarrow\ P_\pi^\dagger P_\pi=I_8$
For a real matrix the conjugate transpose is the transpose, so orthogonality is unitarity.
Step 5:
$P_\sigma P_\tau\lvert k\rangle=P_\sigma\lvert\tau(k)\rangle=\lvert\sigma(\tau(k))\rangle\ \Rightarrow\ P_\sigma P_\tau=P_{\sigma\circ\tau}$
Permutation matrices multiply like the permutations they represent (check on every basis vector).
Step 6:
$\pi\circ\pi=\mathrm{id}\ \Rightarrow\ \mathrm{CSWAP}^2=P_{\pi\circ\pi}=P_{\mathrm{id}}=I_8\ \Rightarrow\ \mathrm{CSWAP}^{-1}=\mathrm{CSWAP}=\mathrm{CSWAP}^\dagger$
A transposition undone by itself: applying the Fredkin gate twice restores every basis state. Combining $\mathrm{CSWAP}^{-1}=\mathrm{CSWAP}$ with $\mathrm{CSWAP}^{-1}=\mathrm{CSWAP}^\dagger$ shows that the gate is Hermitian (equivalently, the matrix is symmetric because $\pi=\pi^{-1}$ ).
Step 7:
$\mathrm{CSWAP}\,\tfrac1{\sqrt2}\big(\lvert101\rangle\mp\lvert110\rangle\big)=\tfrac1{\sqrt2}\big(\lvert110\rangle\mp\lvert101\rangle\big)=\mp\tfrac1{\sqrt2}\big(\lvert101\rangle\mp\lvert110\rangle\big)$
Inside the invariant plane spanned by $\lvert101\rangle,\lvert110\rangle$ the gate acts as $X$ , with eigenvalues $\pm1$ . The six fixed basis states and $\frac1{\sqrt2}(\lvert101\rangle+\lvert110\rangle)$ have eigenvalue $+1$ , so the trace is $7\cdot1+1\cdot(-1)=6$ , the number of fixed points of $\pi$ .
Step 8:
$\lvert0\rangle\langle0\rvert\otimes I_4+\lvert1\rangle\langle1\rvert\otimes\mathrm{SWAP}=\begin{pmatrix}1&0\\0&0\end{pmatrix}\otimes I_4+\begin{pmatrix}0&0\\0&1\end{pmatrix}\otimes\mathrm{SWAP}=\begin{pmatrix}I_4&0\\0&\mathrm{SWAP}\end{pmatrix}$
The operator form of the definition: with the control as the leftmost Kronecker factor, $A\otimes B$ places the entry $A_{rc}$ times the block $B$ at block position $(r,c)$ , so the upper-left block acts on $c=0$ and the lower-right block on $c=1$ .

∎

\lvert c\,a\,b\rangle

Quick check

\mathrm{CSWAP}_{0;1,2}\,\lvert110\rangle

The acceptance probability#

0

Theorem

Acceptance probability of the SWAP test

\lvert\psi\rangle,\lvert\phi\rangle\in\mathbb C^d

Proof (11 steps)

Step 1:
$\lvert\Psi_0\rangle=\lvert0\rangle\otimes\lvert\psi\rangle\otimes\lvert\phi\rangle=\lvert0\rangle\lvert\psi\phi\rangle$
Initial state: ancilla in $\lvert0\rangle$ , the two registers loaded with the states to be compared.
Step 2:
$\lvert\Psi_1\rangle=(H\otimes I)\lvert\Psi_0\rangle=\tfrac1{\sqrt2}\big(\lvert0\rangle+\lvert1\rangle\big)\lvert\psi\phi\rangle=\tfrac1{\sqrt2}\big(\lvert0\rangle\lvert\psi\phi\rangle+\lvert1\rangle\lvert\psi\phi\rangle\big)$
$H\lvert0\rangle=\frac1{\sqrt2}(\lvert0\rangle+\lvert1\rangle)$ on the ancilla, identity on the registers, and distributivity of $\otimes$ .
Step 3:
$\mathrm{SWAP}\lvert\psi\phi\rangle=\sum_{i,j}\psi_i\phi_j\,\mathrm{SWAP}\lvert i\rangle\lvert j\rangle=\sum_{i,j}\psi_i\phi_j\lvert j\rangle\lvert i\rangle=\Big(\sum_j\phi_j\lvert j\rangle\Big)\otimes\Big(\sum_i\psi_i\lvert i\rangle\Big)=\lvert\phi\psi\rangle$
Expand both states in the computational basis, use the defining action $\mathrm{SWAP}\lvert i\rangle\lvert j\rangle=\lvert j\rangle\lvert i\rangle$ and linearity, and refactor the double sum as a product.
Step 4:
$\lvert\Psi_2\rangle=\tfrac1{\sqrt2}\big(\lvert0\rangle\lvert\psi\phi\rangle+\lvert1\rangle\,\mathrm{SWAP}\lvert\psi\phi\rangle\big)=\tfrac1{\sqrt2}\big(\lvert0\rangle\lvert\psi\phi\rangle+\lvert1\rangle\lvert\phi\psi\rangle\big)$
The controlled swap $\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes\mathrm{SWAP}$ leaves the $\lvert0\rangle$ branch alone and swaps the registers in the $\lvert1\rangle$ branch.
Step 5:
$\lvert\Psi_3\rangle=\tfrac12\big(\lvert0\rangle+\lvert1\rangle\big)\lvert\psi\phi\rangle+\tfrac12\big(\lvert0\rangle-\lvert1\rangle\big)\lvert\phi\psi\rangle=\tfrac12\lvert0\rangle\big(\lvert\psi\phi\rangle+\lvert\phi\psi\rangle\big)+\tfrac12\lvert1\rangle\big(\lvert\psi\phi\rangle-\lvert\phi\psi\rangle\big)$
Second Hadamard: $H\lvert0\rangle=\frac1{\sqrt2}(\lvert0\rangle+\lvert1\rangle)$ , $H\lvert1\rangle=\frac1{\sqrt2}(\lvert0\rangle-\lvert1\rangle)$ ; the factors $\frac1{\sqrt2}\cdot\frac1{\sqrt2}=\frac12$ ; then collect the terms by the ancilla basis state.
Step 6:
$P(0)=\big\lVert(\langle0\rvert\otimes I)\lvert\Psi_3\rangle\big\rVert^2=\tfrac14\big\lVert\lvert\psi\phi\rangle+\lvert\phi\psi\rangle\big\rVert^2$
Born rule for a measurement of the ancilla alone: the probability of outcome $0$ is the squared norm of the projection $(\lvert0\rangle\langle0\rvert\otimes I)\lvert\Psi_3\rangle$ , i.e. of the register vector multiplying $\lvert0\rangle$ .
Step 7:
$\lVert u+v\rVert^2=\langle u\vert u\rangle+\langle v\vert v\rangle+\langle u\vert v\rangle+\langle v\vert u\rangle=\lVert u\rVert^2+\lVert v\rVert^2+2\,\mathrm{Re}\langle u\vert v\rangle$
Sesquilinearity of the inner product and $\langle v\vert u\rangle=\overline{\langle u\vert v\rangle}$ , so the two cross terms add up to twice the real part.
Step 8:
$\lVert\lvert\psi\phi\rangle\rVert=\lVert\psi\rVert\,\lVert\phi\rVert=1,\qquad\langle\psi\phi\vert\phi\psi\rangle=\langle\psi\vert\phi\rangle\langle\phi\vert\psi\rangle=\langle\psi\vert\phi\rangle\overline{\langle\psi\vert\phi\rangle}=\lvert\langle\psi\vert\phi\rangle\rvert^2$
Inner products of product vectors factorise, $\langle a\otimes b\vert c\otimes d\rangle=\langle a\vert c\rangle\langle b\vert d\rangle$ . The cross term is real and nonnegative, so its real part is itself.
Step 9:
$P(0)=\tfrac14\big(1+1+2\lvert\langle\psi\vert\phi\rangle\rvert^2\big)=\tfrac12\big(1+\lvert\langle\psi\vert\phi\rangle\rvert^2\big)$
Insert $u=\lvert\psi\phi\rangle$ , $v=\lvert\phi\psi\rangle$ into the norm expansion: $\lVert u+v\rVert^2=2+2\lvert\langle\psi\vert\phi\rangle\rvert^2$ .
Step 10:
$P(1)=\tfrac14\big\lVert\lvert\psi\phi\rangle-\lvert\phi\psi\rangle\big\rVert^2=\tfrac14\big(2-2\lvert\langle\psi\vert\phi\rangle\rvert^2\big)=\tfrac12\big(1-\lvert\langle\psi\vert\phi\rangle\rvert^2\big)$
The same computation with $v\mapsto-v$ flips the sign of the cross term. As a check, $P(0)+P(1)=1$ .
Step 11:
$0\le\lvert\langle\psi\vert\phi\rangle\rvert^2\le1\ \Rightarrow\ \tfrac12\le P(0)\le1$
Cauchy–Schwarz for unit vectors, with equality $\lvert\langle\psi\vert\phi\rangle\rvert=1$ exactly when $\lvert\phi\rangle=e^{i\alpha}\lvert\psi\rangle$ ; the lower end is reached exactly for orthogonal states. Since $P(0)\ge\frac12$ , a single shot can never certify that two states differ.

∎

Corollary

The SWAP test measures the projector onto the symmetric subspace

\lvert\chi\rangle

Proof (6 steps)

Step 1:
$\lvert0\rangle\lvert\chi\rangle\ \xrightarrow{H_0}\ \tfrac1{\sqrt2}\big(\lvert0\rangle+\lvert1\rangle\big)\lvert\chi\rangle\ \xrightarrow{\text{C-SWAP}}\ \tfrac1{\sqrt2}\big(\lvert0\rangle\lvert\chi\rangle+\lvert1\rangle\,\mathrm{SWAP}\lvert\chi\rangle\big)$
The first two layers of the theorem, with $\lvert\psi\phi\rangle$ replaced by an arbitrary register state.
Step 2:
$\xrightarrow{H_0}\ \lvert0\rangle\,\tfrac12\big(I+\mathrm{SWAP}\big)\lvert\chi\rangle+\lvert1\rangle\,\tfrac12\big(I-\mathrm{SWAP}\big)\lvert\chi\rangle=\lvert0\rangle\,\Pi_{\mathrm{sym}}\lvert\chi\rangle+\lvert1\rangle\,\Pi_{\mathrm{anti}}\lvert\chi\rangle$
The final Hadamard, collecting the terms by ancilla value as before.
Step 3:
$\mathrm{SWAP}^\dagger=\mathrm{SWAP},\qquad\mathrm{SWAP}^2=I$
$\mathrm{SWAP}$ is a permutation matrix of the basis $\lvert i\rangle\lvert j\rangle$ whose permutation $(i,j)\mapsto(j,i)$ is its own inverse; as for the Fredkin gate, such a matrix is real, symmetric and squares to the identity.
Step 4:
$\Pi_{\mathrm{sym}}^\dagger=\Pi_{\mathrm{sym}},\qquad\Pi_{\mathrm{sym}}^2=\tfrac14\big(I+2\,\mathrm{SWAP}+\mathrm{SWAP}^2\big)=\tfrac14\big(2I+2\,\mathrm{SWAP}\big)=\Pi_{\mathrm{sym}}$
Hermitian and idempotent: an orthogonal projector. Its range consists of the vectors with $\mathrm{SWAP}\lvert v\rangle=\lvert v\rangle$ , because $\Pi_{\mathrm{sym}}\lvert v\rangle=\lvert v\rangle\iff\mathrm{SWAP}\lvert v\rangle=\lvert v\rangle$ . The same algebra applies to $\Pi_{\mathrm{anti}}$ , and $\Pi_{\mathrm{sym}}+\Pi_{\mathrm{anti}}=I$ .
Step 5:
$P(0)=\big\lVert\Pi_{\mathrm{sym}}\lvert\chi\rangle\big\rVert^2=\langle\chi\vert\Pi_{\mathrm{sym}}^\dagger\Pi_{\mathrm{sym}}\vert\chi\rangle=\langle\chi\vert\Pi_{\mathrm{sym}}\vert\chi\rangle$
Born rule on the ancilla, then $\Pi^\dagger\Pi=\Pi^2=\Pi$ .
Step 6:
$\lvert\chi\rangle=\lvert\psi\phi\rangle:\quad\langle\psi\phi\vert\Pi_{\mathrm{sym}}\vert\psi\phi\rangle=\tfrac12\big(1+\langle\psi\phi\vert\phi\psi\rangle\big)=\tfrac12\big(1+\lvert\langle\psi\vert\phi\rangle\rvert^2\big)$
For a product input the corollary reproduces the theorem. The formula is linear in the projector $\lvert\chi\rangle\langle\chi\rvert$ , which is what makes the extension to mixed states immediate.

∎

SWAP-test samplerSwapTestSampler

Two single-qubit states on Bloch spheres; sampled SWAP-test acceptance probability with error bars against the exact value ½(1 + |⟨ψ|φ⟩|²).

State

|a\rangle

θ of state Aπ/3

φ of state A0

State

|b\rangle

θ of state B0

φ of state B0

$F = |\langle a|b\rangle|^2 =$ 0.75· $P(0) = \tfrac{1}{2}(1 + F) =$ 0.875

Simulated circuit: $P(q_0 = 0) =$ 0.875 (matches the closed form to 10⁻¹²)

Shots N (log scale)200

seed 1

sampling…

Shots for $\mathrm{SE}(\hat F) \le 0.01$ : 4375; for 0.05: 175 $\big(N = \lceil 4P_0(1-P_0)/\varepsilon^2\rceil\big)$

Acceptance probability P(0)

Fidelity F = |⟨a|b⟩|²

Preparation $R_Z(\varphi)R_Y(\theta)|0\rangle = e^{-i\varphi/2}\big(\cos\tfrac{\theta}{2}|0\rangle + e^{i\varphi}\sin\tfrac{\theta}{2}|1\rangle\big)$ — the global phase $e^{-i\varphi/2}$ is unobservable, so the circuit prepares exactly the states shown on the Bloch spheres.

\lvert\psi\rangle=\cos\frac\theta2\lvert0\rangle+e^{i\varphi}\sin\frac\theta2\lvert1\rangle

Quick check

\lvert\psi\rangle=\lvert+\rangle=\frac1{\sqrt2}(\lvert0\rangle+\lvert1\rangle)

Registers of n qubits#

n

Lemma

A register swap is a product of qubit swaps

\mathrm{SWAP}_{A,B}\lvert x\rangle_A\lvert y\rangle_B=\lvert y\rangle_A\lvert x\rangle_B

Proof (4 steps)

Step 1:
$\mathrm{SWAP}_{a_i,b_i}\,\lvert x_0\cdots x_i\cdots x_{n-1}\rangle_A\lvert y_0\cdots y_i\cdots y_{n-1}\rangle_B=\lvert x_0\cdots y_i\cdots x_{n-1}\rangle_A\lvert y_0\cdots x_i\cdots y_{n-1}\rangle_B$
A qubit swap exchanges the bits on its two wires and leaves every other wire unchanged.
Step 2:
$\mathrm{SWAP}_{a_i,b_i}\mathrm{SWAP}_{a_j,b_j}=\mathrm{SWAP}_{a_j,b_j}\mathrm{SWAP}_{a_i,b_i}\qquad(i\ne j)$
Operators acting on disjoint sets of qubits commute ( $(P\otimes I)(I\otimes Q)=P\otimes Q=(I\otimes Q)(P\otimes I)$ after reordering the wires), so the product does not depend on the order.
Step 3:
$\prod_{i=0}^{n-1}\mathrm{SWAP}_{a_i,b_i}\,\lvert x\rangle_A\lvert y\rangle_B=\lvert y_0\cdots y_{n-1}\rangle_A\lvert x_0\cdots x_{n-1}\rangle_B=\lvert y\rangle_A\lvert x\rangle_B$
Each factor exchanges one bit position, and every position is exchanged exactly once.
Step 4:
$\mathrm{SWAP}_{A,B}\lvert\psi\rangle\lvert\phi\rangle=\sum_{x,y}\psi_x\phi_y\lvert y\rangle\lvert x\rangle=\lvert\phi\rangle\lvert\psi\rangle$
Linearity, exactly as in the one-qubit computation of the acceptance theorem.

∎

Lemma

Controlled products are products of controlled gates

U_1,\dots,U_n

Proof (4 steps)

Step 1:
$P_0=\lvert0\rangle\langle0\rvert,\ P_1=\lvert1\rangle\langle1\rvert:\qquad P_0^2=P_0,\quad P_1^2=P_1,\quad P_0P_1=P_1P_0=0$
The two computational-basis projectors of the control are orthogonal idempotents.
Step 2:
$C(U)\,C(V)=P_0^2\otimes I+P_0P_1\otimes V+P_1P_0\otimes U+P_1^2\otimes UV=P_0\otimes I+P_1\otimes UV=C(UV)$
Multiply out with the mixed-product rule $(A\otimes B)(C\otimes D)=AC\otimes BD$ ; the cross terms vanish.
Step 3:
$C(U_n\cdots U_1)=C(U_n)\,C(U_{n-1}\cdots U_1)=\cdots=C(U_n)\cdots C(U_1)$
Induction on $n$ using the two-factor identity.
Step 4:
$C\big(\mathrm{SWAP}_{A,B}\big)=C\Big(\prod_i\mathrm{SWAP}_{a_i,b_i}\Big)=\prod_{i=0}^{n-1}C\big(\mathrm{SWAP}_{a_i,b_i}\big)=\prod_{i=0}^{n-1}\mathrm{CSWAP}_{0;a_i,b_i}$
Apply the lemma to the factorisation of the register swap; a controlled qubit swap is by definition a Fredkin gate.

∎

Corollary

The SWAP test for n-qubit states

H(0);\ \mathrm{CSWAP}(0,1,n+1);\ \mathrm{CSWAP}(0,2,n+2);\ \dots;\ \mathrm{CSWAP}(0,n,2n);\ H(0)

Proof (4 steps)

Step 1:
$\prod_{i=0}^{n-1}\mathrm{CSWAP}_{0;1+i,1+n+i}=\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes\mathrm{SWAP}_{A,B}$
The controlled-product lemma applied to the register-swap factorisation.
Step 2:
$\mathrm{SWAP}_{A,B}\lvert\psi\rangle\lvert\phi\rangle=\lvert\phi\rangle\lvert\psi\rangle$
The factorisation lemma; this is the only property of the swap used in the acceptance theorem.
Step 3:
$P(0)=\tfrac12\big(1+\lvert\langle\psi\vert\phi\rangle\rvert^2\big)$
The acceptance theorem with $d=2^n$ .
Step 4:
$\#\text{qubits}=1+n+n=2n+1,\qquad\#\mathrm{CSWAP}=n,\qquad\#H=2$
Count of the circuit elements. All Fredkin gates touch the ancilla, so in this form they run one after another and the controlled swap has depth $n$ in Fredkin gates.

∎

Quick check

n=4

Mixed states and the SWAP trick#

Lemma

The SWAP trick

A,B\in\mathbb C^{d\times d}

Proof (6 steps)

Step 1:
$\mathrm{SWAP}=\sum_{i,j=0}^{d-1}\lvert j\,i\rangle\langle i\,j\rvert\ \Rightarrow\ \langle k\,l\vert\mathrm{SWAP}\vert i\,j\rangle=\langle k\,l\vert j\,i\rangle=\delta_{kj}\,\delta_{li}$
The swap maps the basis vector $\lvert i\,j\rangle=\lvert i\rangle\otimes\lvert j\rangle$ to $\lvert j\,i\rangle$ ; its matrix elements are products of Kronecker deltas.
Step 2:
$\langle i\,j\vert A\otimes B\vert k\,l\rangle=\langle i\vert A\vert k\rangle\langle j\vert B\vert l\rangle=A_{ik}\,B_{jl}$
Matrix elements of a Kronecker product between product basis vectors factorise.
Step 3:
$\mathrm{Tr}\big[\mathrm{SWAP}(A\otimes B)\big]=\sum_{i,j}\langle i\,j\vert\mathrm{SWAP}(A\otimes B)\vert i\,j\rangle=\sum_{i,j}\sum_{k,l}\langle i\,j\vert\mathrm{SWAP}\vert k\,l\rangle\,\langle k\,l\vert A\otimes B\vert i\,j\rangle$
The trace is the sum of the diagonal elements in the product basis; insert the resolution of the identity $\sum_{k,l}\lvert k\,l\rangle\langle k\,l\rvert=I$ between the two factors.
Step 4:
$=\sum_{i,j,k,l}\delta_{il}\,\delta_{jk}\,A_{ki}\,B_{lj}$
Insert the two matrix-element formulas: $\langle i\,j\vert\mathrm{SWAP}\vert k\,l\rangle=\delta_{il}\delta_{jk}$ (the first line with the indices renamed) and $\langle k\,l\vert A\otimes B\vert i\,j\rangle=A_{ki}B_{lj}$ .
Step 5:
$=\sum_{i,j}A_{ji}\,B_{ij}=\sum_i\Big(\sum_jB_{ij}A_{ji}\Big)=\sum_i(BA)_{ii}=\mathrm{Tr}(BA)=\mathrm{Tr}(AB)$
The deltas set $k=j$ and $l=i$ ; the inner sum is the matrix product $BA$ ; finally cyclicity of the trace.
Step 6:
$A=\rho,\ B=\sigma:\ \mathrm{Tr}\big[\mathrm{SWAP}(\rho\otimes\sigma)\big]=\mathrm{Tr}(\rho\sigma);\qquad A=B=\rho:\ \mathrm{Tr}\big[\mathrm{SWAP}(\rho\otimes\rho)\big]=\mathrm{Tr}(\rho^2)$
The two special cases used below. A quadratic function of $\rho$ becomes a linear function of the two-copy state $\rho\otimes\rho$ : this is the general mechanism behind estimating nonlinear functionals of quantum states (Ekert et al. 2002).

∎

Theorem

The SWAP test on mixed states

\rho

Proof (6 steps)

Step 1:
$P(0)=\mathrm{Tr}\Big[\big(\lvert0\rangle\langle0\rvert\otimes I\big)\,V\big(\lvert0\rangle\langle0\rvert\otimes\omega\big)V^\dagger\Big],\qquad V=H_0\,C(\mathrm{SWAP})\,H_0$
Born rule for a density operator: the circuit maps the input $\lvert0\rangle\langle0\rvert\otimes\omega$ to $V(\cdot)V^\dagger$ , and the outcome probability is the trace with the measurement projector. This expression is linear in the register state $\omega$ .
Step 2:
$\omega=\lvert\chi\rangle\langle\chi\rvert:\quad P(0)=\langle\chi\vert\Pi_{\mathrm{sym}}\vert\chi\rangle=\mathrm{Tr}\big(\Pi_{\mathrm{sym}}\,\lvert\chi\rangle\langle\chi\rvert\big)$
For a pure register state this is the symmetric-projector corollary, rewritten with $\langle\chi\vert M\vert\chi\rangle=\mathrm{Tr}(M\lvert\chi\rangle\langle\chi\rvert)$ (cyclicity).
Step 3:
$\omega=\sum_mq_m\lvert\chi_m\rangle\langle\chi_m\rvert\ \Rightarrow\ P(0)=\sum_mq_m\,\mathrm{Tr}\big(\Pi_{\mathrm{sym}}\lvert\chi_m\rangle\langle\chi_m\rvert\big)=\mathrm{Tr}\big(\Pi_{\mathrm{sym}}\,\omega\big)$
Every density operator has a spectral decomposition with $q_m\ge0$ , $\sum_mq_m=1$ ; linearity of the first line in $\omega$ carries the pure-state formula over to every mixed register state.
Step 4:
$\omega=\rho\otimes\sigma:\quad P(0)=\tfrac12\,\mathrm{Tr}(\rho\otimes\sigma)+\tfrac12\,\mathrm{Tr}\big[\mathrm{SWAP}(\rho\otimes\sigma)\big]=\tfrac12\,\mathrm{Tr}\rho\,\mathrm{Tr}\sigma+\tfrac12\,\mathrm{Tr}(\rho\sigma)=\tfrac12\big(1+\mathrm{Tr}(\rho\sigma)\big)$
Insert $\Pi_{\mathrm{sym}}=\frac12(I+\mathrm{SWAP})$ , use $\mathrm{Tr}(A\otimes B)=\mathrm{Tr}A\,\mathrm{Tr}B$ , the SWAP trick, and unit traces. $P(1)=1-P(0)$ .
Step 5:
$\rho=\sum_kp_k\lvert e_k\rangle\langle e_k\rvert:\quad\mathrm{Tr}(\rho\sigma)=\sum_kp_k\langle e_k\vert\sigma\vert e_k\rangle\in[0,1]$
Spectral decomposition of $\rho$ and linearity of the trace. Each $\langle e_k\vert\sigma\vert e_k\rangle$ lies in $[0,1]$ because $\sigma$ is positive semidefinite with eigenvalues in $[0,1]$ , and the weights $p_k\ge0$ sum to $1$ .
Step 6:
$\rho=\lvert\psi\rangle\langle\psi\rvert,\ \sigma=\lvert\phi\rangle\langle\phi\rvert:\quad\mathrm{Tr}(\rho\sigma)=\langle\psi\vert\phi\rangle\langle\phi\vert\psi\rangle=\lvert\langle\psi\vert\phi\rangle\rvert^2;\qquad\sigma=\rho:\ P(0)=\tfrac12\big(1+\mathrm{Tr}\,\rho^2\big)$
The pure-state theorem is recovered, and two copies of one state reveal its purity, which equals $1$ exactly for pure states.

∎

Derivation

Example: purity of a qubit and a mixed pair

Step 1:
$\rho=\tfrac12\big(I+\vec r\cdot\vec\sigma\big)\ \Rightarrow\ \mathrm{Tr}\,\rho^2=\tfrac12\big(1+\lvert\vec r\rvert^2\big)$
The Bloch formula $\mathrm{Tr}(\rho\rho')=\frac12(1+\vec r\cdot\vec r\,')$ of the previous lesson with $\rho'=\rho$ .
Step 2:
$\vec r=(0,0,0.6):\quad\mathrm{Tr}\,\rho^2=\tfrac12(1+0.36)=0.68,\qquad P(0)=\tfrac12(1+0.68)=0.84$
A qubit with $\rho=\mathrm{diag}(0.8,0.2)$ ; two copies of it pass the SWAP test with probability $0.84$ .
Step 3:
$\rho=\begin{pmatrix}0.7&0.2-0.1i\\0.2+0.1i&0.3\end{pmatrix},\ \ \sigma=\begin{pmatrix}0.4&0.1i\\-0.1i&0.6\end{pmatrix}$
Two valid mixed states: Hermitian, trace $1$ , and determinants $0.21-0.05=0.16>0$ and $0.24-0.01=0.23>0$ , so both eigenvalues are positive.
Step 4:
$\mathrm{Tr}(\rho\sigma)=\sum_{i,j}\rho_{ij}\sigma_{ji}=0.7\cdot0.4+(0.2-0.1i)(-0.1i)+(0.2+0.1i)(0.1i)+0.3\cdot0.6$
$\mathrm{Tr}(\rho\sigma)=\sum_{ij}\rho_{ij}\sigma_{ji}$ , the formula of the SWAP trick.
Step 5:
$=0.28+(-0.01-0.02i)+(-0.01+0.02i)+0.18=0.44,\qquad P(0)=\tfrac12(1+0.44)=0.72$
The imaginary parts cancel, as they must for a product of Hermitian matrices under the trace. The NumPy cell at the end of the lesson reproduces $0.44$ from $\mathrm{Tr}[\mathrm{SWAP}(\rho\otimes\sigma)]$ and $P(0)=0.72$ from the full three-qubit density-matrix simulation.

Result

\boxed{P(0)=\tfrac12\big(1+\mathrm{Tr}(\rho\sigma)\big)=0.72\quad\text{for the pair above},\qquad P(0)=\tfrac12\big(1+\mathrm{Tr}\,\rho^2\big)=0.84\quad\text{for two copies of }\mathrm{diag}(0.8,0.2)}

Warning

\mathrm{Tr}(\rho\sigma)

Quick check

\rho=\sigma=\frac12I

From shots to an estimate#

Theorem

The SWAP-test fidelity estimator

N

Proof (6 steps)

Step 1:
$B_s=\mathbf 1\{\text{shot }s\text{ returns }0\},\quad P(B_s=1)=P_0,\quad N_0=\sum_{s=1}^NB_s$
Each shot uses fresh copies and a fresh ancilla, so the indicators are independent Bernoulli variables with success probability $P_0$ .
Step 2:
$\mathbb E[\hat P(0)]=\frac1N\sum_s\mathbb E[B_s]=P_0,\qquad\mathrm{Var}[\hat P(0)]=\frac1{N^2}\sum_s\mathrm{Var}[B_s]=\frac{P_0(1-P_0)}N$
Linearity of expectation; variances of independent variables add; $\mathrm{Var}[B_s]=\mathbb E[B_s^2]-\mathbb E[B_s]^2=P_0-P_0^2$ .
Step 3:
$\mathbb E[\hat F]=2\,\mathbb E[\hat P(0)]-1=2P_0-1=(1+F)-1=F$
The estimator is an affine function of $\hat P(0)$ ; insert $P_0=\frac12(1+F)$ from the acceptance theorem. It is unbiased.
Step 4:
$\mathrm{Var}[\hat F]=\mathrm{Var}[2\hat P(0)-1]=4\,\mathrm{Var}[\hat P(0)]=\frac{4P_0(1-P_0)}N$
$\mathrm{Var}[aX+b]=a^2\mathrm{Var}[X]$ .
Step 5:
$4P_0(1-P_0)=4\cdot\frac{1+F}2\cdot\frac{1-F}2=(1+F)(1-F)=1-F^2$
$1-P_0=\frac12(1-F)$ , and the difference of squares.
Step 6:
$F\in[0,1]\ \Rightarrow\ 0\le1-F^2\le1,\qquad\mathrm{Var}[\hat F]=0\iff F=1$
The worst case is $F=0$ , where $P_0=\frac12$ is a fair coin. A single estimate may fall outside $[0,1]$ : for $F$ near $0$ the event $N_0<N/2$ has probability close to $\frac12$ and gives $\hat F<0$ . Clamping to $[0,1]$ , as the library routine $\mathtt{swapTestEstimate}$ does, keeps the value in range but introduces a bias near the ends.

∎

Lemma

Hoeffding’s inequality for Bernoulli averages

B_1,\dots,B_N

Proof (7 steps)

Step 1:
$\mathbb E\big[e^{sB}\big]=(1-p)e^{0}+p\,e^{s}=1-p+p\,e^{s},\qquad L(s)=\ln\mathbb E\big[e^{s(B-p)}\big]=-sp+\ln\big(1-p+pe^s\big)$
Moment generating function of one Bernoulli variable, and the logarithm of the centred one.
Step 2:
$L(0)=0,\qquad L'(s)=-p+\frac{pe^s}{1-p+pe^s}=-p+q(s),\qquad L'(0)=0$
Differentiate; $q(s)=\frac{pe^s}{1-p+pe^s}\in[0,1]$ , and $q(0)=p$ .
Step 3:
$L''(s)=q'(s)=\frac{pe^s(1-p+pe^s)-pe^s\cdot pe^s}{(1-p+pe^s)^2}=q(s)\big(1-q(s)\big)\le\tfrac14$
Quotient rule; the numerator is $pe^s(1-p)$ , so $q'=q(1-q)$ , which is at most $\frac14$ because $u(1-u)=\frac14-(u-\frac12)^2$ .
Step 4:
$L(s)=L(0)+sL'(0)+\tfrac{s^2}2L''(\xi)\le\frac{s^2}8\qquad(\text{some }\xi\text{ between }0\text{ and }s)$
Taylor's theorem with the Lagrange remainder (Hoeffding's lemma for Bernoulli variables): $\mathbb E[e^{s(B-p)}]\le e^{s^2/8}$ .
Step 5:
$P\big(\bar B-p\ge t\big)=P\big(e^{sN(\bar B-p)}\ge e^{sNt}\big)\le e^{-sNt}\,\mathbb E\Big[\prod_{s'=1}^Ne^{s(B_{s'}-p)}\Big]=e^{-sNt}\prod_{s'=1}^N\mathbb E\big[e^{s(B_{s'}-p)}\big]$
For $s>0$ the exponential is increasing; Markov's inequality $P(X\ge a)\le\mathbb E[X]/a$ for the nonnegative variable $e^{sN(\bar B-p)}$ ; independence factorises the expectation of the product.
Step 6:
$\le\exp\Big(-sNt+\frac{Ns^2}8\Big)\ \xrightarrow{\ s=4t\ }\ \exp\big(-4Nt^2+2Nt^2\big)=e^{-2Nt^2}$
Hoeffding's lemma for each factor, then minimise the exponent $-sNt+Ns^2/8$ over $s$ : the derivative $-Nt+Ns/4$ vanishes at $s=4t$ .
Step 7:
$P\big(\lvert\bar B-p\rvert\ge t\big)\le P\big(\bar B-p\ge t\big)+P\big((1-\bar B)-(1-p)\ge t\big)\le2e^{-2Nt^2}$
Union bound over the two tails; the lower tail of $\bar B$ is the upper tail of the average of the Bernoulli variables $1-B_s$ with success probability $1-p$ , to which the same bound applies.

∎

Theorem

Shot budget of the SWAP test

N\ \ge\ \frac{2\ln(2/\delta)}{\varepsilon^2},

Proof (4 steps)

Step 1:
$\lvert\hat F-F\rvert=\big\lvert\big(2\hat P(0)-1\big)-\big(2P_0-1\big)\big\rvert=2\,\big\lvert\hat P(0)-P_0\big\rvert$
The estimator and its mean differ by twice the error of the Bernoulli average: an error $\varepsilon$ on $\hat F$ is an error $\varepsilon/2$ on $\hat P(0)$ .
Step 2:
$P\big(\lvert\hat F-F\rvert>\varepsilon\big)\le P\Big(\big\lvert\hat P(0)-P_0\big\rvert\ge\frac\varepsilon2\Big)\le2\exp\Big(-2N\frac{\varepsilon^2}4\Big)=2e^{-N\varepsilon^2/2}$
Hoeffding's inequality with $p=P_0$ and tolerance $t=\varepsilon/2$ .
Step 3:
$2e^{-N\varepsilon^2/2}\le\delta\iff-\frac{N\varepsilon^2}2\le\ln\frac\delta2\iff N\ge\frac{2\ln(2/\delta)}{\varepsilon^2}$
Take logarithms (monotone) and multiply by $-2/\varepsilon^2<0$ , which reverses the inequality.
Step 4:
$P\big(\lvert\hat K-K\rvert\ge\varepsilon\big)\le2e^{-2N\varepsilon^2}\le\delta\iff N\ge\frac{\ln(2/\delta)}{2\varepsilon^2}=\frac14\cdot\frac{2\ln(2/\delta)}{\varepsilon^2}$
The inversion test estimates $K$ directly as a Bernoulli frequency, so Hoeffding applies with $t=\varepsilon$ , without the factor $2$ .

∎

Derivation

Worked shot budget: ε = 0.01, δ = 0.05

Step 1:
$\ln\frac2\delta=\ln40=3.688879\ldots$
A $95\,\%$ guarantee.
Step 2:
$N\ge\frac{2\cdot3.688879}{(0.01)^2}=73777.6\ \Rightarrow\ N=73778$
Hoeffding's budget for the SWAP test; for $\varepsilon=0.05$ the same formula gives $N=2952$ .
Step 3:
$N_{\mathrm{inv}}\ge\frac{3.688879}{2\cdot(0.01)^2}=18444.4\ \Rightarrow\ N_{\mathrm{inv}}=18445$
The inversion test for the same precision and confidence.
Step 4:
$F=\tfrac34:\quad1.96\sqrt{\frac{1-F^2}N}\le0.01\iff N\ge\frac{1.96^2\cdot0.4375}{10^{-4}}=16807$
The normal approximation with the true variance $(1-F^2)/N$ asks for fewer shots, but it requires knowing $F$ and is only asymptotic. Hoeffding's bound holds for every $N$ and every pair of states, which is why it is used to plan experiments.

Result

\boxed{\varepsilon=0.01,\ \delta=0.05:\qquad N_{\mathrm{SWAP}}=73778,\qquad N_{\mathrm{inv}}=18445}

Corollary

Concentrated kernels cost about 4^n shots with the SWAP test

F\approx2^{-n}

Proof (5 steps)

Step 1:
$\sqrt{\frac{1-F^2}N}\le\varepsilon_rF\iff N\ge\frac{1-F^2}{\varepsilon_r^2F^2}$
Square the relative-precision requirement with the SWAP-test variance and solve for $N$ .
Step 2:
$F=2^{-n}:\quad\frac{1-4^{-n}}{\varepsilon_r^2\,4^{-n}}=\frac{4^n-1}{\varepsilon_r^2}$
Multiply numerator and denominator by $4^n$ .
Step 3:
$\sqrt{\frac{F(1-F)}N}\le\varepsilon_rF\iff N\ge\frac{1-F}{\varepsilon_r^2F}=\frac{2^n-1}{\varepsilon_r^2}\quad(F=2^{-n})$
The inversion-test variance $K(1-K)/N$ vanishes as $K\to0$ , while the SWAP-test variance $(1-F^2)/N$ tends to its maximum $1/N$ : a near-zero overlap means a fair coin on the ancilla, the noisiest possible signal.
Step 4:
$\varepsilon=c\,2^{-n}:\quad N\ge\frac{2\ln(2/\delta)}{c^2\,4^{-n}}=\frac{2\ln(2/\delta)}{c^2}\,4^n$
Hoeffding's budget with a tolerance below the value to be resolved.
Step 5:
$n=10,\ \varepsilon_r=0.1:\quad N_{\mathrm{SWAP}}\approx1.05\times10^8,\qquad N_{\mathrm{inv}}\approx1.02\times10^5$
The values $(4^{10}-1)/0.01$ and $(2^{10}-1)/0.01$ : ten qubits already separate the two tests by three orders of magnitude, per kernel entry.

∎

SWAP-test samplerSwapTestSampler

Two single-qubit states on Bloch spheres; sampled SWAP-test acceptance probability with error bars against the exact value ½(1 + |⟨ψ|φ⟩|²).

State

|a\rangle

θ of state Aπ

φ of state A0

State

|b\rangle

θ of state B0

φ of state B0

$F = |\langle a|b\rangle|^2 =$ 0· $P(0) = \tfrac{1}{2}(1 + F) =$ 0.5

Simulated circuit: $P(q_0 = 0) =$ 0.5 (matches the closed form to 10⁻¹²)

Shots N (log scale)200

seed 1

sampling…

Shots for $\mathrm{SE}(\hat F) \le 0.01$ : 10000; for 0.05: 400 $\big(N = \lceil 4P_0(1-P_0)/\varepsilon^2\rceil\big)$

Acceptance probability P(0)

Fidelity F = |⟨a|b⟩|²

\lvert1\rangle

\mathtt{swapTestCircuit}

TypeScriptrunnable

import type { CircuitIR } from '@/lib/quantum-simulator';
import { mulberry32, runCircuit, runStatevector } from '@/lib/quantum-simulator';
import { swapTestCircuit, swapTestProbability } from '@/lib/qml';

// One-qubit preparations: |psi> = RY(pi/3)|0> and |phi> = |0>.
const prepPsi: CircuitIR = { version: 1, numQubits: 1, numClbits: 0, ops: [{ kind: 'gate', gate: 'RY', targets: [0], params: [Math.PI / 3] }] };
const prepPhi: CircuitIR = { version: 1, numQubits: 1, numClbits: 0, ops: [] };

// (1) The SWAP-test circuit: ancilla = qubit 0, |psi> on qubit 1, |phi> on qubit 2, ancilla measured into clbit 0.
const test = swapTestCircuit(1)(prepPsi, prepPhi);
console.log('ops: ' + test.ops.map((op) => (op.kind === 'gate' ? op.gate + '(' + op.targets.join(',') + ')' : op.kind)).join('; '));

// (2) Exact values: F = |<psi|phi>|^2 and P(0) = (1 + F)/2.
const F = runStatevector(prepPsi).fidelity(runStatevector(prepPhi));
const p0 = swapTestProbability(runStatevector(prepPsi), runStatevector(prepPhi));
console.log('F = ' + F.toFixed(12) + '   P(0) = ' + p0.toFixed(12) + '   (1 + F)/2 = ' + ((1 + F) / 2).toFixed(12));

// (3) Shot estimates F_hat = 2 N0/N - 1 from the simulator's seeded sampler, with the standard deviation sqrt((1 - F^2)/N).
for (const shots of [100, 1000, 10000, 100000]) {
  const n0 = runCircuit(test, { shots, seed: 40 }).counts?.['0'] ?? 0;
  console.log('N = ' + shots + ': N0 = ' + n0 + '   F_hat = ' + ((2 * n0) / shots - 1).toFixed(4) + '   std = ' + Math.sqrt((1 - F * F) / shots).toFixed(4));
}

// (4) Hoeffding: N = ceil(2 ln(2/delta) / eps^2) shots give |F_hat - F| <= eps with probability >= 1 - delta.
const eps = 0.05;
const delta = 0.05;
const N = Math.ceil((2 * Math.log(2 / delta)) / eps ** 2);
const rng = mulberry32(40);
const repetitions = 2000;
let inside = 0;
let worst = 0;
for (let r = 0; r < repetitions; r++) {
  let n0 = 0;
  for (let s = 0; s < N; s++) if (rng() < p0) n0++;
  const err = Math.abs((2 * n0) / N - 1 - F);
  worst = Math.max(worst, err);
  if (err <= eps) inside++;
}
console.log('Hoeffding N = ' + N + ': ' + inside + ' of ' + repetitions + ' experiments within eps = ' + eps + ' (largest error ' + worst.toFixed(4) + ')');
console.log('normal-approximation N = ' + Math.ceil((1.96 ** 2 * (1 - F * F)) / eps ** 2));

// (5) Orthogonal states |1> and |0>: P(0) = 1/2, where the variance (1 - F^2)/N = 1/N is largest.
const prepOne: CircuitIR = { version: 1, numQubits: 1, numClbits: 0, ops: [{ kind: 'gate', gate: 'X', targets: [0] }] };
console.log('orthogonal states: P(0) = ' + swapTestProbability(runStatevector(prepOne), runStatevector(prepPhi)).toFixed(12));

Expected output

ops: RY(1); H(0); CSWAP(0,1,2); H(0); measure
F = 0.750000000000   P(0) = 0.875000000000   (1 + F)/2 = 0.875000000000
N = 100: N0 = 86   F_hat = 0.7200   std = 0.0661
N = 1000: N0 = 883   F_hat = 0.7660   std = 0.0209
N = 10000: N0 = 8703   F_hat = 0.7406   std = 0.0066
N = 100000: N0 = 87577   F_hat = 0.7515   std = 0.0021
Hoeffding N = 2952: 2000 of 2000 experiments within eps = 0.05 (largest error 0.0454)
normal-approximation N = 673
orthogonal states: P(0) = 0.500000000000

F=0.75

Quick check

\lvert\hat F-F\rvert\le0.05

Compiling the Fredkin gate#

\mathrm{CCX}_{c_1,c_2\to t}\lvert x_{c_1},x_{c_2},x_t\rangle=\lvert x_{c_1},x_{c_2},x_t\oplus x_{c_1}x_{c_2}\rangle

Theorem

Fredkin from two CNOTs and a Toffoli

\mathrm{CSWAP}_{0;1,2}=\mathrm{CNOT}_{2\to1}\;\mathrm{CCX}_{0,1\to2}\;\mathrm{CNOT}_{2\to1}.

Proof (7 steps)

Step 1:
$\mathrm{CNOT}_{2\to1}:\ (c,a,b)\mapsto(c,\,a\oplus b,\,b),\qquad\mathrm{CCX}_{0,1\to2}:\ (c,a,b)\mapsto(c,\,a,\,b\oplus ca)$
Bit maps of the factors on $\lvert c\,a\,b\rangle$ . All three gates and $\mathrm{CSWAP}$ are permutation matrices of the basis, and a linear map is determined by its values on a basis, so it suffices to show that the composed bit map is $(c,a,b)\mapsto(c,a,b)$ for $c=0$ and $(c,b,a)$ for $c=1$ .
Step 2:
$c\ \text{is unchanged by every factor}$
Qubit $0$ is only ever a control. So the product preserves the subspaces $c=0$ and $c=1$ , and we can argue case by case.
Step 3:
$c=0:\quad(a,b)\xrightarrow{\mathrm{CNOT}_{2\to1}}(a\oplus b,\,b)\xrightarrow{\ \mathrm{CCX}\ =\ I\ }(a\oplus b,\,b)\xrightarrow{\mathrm{CNOT}_{2\to1}}(a\oplus b\oplus b,\,b)=(a,\,b)$
With $c=0$ the Toffoli adds $ca=0$ and acts as the identity, and $\mathrm{CNOT}_{2\to1}^2=I$ because $b\oplus b=0$ . This is the action of $\mathrm{CSWAP}$ for $c=0$ .
Step 4:
$c=1:\quad\mathrm{CCX}_{0,1\to2}\big\vert_{c=1}:\ (a,b)\mapsto(a,\,b\oplus a)=\mathrm{CNOT}_{1\to2}$
With $c=1$ the Toffoli adds $1\cdot a=a$ to the target: a CNOT from qubit $1$ to qubit $2$ .
Step 5:
$(a,b)\xrightarrow{\mathrm{CNOT}_{2\to1}}(a\oplus b,\,b)\xrightarrow{\mathrm{CNOT}_{1\to2}}\big(a\oplus b,\,b\oplus a\oplus b\big)=(a\oplus b,\,a)\xrightarrow{\mathrm{CNOT}_{2\to1}}\big(a\oplus b\oplus a,\,a\big)=(b,\,a)$
The three-CNOT SWAP identity, by following the bits: $x\oplus x=0$ and $\oplus$ is associative and commutative.
Step 6:
$\mathrm{CNOT}_{2\to1}\,\mathrm{CCX}_{0,1\to2}\,\mathrm{CNOT}_{2\to1}=\lvert0\rangle\langle0\rvert\otimes I_4+\lvert1\rangle\langle1\rvert\otimes\mathrm{SWAP}_{1,2}=\mathrm{CSWAP}_{0;1,2}$
The two cases combine into the operator form of the Fredkin gate.
Step 7:
$\lvert101\rangle\mapsto\lvert111\rangle\mapsto\lvert110\rangle\mapsto\lvert110\rangle,\qquad\lvert110\rangle\mapsto\lvert110\rangle\mapsto\lvert111\rangle\mapsto\lvert101\rangle$
Spot check on the two basis states that the Fredkin gate moves, layer by layer.

∎

Circuit · 3 qubits

\mathrm{CNOT}(2,1);\ \mathrm{CCX}(0,1,2);\ \mathrm{CNOT}(2,1)

U = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}

Proposition

Two-qubit gate count of the SWAP test

8

Proof (4 steps)

Step 1:
$\#\mathrm{CNOT}(\mathrm{CSWAP})=\underbrace{2}_{\mathrm{CNOT}_{2\to1}\ \text{twice}}+\underbrace{6}_{\mathrm{CCX}}=8$
Count the factors of the decomposition, using the six-CNOT Toffoli circuit.
Step 2:
$\#T\text{-type}(\mathrm{CSWAP})=7,\qquad\#H(\mathrm{CSWAP})=2$
The CNOTs of the decomposition contribute no single-qubit gates; the Toffoli circuit contributes seven $T/T^\dagger$ gates and two Hadamards.
Step 3:
$n\ \mathrm{CSWAP}:\quad8n\ \mathrm{CNOT},\quad7n\ T\text{-type},\quad2n+2\ H$
The $n$ -qubit test consists of $n$ Fredkin gates plus the two Hadamards on the ancilla.
Step 4:
$n=1,\ \text{gate set }\{H,\mathrm{CNOT},\mathrm{CCX}\}:\quad H;\ \mathrm{CNOT};\ \mathrm{CCX};\ \mathrm{CNOT};\ H\ =\ 5\ \text{gates}$
When the Toffoli is available as a primitive, as in the lab, the decomposed test has exactly five gates.

∎

On hardware

8

Quick check

How many CNOTs does the SWAP test for three-qubit states cost when every Fredkin gate is compiled with the decomposition above and a six-CNOT Toffoli?

The Hadamard test#

U

Theorem

Hadamard test for the real part

U

Proof (5 steps)

Step 1:
$\lvert0\rangle\lvert\psi\rangle\xrightarrow{H_0}\tfrac1{\sqrt2}\big(\lvert0\rangle\lvert\psi\rangle+\lvert1\rangle\lvert\psi\rangle\big)\xrightarrow{C(U)}\tfrac1{\sqrt2}\big(\lvert0\rangle\lvert\psi\rangle+\lvert1\rangle U\lvert\psi\rangle\big)$
The Hadamard prepares $\lvert+\rangle$ on the ancilla; the controlled unitary acts on the $\lvert1\rangle$ branch only.
Step 2:
$\xrightarrow{H_0}\tfrac12\lvert0\rangle\big(\lvert\psi\rangle+U\lvert\psi\rangle\big)+\tfrac12\lvert1\rangle\big(\lvert\psi\rangle-U\lvert\psi\rangle\big)$
$H\lvert0\rangle=\frac1{\sqrt2}(\lvert0\rangle+\lvert1\rangle)$ , $H\lvert1\rangle=\frac1{\sqrt2}(\lvert0\rangle-\lvert1\rangle)$ , collected by ancilla value.
Step 3:
$P(0)=\tfrac14\big\lVert\lvert\psi\rangle+U\lvert\psi\rangle\big\rVert^2=\tfrac14\Big(\lVert\psi\rVert^2+\lVert U\psi\rVert^2+2\,\mathrm{Re}\langle\psi\vert U\vert\psi\rangle\Big)$
Born rule on the ancilla and the expansion $\lVert u+v\rVert^2=\lVert u\rVert^2+\lVert v\rVert^2+2\,\mathrm{Re}\langle u\vert v\rangle$ .
Step 4:
$\lVert U\psi\rVert^2=\langle\psi\vert U^\dagger U\vert\psi\rangle=\langle\psi\vert\psi\rangle=1\ \Rightarrow\ P(0)=\tfrac14\big(2+2\,\mathrm{Re}\langle\psi\vert U\vert\psi\rangle\big)=\tfrac12\big(1+\mathrm{Re}\langle\psi\vert U\vert\psi\rangle\big)$
Unitarity preserves the norm.
Step 5:
$P(1)=\tfrac14\big\lVert\lvert\psi\rangle-U\lvert\psi\rangle\big\rVert^2=\tfrac12\big(1-\mathrm{Re}\langle\psi\vert U\vert\psi\rangle\big),\qquad\mathbb E[Z_0]=P(0)-P(1)=\mathrm{Re}\langle\psi\vert U\vert\psi\rangle$
The same expansion with $v\mapsto-v$ ; the ancilla's $Z$ expectation is the difference of the two probabilities.

∎

Theorem

Hadamard test for the imaginary part

S^\dagger=\mathrm{diag}(1,-i)

Proof (6 steps)

Step 1:
$S^\dagger\tfrac1{\sqrt2}\big(\lvert0\rangle+\lvert1\rangle\big)=\tfrac1{\sqrt2}\big(\lvert0\rangle-i\lvert1\rangle\big)$
$S^\dagger$ multiplies the $\lvert1\rangle$ amplitude by $-i$ .
Step 2:
$\xrightarrow{C(U)}\tfrac1{\sqrt2}\big(\lvert0\rangle\lvert\psi\rangle-i\,\lvert1\rangle U\lvert\psi\rangle\big)\xrightarrow{H_0}\tfrac12\lvert0\rangle\big(\lvert\psi\rangle-iU\lvert\psi\rangle\big)+\tfrac12\lvert1\rangle\big(\lvert\psi\rangle+iU\lvert\psi\rangle\big)$
Controlled unitary on the $\lvert1\rangle$ branch, then the final Hadamard as before.
Step 3:
$P(0)=\tfrac14\big\lVert\lvert\psi\rangle-iU\lvert\psi\rangle\big\rVert^2=\tfrac14\Big(1+1+2\,\mathrm{Re}\langle\psi\vert(-iU)\vert\psi\rangle\Big)$
The norm expansion with $u=\lvert\psi\rangle$ , $v=-iU\lvert\psi\rangle$ , $\lVert v\rVert=1$ .
Step 4:
$z=\langle\psi\vert U\vert\psi\rangle=x+iy:\quad\mathrm{Re}(-iz)=\mathrm{Re}(-ix+y)=y=\mathrm{Im}\,z$
Multiplication by $-i$ rotates the complex plane by $-90^\circ$ and moves the imaginary part onto the real axis.
Step 5:
$P(0)=\tfrac12\big(1+\mathrm{Im}\langle\psi\vert U\vert\psi\rangle\big),\qquad P(1)=\tfrac14\big\lVert\lvert\psi\rangle+iU\lvert\psi\rangle\big\rVert^2=\tfrac12\big(1-\mathrm{Im}\langle\psi\vert U\vert\psi\rangle\big)$
Insert into the previous line; for $P(1)$ , $\mathrm{Re}(iz)=-\mathrm{Im}\,z$ .
Step 6:
$S:\ \tfrac1{\sqrt2}\big(\lvert0\rangle+i\lvert1\rangle\big)\ \Rightarrow\ P(0)=\tfrac12\big(1+\mathrm{Re}(iz)\big)=\tfrac12\big(1-\mathrm{Im}\,z\big)$
With $S$ the branch carries $+i$ , and $\mathrm{Re}(iz)=-y$ : the sign convention matters, and the numerical check below confirms it.

∎

Corollary

The SWAP test is the Hadamard test of SWAP

U=\mathrm{SWAP}_{A,B}

Proof (4 steps)

Step 1:
$C(\mathrm{SWAP}_{A,B})=\prod_i\mathrm{CSWAP}_{0;a_i,b_i}$
The controlled unitary of the Hadamard test is the controlled register swap of the SWAP test (controlled-product lemma), and the two circuits coincide gate for gate.
Step 2:
$\langle\psi\phi\vert\mathrm{SWAP}\vert\psi\phi\rangle=\langle\psi\phi\vert\phi\psi\rangle=\langle\psi\vert\phi\rangle\langle\phi\vert\psi\rangle=\lvert\langle\psi\vert\phi\rangle\rvert^2$
The swap exchanges the factors, and inner products of product vectors factorise.
Step 3:
$\mathrm{SWAP}^\dagger=\mathrm{SWAP}\ \Rightarrow\ \langle\chi\vert\mathrm{SWAP}\vert\chi\rangle\in\mathbb R\ \text{for every}\ \lvert\chi\rangle$
Expectation values of Hermitian operators are real: $\overline{\langle\chi\vert A\vert\chi\rangle}=\langle\chi\vert A^\dagger\vert\chi\rangle=\langle\chi\vert A\vert\chi\rangle$ . So the imaginary part vanishes even for entangled register states.
Step 4:
$P(0)=\tfrac12\big(1+\mathrm{Re}\langle\psi\phi\vert\mathrm{SWAP}\vert\psi\phi\rangle\big)=\tfrac12\big(1+\lvert\langle\psi\vert\phi\rangle\rvert^2\big)$
The Hadamard-test formula reproduces the acceptance theorem.

∎

Derivation

Example: U = R_Z(0.8) on the lab state

Step 1:
$\lvert\psi\rangle=R_Y(\tfrac\pi3)\lvert0\rangle=\tfrac{\sqrt3}2\lvert0\rangle+\tfrac12\lvert1\rangle,\qquad U=R_Z(0.8)=\mathrm{diag}\big(e^{-0.4i},e^{0.4i}\big)$
$R_Z(\theta)=e^{-i\theta Z/2}$ with $\theta=0.8$ .
Step 2:
$\langle\psi\vert U\vert\psi\rangle=\tfrac34e^{-0.4i}+\tfrac14e^{0.4i}=\cos0.4-\tfrac i2\sin0.4$
$\langle\psi\vert U\vert\psi\rangle=\sum_k\lvert\psi_k\rvert^2U_{kk}$ for diagonal $U$ ; Euler's formula: $\frac34(\cos0.4-i\sin0.4)+\frac14(\cos0.4+i\sin0.4)$ .
Step 3:
$\mathrm{Re}=\cos0.4=0.921061,\qquad\mathrm{Im}=-\tfrac12\sin0.4=-0.194709$
Numerical values.
Step 4:
$P_{\mathrm{Re}}(0)=\tfrac12(1+0.921061)=0.960530,\qquad P_{S^\dagger}(0)=\tfrac12(1-0.194709)=0.402645$
The two Hadamard-test variants. The NumPy cell recovers both numbers from $2P(0)-1$ .

Result

\boxed{\langle\psi\vert R_Z(0.8)\vert\psi\rangle=0.921061-0.194709\,i}

Quick check

U=-I

Worked example: the lab state#

Derivation

SWAP test of R_Y(π/3)|0⟩ against |0⟩, amplitude by amplitude

Step 1:
$\lvert\psi\rangle=R_Y(\tfrac\pi3)\lvert0\rangle=\cos\tfrac\pi6\lvert0\rangle+\sin\tfrac\pi6\lvert1\rangle=\tfrac{\sqrt3}2\lvert0\rangle+\tfrac12\lvert1\rangle,\qquad\lvert\phi\rangle=\lvert0\rangle$
First column of $R_Y(\theta)=\begin{pmatrix}\cos\frac\theta2&-\sin\frac\theta2\\\sin\frac\theta2&\cos\frac\theta2\end{pmatrix}$ at $\theta=\frac\pi3$ .
Step 2:
$F=\lvert\langle\psi\vert\phi\rangle\rvert^2=\cos^2\tfrac\pi6=\tfrac34,\qquad P(0)=\tfrac12\big(1+\tfrac34\big)=\tfrac78$
The prediction of the acceptance theorem; the remaining steps confirm it amplitude by amplitude.
Step 3:
$\lvert\Psi_0\rangle=\lvert0\rangle\lvert\psi\rangle\lvert0\rangle=\tfrac{\sqrt3}2\lvert000\rangle+\tfrac12\lvert010\rangle=\big(\tfrac{\sqrt3}2,0,\tfrac12,0,0,0,0,0\big)^{\top}$
Kronecker product with the ancilla as the leftmost factor; index $4c+2a+b$ , so $\lvert010\rangle$ is index $2$ .
Step 4:
$\lvert\Psi_1\rangle=\tfrac{\sqrt6}4\lvert000\rangle+\tfrac{\sqrt2}4\lvert010\rangle+\tfrac{\sqrt6}4\lvert100\rangle+\tfrac{\sqrt2}4\lvert110\rangle=\big(\tfrac{\sqrt6}4,0,\tfrac{\sqrt2}4,0,\tfrac{\sqrt6}4,0,\tfrac{\sqrt2}4,0\big)^{\top}$
$H$ on the ancilla copies each amplitude into the $c=1$ half with the factor $\frac1{\sqrt2}$ : $\frac{\sqrt3}2\cdot\frac1{\sqrt2}=\frac{\sqrt6}4\approx0.612372$ and $\frac12\cdot\frac1{\sqrt2}=\frac{\sqrt2}4\approx0.353553$ .
Step 5:
$\lvert\Psi_2\rangle=\tfrac{\sqrt6}4\lvert000\rangle+\tfrac{\sqrt2}4\lvert010\rangle+\tfrac{\sqrt6}4\lvert100\rangle+\tfrac{\sqrt2}4\lvert101\rangle=\big(\tfrac{\sqrt6}4,0,\tfrac{\sqrt2}4,0,\tfrac{\sqrt6}4,\tfrac{\sqrt2}4,0,0\big)^{\top}$
The Fredkin gate moves the amplitude of $\lvert110\rangle$ (index $6$ ) to $\lvert101\rangle$ (index $5$ ); $\lvert100\rangle$ has equal targets and stays.
Step 6:
$H_0:\ \lvert0\,ab\rangle\mapsto\tfrac1{\sqrt2}\big(\lvert0\,ab\rangle+\lvert1\,ab\rangle\big),\quad\lvert1\,ab\rangle\mapsto\tfrac1{\sqrt2}\big(\lvert0\,ab\rangle-\lvert1\,ab\rangle\big)$
The final Hadamard combines the amplitudes of each pair of indices $(k,k+4)$ into their sum and difference over $\sqrt2$ .
Step 7:
$\lvert000\rangle:\ \tfrac1{\sqrt2}\big(\tfrac{\sqrt6}4+\tfrac{\sqrt6}4\big)=\tfrac{\sqrt3}2,\quad\lvert100\rangle:\ \tfrac1{\sqrt2}\big(\tfrac{\sqrt6}4-\tfrac{\sqrt6}4\big)=0,\quad\lvert010\rangle,\lvert110\rangle:\ \tfrac1{\sqrt2}\cdot\tfrac{\sqrt2}4=\tfrac14$
Pairs $(0,4)$ and $(2,6)$ : the pair $(0,4)$ interferes completely constructively and destructively, and the pair $(2,6)$ has a single nonzero amplitude, at index $2$ .
Step 8:
$\lvert001\rangle:\ \tfrac1{\sqrt2}\cdot\tfrac{\sqrt2}4=\tfrac14,\qquad\lvert101\rangle:\ -\tfrac1{\sqrt2}\cdot\tfrac{\sqrt2}4=-\tfrac14,\qquad\lvert011\rangle,\lvert111\rangle:\ 0$
Pair $(1,5)$ has only the amplitude at index $5$ , which enters the $c=1$ output with a minus sign; pair $(3,7)$ is empty.
Step 9:
$\lvert\Psi_3\rangle=\big(\tfrac{\sqrt3}2,\ \tfrac14,\ \tfrac14,\ 0,\ 0,\ -\tfrac14,\ \tfrac14,\ 0\big)^{\top}\approx(0.866025,\,0.25,\,0.25,\,0,\,0,\,-0.25,\,0.25,\,0)^{\top}$
All eight amplitudes. Norm check: $\frac34+4\cdot\frac1{16}=1$ . It agrees with the theorem: $\frac12(\lvert\psi\phi\rangle+\lvert\phi\psi\rangle)=\frac{\sqrt3}2\lvert00\rangle+\frac14\lvert10\rangle+\frac14\lvert01\rangle$ and $\frac12(\lvert\psi\phi\rangle-\lvert\phi\psi\rangle)=\frac14\lvert10\rangle-\frac14\lvert01\rangle$ .
Step 10:
$P(0)=\tfrac34+\tfrac1{16}+\tfrac1{16}=\tfrac78=0.875,\qquad P(1)=\tfrac1{16}+\tfrac1{16}=\tfrac18,\qquad\langle Z_0\rangle=\tfrac78-\tfrac18=\tfrac34$
Sum the squared moduli over indices $0$ – $3$ (ancilla $0$ ) and $4$ – $7$ (ancilla $1$ ). The ancilla expectation $\langle Z_0\rangle=2P(0)-1=F$ is the auxiliary quantity checked by the lab.

Result

\boxed{P(0)=\tfrac78,\qquad P(1)=\tfrac18,\qquad\hat F=2P(0)-1=\tfrac34=\cos^2\tfrac\pi6}

Circuit · 3 qubits

R_Y(\pi/3)

\lvert\psi\rangle = \tfrac{\sqrt{3}}{2}\lvert 000\rangle + \tfrac{1}{4}\lvert 001\rangle + \tfrac{1}{4}\lvert 010\rangle - \tfrac{1}{4}\lvert 101\rangle + \tfrac{1}{4}\lvert 110\rangle

|000⟩0.75
|001⟩0.0625
|010⟩0.0625
|011⟩0
|100⟩0
|101⟩0.0625
|110⟩0.0625
|111⟩0

0.72

Pythonrunnable

import numpy as np

# Basis |c a b> with qubit 0 (the ancilla c) as the most significant bit: index 4c + 2a + b.
def bits(k):
    return (k >> 2) & 1, (k >> 1) & 1, k & 1

def perm(f):
    """8 x 8 permutation matrix of the bit map (c, a, b) -> f(c, a, b)."""
    P = np.zeros((8, 8))
    for k in range(8):
        c, a, b = f(*bits(k))
        P[4 * c + 2 * a + b, k] = 1.0
    return P

CSWAP = perm(lambda c, a, b: (c, b, a) if c else (c, a, b))
CNOT21 = perm(lambda c, a, b: (c, a ^ b, b))
CCX = perm(lambda c, a, b: (c, a, b ^ (c & a)))
print("CSWAP: unitary", np.allclose(CSWAP.T @ CSWAP, np.eye(8)), "| self-inverse", np.allclose(CSWAP @ CSWAP, np.eye(8)),
      "| CNOT_21 CCX CNOT_21 = CSWAP", np.allclose(CNOT21 @ CCX @ CNOT21, CSWAP))

# (1) The SWAP test on |psi> = RY(pi/3)|0>, |phi> = |0>: all eight amplitudes after each layer.
H = np.array([[1.0, 1.0], [1.0, -1.0]]) / np.sqrt(2)
H0 = np.kron(H, np.eye(4))
psi = np.array([np.cos(np.pi / 6), np.sin(np.pi / 6)])
phi = np.array([1.0, 0.0])
state = np.kron([1.0, 0.0], np.kron(psi, phi))
for name, U in (("H", H0), ("CSWAP", CSWAP), ("H", H0)):
    state = U @ state
    print(f"after {name:5s}", " ".join(f"{v:+.6f}" for v in state + 0.0))
F = abs(np.vdot(psi, phi)) ** 2
p0 = float(np.sum(state[:4] ** 2))
print(f"F = {F:.6f}   P(0) = {p0:.6f}   (1 + F)/2 = {(1 + F) / 2:.6f}   P(1) = {1 - p0:.6f}")

# (2) Mixed states: Tr[SWAP (rho x sigma)] = Tr(rho sigma) and P(0) = (1 + Tr(rho sigma))/2.
SWAP = CSWAP[4:, 4:]
rho = np.array([[0.7, 0.2 - 0.1j], [0.2 + 0.1j, 0.3]])
sigma = np.array([[0.4, 0.1j], [-0.1j, 0.6]])
V = H0 @ CSWAP @ H0
out = V @ np.kron(np.diag([1.0, 0.0]), np.kron(rho, sigma)) @ V.conj().T
print(f"Tr[SWAP (rho x sigma)] = {np.trace(SWAP @ np.kron(rho, sigma)).real:.6f}   Tr(rho sigma) = {np.trace(rho @ sigma).real:.6f}   P(0) = {np.trace(out[:4, :4]).real:.6f}")

# (3) Hadamard test for U = RZ(0.8) on |psi>: P(0) = (1 + Re<psi|U|psi>)/2, with S^dagger: (1 + Im<psi|U|psi>)/2.
U = np.diag([np.exp(-0.4j), np.exp(0.4j)])
CU = np.block([[np.eye(2), np.zeros((2, 2))], [np.zeros((2, 2)), U]])
Hd, Sdg = np.kron(H, np.eye(2)), np.kron(np.diag([1.0, -1.0j]), np.eye(2))
z = np.vdot(psi, U @ psi)
for label, pre, exact in (("Re", np.eye(4), z.real), ("Im", Sdg, z.imag)):
    s = Hd @ CU @ pre @ Hd @ np.kron([1.0, 0.0], psi)
    print(f"Hadamard test ({label}): 2 P(0) - 1 = {2 * np.sum(np.abs(s[:2]) ** 2) - 1:+.6f}   exact = {exact:+.6f}")

# (4) Shots: F_hat = 2 N0/N - 1 with a seeded generator; Hoeffding N >= 2 ln(2/delta)/eps^2.
rng = np.random.default_rng(40)
for N in (100, 1000, 10000, 100000):
    n0 = int(np.count_nonzero(rng.random(N) < p0))
    print(f"N = {N:6d}: N0 = {n0:5d}   F_hat = {2 * n0 / N - 1:+.4f}   std = {np.sqrt((1 - F ** 2) / N):.4f}")
for eps in (0.05, 0.01):
    print(f"Hoeffding, eps = {eps}, delta = 0.05: N = {int(np.ceil(2 * np.log(2 / 0.05) / eps ** 2))}")
for n in (2, 5, 10, 20):
    K = 2.0 ** -n
    print(f"K = 2^-{n:<2d}: shots for 10% relative error  SWAP test {(1 - K ** 2) / (0.1 * K) ** 2:.3e}   inversion test {K * (1 - K) / (0.1 * K) ** 2:.3e}")

Expected output

CSWAP: unitary True | self-inverse True | CNOT_21 CCX CNOT_21 = CSWAP True
after H     +0.612372 +0.000000 +0.353553 +0.000000 +0.612372 +0.000000 +0.353553 +0.000000
after CSWAP +0.612372 +0.000000 +0.353553 +0.000000 +0.612372 +0.353553 +0.000000 +0.000000
after H     +0.866025 +0.250000 +0.250000 +0.000000 +0.000000 -0.250000 +0.250000 +0.000000
F = 0.750000   P(0) = 0.875000   (1 + F)/2 = 0.875000   P(1) = 0.125000
Tr[SWAP (rho x sigma)] = 0.440000   Tr(rho sigma) = 0.440000   P(0) = 0.720000
Hadamard test (Re): 2 P(0) - 1 = +0.921061   exact = +0.921061
Hadamard test (Im): 2 P(0) - 1 = -0.194709   exact = -0.194709
N =    100: N0 =    89   F_hat = +0.7800   std = 0.0661
N =   1000: N0 =   883   F_hat = +0.7660   std = 0.0209
N =  10000: N0 =  8737   F_hat = +0.7474   std = 0.0066
N = 100000: N0 = 87315   F_hat = +0.7463   std = 0.0021
Hoeffding, eps = 0.05, delta = 0.05: N = 2952
Hoeffding, eps = 0.01, delta = 0.05: N = 73778
K = 2^-2 : shots for 10% relative error  SWAP test 1.500e+03   inversion test 3.000e+02
K = 2^-5 : shots for 10% relative error  SWAP test 1.023e+05   inversion test 3.100e+03
K = 2^-10: shots for 10% relative error  SWAP test 1.049e+08   inversion test 1.023e+05
K = 2^-20: shots for 10% relative error  SWAP test 1.100e+14   inversion test 1.049e+08

R_Y(1,\pi/3)

References

H. Buhrman, R. Cleve, J. Watrous and R. de Wolf, Quantum fingerprinting, Physical Review Letters 87, 167902 (2001).doi:10.1103/PhysRevLett.87.167902
A. K. Ekert, C. M. Alves, D. K. L. Oi, M. Horodecki, P. Horodecki and L. C. Kwek, Direct estimations of linear and nonlinear functionals of a quantum state, Physical Review Letters 88, 217901 (2002).doi:10.1103/PhysRevLett.88.217901
J. C. Garcia-Escartin and P. Chamorro-Posada, Swap test and Hong-Ou-Mandel effect are equivalent, Physical Review A 87, 052330 (2013).doi:10.1103/PhysRevA.87.052330
L. Cincio, Y. Subaşı, A. T. Sornborger and P. J. Coles, Learning the quantum algorithm for state overlap, New Journal of Physics 20, 113022 (2018).doi:10.1088/1367-2630/aae94a
E. Fredkin and T. Toffoli, Conservative logic, International Journal of Theoretical Physics 21, 219–253 (1982).doi:10.1007/BF01857727
J. A. Smolin and D. P. DiVincenzo, Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate, Physical Review A 53, 2855 (1996).doi:10.1103/PhysRevA.53.2855
D. Aharonov, V. Jones and Z. Landau, A polynomial quantum algorithm for approximating the Jones polynomial, Algorithmica 55, 395–421 (2009).doi:10.1007/s00453-008-9168-0
W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58(301), 13–30 (1963).doi:10.1080/01621459.1963.10500830
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, Cambridge University Press (2010).doi:10.1017/CBO9780511976667
V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow and J. M. Gambetta, Supervised learning with quantum-enhanced feature spaces, Nature 567, 209–212 (2019).doi:10.1038/s41586-019-0980-2

Hands-on labs

Build the SWAP test
1 step · auto-graded
$\lvert\psi\rangle=R_Y(\pi/3)\lvert0\rangle$
Open lab

Why a second overlap test?#

The overlap-estimation task

The controlled-SWAP (Fredkin) gate#

Controlled-SWAP (Fredkin) gate

The acceptance probability#

Registers of n qubits#

Mixed states and the SWAP trick#

From shots to an estimate#

Compiling the Fredkin gate#

The Hadamard test#

Worked example: the lab state#

References

Hands-on labs

Build the SWAP test