Quantum Computation · Study tools

InteractiveNielsen–Chuang, Ch. 1: Introduction and overview

Qubits and the Bloch sphere

A qubit's state is a pair of complex numbers. Throw away the overall phase, which no experiment can see, and what is left is a point on a sphere. Every single-qubit gate is then a rotation of that sphere, and you can watch each one turn the state.

The idea

Qubit. A unit vector

\ket{\psi}=\alpha\ket{0}+\beta\ket{1}

in

\C^2

, with

|\alpha|^2+|\beta|^2=1

. Measuring in the computational basis gives

0

with probability

|\alpha|^2

and

1

with probability

|\beta|^2

.

Bloch sphere. The states

\ket\psi

and

e^{i\gamma}\ket\psi

give the same probabilities for every measurement, so up to this global phase every qubit state can be written

\ket\psi=\cos\tfrac\theta2\,\ket0+e^{i\varphi}\sin\tfrac\theta2\,\ket1,\qquad \vec r=(\sin\theta\cos\varphi,\ \sin\theta\sin\varphi,\ \cos\theta).

$\ket0$ is the north pole, $\ket1$ the south pole, and $\ket\pm=(\ket0\pm\ket1)/\sqrt2$ and $\ket{\pm i}=(\ket0\pm i\ket1)/\sqrt2$ sit on the equator along $\pm x$ and $\pm y$ . The common gates are

X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\ Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\ Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix},\ H=\tfrac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\ S=\begin{pmatrix}1&0\\0&i\end{pmatrix},\ T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}.

Gates are rotations. For a real unit vector

\hat n

,

R_{\hat n}(\theta)=e^{-i\theta\,\hat n\cdot\vec\sigma/2}=\cos\tfrac\theta2\,I-i\sin\tfrac\theta2\,(\hat n\cdot\vec\sigma)

rotates the Bloch vector by

\theta

about

\hat n

. Every one-qubit unitary is

e^{i\gamma}R_{\hat n}(\theta)

for some

\gamma,\hat n,\theta

. For example

X

is a half turn about

x

,

H

a half turn about

(x+z)/\sqrt2

,

S

a quarter turn about

z

, and

T

an eighth of a turn about

z

.

Angles double. Orthogonal states are antipodal on the sphere, not perpendicular: the angle between Bloch vectors is twice the angle between the state vectors.

Explore

the state

\vec r

path of the last gate its rotation axis · drag to turn the sphere

Start from

Apply a gate

Rotation angle θ

Worked example

Find the rotation performed by the gate $SH$ (first $H$ , then $S$ ), and what happens if you apply it three times.

Where does $H$ send the three Bloch axes $x$ , $y$ , $z$ ?

$H$ is a half turn about $(x+z)/\sqrt2$ . A half turn swaps the two axes symmetric about its axis and reverses the one perpendicular to it: $x\mapsto z$ , $z\mapsto x$ , $y\mapsto -y$ . Check: $H\ket0=\ket+$ and $H\ket{+i}=e^{i\pi/4}\ket{-i}$ .
And $S$ ?

A quarter turn counterclockwise about $z$ : $x\mapsto y$ , $y\mapsto -x$ , $z\mapsto z$ . Indeed $S\ket+=(\ket0+i\ket1)/\sqrt2=\ket{+i}$ .
Compose them. What does $SH$ do to the axes, and what rotation is that?

$x\mapsto z\mapsto z$ , $\ y\mapsto -y\mapsto x$ , $\ z\mapsto x\mapsto y$ . So $SH$ cycles $z\to y\to x\to z$ . A rotation that permutes the axes cyclically fixes the diagonal $(1,1,1)/\sqrt3$ and turns by a third of a full turn. The cycle $x\to y\to z$ is $+2\pi/3$ about that axis, so ours, the reverse cycle, is

$SH = e^{i\gamma}R_{\hat n}(-2\pi/3),\qquad \hat n=\tfrac1{\sqrt3}(1,1,1).$
Try it in the explorer: start at $\ket0$ and press H, S three times over. Then compute $(SH)^3$ exactly.

The state goes $\ket0\to\ket{+i}\to\ket+\to\ket0$ on the sphere, as the cycle predicts. Three thirds of a turn is the identity rotation, so $(SH)^3$ is a multiple of $I$ . Multiplying the matrices gives

$(SH)^3 = e^{i\pi/4}\,I.$

The phase $e^{i\pi/4}$ is global, so it is invisible, but the amplitudes shown in the explorer do carry it.

Check your understanding

Which pair of states can be told apart by some measurement (given many copies)?

$\ket0+\ket1$ and $-\ket0-\ket1$ (normalised)These differ by the global factor $-1$ . Every probability $|\langle\phi|\psi\rangle|^2$ is unchanged by a global phase.
$\ket0+\ket1$ and $\ket0-\ket1$ (normalised)
$\ket1$ and $i\ket1$ $i$ multiplies the whole state, so it is a global phase.

A relative phase between

\ket0

and

\ket1

moves the Bloch vector around the equator:

\ket+

and

\ket-

are antipodal, and a measurement in the

X

basis tells them apart with certainty. A global phase doesn't move the Bloch vector at all.

What is $T^8$ ?

Exactly $I$
$-I$ : eight eighth-turns make a full turn, and $R_z(2\pi)=-I$ $R_z(2\pi)$ is indeed $-I$ , but $T$ is $R_z(\pi/4)$ times the phase $e^{i\pi/8}$ , and that phase also gets raised to the 8th power.
$Z$ $T^2=S$ and $S^2=Z$ , so $Z$ is $T^4$ . Keep going.

T=\mathrm{diag}(1,e^{i\pi/4})

, so

T^8=\mathrm{diag}(1,e^{2\pi i})=I

. As a rotation,

T^8 = e^{i\pi}R_z(2\pi)=(-1)(-I)=I

. The sign of a full rotation and the global phase cancel.

The Bloch vectors of two pure states make an angle of $90^\circ$ . What is $|\langle\phi|\psi\rangle|^2$ ?

$0$ Orthogonal states are antipodal ( $180^\circ$ apart), not perpendicular.
$1/2$
$1/\sqrt2$ That's $|\langle\phi|\psi\rangle|$ , before squaring.

For pure states

|\langle\phi|\psi\rangle|^2=(1+\vec r\cdot\vec s)/2

. At

90^\circ

,

\vec r\cdot\vec s=0

, giving

1/2

. Example:

\ket0

and

\ket+

.

Practice

Locate a stateFrom amplitudes to the Bloch vector

Find the Bloch vector of $\ket\psi=\big(\ket0+(1+i)\ket1\big)/\sqrt3$ .

Hint

For $\alpha\ket0+\beta\ket1$ , the Bloch vector is $\big(2\,\mathrm{Re}(\bar\alpha\beta),\ 2\,\mathrm{Im}(\bar\alpha\beta),\ |\alpha|^2-|\beta|^2\big)$ .

Solution

$\bar\alpha\beta=(1+i)/3$ , so $x=y=2/3$ , and $z=1/3-2/3=-1/3$ . Check: $4/9+4/9+1/9=1$ . The state is just below the equator, halfway between $+x$ and $+y$ .

A square root of NOTRotations by half the angle

Find a unitary $V$ with $V^2=X$ , and describe it on the Bloch sphere.

Hint

$X$ is a half turn about $x$ , so try a quarter turn about $x$ , and fix the phase afterwards.

Solution

$R_x(\pi/2)^2=R_x(\pi)=-iX$ . Multiplying by $e^{i\pi/4}$ fixes the phase, since $(e^{i\pi/4})^2(-i)=1$ :

V=e^{i\pi/4}R_x(\pi/2)=\tfrac12\begin{pmatrix}1+i&1-i\\1-i&1+i\end{pmatrix},\qquad V^2=X.

On the sphere $V$ is a quarter turn about $x$ . (Rx in the explorer with θ = π/2 does the same rotation, with a different global phase.)

More practice: Nielsen–Chuang, Exercises 4.1, 4.4 and 4.6.

Animated lessonNielsen–Chuang, Ch. 1: Introduction and overview

Bell states and teleportation

With one shared entangled pair and two classical bits, Alice can hand Bob an unknown qubit without ever learning what it is. The animation follows the state through the circuit and shows, at each moment, what Bob would hold for each result Alice could get.

The idea

Two qubits. The state space is

\C^2\otimes\C^2\cong\C^4

, with basis

\ket{00},\ket{01},\ket{10},\ket{11}

. A state is a product if it equals

\ket a\otimes\ket b

, and entangled otherwise.

Bell states.

H

on the first qubit followed by a CNOT turns

\ket{xy}

into

\ket{\beta_{xy}}=\frac{\ket{0\,y}+(-1)^x\ket{1\,\bar y}}{\sqrt2}:\qquad \ket{\beta_{00}}=\tfrac{\ket{00}+\ket{11}}{\sqrt2},\ \ket{\beta_{01}}=\tfrac{\ket{01}+\ket{10}}{\sqrt2},\ \ket{\beta_{10}}=\tfrac{\ket{00}-\ket{11}}{\sqrt2},\ \ket{\beta_{11}}=\tfrac{\ket{01}-\ket{10}}{\sqrt2}.

No cloning. No unitary sends

\ket\psi\ket0\mapsto\ket\psi\ket\psi

for every

\ket\psi

: it would have to preserve inner products, but

\langle\phi|\psi\rangle

and

\langle\phi|\psi\rangle^2

differ unless the states are equal or orthogonal. So a teleported qubit cannot also stay with Alice.

Teleportation identity. If Alice holds

\ket\psi

and shares

\ket{\beta_{00}}

with Bob, then after Alice applies CNOT (her two qubits) and

H

(her first qubit),

\ket\psi\ket{\beta_{00}}\ \longmapsto\ \frac12\sum_{m_1,m_2\in\{0,1\}}\ket{m_1m_2}\otimes X^{m_2}Z^{m_1}\ket\psi.

Alice measures, gets $m_1m_2$ with probability $1/4$ whatever $\ket\psi$ is, and sends the two bits. Bob applies $X^{m_2}$ then $Z^{m_1}$ and holds $\ket\psi$ .

Nothing travels faster than light. Until the bits arrive, Bob's qubit is an equal mixture of the four branches, which is the state

I/2

for every

\ket\psi

.

Watch

Alice's unknown state

Alice's measurement result

Top: the circuit, Alice's two qubits above and Bob's below. Bottom: Bob's qubit in each branch

m_1m_2

, that is, what he would hold if Alice measured now. Bob's state Alice's

\ket\psi

, for comparison

Alice holds an unknown qubit $\ket\psi$ . Two more qubits start in $\ket0$ . No branch shows $\ket\psi$ on Bob's side yet.
$H$ and CNOT make the Bell pair $\ket{\beta_{00}}$ . Alice keeps one half, Bob takes the other.
Alice applies CNOT from $\ket\psi$ to her half of the pair. Bob's branches are now $\ket0$ or $\ket1$ : only the amplitudes' sizes have moved, not the phase.
Alice applies $H$ to her first qubit. Every branch is now equally likely and holds $\ket\psi$ up to a Pauli: $X^{m_2}Z^{m_1}\ket\psi$ .
Alice measures and gets $m_1m_2$ . The other branches vanish; Bob holds $X^{m_2}Z^{m_1}\ket\psi$ but doesn't yet know which.
The two bits reach Bob. He applies $X^{m_2}$ , then $Z^{m_1}$ , and now holds exactly $\ket\psi$ . Alice's copy is gone.

Worked example

Suppose Alice and Bob share $\ket{\beta_{11}}=(\ket{01}-\ket{10})/\sqrt2$ instead of $\ket{\beta_{00}}$ , and Alice does exactly the same steps. Which correction must Bob apply for each result?

Write $\ket{\beta_{11}}$ as a one-qubit operation on Bob's half of $\ket{\beta_{00}}$ .

$(I\otimes X)\ket{\beta_{00}}=(\ket{01}+\ket{10})/\sqrt2$ , and then $(I\otimes Z)$ gives $(-\ket{01}+\ket{10})/\sqrt2=-\ket{\beta_{11}}$ . So $\ket{\beta_{11}}=-(I\otimes ZX)\ket{\beta_{00}}$ .
Why can we pretend Bob applied $ZX$ at the very start?

Alice's CNOT, $H$ and measurement act only on her two qubits, and $ZX$ acts only on Bob's. Operators on different qubits commute, so the extra $ZX$ can be moved past all of Alice's steps.
So what does Bob hold after Alice reports $m_1m_2$ ?

Up to a sign, $ZX\,X^{m_2}Z^{m_1}\ket\psi$ . He must undo this with $Z^{m_1}X^{m_2}XZ$ (read right to left: apply $Z$ first).
Simplify the four corrections.

Using $X^2=Z^2=I$ and $ZX=-XZ$ :

$00:\ XZ,\qquad 01:\ Z,\qquad 10:\ X\ (\text{up to sign}),\qquad 11:\ \text{nothing}.$

Check $11$ : Bob holds $ZX\cdot XZ\ket\psi=\ket\psi$ up to sign. Any shared Bell state works, as long as Alice and Bob agree in advance which one it is.

Check your understanding

Alice has measured, but her two bits haven't reached Bob. What state should Bob use to predict his own measurements?

$\ket\psi$ Then Alice could signal instantly, by choosing $\ket\psi$ and letting Bob measure.
$X^{m_2}Z^{m_1}\ket\psi$ That's correct only for someone who knows $m_1m_2$ . Bob doesn't.
The maximally mixed state $I/2$ , whatever $\ket\psi$ is

Each of the four Pauli-rotated copies of

\ket\psi

has probability

1/4

, and

\tfrac14\sum_P P\ket\psi\bra\psi P^\dagger=I/2

for the Paulis

I,X,Z,XZ

. Bob's statistics don't depend on

\ket\psi

until the bits arrive.

Is $\tfrac12(\ket{00}+\ket{01}+\ket{10}+\ket{11})$ entangled?

Yes: all four basis states appear.The number of terms depends on the basis. Try to factor it.
No: it is $\ket+\otimes\ket+$ .
Yes: it's one of the Bell states.Each Bell state has only two terms in this basis.

Write the amplitudes as a matrix

\big(\begin{smallmatrix}c_{00}&c_{01}\\c_{10}&c_{11}\end{smallmatrix}\big)

. The state is a product exactly when this matrix has rank 1, i.e.

c_{00}c_{11}=c_{01}c_{10}

. Here

\tfrac14=\tfrac14

.

Why does Alice apply $H$ to $\ket\psi$ 's qubit before measuring?

Without it, Bob's branch states are just $\ket0$ or $\ket1$ , and the phase of $\ket\psi$ would be lost in the measurement.
It is part of making the Bell pair.The Bell pair's $H$ acts on Alice's other qubit, earlier in the circuit.
It only changes a global phase, so it could be skipped.Scrub the animation to just before the $H$ : Bob's branches are $\ket0$ or $\ket1$ , not copies of $\ket\psi$ .

After the CNOT, the branches are

\alpha\ket0,\alpha\ket1,\beta\ket1,\beta\ket0

: a measurement then would reveal partial information about

|\alpha|,|\beta|

and destroy the relative phase. The

H

mixes the branches so each one carries all of

\ket\psi

, and each outcome has probability

1/4

.

Practice

Back from the Bell basisChange of basis

Express $\ket{01}$ and $\ket{11}$ as combinations of Bell states.

Hint

Add and subtract Bell states that contain the same two basis vectors.

Solution

$\ket{\beta_{01}}+\ket{\beta_{11}}=\tfrac{2}{\sqrt2}\ket{01}$ , so $\ket{01}=(\ket{\beta_{01}}+\ket{\beta_{11}})/\sqrt2$ . Similarly $\ket{\beta_{00}}-\ket{\beta_{10}}=\sqrt2\ket{11}$ , so $\ket{11}=(\ket{\beta_{00}}-\ket{\beta_{10}})/\sqrt2$ .

Teleporting entanglementEntanglement swapping

Charlie and Alice share $\ket{\beta_{00}}$ , and Alice and Bob share another $\ket{\beta_{00}}$ . Alice teleports her half of the first pair to Bob, using the second pair. What do Charlie and Bob end up with?

Hint

Teleportation is linear: it works term by term on $\tfrac1{\sqrt2}(\ket0_C\ket0_A+\ket1_C\ket1_A)$ .

Solution

The protocol maps $\ket{c}_C\ket{a}_A$ to $\ket{c}_C\ket{a}_B$ (after Bob's correction) for each basis state $a$ , with the same correction for both terms, since the correction depends only on Alice's outcome. By linearity Charlie and Bob share $\ket{\beta_{00}}$ , though Charlie and Bob never interacted.

More practice: Nielsen–Chuang, Exercises 1.2, 2.69 and 4.33.

SimulationNielsen–Chuang, Ch. 2: Introduction to quantum mechanics

Measurement and density operators

Quantum mechanics predicts probabilities, and probabilities only show up as frequencies over many runs. Measure a prepared state again and again, watch the frequency settle, and find out which preparations no experiment can tell apart.

The idea

The postulates, briefly. A closed system's state is a unit vector in a Hilbert space; it evolves by unitaries; the state space of a composite system is the tensor product. A measurement is a set of operators

\{M_m\}

with

\sum_m M_m^\dagger M_m=I

: outcome

m

has probability

p(m)=\bra\psi M_m^\dagger M_m\ket\psi

and leaves the state

M_m\ket\psi/\sqrt{p(m)}

.

Projective measurement. An observable

A=\sum_m m\,P_m

(spectral decomposition) is measured by the projectors

P_m

. Its mean is

\langle A\rangle=\bra\psi A\ket\psi

. For a qubit with Bloch vector

\vec r

, measuring

\hat n\cdot\vec\sigma

gives

p(+1)=\frac{1+\vec r\cdot\hat n}{2},\qquad \langle \hat n\cdot\vec\sigma\rangle = \vec r\cdot\hat n.

Density operator. If the system is

\ket{\psi_i}

with probability

p_i

, its state is

\rho=\sum_i p_i\ket{\psi_i}\bra{\psi_i}

: positive with trace 1, and

p(m)=\mathrm{tr}(M_m^\dagger M_m\rho)

. For a qubit,

\rho=\tfrac12\big(I+\vec r\cdot\vec\sigma\big),\qquad |\vec r|\le1,\qquad \text{pure}\iff|\vec r|=1.

Same $\rho$ , same physics. Every measurement probability depends on the ensemble only through

\rho

. Two ensembles with the same density operator cannot be told apart by any experiment.

Superposition is not mixture.

\ket+

and "

\ket0

or

\ket1

with probability

\tfrac12

" give the same

Z

statistics. Their density operators differ (

\vec r=(1,0,0)

against

\vec r=0

), and an

X

measurement shows it.

Explore

prepared state

\vec r

measurement axis: outcome

+1

toward the arrow · drag to turn

Preparation

Measure

frequency of

+1

so far Born probability, with a band of

\pm2

standard deviations

Worked example

A qubit is prepared in $\ket\psi=\tfrac{\sqrt3}2\ket0+\tfrac12\ket1$ (the "tilted" preparation in the explorer). Predict its $Z$ and $X$ statistics, then check them against its density matrix.

What are the probabilities in the $Z$ basis?

$p(0)=3/4$ and $p(1)=1/4$ , so $\langle Z\rangle=3/4-1/4=1/2$ .
What is $p(+)$ for an $X$ measurement?

$\langle+|\psi\rangle=\tfrac1{\sqrt2}\big(\tfrac{\sqrt3}2+\tfrac12\big)$ , so

$p(+)=\frac{(\sqrt3+1)^2}{8}=\frac{2+\sqrt3}{4}\approx0.933.$
Find the Bloch vector and confirm $p(+)=(1+r_x)/2$ .

$\cos\tfrac\theta2=\tfrac{\sqrt3}2$ gives $\theta=\pi/3$ , and $\varphi=0$ . So $\vec r=(\sin\tfrac\pi3,0,\cos\tfrac\pi3)=(\tfrac{\sqrt3}2,0,\tfrac12)$ , and $(1+\tfrac{\sqrt3}2)/2=(2+\sqrt3)/4$ . The $z$ -component $1/2$ is $\langle Z\rangle$ , as it should be.
Write $\rho$ and compute $\mathrm{tr}(\rho X)$ .

$\rho=\ket\psi\bra\psi=\begin{pmatrix}3/4&\sqrt3/4\\ \sqrt3/4&1/4\end{pmatrix},\qquad \mathrm{tr}(\rho X)=\rho_{01}+\rho_{10}=\frac{\sqrt3}2=r_x.$

In the explorer, run 1000 shots in $X$ : the frequency should land within about $2\sqrt{0.933\cdot0.067/1000}\approx0.016$ of 0.933.

Check your understanding

Preparation A: $\ket0$ or $\ket1$ , each with probability $\tfrac12$ . Preparation B: $\ket+$ or $\ket-$ , each with probability $\tfrac12$ . Can any measurement tell A from B?

Yes: measure $X$ . B always gives a definite $X$ outcome.Each member of B has a definite $X$ value, but you don't know which member was sent. Try both in the explorer.
Only a measurement on many copies at once.Even joint measurements on many copies see $\rho^{\otimes n}$ , which is the same for A and B.
No: both have $\rho=I/2$ .

\tfrac12(\ket0\bra0+\ket1\bra1)=\tfrac12(\ket+\bra++\ket-\bra-)=I/2

. Probabilities depend only on

\rho

, so A and B give identical statistics for every measurement.

A qubit has Bloch vector $\vec r$ . What is the mean value of the observable $\hat n\cdot\vec\sigma$ ?

$\vec r\cdot\hat n$
$(1+\vec r\cdot\hat n)/2$ That's the probability of the outcome $+1$ . The mean is $p(+1)-p(-1)$ .
$(\vec r\cdot\hat n)^2$ Squaring belongs to amplitudes, not to Bloch components.

\langle\hat n\cdot\vec\sigma\rangle=\mathrm{tr}\big(\tfrac12(I+\vec r\cdot\vec\sigma)\,\hat n\cdot\vec\sigma\big)=\vec r\cdot\hat n

, using

\mathrm{tr}(\sigma_j\sigma_k)=2\delta_{jk}

and

\mathrm{tr}\,\sigma_j=0

.

You measure $Z$ on 100 fresh copies of $\ket+$ and get 58 zeros. What should you conclude?

The source is not producing $\ket+$ .How big a fluctuation is normal for 100 shots?
Nothing alarming: the count has standard deviation 5, so 58 is 1.6 standard deviations from 50.
Earlier measurements disturbed the later copies.Each shot uses a fresh copy, so earlier outcomes have no effect.

The number of zeros is binomial with

n=100

,

p=\tfrac12

: standard deviation

\sqrt{np(1-p)}=5

. Deviations of order

\sqrt n

are expected; the explorer's band shows this shrinking like

1/\sqrt N

in the frequency.

Practice

Purity on the Bloch ballPure states live on the surface

Show that $\mathrm{tr}(\rho^2)=(1+|\vec r|^2)/2$ for a qubit, and conclude that $\rho$ is pure exactly when $|\vec r|=1$ .

Hint

$(\vec r\cdot\vec\sigma)^2=|\vec r|^2I$ , because the Pauli matrices anticommute and square to $I$ .

Solution

$\rho^2=\tfrac14\big(I+2\,\vec r\cdot\vec\sigma+|\vec r|^2I\big)$ , and the Paulis are traceless, so $\mathrm{tr}\rho^2=\tfrac14(2+2|\vec r|^2)$ . A density operator is pure iff $\mathrm{tr}\rho^2=1$ (its eigenvalues are then 1 and 0), i.e. iff $|\vec r|=1$ .

An ensemble on two axesFrom an ensemble to

\rho

A source emits $\ket0$ or $\ket{+i}$ , each with probability $\tfrac12$ . Find $\rho$ , its Bloch vector, its purity, and the probability of outcome 0 in a $Z$ measurement.

Solution

Bloch vectors average: $\vec r=\tfrac12(0,0,1)+\tfrac12(0,1,0)=(0,\tfrac12,\tfrac12)$ . Then

\rho=\tfrac12(I+\vec r\cdot\vec\sigma)=\begin{pmatrix}3/4&-i/4\\ i/4&1/4\end{pmatrix},

with purity $(1+\tfrac12)/2=\tfrac34$ , so the state is mixed. $p(0)=\rho_{00}=\tfrac34$ , which matches $\tfrac12\cdot1+\tfrac12\cdot\tfrac12$ .

More practice: Nielsen–Chuang, Exercises 2.59, 2.61, 2.71 and 2.72.

InteractiveNielsen–Chuang, Ch. 2: Introduction to quantum mechanics

Entanglement and Bell's inequality

If every measurement result were fixed in advance by shared local information, one combination of correlations, the CHSH quantity $S$ , could never exceed 2. Entangled qubits reach $2\sqrt2$ . Turn the four measurement directions and run the experiment.

The idea

Schmidt decomposition. Every pure state of a system

AB

can be written

\ket\psi=\sum_i\lambda_i\ket{i_A}\ket{i_B}

with orthonormal

\ket{i_A}

, orthonormal

\ket{i_B}

, and

\lambda_i\ge0

,

\sum\lambda_i^2=1

. The state is entangled exactly when more than one

\lambda_i

is nonzero.

Reduced state. Alice's half is described by

\rho_A=\mathrm{tr}_B\ket\psi\bra\psi=\sum_i\lambda_i^2\ket{i_A}\bra{i_A}

. For a Bell state

\rho_A=I/2

: Alice alone sees pure noise.

CHSH inequality. Suppose each run assigns definite values

A,A',B,B'\in\{\pm1\}

to the four possible measurements, and Alice's choice of setting does not affect Bob's values. Then

A(B-B')+A'(B+B')=\pm2\quad\Longrightarrow\quad S=E(a,b)-E(a,b')+E(a',b)+E(a',b')\le 2,

where $E$ is the average of the product of the two $\pm1$ results.

The quantum prediction. For

\ket{\beta_{00}}

, with Alice measuring

\cos a\,Z+\sin a\,X

and Bob

\cos b\,Z+\sin b\,X

,

E(a,b)=\cos(a-b),\qquad S=2\sqrt2\ \text{ at } a=0,\ a'=\tfrac\pi2,\ b=\tfrac\pi4,\ b'=\tfrac{3\pi}4.

$2\sqrt2$ is the largest value quantum mechanics allows (Tsirelson's bound).

Explore

Source

Drag the four directions (angles from

z

toward

x

). Alice:

a, a'

Bob:

b, b'

Correlation

E

against the angle difference. quantum

\cos\Delta

the local model sampled estimates

Worked example

The explorer uses $\ket{\beta_{00}}$ . Work out the correlations of the singlet $\ket{\beta_{11}}=(\ket{01}-\ket{10})/\sqrt2$ instead, and find its best CHSH value.

Compute $\langle Z\otimes Z\rangle$ , $\langle X\otimes X\rangle$ and $\langle Z\otimes X\rangle$ in the singlet.

$Z\otimes Z$ multiplies both $\ket{01}$ and $\ket{10}$ by $-1$ : mean $-1$ . $X\otimes X$ swaps $\ket{01}\leftrightarrow\ket{10}$ , turning the singlet into minus itself: mean $-1$ . $Z\otimes X$ maps it to $(\ket{00}+\ket{11})/\sqrt2$ , which is orthogonal to it: mean 0. Likewise $\langle X\otimes Z\rangle=0$ .
Expand $E(a,b)$ .

$E(a,b)=\cos a\cos b\,\langle ZZ\rangle+\sin a\sin b\,\langle XX\rangle+(\text{cross terms}=0)=-\cos(a-b).$

The singlet is perfectly anticorrelated along every common axis.
Evaluate $S$ at the settings that give $2\sqrt2$ for $\ket{\beta_{00}}$ .

Every correlation changes sign, so $S=-2\sqrt2$ . The inequality really bounds $|S|$ : local models satisfy $-2\le S\le2$ , because $A(B-B')+A'(B+B')=\pm2$ . Relabelling Bob's outcomes ( $\pm1\to\mp1$ ) turns the singlet's $-2\sqrt2$ into $+2\sqrt2$ .
Where exactly does the local argument fail for quantum systems?

It assumes all four values $A,A',B,B'$ exist in every run. In the quantum experiment only one setting per side is measured, and $\cos a\,Z+\sin a\,X$ and $\cos a'\,Z+\sin a'\,X$ don't commute, so there is no joint value of $A$ and $A'$ to plug into the identity.

Check your understanding

Alice and Bob share $\ket{\beta_{00}}$ . Alice measures in some basis of her choice, then Bob measures $Z$ . Does Alice's choice change the probabilities Bob sees?

Yes: her measurement collapses his qubit.It collapses to a state that depends on her random outcome. Average over that outcome.
No: Bob's reduced state is $I/2$ whatever she does.
Only if she measures $Z$ too.Then the outcomes are correlated, but Bob's own frequencies are still 50/50.

Operations on Alice's qubit can't change

\rho_B=\mathrm{tr}_A\rho

. Entanglement shows up in correlations, which need both records to be compared; it can't be used to signal.

Point all four directions along $z$ ( $a=a'=b=b'$ ). What is $S$ for $\ket{\beta_{00}}$ ?

0Every correlation is $\cos 0=1$ here, not 0; only the signs in $S$ can cancel them.
2
4One of the four terms enters with a minus sign.
$2\sqrt2$ That needs the directions spread out by $45^\circ$ steps.

All four correlations are

\cos0=1

, so

S=1-1+1+1=2

. Perfect correlation along one axis is easy to fake classically. Press "All along z" and compare the two sources.

An experiment measures $S=2.7\pm0.05$ . What has it ruled out?

Quantum mechanics.Quantum mechanics predicts values up to $2\sqrt2\approx2.83$ .
Every model in which outcomes are fixed by shared local variables and neither side's setting affects the other's result.
Entanglement between the two qubits.The other way around: unentangled (separable) states always satisfy $|S|\le2$ , so a violation certifies entanglement.

The CHSH bound uses only the two assumptions in the correct answer, plus free choice of settings. A violation means at least one of them fails in nature.

Practice

Four terms, two in disguiseA Schmidt decomposition

Find the Schmidt decomposition and $\rho_A$ for $\ket\psi=\tfrac12(\ket{00}+\ket{01}+\ket{10}-\ket{11})$ .

Hint

Group the terms by the first qubit.

Solution

$\ket\psi=\tfrac1{\sqrt2}\big(\ket0\ket++\ket1\ket-\big)$ . This is a Schmidt form with $\lambda_1=\lambda_2=1/\sqrt2$ , so the state is maximally entangled and $\rho_A=I/2$ . (Its amplitude matrix is $H/\sqrt2$ , and $\tfrac12HH^\dagger=I/2$ .)

Product states obey CHSHNo entanglement, no violation

Show that $|S|\le2$ for every product state $\ket\alpha\ket\beta$ , whatever the four settings.

Hint

For a product state, $E(a,b)=\langle A\rangle\langle B\rangle$ . Use $|x-y|+|x+y|=2\max(|x|,|y|)$ .

Solution

With $\langle A\rangle,\langle A'\rangle,\langle B\rangle,\langle B'\rangle\in[-1,1]$ ,

|S|=\big|\langle A\rangle(\langle B\rangle-\langle B'\rangle)+\langle A'\rangle(\langle B\rangle+\langle B'\rangle)\big|\le|\langle B\rangle-\langle B'\rangle|+|\langle B\rangle+\langle B'\rangle|\le2.

Mixtures of product states inherit the bound, since $S$ is linear in $\rho$ .

More practice: Nielsen–Chuang, Exercises 2.75, 2.78 and 2.79.

Worked examplesNielsen–Chuang, Ch. 3: Introduction to computer science

Reversible computation and complexity

A quantum computer evolves by unitaries, so whatever it computes it must compute reversibly. Classical logic can be made reversible at modest cost, which is why a quantum computer can run any classical algorithm, and the scratch work has to be cleaned up afterwards.

The idea

Circuits. A Boolean circuit is built from gates such as AND, OR, NOT, with wires that can be copied (FANOUT). NAND alone, with FANOUT, is universal: it can build every Boolean function.

Toffoli gate.

(a,b,c)\mapsto(a,\,b,\,c\oplus ab)

. It is a permutation of the 8 inputs and its own inverse. With

c=1

it outputs NAND; with

a=b=1

it is NOT on

c

; with

a=1,c=0

it copies

b

. So reversible circuits can compute anything.

Landauer's principle. Erasing one bit of information in an environment at temperature

T

dissipates at least

k_BT\ln2

of heat. Reversible gates erase nothing, so in principle they need not dissipate.

Uncomputation (Bennett). A reversible circuit for

f

leaves garbage:

(x,0,0)\mapsto(x,g(x),f(x))

. Copy

f(x)

into a fresh register with CNOTs, then run the circuit backwards. The result is

(x,0,0,f(x))

, at about twice the gate count.

Complexity classes. P: decided in polynomial time. NP: "yes" answers can be checked in polynomial time. BPP: decided by a randomised polynomial algorithm with error at most 1/3. BQP: the same for quantum circuits. Known:

\mathrm P\subseteq\mathrm{BPP}\subseteq\mathrm{BQP}\subseteq\mathrm{PSPACE}

. Whether any of these inclusions is strict is open.

Not a shortcut to NP. Factoring is in BQP (Shor) but is not believed to be NP-complete, and there is no known efficient quantum algorithm for NP-complete problems.

Worked example

Build a reversible circuit that computes $y=x_1x_2x_3$ (AND of three bits) into a target bit, using Toffoli gates and one scratch bit $w$ , and leave the scratch bit clean. Then see why the cleaning matters quantum mechanically.

One Toffoli computes the AND of two bits. How?

Toffoli $(x_1,x_2;w)$ with $w=0$ gives $w=0\oplus x_1x_2=x_1x_2$ .
Now get $x_1x_2x_3$ into the target $y$ (initially 0).

Toffoli $(w,x_3;y)$ gives $y=x_1x_2x_3$ . The scratch bit $w$ still holds $x_1x_2$ : this is garbage.
Why is the garbage harmful on a quantum computer?

On a superposition of inputs the circuit produces $\sum_x c_x\ket x\ket{w(x)}\ket{f(x)}$ instead of $\sum_x c_x\ket x\ket0\ket{f(x)}$ . The garbage register is entangled with the input. Tracing it out leaves the rest in a mixed state, and the interference that a quantum algorithm relies on is lost.
Clean up $w$ .

Apply Toffoli $(x_1,x_2;w)$ once more: $w\mapsto x_1x_2\oplus x_1x_2=0$ . Nothing it depends on ( $x_1,x_2$ ) has changed, so the uncomputation is exact. The circuit is three Toffolis, and its output is $(x_1,x_2,x_3,\,w=0,\,y=x_1x_2x_3)$ .
Generalise to the AND of $n$ bits. How many Toffolis and scratch bits?

Chain the partial ANDs $x_1x_2,\ x_1x_2x_3,\ \dots$ into $n-2$ scratch bits, with the last Toffoli writing into the target: $n-1$ gates. Uncompute the $n-2$ scratch bits in reverse order: $n-2$ more. Total $2n-3$ Toffolis and $n-2$ clean scratch bits; for $n=3$ , three Toffolis and one scratch bit, as above.
What does Landauer's principle say about the ordinary irreversible AND gate on uniformly random inputs?

The input carries 2 bits of entropy. The output is 1 with probability $1/4$ , so it carries $H(1/4)\approx0.811$ bits. The gate erases about $2-0.811=1.19$ bits, so it must dissipate at least $1.19\,k_BT\ln2$ per use. The reversible version keeps $x_1,x_2$ , erases nothing, and has no such floor.

Check your understanding

A Toffoli gate gets inputs $(a,b,1)$ . What is its third output?

$a\wedge b$ The target starts at 1, so it becomes $1\oplus ab$ .
$\neg(a\wedge b)$ , the NAND
$a\oplus b$ Toffoli multiplies the controls; XOR would need two CNOTs.

1\oplus ab

is 0 exactly when

a=b=1

. Since NAND is universal, so is Toffoli, with constant inputs and spare outputs allowed.

Why must every gate in a quantum circuit be reversible?

Closed quantum evolution is unitary, and unitaries are invertible.
To avoid Landauer heat, which would destroy the qubits.Heat is a practical concern; the requirement is more basic than that.
Because of the no-cloning theorem.No-cloning forbids copying unknown states; reversibility comes from unitarity itself.

A unitary

U

has inverse

U^\dagger

. Irreversible steps (such as a reset) are possible only by involving an environment or a measurement, which is not a gate on the qubits alone.

Which of these is known to be true?

$\mathrm{BPP}\subseteq\mathrm{BQP}\subseteq\mathrm{PSPACE}$
NP $\subseteq$ BQPOpen, and widely doubted: search gives only a square-root speed-up for unstructured problems.
Factoring is NP-completeFactoring (as a decision problem) lies in NP ∩ co-NP, which makes NP-completeness unlikely.

A quantum circuit can simulate coin flips, giving BPP ⊆ BQP. A classical machine can add up the amplitudes of all paths through a quantum circuit using polynomial space, giving BQP ⊆ PSPACE.

Practice

A reversible ORDe Morgan with a Toffoli

Using one Toffoli and some NOT gates, compute $a\vee b$ into a target bit and leave $a,b$ unchanged.

Hint

$a\vee b=\neg(\neg a\wedge\neg b)$ .

Solution

NOT $a$ and $b$ , apply Toffoli onto a target that starts at 1 (giving $1\oplus\bar a\bar b=a\vee b$ ), then NOT $a$ and $b$ again to restore them.

The Fredkin gateControlled swap

The Fredkin gate swaps its second and third bits when the first is 1. Show it never changes the number of 1s, and use it with constant inputs to compute AND and NOT.

Solution

It either does nothing or swaps two bits, so the count of 1s is unchanged. Input $(a,b,0)$ : if $a=1$ the output is $(1,0,b)$ , otherwise $(0,b,0)$ ; the third output is $ab$ . Input $(a,0,1)$ : if $a=1$ the output is $(1,1,0)$ , otherwise $(0,0,1)$ ; the third output is $\neg a$ , and the second is a copy of $a$ .

More practice: Nielsen–Chuang, Exercises 3.29, 3.31 and 3.32.

SimulatorNielsen–Chuang, Ch. 4: Quantum circuits

Quantum circuits

Single-qubit gates and CNOT are enough to build any unitary. Put gates on three wires and watch all eight amplitudes change, column by column. Entanglement shows up as a qubit whose own state is no longer pure.

The idea

Many qubits.

n

qubits have

2^n

amplitudes, one for each bit string. Here

\ket{q_1q_2q_3}

lists the wires top to bottom. A gate

U

on wire

k

acts as

I\otimes\cdots\otimes U\otimes\cdots\otimes I

.

Controlled gates. Controlled-

U

maps

\ket c\ket t\mapsto\ket c\,U^c\ket t

. CNOT is controlled-

X

; CZ is controlled-

Z

, which multiplies

\ket{11}

by

-1

and is symmetric in its two qubits.

Universality. CNOT and all one-qubit gates generate every unitary exactly. The finite set

\{H, S, T, \mathrm{CNOT}\}

approximates any unitary to accuracy

\varepsilon

, and by the Solovay–Kitaev theorem a one-qubit gate costs only

O(\log^c(1/\varepsilon))

gates from the set, for a constant

c

near 2.

Phase kickback. If the target is an eigenvector,

U\ket u=e^{i\phi}\ket u

, then controlled-

U

sends

(a\ket0+b\ket1)\ket u\mapsto(a\ket0+e^{i\phi}b\ket1)\ket u

. The phase lands on the control. With CNOT and

\ket u=\ket-

,

\phi=\pi

.

Exponential bookkeeping. A simulator like the one below stores

2^n

numbers. That is easy for 3 qubits and hopeless for 300, which is part of why quantum computers might be powerful.

Explore

Gate to place

Load a circuit

Click a cell to place the gate. For CNOT and CZ, click the control, then the target in the same column. Click a gate again to remove it.

Show the state after column

Bar height: probability

|c_x|^2

. The dial above each bar shows the amplitude

c_x

as an arrow in the complex plane (pointing right means positive real).

Worked example

Load "Deutsch–Jozsa" in the simulator. It tests whether $f:\{0,1\}^2\to\{0,1\}$ is constant or balanced with one call to the oracle $\ket x\ket y\mapsto\ket x\ket{y\oplus f(x)}$ , here for $f(x_1,x_2)=x_1\oplus x_2$ , built from two CNOTs into the third wire. Work through the circuit by hand.

After $X$ on wire 3 and $H$ on all three wires, what is the state?

$\ket+\ket+\ket-=\tfrac12\sum_{x\in\{0,1\}^2}\ket x\otimes\ket-$ .
What does the oracle do to $\ket x\ket-$ ?

$\ket x\big(\ket{f(x)}-\ket{1\oplus f(x)}\big)/\sqrt2=(-1)^{f(x)}\ket x\ket-$ : phase kickback. So the state becomes

$\tfrac12\big(\ket{00}-\ket{01}-\ket{10}+\ket{11}\big)\ket-=\ket-\ket-\ket-.$
Apply $H$ to wires 1 and 2. What is measured?

$H\ket-=\ket1$ , so the result is $\ket{11}\ket-$ : wires 1 and 2 read $11$ with certainty. The simulator shows probability $\tfrac12$ on each of $\ket{110}$ and $\ket{111}$ because wire 3 is $\ket-$ .
What would a constant $f$ give, and why does this decide the question?

For constant $f$ the kickback is a global sign, the first two wires stay $\ket{++}$ , and the final $H$ s return $\ket{00}$ . For any balanced $f$ , the amplitude of $\ket{00}$ after the final $H$ s is $\tfrac14\sum_x(-1)^{f(x)}=0$ . So "00" means constant and anything else means balanced. Remove one CNOT from the oracle (it becomes $f=x_1$ or $x_2$ , still balanced) and check that 00 still never appears.

Check your understanding

In a CZ gate, which qubit is the control?

The top one, by convention.Write out its matrix and swap the qubits.
Either: CZ is symmetric.
The one in state $\ket1$ .Control is a role in the circuit, not a property of the state.

CZ

=\mathrm{diag}(1,1,1,-1)

: it multiplies

\ket{11}

by

-1

and leaves the rest alone, which doesn't distinguish the qubits. Even for CNOT the roles depend on basis: in the

\ket\pm

basis, control and target swap.

$H$ on wire 1 then CNOT 1→2 turns $\ket{00}$ into a Bell state. What if the CNOT comes first and the $H$ second?

The same Bell state.Look at what the CNOT does when its control is $\ket0$ .
The product state $\ket+\ket0$ .
A different Bell state.No entangling step acts on a superposition, so no entanglement can appear.

With control

\ket0

the CNOT does nothing, and then

H

just makes

\ket+\ket0

. Gates don't commute in general, so order matters; try both in the simulator and look at the purities.

Control in $\ket+$ , target in $\ket-$ . What does a CNOT produce?

$\ket+\ket-$ , unchanged.The target is unchanged. The control is not.
$\ket-\ket-$
An entangled state.The target is an eigenvector of $X$ , so the output stays a product.

X\ket-=-\ket-

, so CNOT

\,\ket x\ket-=(-1)^x\ket x\ket-

. The control picks up the relative sign:

\ket+\mapsto\ket-

. This is phase kickback, the engine of Deutsch–Jozsa and phase estimation.

Practice

Three-qubit GHZ stateEntangled, but each pair is not

Give a circuit that makes $(\ket{000}+\ket{111})/\sqrt2$ from $\ket{000}$ . Then trace out qubit 3 and decide whether qubits 1 and 2 are entangled with each other.

Solution

$H$ on wire 1, then CNOT 1→2 and CNOT 2→3 (the "GHZ" preset). Tracing out qubit 3 gives $\rho_{12}=\tfrac12(\ket{00}\bra{00}+\ket{11}\bra{11})$ , a classical mixture of product states: perfectly correlated, but not entangled. Each single qubit has purity $\tfrac12$ , the minimum.

Kickback from controlled-SReading off an eigenvalue

A controlled- $S$ gate has its control in $\ket+$ and its target in $\ket1$ . What is the output, and how could you tell the phase from a measurement of the control?

Hint

$\ket1$ is an eigenvector of $S$ . With which eigenvalue?

Solution

$S\ket1=i\ket1$ , so the output is $\tfrac1{\sqrt2}(\ket0+i\ket1)\ket1=\ket{+i}\ket1$ . Measuring the control in the $Y$ basis gives $+1$ with certainty; in the $X$ basis it gives each outcome half the time. Phase estimation generalises this: controlled powers of $U$ write the eigenphase into a register, and an inverse Fourier transform reads it out.

More practice: Nielsen–Chuang, Exercises 4.13, 4.17 and 4.20.

SimulationNielsen–Chuang, Ch. 5: The quantum Fourier transform and its applications

Fourier transform and period finding

Shor's algorithm turns factoring into finding the period of $x\mapsto a^x\bmod N$ . The quantum Fourier transform turns a periodic superposition into sharp peaks, and a short continued-fraction calculation reads the period off one measurement. Here it is for $N=15$ and $N=21$ .

The idea

Quantum Fourier transform. On

t

qubits, with

Q=2^t

,

\ket j\ \longmapsto\ \frac1{\sqrt Q}\sum_{k=0}^{Q-1}e^{2\pi i\,jk/Q}\ket k.

It is unitary and needs only $O(t^2)$ gates (Hadamards and controlled phase rotations), against $O(t\,2^t)$ steps for the classical fast Fourier transform of $2^t$ numbers. The catch: the output amplitudes can't be read, only sampled.

Order. For

a

coprime to

N

, the order

r

is the least

r>0

with

a^r\equiv1\pmod N

.

From order to factors. If

r

is even and

a^{r/2}\not\equiv-1\pmod N

, then

\gcd(a^{r/2}-1,N)

and

\gcd(a^{r/2}+1,N)

are nontrivial factors of

N

. For odd

N

that isn't a prime power, a random

a

works with probability at least

1/2

.

Order finding. Prepare

\frac1{\sqrt Q}\sum_x\ket x\ket{a^x\bmod N}

, apply the QFT to the first register and measure it, getting

y

. Then

y/Q

is close to

s/r

for a uniformly random

s\in\{0,\dots,r-1\}

. If

Q\ge N^2

, the fraction

s/r

(in lowest terms) is one of the continued-fraction convergents of

y/Q

.

Lowest terms. If

\gcd(s,r)>1

, continued fractions return a proper divisor of

r

. Check whether

a^q\equiv1

; if not, try small multiples of

q

or run again.

Explore

N

Base a

Counting qubits t

P(y)

after the QFT the ideal peak positions

sQ/r

your measured

y

Worked example

Factor $N=21$ with $a=2$ and $t=9$ counting qubits ( $Q=512\ge21^2=441$ ). Set the explorer to the same values to follow along.

What is the order of 2 modulo 21? (The quantum computer finds this; we check it by hand.)

$2,4,8,16,32\equiv11,22\equiv1$ . So $r=6$ .
Where are the peaks of $P(y)$ ?

Near $y=sQ/r=512s/6$ : $0,\ 85.3,\ 170.7,\ 256,\ 341.3,\ 426.7$ . Since 6 doesn't divide 512, the peaks spill onto neighbouring $y$ .
Suppose the measurement gives $y=427$ . Expand $427/512$ as a continued fraction and list the convergents.

$512=1\cdot427+85,\ 427=5\cdot85+2,\ 85=42\cdot2+1,\ 2=2\cdot1$ , so $427/512=[0;1,5,42,2]$ , with convergents

$\tfrac01,\quad\tfrac11,\quad\tfrac56,\quad\tfrac{211}{253},\quad\tfrac{427}{512}.$

The last convergent with denominator below $N=21$ is $5/6$ , so the candidate is $r=6$ . Check: $2^6=64=3\cdot21+1$ .
Turn $r=6$ into factors.

$r$ is even and $2^{3}=8\not\equiv-1\pmod{21}$ . Then $\gcd(8-1,21)=7$ and $\gcd(8+1,21)=3$ , and $21=3\cdot7$ .
What if the measurement had given $y=341$ ?

$341/512=[0;1,1,1,170]$ , convergents $0,\ 1,\ \tfrac12,\ \tfrac23,\ \tfrac{341}{512}$ . The candidate is $q=3$ , but $2^3=8\not\equiv1$ . Here $s=4$ shares the factor 2 with $r=6$ , and $4/6$ reduced to $2/3$ . Trying the multiple $2q=6$ works.

Check your understanding

$N=15$ , $a=7$ (order 4), $Q=256$ . Which outcomes $y$ can occur?

Any $y$ , with peaks near multiples of 64.When $r$ divides $Q$ the cancellation away from the peaks is exact.
Only $0, 64, 128, 192$ , each with probability $1/4$ .
Only $y=64$ , which gives $r=4$ directly. $s$ is uniformly random in $\{0,1,2,3\}$ , so all four peaks are equally likely.

With

r\mid Q

, the sum

\sum_k e^{2\pi i\,kry/Q}

is zero unless

ry/Q

is an integer, i.e.

y

is a multiple of

Q/r=64

. Only

y=64

and

y=192

(

s

odd, coprime to 4) give

r

directly;

y=128

gives

1/2

.

You measure $y=0$ . What do you learn?

Nothing: $0/Q=0/1$ , the candidate order is 1, and you run again.
That $r=Q$ .The order is at most $N$ , far below $Q$ .
That $a$ is a bad choice. $y=0$ (that is, $s=0$ ) has probability about $1/r$ for every $a$ .

The

s=0

peak always exists and carries no information about

r

. It is one reason the algorithm is repeated a few times.

Why take $Q\ge N^2$ ?

The QFT only works when $Q$ is a perfect square.The QFT works for every $Q=2^t$ .
Then $|y/Q-s/r|\le1/(2Q)\le1/(2r^2)$ , which guarantees $s/r$ is a convergent of $y/Q$ .
To make the peaks wider and easier to hit.Larger $Q$ makes the peaks narrower relative to their spacing.

A classical theorem: if

|x-s/r|\le1/(2r^2)

, then

s/r

is a convergent of

x

. With

r<N

and

Q\ge N^2

the peaks are sharp enough. Lower

t

in the explorer and watch the continued fractions start to fail.

Practice

The four-point transformQFT by hand

Write the matrix of the QFT for $Q=4$ , check that for $Q=2$ it is $H$ , and show that applying the $Q=4$ transform twice sends $\ket j$ to $\ket{-j\bmod4}$ .

Solution

With $\omega=e^{2\pi i/4}=i$ , the entries are $\omega^{jk}/2$ :

F_4=\frac12\begin{pmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{pmatrix},\qquad F_2=\tfrac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}=H.

$(F^2)_{jl}=\tfrac1Q\sum_k\omega^{k(j+l)}$ , which is 1 when $j+l\equiv0\pmod Q$ and 0 otherwise. So $F^2\ket l=\ket{-l}$ , and $F^4=I$ .

Exact peaksWhy

r\mid Q

gives a clean comb

Let $r$ divide $Q$ and $\ket\phi=\sqrt{r/Q}\sum_{k=0}^{Q/r-1}\ket{x_0+kr}$ . Show that the QFT of $\ket\phi$ is $\frac1{\sqrt r}\sum_{s=0}^{r-1}e^{2\pi i\,x_0s/r}\ket{sQ/r}$ .

Hint

The amplitude of $\ket y$ contains the geometric sum $\sum_k e^{2\pi i\,kry/Q}$ .

Solution

The amplitude of $\ket y$ is $\frac{\sqrt r}{Q}e^{2\pi i x_0y/Q}\sum_{k=0}^{Q/r-1}e^{2\pi i\,kry/Q}$ . The sum is $Q/r$ if $ry/Q\in\Z$ , i.e. $y=sQ/r$ , and 0 otherwise. At $y=sQ/r$ the amplitude is $\frac{\sqrt r}{Q}\cdot\frac Qr\,e^{2\pi i x_0s/r}=\frac1{\sqrt r}e^{2\pi ix_0s/r}$ . The offset $x_0$ only affects phases, so measuring $a^x\bmod N$ first changes nothing about $P(y)$ .

More practice: Nielsen–Chuang, Exercises 5.10, 5.18 and 5.19.

InteractiveNielsen–Chuang, Ch. 6: Quantum search algorithms

Grover search as a rotation

Each Grover iteration is two reflections, and two reflections make a rotation. In the plane spanned by "marked" and "unmarked", the state turns by a fixed angle each step, so about $\tfrac\pi4\sqrt{N/M}$ steps reach a marked item, and further steps overshoot.

The idea

Oracle.

O\ket x=(-1)^{f(x)}\ket x

, where

f(x)=1

for the

M

marked items out of

N=2^n

. (A bit-flip oracle with its output qubit in

\ket-

acts this way, by phase kickback.)

Grover iteration.

G=(2\ket\psi\bra\psi-I)\,O

, where

\ket\psi=H^{\otimes n}\ket0

is the uniform superposition. The second factor, the diffusion, maps each amplitude

c_x

to

2\bar c-c_x

: an inversion about the mean.

The geometry. Let

\ket\alpha

and

\ket\beta

be the uniform superpositions of unmarked and marked items. Then

\ket\psi=\cos\tfrac\theta2\ket\alpha+\sin\tfrac\theta2\ket\beta

with

\sin\tfrac\theta2=\sqrt{M/N}

.

O

reflects about

\ket\alpha

, the diffusion reflects about

\ket\psi

, and together they rotate by

\theta

:

G^k\ket\psi=\cos\tfrac{(2k+1)\theta}2\ket\alpha+\sin\tfrac{(2k+1)\theta}2\ket\beta,\qquad P_{\text{success}}=\sin^2\tfrac{(2k+1)\theta}2.

Optimality. Any quantum algorithm that finds a marked item with high probability needs

\Omega(\sqrt{N/M})

oracle calls, so Grover's algorithm is optimal up to a constant factor.

Explore

Qubits n (N = 2ⁿ items) Marked items M

the state

\ket\psi

, the start the mirror of the last reflection

Success probability after

k

iterations. where you are now

Worked example

Search $N=16$ items with one marked item, tracking the actual amplitudes. (Set $n=4$ , $M=1$ in the explorer.)

What is $\theta$ , and what does the formula predict for $k=1,2,3,4$ ?

$\sin\tfrac\theta2=\tfrac14$ , so $\tfrac\theta2\approx14.48^\circ$ . The success probabilities $\sin^2\big((2k+1)\cdot14.48^\circ\big)$ are $0.473,\ 0.908,\ 0.961,\ 0.582$ . Best is $k=3$ , close to $\tfrac\pi4\sqrt{16}\approx3.1$ .
Do the first iteration with amplitudes. All 16 start at $\tfrac14$ .

Oracle: the marked amplitude becomes $-\tfrac14$ . The mean is $(15\cdot\tfrac14-\tfrac14)/16=0.21875$ . Inversion about the mean: unmarked $2(0.21875)-0.25=0.1875$ ; marked $2(0.21875)+0.25=0.6875$ . Probability $0.6875^2=0.473$ , as predicted.
Do the second and third iterations.

Second: mean $(15\cdot0.1875-0.6875)/16=0.1328$ ; unmarked $0.0781$ , marked $0.9531$ , probability $0.908$ . Third: mean $(15\cdot0.0781-0.9531)/16=0.0137$ ; unmarked $-0.0508$ , marked $0.9805$ , probability $0.961$ .
The unmarked amplitudes just went negative. What does that tell you?

The state has rotated past $\ket\beta$ : its $\ket\alpha$ -component is now negative. A fourth iteration moves it further from $\ket\beta$ , and the probability drops to $0.582$ . A classical search with 3 queries succeeds with probability only $3/16$ , or $4/16$ if you guess one of the unchecked items at the end.

Check your understanding

$N=2^{20}\approx10^6$ , one marked item. Roughly how many iterations give the best chance of success?

About 20That's $\log_2N$ . Search is quadratically faster than classical, not exponentially.
About 800
About 500,000That's the average for a classical search.

\tfrac\pi4\sqrt{2^{20}}=\tfrac\pi4\cdot1024\approx804

. Each iteration rotates by

\theta\approx2/\sqrt N

, and the state has to turn through about

\pi/2

.

You run twice the optimal number of iterations. The success probability is then

close to 1, since extra iterations can't hurt.The iteration is a rotation, and it keeps turning past $\ket\beta$ .
close to 0.
about 1/2.After twice the optimum the angle is close to $\pi$ , not $3\pi/4$ .

The optimum puts the angle near

\pi/2

; twice as many steps put it near

\pi

, that is, near

-\ket\alpha

, where the marked amplitude is almost zero. Try "Run to the best k", then keep pressing "Full iteration".

What does the oracle step alone do to the measurement probabilities?

It raises the probability of the marked items.It only flips the sign of their amplitudes.
Nothing: it changes signs, and probabilities are squared magnitudes.
It sets the marked amplitudes to zero.A unitary can't destroy amplitude; it reflects it.

On its own the sign flip is invisible to a computational-basis measurement. The diffusion step turns the sign difference into a size difference. Press Oracle alone in the explorer and watch the probability readout.

Practice

Eight itemsChoosing the number of iterations

For $N=8$ and $M=1$ , find $\theta$ , the best number of iterations, and its success probability.

Solution

$\sin\tfrac\theta2=1/\sqrt8$ gives $\tfrac\theta2\approx20.7^\circ$ . The angles $(2k+1)\theta/2$ are $62.1^\circ, 103.5^\circ, 144.9^\circ$ for $k=1,2,3$ , with probabilities $0.781, 0.945, 0.330$ . Best is $k=2$ , at about $94.5\%$ .

A quarter markedCertainty in one step

Show that if exactly a quarter of the items are marked, one Grover iteration finds a marked item with certainty.

Solution

$\sin\tfrac\theta2=\sqrt{1/4}=\tfrac12$ , so $\tfrac\theta2=30^\circ$ and after one iteration the angle is $3\cdot30^\circ=90^\circ$ : the state is exactly $\ket\beta$ . (With amplitudes: after the oracle the mean is $\tfrac1{2\sqrt N}$ , so unmarked amplitudes $\tfrac1{\sqrt N}$ become 0.)

More practice: Nielsen–Chuang, Exercises 6.2 and 6.3.

InteractiveNielsen–Chuang, Ch. 7: Quantum computers: physical realization

Driving a qubit: Rabi oscillations

In NMR, ion traps and cavity QED, a gate is a pulse of radiation of a chosen length. On resonance the qubit swings all the way from $\ket0$ to $\ket1$ and back. Off resonance it precesses about a tilted axis and never fully flips, which is one way real gates go wrong.

The idea

What a physical qubit needs. A robust way to represent quantum information, a way to perform a universal set of unitaries, a way to prepare a known initial state, and a way to measure the result, all with decoherence slow compared with the gates.

Driven two-level system. In a frame rotating with the drive, a qubit driven with Rabi frequency

\Omega

and detuning

\Delta

(drive frequency minus qubit frequency, up to sign convention) has, with

\hbar=1

,

H=\tfrac\Delta2\,Z+\tfrac\Omega2\,X.

Rabi formula.

e^{-iHt}

rotates the Bloch vector about

\hat n=(\Omega,0,\Delta)/\Omega'

at angular speed

\Omega'=\sqrt{\Omega^2+\Delta^2}

. Starting in

\ket0

,

P_1(t)=\frac{\Omega^2}{\Omega^2+\Delta^2}\,\sin^2\!\Big(\frac{\Omega' t}2\Big).

On resonance a pulse of area $\Omega t=\pi$ (a " $\pi$ pulse") is $X$ up to phase, and $\Omega t=\pi/2$ makes an equal superposition. Shifting the phase of the drive changes $X$ to $\cos\chi\,X+\sin\chi\,Y$ , which gives rotations about any axis in the equatorial plane.

Explore

the state rotation axis

\hat n

its path during the pulse · drag to turn

Detuning Δ / Ω Pulse area Ωt

P_1

against pulse area on resonance, for comparison

Worked example

Design a pulse that takes $\ket0$ to $\ket+$ on a resonantly driven qubit with $\Omega/2\pi=50$ kHz, and estimate the error if the drive is detuned by $\Delta=0.1\,\Omega$ .

A drive with phase $\chi=0$ rotates about $x$ . Can it reach $\ket+$ from $\ket0$ ?

No. A rotation about $x$ moves the north pole around the circle in the $y$ – $z$ plane, through $\ket{-i}$ and $\ket1$ , never reaching $+x$ .
Which axis and angle work, and what is the matrix?

A quarter turn about $+y$ (drive phase $\chi=\pi/2$ ) sends $+z$ to $+x$ :

$R_y(\pi/2)=\tfrac1{\sqrt2}\begin{pmatrix}1&-1\\1&1\end{pmatrix},\qquad R_y(\pi/2)\ket0=\ket+.$
How long is the pulse?

We need $\Omega t=\pi/2$ , so $t=\pi/(2\Omega)=\pi/(2\cdot2\pi\cdot50\,\text{kHz})=5\ \mu\text{s}$ .
With $\Delta=0.1\,\Omega$ , how far off is a $\pi$ pulse? (Set Δ/Ω = 0.10 in the explorer.)

The axis tilts by $\arctan0.1\approx5.7^\circ$ , and the largest possible $P_1$ is $\Omega^2/(\Omega^2+\Delta^2)=1/1.01\approx0.990$ . The nominal $\pi$ pulse is also slightly too short for the faster rotation: $\Omega' t=\pi\sqrt{1.01}$ , giving $P_1=0.990\,\sin^2(0.5025\pi)\approx0.990$ . So the error is about 1%, second order in $\Delta/\Omega$ .

Check your understanding

On resonance, a $2\pi$ pulse is applied to $\alpha\ket0+\beta\ket1$ . The result is

exactly the original state.The Bloch vector comes back, but $R_x(2\pi)$ is not the identity matrix.
$-(\alpha\ket0+\beta\ket1)$ .
$\beta\ket0+\alpha\ket1$ .That (up to phase) is what a $\pi$ pulse does: half a turn about $x$ .

R_x(2\pi)=\cos\pi\,I-i\sin\pi\,X=-I

. The sign is a global phase for an isolated qubit, but it becomes a measurable relative phase if the qubit is in superposition with a third, undriven level. A spin-

\tfrac12

state needs a

4\pi

rotation to return to itself exactly.

The detuning equals the Rabi frequency, $\Delta=\Omega$ . What is the largest $P_1$ any pulse length can give?

1, with a long enough pulseOff resonance the oscillation has reduced amplitude, however long you wait.
1/2
1/4The amplitude is $\Omega^2/(\Omega^2+\Delta^2)$ ; don't square it again.

\Omega^2/(\Omega^2+\Delta^2)=1/2

. The axis is tilted

45^\circ

from

z

, so the state circles from the north pole down to the equator and back. Set Δ/Ω = 1 in the explorer.

A qubit has coherence time $T_2=1$ ms and a $\pi$ pulse takes $10\ \mu$ s. Roughly how many sequential gates fit before coherence is mostly lost?

About 10Divide the two times.
About 100
About 10,000Check the units: 1 ms is 1000 μs.

T_2/t_{\text{gate}}=1000/10=100

. This ratio, not either time alone, is the figure of merit, and error correction needs it to be large.

Practice

How far down?The precession cone

With detuning $\Delta$ , the Bloch vector starting at the north pole moves on a circle around $\hat n$ . Find the lowest $z$ it reaches, and check that it agrees with the Rabi formula.

Hint

Rotating $\hat z$ by $\pi$ about $\hat n$ gives the point on the circle farthest from where it started.

Solution

A half turn sends $\hat z$ to $2(\hat n\cdot\hat z)\hat n-\hat z$ , whose $z$ -component is $2n_z^2-1=2\Delta^2/\Omega'^2-1$ . Then $P_1=(1-z)/2=1-\Delta^2/\Omega'^2=\Omega^2/\Omega'^2$ , the amplitude in the Rabi formula.

Pulse lengths for an ionUnits

An ion qubit is driven with $\Omega/2\pi=100$ kHz. How long are its $\pi$ and $\pi/2$ pulses?

Solution

$t_\pi=\pi/\Omega=1/(2\cdot100\,\text{kHz})=5\ \mu$ s and $t_{\pi/2}=2.5\ \mu$ s. A common slip is to use $\Omega=100$ kHz instead of $2\pi\times100$ kHz, which gives a time $2\pi$ times too long.

More practice: Nielsen–Chuang, Exercises 7.18 and 7.31.

InteractiveNielsen–Chuang, Ch. 8: Quantum noise and quantum operations

Noise on the Bloch ball

A qubit that interacts with its surroundings no longer evolves by a unitary. Its evolution is a quantum operation, and for one qubit every such operation squashes and shifts the Bloch ball into an ellipsoid inside it. Pick a channel and watch the ball deform.

The idea

Quantum operation. A map of density operators of the form

\mathcal E(\rho)=\sum_k E_k\,\rho\,E_k^\dagger,\qquad \sum_k E_k^\dagger E_k=I.

The $E_k$ are Kraus operators (operation elements). Every such map arises from a unitary interaction with an environment that starts in a fixed state and is then discarded, and conversely. These maps are exactly the trace-preserving, completely positive ones.

On one qubit. Writing

\rho=\tfrac12(I+\vec r\cdot\vec\sigma)

, every quantum operation acts as an affine map

\vec r\mapsto M\vec r+\vec c

. The image of the ball is an ellipsoid. The common channels:

Bit flip ( $X$ with probability $p$ ): $(x,y,z)\mapsto(x,\,(1-2p)y,\,(1-2p)z)$ .
Phase flip ( $Z$ with probability $p$ ): $(x,y,z)\mapsto((1-2p)x,\,(1-2p)y,\,z)$ .
Depolarising, $\rho\mapsto(1-p)\rho+p\,I/2$ : $\vec r\mapsto(1-p)\vec r$ .
Amplitude damping (energy loss, $\ket1\to\ket0$ with probability $\gamma$ ), $E_0=\big(\begin{smallmatrix}1&0\\0&\sqrt{1-\gamma}\end{smallmatrix}\big)$ , $E_1=\big(\begin{smallmatrix}0&\sqrt\gamma\\0&0\end{smallmatrix}\big)$ : $(x,y,z)\mapsto(\sqrt{1-\gamma}\,x,\,\sqrt{1-\gamma}\,y,\,\gamma+(1-\gamma)z)$ .
Phase damping (loss of coherence without energy loss): $(x,y,z)\mapsto(\sqrt{1-\lambda}\,x,\,\sqrt{1-\lambda}\,y,\,z)$ .

Positive is not enough. The map must stay positive when it acts on half of an entangled pair. The transpose

\rho\mapsto\rho^{\mathsf T}

(a reflection

y\mapsto-y

of the ball) maps the ball to itself, but it is not a quantum operation.

Explore

the Bloch sphere its image under the channel input state after each application · drag to turn

Channel

Strength p Applied n times Input state: polar angle θ Input state: azimuth φ

Worked example

Alice and Bob share $\ket{\beta_{00}}$ , and Bob's qubit goes through a depolarising channel with parameter $p$ . For which $p$ do they still violate CHSH, and for which $p$ are they still entangled?

Find the shared state.

The channel replaces Bob's qubit by $I/2$ with probability $p$ . Since Alice's reduced state is $I/2$ ,

$\rho=(1-p)\ket{\beta_{00}}\bra{\beta_{00}}+p\,\frac{I}{4}.$
What are the CHSH correlations now?

The $I/4$ part has $E=0$ for every pair of settings, so $E(a,b)=(1-p)\cos(a-b)$ and the best value is $S=2\sqrt2\,(1-p)$ . This exceeds 2 only when $p<1-1/\sqrt2\approx0.293$ .
Is the state entangled for larger $p$ ? Use the partial transpose: a separable state stays positive under it.

The partial transpose of $\ket{\beta_{00}}\bra{\beta_{00}}$ is $\tfrac12\mathrm{SWAP}$ , with eigenvalues $\tfrac12,\tfrac12,\tfrac12,-\tfrac12$ . So the partial transpose of $\rho$ has smallest eigenvalue $-\tfrac{1-p}2+\tfrac p4$ , negative exactly when $p<2/3$ . For two qubits this test is also sufficient, so $\rho$ is entangled iff $p<2/3$ .
Put the two thresholds together.

For $0.293<p<2/3$ the pair is entangled but the CHSH test can't show it. Bell violation is a stronger property than entanglement. Its fidelity with $\ket{\beta_{00}}$ , $1-3p/4$ , crosses $1/2$ exactly at $p=2/3$ .

Check your understanding

Apply the channel many times. Which channel drives every input to the same pure state?

DepolarisingIt drives everything to the centre, $I/2$ , which is mixed.
Phase flipIt drives each state to the point on the $z$ -axis below or above it, so different inputs end in different places.
Amplitude damping

Amplitude damping with

n

applications is amplitude damping with

\gamma_n=1-(1-\gamma)^n\to1

, whose image is the single point

\ket0

. It models a qubit relaxing to its ground state. Set n = 12 in the explorer.

A pure state goes through the depolarising channel with parameter $p$ . What is the purity $\mathrm{tr}\rho^2$ of the output?

$1-p$ That's the length of the output Bloch vector. Purity is $(1+|\vec r|^2)/2$ .
$\big(1+(1-p)^2\big)/2$
$1-p/2$ That's the largest eigenvalue, $(1+|\vec r|)/2$ .

|\vec r'|=1-p

, and

\mathrm{tr}\rho^2=(1+|\vec r|^2)/2

. At

p=1

it reaches the minimum

1/2

.

The transpose map $\rho\mapsto\rho^{\mathsf T}$ sends every qubit density operator to a density operator. Is it a quantum operation?

Yes: it maps the Bloch ball onto itself.That shows it is positive. Quantum operations must be completely positive.
No: applied to one half of $\ket{\beta_{00}}$ it produces an operator with a negative eigenvalue.
Yes: it is unitary conjugation by $Y$ . $Y\rho Y$ flips both $x$ and $z$ ; the transpose flips only $y$ . A reflection is not a rotation.

Transposing Bob's half of

\ket{\beta_{00}}\bra{\beta_{00}}

gives

\tfrac12

SWAP, which has eigenvalue

-\tfrac12

. A physical process on Bob's qubit must leave the joint state physical, so the transpose is not one. Unitaries act on the ball as rotations, never as reflections.

Practice

Two flips make a depolariser?Composing channels

Apply a bit flip with probability $p$ and then a phase flip with probability $q$ . Find the combined map on Bloch vectors. For which $p,q$ is it a depolarising channel?

Solution

The scalings multiply: $(x,y,z)\mapsto\big((1-2q)x,\ (1-2p)(1-2q)y,\ (1-2p)z\big)$ . Depolarising needs all three factors equal: $1-2q=1-2p$ and $(1-2p)^2=1-2p$ . So $p=q=0$ (no noise) or $p=q=\tfrac12$ (everything sent to $I/2$ ). Otherwise the ellipsoid is squashed most along $y$ .

Kraus operators for depolarising noiseUsing the Paulis

Find Kraus operators for $\rho\mapsto(1-p)\rho+p\,I/2$ .

Hint

For every qubit $\rho$ , $\tfrac14(\rho+X\rho X+Y\rho Y+Z\rho Z)=I/2$ .

Solution

Substituting, $\mathcal E(\rho)=\big(1-\tfrac{3p}4\big)\rho+\tfrac p4(X\rho X+Y\rho Y+Z\rho Z)$ , so

E_0=\sqrt{1-3p/4}\,I,\quad E_1=\tfrac{\sqrt p}2X,\quad E_2=\tfrac{\sqrt p}2Y,\quad E_3=\tfrac{\sqrt p}2Z,

and $\sum E_k^\dagger E_k=(1-\tfrac{3p}4+\tfrac{3p}4)I=I$ .

More practice: Nielsen–Chuang, Exercises 8.22, 8.27 and 8.30.

InteractiveNielsen–Chuang, Ch. 9: Distance measures for quantum information

Trace distance and fidelity

How different are two quantum states? Trace distance answers operationally: it is the best advantage you can get in telling them apart with one measurement. Fidelity is a generalised overlap. On the Bloch ball both have pictures, and noise can only bring states closer.

The idea

Trace distance.

D(\rho,\sigma)=\tfrac12\,\mathrm{tr}|\rho-\sigma|

, half the sum of the absolute eigenvalues of

\rho-\sigma

. For qubits it is half the Euclidean distance between Bloch vectors:

D=\tfrac12|\vec r-\vec s|

.

What it means.

D(\rho,\sigma)=\max_P\mathrm{tr}\big(P(\rho-\sigma)\big)

over projectors

P

. So if you are handed

\rho

or

\sigma

with probability

\tfrac12

each, the best measurement guesses right with probability

\tfrac12+\tfrac12D

. For qubits the best measurement is along

\vec r-\vec s

.

Fidelity.

F(\rho,\sigma)=\mathrm{tr}\sqrt{\rho^{1/2}\sigma\rho^{1/2}}

. For pure states

F=|\langle\psi|\phi\rangle|

, and

F(\ket\psi,\sigma)=\sqrt{\bra\psi\sigma\ket\psi}

. For qubits,

F^2=\tfrac12\Big(1+\vec r\cdot\vec s+\sqrt{(1-|\vec r|^2)(1-|\vec s|^2)}\Big).

Noise only helps confusion. For every trace-preserving quantum operation,

D(\mathcal E(\rho),\mathcal E(\sigma))\le D(\rho,\sigma)

and

F(\mathcal E(\rho),\mathcal E(\sigma))\ge F(\rho,\sigma)

. The two measures bound each other:

1-F\ \le\ D\ \le\ \sqrt{1-F^2},

with the upper bound an equality for pure states.

Explore

The

x

–

z

slice of the Bloch ball. Drag

\rho

and

\sigma

. Hollow dots: the states after noise. best measurement axis

Try

Depolarising noise on both, p

Worked example

Compare $\ket0$ and $\ket+$ : find $D$ , $F$ , the best measurement, and what depolarising noise with $p=\tfrac12$ does. (Press " $\ket0$ vs $\ket+$ " in the explorer.)

Find the trace distance.

$\vec r=(0,0,1)$ , $\vec s=(1,0,0)$ , $|\vec r-\vec s|=\sqrt2$ , so $D=\sqrt2/2\approx0.707$ .
Find the fidelity, and check both bounds.

$F=|\langle0|+\rangle|=1/\sqrt2\approx0.707$ . Then $1-F\approx0.293\le0.707$ , and $\sqrt{1-F^2}=\sqrt{1/2}\approx0.707$ : the upper bound is attained, as it must be for pure states.
What measurement tells them apart best, and how often does it succeed?

Measure along $(\vec r-\vec s)/|\vec r-\vec s|=(-1,0,1)/\sqrt2$ , halfway between $\ket0$ and $\ket-$ ; guess $\ket0$ on outcome $+1$ . Success probability $\tfrac12+\tfrac12\cdot0.707\approx0.854$ . Measuring $Z$ instead gives only $0.75$ .
After depolarising noise with $p=\tfrac12$ , recompute $D$ and $F$ .

Both Bloch vectors halve: $D'=0.354$ . With $\vec r'\cdot\vec s'=0$ and $|\vec r'|^2=|\vec s'|^2=\tfrac14$ ,

$F'^2=\tfrac12\big(1+0+\tfrac34\big)=\tfrac78,\qquad F'\approx0.935.$

Distance went down and fidelity up, as contractivity says.

Check your understanding

What is $D(\ket0,\ket1)$ ?

2The Bloch vectors are 2 apart, but $D$ has a factor $\tfrac12$ .
1
0.5Orthogonal states are perfectly distinguishable, the maximum.

D

ranges from 0 to 1, and

D=1

means a single measurement tells the states apart with certainty: here a

Z

measurement.

Two states have $D=0.1$ . You get one copy of one of them, each with probability $\tfrac12$ . What is the best chance of naming it correctly?

0.1Guessing blindly already gives 0.5.
0.55
0.9That would need the states to be nearly orthogonal.

The optimum is

\tfrac12+\tfrac12D

. Trace distance is the advantage over a coin flip, doubled.

Can some quantum operation make two states more distinguishable?

Yes, a suitable unitary.Unitaries preserve $D$ exactly: they move the two Bloch points rigidly.
Yes, a measurement that sharpens them.A measurement whose result is kept is also a trace-preserving operation, and it obeys the same bound.
No, not if it is trace-preserving.

Contractivity:

D(\mathcal E(\rho),\mathcal E(\sigma))\le D(\rho,\sigma)

. Processing can't create distinguishability; it can only preserve or lose it. Raise the noise in the explorer and watch

D

fall.

Practice

Pure versus maximally mixedBoth formulas

Compute $D$ and $F$ for $\ket0$ and $I/2$ , and check the bounds $1-F\le D\le\sqrt{1-F^2}$ .

Solution

$D=\tfrac12|(0,0,1)-0|=\tfrac12$ . $F=\sqrt{\bra0\tfrac I2\ket0}=1/\sqrt2\approx0.707$ . Bounds: $0.293\le0.5\le0.707$ , both strict, because $I/2$ is mixed.

Commuting statesBack to classical distances

Suppose $\rho=\sum_ip_i\ket i\bra i$ and $\sigma=\sum_iq_i\ket i\bra i$ are diagonal in the same basis. Show that $D$ and $F$ reduce to the classical distances between the distributions $p$ and $q$ .

Solution

$\rho-\sigma=\sum_i(p_i-q_i)\ket i\bra i$ , so $D=\tfrac12\sum_i|p_i-q_i|$ , the classical total variation distance. And $\rho^{1/2}\sigma\rho^{1/2}=\sum_ip_iq_i\ket i\bra i$ , so $F=\sum_i\sqrt{p_iq_i}$ , the Bhattacharyya overlap. The quantum measures are new only when the states don't commute.

More practice: Nielsen–Chuang, Exercises 9.6, 9.12 and 9.13.

SimulationNielsen–Chuang, Ch. 10: Quantum error-correction

The three-qubit bit-flip code

You can't copy an unknown qubit, and you can't look at it without disturbing it. Even so, $\alpha\ket0+\beta\ket1$ can be spread over three qubits so that a single bit flip is found and undone without anyone learning $\alpha$ or $\beta$ . Flip qubits by hand, then run thousands of noisy rounds.

The idea

Encoding.

\alpha\ket0+\beta\ket1\mapsto\alpha\ket{000}+\beta\ket{111}

, by two CNOTs from the data qubit onto two fresh

\ket0

s. This is an entangled state, not three copies.

Syndrome. Measure the parities

Z_1Z_2

and

Z_2Z_3

. Both

\ket{000}

and

\ket{111}

(and their versions with the same qubit flipped) give the same values, so the measurement learns only which qubit, if any, was flipped:

(+,+):\ \text{none},\qquad(-,+):\ \text{qubit 1},\qquad(-,-):\ \text{qubit 2},\qquad(+,-):\ \text{qubit 3}.

When it helps. If each qubit flips independently with probability

p

, the code fails only when two or more flip:

p_L=3p^2(1-p)+p^3=3p^2-2p^3,

which is smaller than $p$ for every $p<\tfrac12$ .

General codes. A code with projector

P

corrects a set of errors

\{E_i\}

iff

PE_i^\dagger E_jP=\alpha_{ij}P

for a Hermitian matrix

(\alpha_{ij})

. Correcting

X

,

Y

and

Z

on a qubit corrects every error on it (errors are discretised by the syndrome measurement). Nesting this code inside a phase-flip version of itself gives Shor's 9-qubit code, which corrects any single-qubit error.

Explore

no code:

p

with the code:

3p^2-2p^3

your simulated runs

One round by hand: flip these qubits

Flip probability per qubit, p

Worked example

Encode $0.6\ket0+0.8\ket1$ . Follow one round with a single error and one with a double error.

Write the encoded state, and the state after an $X$ error on qubit 2.

$0.6\ket{000}+0.8\ket{111}$ , and after $X_2$ : $0.6\ket{010}+0.8\ket{101}$ .
What syndrome is measured, and what is the state afterwards?

On both terms, qubits 1 and 2 differ and qubits 2 and 3 differ, so $(Z_1Z_2,Z_2Z_3)=(-1,-1)$ with certainty. Since the outcome was certain, the state is undisturbed: $0.6$ and $0.8$ are untouched, and nobody learned them.
Correct and decode.

$(-,-)$ points to qubit 2. Applying $X_2$ restores $0.6\ket{000}+0.8\ket{111}$ , and reversing the encoder gives $0.6\ket0+0.8\ket1$ .
Now suppose qubits 1 and 2 both flip. What happens?

The state is $0.6\ket{110}+0.8\ket{001}$ , the syndrome is $(+,-)$ , which points to qubit 3. "Correcting" qubit 3 gives $0.6\ket{111}+0.8\ket{000}$ : a logical $X$ . The decoded state is $0.8\ket0+0.6\ket1$ , whose overlap with the original is $0.6\cdot0.8+0.8\cdot0.6=0.96$ . The code has silently made an error; the fidelity happens to be high only because this particular state is close to its own image under $X$ .

Check your understanding

An $X$ error hits qubit 3 of $\alpha\ket{000}+\beta\ket{111}$ . What syndrome $(Z_1Z_2,Z_2Z_3)$ is measured?

$(-,+)$ That pattern means qubit 1 disagrees with qubit 2.
$(+,-)$
It depends on $\alpha$ and $\beta$ .Both terms, $\ket{001}$ and $\ket{110}$ , have the same parities.

After the error the state is

\alpha\ket{001}+\beta\ket{110}

. Qubits 1 and 2 agree, qubits 2 and 3 differ, in both terms. The syndrome is a fact about the error, not about the encoded data.

Why doesn't measuring $Z_1Z_2$ collapse the encoded superposition, when measuring $Z_1$ would?

$\ket{000}$ and $\ket{111}$ have the same $Z_1Z_2$ value but opposite $Z_1$ values.
Because two-qubit measurements never disturb states.A Bell measurement disturbs plenty. It's about which eigenspace the state lies in.
It does collapse it, but the correction step undoes that.The correction is a fixed $X$ , which can't restore lost amplitudes.

The encoded state lies entirely inside one eigenspace of

Z_1Z_2

, so the measurement has a certain outcome and leaves it alone.

Z_1

would distinguish

\ket{000}

from

\ket{111}

, revealing

|\alpha|^2

versus

|\beta|^2

and destroying the superposition.

Can this code correct a phase flip $Z_1$ ?

Yes, it corrects any single-qubit error.That's Shor's 9-qubit code, not this one.
No: $Z_1$ turns the codeword into another codeword, so the syndrome is trivial.
Yes, by applying $Z$ to all three qubits.The syndrome gives no sign that anything happened, so the decoder wouldn't know to.

Z_1(\alpha\ket{000}+\beta\ket{111})=\alpha\ket{000}-\beta\ket{111}

: a logical

Z

, undetectable. To handle phase flips, encode in the

\ket\pm

basis instead; to handle both, nest the two codes.

Practice

Is it worth it?Numbers

At $p=0.1$ , what is $p_L$ and by what factor has the code helped? At what $p$ does the code stop helping?

Solution

$p_L=3(0.01)-2(0.001)=0.028$ , about 3.6 times better than 0.1. Solving $3p^2-2p^3=p$ gives $p=\tfrac12$ (and $p=0,1$ ); the code helps for all $0<p<\tfrac12$ . Check with the slider and "Run".

A small rotation, not a flipErrors are discretised

Instead of a flip, qubit 1 suffers the small rotation $e^{-i\varepsilon X_1}$ . Show that the syndrome measurement turns this into either no error or a full $X_1$ , and that the code then recovers the state exactly.

Solution

$e^{-i\varepsilon X_1}\ket{\psi_L}=\cos\varepsilon\ket{\psi_L}-i\sin\varepsilon\,X_1\ket{\psi_L}$ . The two terms lie in the syndrome spaces $(+,+)$ and $(-,+)$ . The measurement picks the first with probability $\cos^2\varepsilon$ (leaving $\ket{\psi_L}$ ) or the second with probability $\sin^2\varepsilon$ (leaving $X_1\ket{\psi_L}$ , which is then corrected). Either way the result is $\ket{\psi_L}$ .

More practice: Nielsen–Chuang, Exercises 10.3 and 10.4.

InteractiveNielsen–Chuang, Ch. 11: Entropy and information

Entropy and entanglement

Shannon entropy measures the uncertainty of a random variable; von Neumann entropy does the same for a quantum state. For a pure state of two qubits, the entropy of either half measures how entangled they are. Set the four amplitudes and watch it.

The idea

Shannon entropy.

H(p)=-\sum_ip_i\log_2p_i

bits. For two outcomes, the binary entropy

H(p)=-p\log_2p-(1-p)\log_2(1-p)

, which peaks at 1 bit when

p=\tfrac12

.

Von Neumann entropy.

S(\rho)=-\mathrm{tr}(\rho\log_2\rho)=H(\lambda)

, the Shannon entropy of the eigenvalues of

\rho

.

S=0

exactly for pure states, and

S\le\log_2 d

in dimension

d

.

Two halves of a pure state. If

\ket\psi_{AB}

is pure,

S(\rho_A)=S(\rho_B)

: both reduced states have the Schmidt coefficients squared as eigenvalues. This common value is the entropy of entanglement, 0 for product states and 1 bit for Bell states.

Quantum oddities. Subadditivity

S(A,B)\le S(A)+S(B)

holds as classically, but the whole can have less entropy than a part: for a Bell state

S(A,B)=0<S(A)=1

. Measuring

\rho

in any basis gives outcomes with Shannon entropy at least

S(\rho)

, with equality in the eigenbasis.

Explore

amplitude of |00⟩ amplitude of |01⟩ amplitude of |10⟩ amplitude of |11⟩

Binary entropy

H(\lambda)

.

S(\rho_A)

at the smaller eigenvalue

\lambda

Shannon entropy of a

Z

measurement on

A

The reduced states in the

x

–

z

slice of the Bloch ball.

\rho_A

\rho_B

Worked example

Find the entropy of entanglement of $\ket\psi=\tfrac1{\sqrt5}\big(\ket{00}+\sqrt2\ket{01}+\sqrt2\ket{10}\big)$ , and compare it with the entropy of a $Z$ measurement on qubit $A$ . (It is a preset in the explorer.)

Arrange the amplitudes in a matrix $C$ (rows: $A$ , columns: $B$ ) and compute $\rho_A=CC^\dagger$ .

$C=\frac1{\sqrt5}\begin{pmatrix}1&\sqrt2\\ \sqrt2&0\end{pmatrix},\qquad \rho_A=CC^\dagger=\frac15\begin{pmatrix}3&\sqrt2\\ \sqrt2&2\end{pmatrix}.$
Find the eigenvalues of $\rho_A$ .

Trace 1, determinant $(6-2)/25=4/25$ . The eigenvalues solve $\lambda^2-\lambda+\tfrac4{25}=0$ : $\lambda=0.8$ and $0.2$ . (Also $\det\rho_A=|\det C|^2=(2/5)^2$ .) The Schmidt coefficients are $\sqrt{0.8}$ and $\sqrt{0.2}$ .
Compute $S(\rho_A)$ .

$S=H(0.2)=-0.2\log_20.2-0.8\log_20.8\approx0.464+0.258=0.722$ bits.
What is the Shannon entropy of a $Z$ measurement on $A$ alone?

$p(A=0)=\rho_{00}=0.6$ , so $H(0.6)\approx0.971$ bits, more than 0.722. The $Z$ basis isn't $\rho_A$ 's eigenbasis (the off-diagonal entry is nonzero), so measuring in it adds uncertainty.

Check your understanding

A pure two-qubit state has $S(\rho_A)=1$ . What is $S(\rho_{AB})$ ?

2Subadditivity gives an upper bound, $S(A,B)\le S(A)+S(B)=2$ , not the value.
1The joint state is pure.
0

Pure states have zero entropy. The whole is perfectly known while each part is maximally uncertain, which has no classical analogue: classically

H(X,Y)\ge H(X)

.

Which is more entangled: $\cos\tfrac\pi8\ket{00}+\sin\tfrac\pi8\ket{11}$ , or $\tfrac12(\ket{00}-\ket{01}+\ket{10}-\ket{11})$ ?

The first.
The second: it has four terms.It factors as $\ket+\otimes\ket-$ .
They are equally entangled.The second is a product state, with entropy 0.

The first is already in Schmidt form with

\lambda^2=\sin^2\tfrac\pi8\approx0.146

, giving

H(0.146)\approx0.60

bits. The second has amplitude matrix

C=\tfrac12\big(\begin{smallmatrix}1&-1\\1&-1\end{smallmatrix}\big)

with

\det C=0

, so it is a product.

$\rho$ has eigenvalues 0.9 and 0.1. You measure it in a basis that is not its eigenbasis. The Shannon entropy of the outcomes is

exactly $H(0.1)\approx0.47$ bits.That equality holds only in the eigenbasis.
less than 0.47 bits.The eigenbasis is the basis that minimises the outcome entropy.
more than 0.47 bits.

The outcome probabilities are averages of the eigenvalues,

p_j=\sum_i|\langle j|e_i\rangle|^2\lambda_i

, which makes them more even unless the basis is the eigenbasis. More even means more entropy. This is how the explorer's gold point stays at or above the blue one.

Practice

Entropy of an ensembleQuantum entropy can be smaller

A source emits $\ket0$ , $\ket1$ or $\ket+$ , each with probability $\tfrac13$ . Compute $S(\rho)$ and compare it with the Shannon entropy $\log_23$ of the source's choice.

Solution

Averaging Bloch vectors, $\vec r=\tfrac13(0,0,1)+\tfrac13(0,0,-1)+\tfrac13(1,0,0)=(\tfrac13,0,0)$ . The eigenvalues are $(1\pm|\vec r|)/2=\tfrac23,\tfrac13$ , so $S=H(\tfrac13)\approx0.918$ bits, less than $\log_23\approx1.585$ . Because the states aren't orthogonal, $\rho$ holds less entropy than the label that picked them.

Equal entropiesFrom the Schmidt decomposition

Show that $S(\rho_A)=S(\rho_B)$ for every pure state $\ket\psi_{AB}$ , even when $A$ and $B$ have different dimensions.

Solution

Write $\ket\psi=\sum_i\lambda_i\ket{i_A}\ket{i_B}$ . Then $\rho_A=\sum_i\lambda_i^2\ket{i_A}\bra{i_A}$ and $\rho_B=\sum_i\lambda_i^2\ket{i_B}\bra{i_B}$ : the same nonzero eigenvalues. Extra zero eigenvalues in the larger system add nothing to the entropy.

More practice: Nielsen–Chuang, Exercises 11.11, 11.12 and 11.14.

SimulationNielsen–Chuang, Ch. 12: Quantum information theory

Quantum key distribution

Learning anything about a non-orthogonal state disturbs it. The BB84 protocol turns that into security: an eavesdropper who gains information about the key leaves errors that Alice and Bob can measure. Send qubits with and without Eve on the line.

The idea

BB84. For each round Alice picks a random bit and a random basis,

Z

or

X

, and sends

\ket0,\ket1

or

\ket+,\ket-

. Bob measures in a random basis. Afterwards they announce the bases (not the bits) and keep only the rounds where the bases agree (sifting, about half). They reveal a random sample of the kept bits to estimate the error rate, then use error correction and privacy amplification to distil a shorter secret key.

Information gain causes disturbance. Any interaction that lets Eve learn something about which of two non-orthogonal states was sent must change at least one of them. (If it didn't, Eve could use it to copy or distinguish them, contradicting no-cloning.)

Intercept–resend. If Eve measures a fraction

f

of the qubits in a random basis and resends what she saw, she picks the wrong basis half the time, and then Bob's sifted bit is random. The error rate in the sifted key is

f/4

.

Security threshold. The Shor–Preskill proof shows a secret key can be extracted at rate

1-2H(e)

per sifted bit when the error rate is

e

. This is positive for

e\lesssim11\%

.

Holevo bound. If Alice encodes

x

in states

\rho_x

with probabilities

p_x

, the information Bob can obtain by any measurement is at most

\chi=S\big(\sum_xp_x\rho_x\big)-\sum_xp_xS(\rho_x)

. For one qubit,

\chi\le1

bit.

Explore

Eve intercepts this fraction of qubits

One column per qubit. Bases: + is

Z

, × is

X

. rounds Eve intercepted kept after sifting Bob's bit differs from Alice's

Worked example

Eve intercepts every qubit ( $f=1$ ), measuring each in a random basis and resending the state she found. Work out the error rate she causes, how much she learns, and how quickly she is caught.

Consider a sifted round (Alice and Bob used the same basis). What happens if Eve guessed that basis too?

She gets Alice's bit exactly and resends the same state. No error, and Eve knows the bit.
And if Eve used the other basis?

Her result is random and she resends, say, $\ket+$ when Alice sent $\ket0$ . Bob measures in Alice's basis and gets a random bit: an error with probability $\tfrac12$ .
Combine the cases: error rate and Eve's chance of knowing a sifted bit.

Error rate $\tfrac12\cdot0+\tfrac12\cdot\tfrac12=\tfrac14$ . Eve's guess at a sifted bit is right with probability $\tfrac12\cdot1+\tfrac12\cdot\tfrac12=\tfrac34$ . If she intercepts only a fraction $f$ of the qubits, the error rate is $f/4$ .
Alice and Bob compare 20 sifted bits. How likely is it that they see no error at all?

$(3/4)^{20}\approx0.003$ . Comparing a few dozen bits catches a full intercept–resend attack almost surely. Partial attacks are subtler, which is why the protocol estimates the rate and then distils the key.

Check your understanding

Why does Alice use two bases rather than just $\ket0$ and $\ket1$ ?

Orthogonal states can be measured and resent perfectly, so Eve would leave no trace.
To double the key rate.Sifting throws half the rounds away, so two bases lower the raw rate.
Because a single basis would violate the Holevo bound.One bit per qubit in one basis is exactly at the Holevo bound, not beyond it.

Disturbance is forced only for non-orthogonal states. Mixing two conjugate bases means Eve can't know which basis to measure in without knowing Alice's choice, which is revealed only after the qubit has reached Bob.

Eve intercepts every qubit with a randomly chosen basis. What error rate do Alice and Bob see in the sifted key?

50%She only chooses the wrong basis half the time.
25%
12.5%That would be the rate if she intercepted half the qubits.

Wrong basis with probability

\tfrac12

, then a random result for Bob with probability

\tfrac12

of disagreement. Set the slider to 100% and send 10,000 qubits.

Alice sends one qubit, prepared in any of infinitely many states. How much classical information can Bob extract, at most?

Unlimited: the amplitudes are continuous.Bob can't read amplitudes, only sample outcomes.
1 bit
2 bitsThat's superdense coding, which needs a pre-shared entangled pair.

Holevo:

\chi\le S(\rho)\le\log_22=1

. A qubit has a continuum of states but carries at most one classical bit.

Practice

A lazy eavesdropperAlways the same basis

Eve intercepts every qubit but always measures in the $X$ basis. What error rate does she cause in the sifted key, and what does she learn?

Solution

In sifted rounds where Alice used $Z$ (half of them), Eve's basis is wrong and Bob errs with probability $\tfrac12$ ; in rounds with $X$ there is no error. Error rate: $\tfrac14$ , the same as before. She learns every $X$ -basis bit exactly and nothing about the $Z$ -basis ones, so after the bases are announced she knows exactly which of her bits are good.

How much key survives?The Shor–Preskill rate

Alice and Bob measure an error rate of 5% in their sifted key. Using the rate $1-2H(e)$ , what fraction of the sifted bits becomes secret key? What about at 11%?

Solution

$H(0.05)\approx0.286$ , so the rate is $1-0.573\approx0.43$ : about 43 key bits per 100 sifted bits. At 11%, $H(0.11)\approx0.4999$ and the rate is essentially zero. One $H(e)$ pays for error correction and the other for privacy amplification.

More practice: Nielsen–Chuang, Exercises 12.27 and 12.29.