PHYS598500 · Week 1 · T1
→Because computation needs hardware.
In physics, we study:
wrong
correct
Seven-place common (base-10) logarithms: the page prints only the last four mantissa digits, the leading \(760\) coming from the block header N. 57500 L. 759.
Charles Babbage (1791–1871) first designed the Difference Engine to automate numerical tables. Finite differences reduce polynomial tabulation to repeated addition, making the task suitable for a gear-based mechanism and reducing human calculation and typesetting errors.
The later Analytical Engine was a general architecture. It separated a “store” from a “mill,” used punched cards to specify operations and data, and included sequencing, repetition, and conditional control.
The full Analytical Engine was not completed in Babbage's lifetime.
Plan of the calculating
mechanism
Ref:
Cronatec · How did the Difference Engine work?
▲
Ref:
https://cronatec.ch/how-did-the-difference-engine-work/
Addition and carriage
mechanisms
Ref:
Cronatec · How did the Difference Engine work?
▲
Ref:
https://cronatec.ch/how-did-the-difference-engine-work/
Complete
reconstruction
Ref:
Science Museum Group Collection
▲
Ref:
https://collection.sciencemuseumgroup.org.uk/objects/co62748/babbages-difference-engine-no-2-2002
Decimal figure wheels and gear
trains
Ref:
Science Museum Group Collection
▲
Ref:
https://collection.sciencemuseumgroup.org.uk/objects/co62748/babbages-difference-engine-no-2-2002
Boole showed that logical statements can be represented by symbols and manipulated with algebraic rules.
For Boolean variables \(a,b\in \{F,T\} \text{ or }\{0,1\}\), logical AND behaves exactly like multiplication:
| \(a\) | \(b\) | \(a\land b\) |
|---|---|---|
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
| \(a\) | \(b\) | \(a*b\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
For \(a,b\in\{0,1\}\), \(a\land b=a*b\).
George Boole
Ref:
Wikipedia
Claude Shannon (1916–2001) showed that the ON/OFF behavior of relay circuits follows Boolean algebra. A switch is OFF when the circuit is open and ON when a conducting path is closed. We encode OFF as \(0\) and ON as \(1\).
| Connection | Boolean operation |
|---|---|
| Series: output is ON only when \(a\) and \(b\) are ON | \(a\land b\) |
| Parallel: output is ON when \(a\) or \(b\) is ON | \(a\lor b\) |
| Normally closed: output is ON when \(a\) is OFF | \(\neg a\) |
\[\boxed{\text{Boolean expression}\longleftrightarrow\text{switching network}.}\]
This made circuit design systematic: specify the desired ON/OFF output, express and simplify it with Boolean algebra, then connect switches that realize the same relation.
Refs: Britannica · UTMEL · Deep Forest
An algorithm or a program is a timed sequence of voltage potential \(V(t)\).
\(H(t)=H_{\mathrm{hardware}}+V(t)\)
A quantum algorithm is a time‑dependent Hamiltonian \(H(t)\).
\[i\hbar\frac{d}{dt}|\psi(t)\rangle=H(t)|\psi(t)\rangle,\]
\[U(T,0)=\mathcal T\exp\!\left[-\frac{i}{\hbar}\int_0^T H(t)\,dt\right],\]
\[|\psi(T)\rangle=U(T,0)|\psi(0)\rangle.\]
\[\begin{align*}
U(T,0)&\approx \mathcal T\exp\!\left[-\frac{i}{\hbar}\int_{T_n}^T H(t)\,dt\right]*\mathcal
T\exp\!\left[-\frac{i}{\hbar}\int_{T_{n-1}}^{T_n} H(t)\,dt\right]*...*\mathcal
T\exp\!\left[-\frac{i}{\hbar}\int_0^{T_1} H(t)\,dt\right],\\
&\approx U(T,T_n)*U(T_n,T_{n-1})*...*U(T_1,0)
\end{align*}\]
\[i\hbar\frac{d}{dt}|\psi(t)\rangle=H(t)|\psi(t)\rangle,\]
\[U(T,0)=\mathcal T\exp\!\left[-\frac{i}{\hbar}\int_0^T H(t)\,dt\right],\]
\[|\psi(T)\rangle=U(T,0)|\psi(0)\rangle.\]
\[\boxed{\text{Reversibility}:\exists U^{-1} \text{ s.t } U*U^{-1}=I}\]
\[U^{-1}(T,0)=U(0,T)=U^\dagger(T,0)=\mathcal T\exp\!\left[\textcolor{red}{+}\frac{i}{\hbar}\int_0^T H(t)\,dt\right]\]
\[\langle \psi(T)|\psi(T)\rangle=\langle \psi(0)|U^\dagger(T,0)* U(T,0)|\psi(T)\rangle=\langle \psi(0)|\psi(0)\rangle=1\]
\[\begin{align*}
U(T,0)&\approx \mathcal T\exp\!\left[-\frac{i}{\hbar}\int_{T_n}^T H(t)\,dt\right]*\mathcal
T\exp\!\left[-\frac{i}{\hbar}\int_{T_{n-1}}^{T_n} H(t)\,dt\right]*...*\mathcal
T\exp\!\left[-\frac{i}{\hbar}\int_0^{T_1} H(t)\,dt\right],\\
&\approx U(T,T_n)*U(T_n,T_{n-1})*...*U(T_1,0)
\end{align*}\]
\[\boxed{\text{Boolean function}\rightarrow\text{reversible embedding}\rightarrow\text{unitary}\rightarrow H(t).}\]
A gate is reversible only when its output identifies one unique input.
Erasing one unbiased bit requires the environment to receive at least
\[\Delta S_{\mathrm{env}}\ge k_B\ln2\]
\[Q_{\min}\ge k_BT\ln2\]
Half adder: \(01\) and \(10\) both produce \((\mathrm{Carry},\mathrm{Sum})=(0,1)\).
Source: Landauer (1961).
| A | B | Carry | Sum |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
01 and 10 both give (Carry, Sum) = (0, 1).
| A | B | C | P | R = Carry | Q = Sum |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 |
With C = 0, P = A preserves the input, so 01 and 10 remain distinct.
\[i\hbar\frac{d}{dt}|\psi(t)\rangle=H(t)|\psi(t)\rangle,\]
\[U(T,0)=\mathcal T\exp\!\left[-\frac{i}{\hbar}\int_0^T H(t)\,dt\right],\]
\[|\psi(T)\rangle=U(T,0)|\psi(0)\rangle.\]
\[\boxed{\text{Reversibility}:\exists U^{-1} \text{ s.t } U*U^{-1}=I}\]
\[U^{-1}(T,0)=U(0,T)=U^\dagger(T,0)=\mathcal T\exp\!\left[\textcolor{red}{+}\frac{i}{\hbar}\int_0^T H(t)\,dt\right]\]
\[\langle \psi(T)|\psi(T)\rangle=\langle \psi(0)|U^\dagger(T,0)* U(T,0)|\psi(T)\rangle=\langle \psi(0)|\psi(0)\rangle=1\]
\[\begin{align*}
U(T,0)&\approx \mathcal T\exp\!\left[-\frac{i}{\hbar}\int_{T_n}^T H(t)\,dt\right]*\mathcal
T\exp\!\left[-\frac{i}{\hbar}\int_{T_{n-1}}^{T_n} H(t)\,dt\right]*...*\mathcal
T\exp\!\left[-\frac{i}{\hbar}\int_0^{T_1} H(t)\,dt\right],\\
&\approx U(T,T_n)*U(T_n,T_{n-1})*...*U(T_1,0)
\end{align*}\]
\[\boxed{\text{Boolean function}\rightarrow\text{reversible embedding}\rightarrow\text{unitary}\rightarrow H(t).}\]
\[U(T,0)=\mathcal T\exp\!\left[-\frac{i}{\hbar}\int_0^T H(t)\,dt\right],\]
\[|\psi(T)\rangle=U(T,0)|\psi(0)\rangle.\]
The Hamiltonian \(H\) is Hermitian, so \(U^\dagger(t)U(t)=I\) and total probability remains
one.
\[
\begin{align*}
i\hbar \partial_t |\psi \rangle
&= H |\psi_\rangle
\\
i\hbar \partial_t
\begin{pmatrix}
\psi_0\\
\psi_1
\end{pmatrix}
&=\begin{pmatrix}
H_{00}&H;_{01}\\
H_{10}&H;_{11}
\end{pmatrix}
\begin{pmatrix}
\psi_0\\
\psi_1
\end{pmatrix}
=\begin{pmatrix}
h_a&h;_x-ih_y\\
h_x+ih_y&h;_b
\end{pmatrix}
\begin{pmatrix}
\psi_0\\
\psi_1
\end{pmatrix}
\end{align*}
\]
\[\qquad a,b,x,y\in\mathbb R\]
Four independent real parameters specify the generator.
\[U(T,0)=\mathcal T\exp\!\left[-\frac{i}{\hbar}\int_0^T H(t)\,dt\right],\]
\[|\psi(T)\rangle=U(T,0)|\psi(0)\rangle.\]
The Hamiltonian \(H\) is Hermitian, so \(U^\dagger(t)U(t)=I\) and total probability remains
one.
\[
\begin{align*}
i\hbar \partial_t |\psi \rangle
&= H |\psi_\rangle
\\
i\hbar \partial_t
\begin{pmatrix}
\psi_0\\
\psi_1
\end{pmatrix}
&=\begin{pmatrix}
H_{00}&H;_{01}\\
H_{10}&H;_{11}
\end{pmatrix}
\begin{pmatrix}
\psi_0\\
\psi_1
\end{pmatrix}
=\begin{pmatrix}
h_a&h;_x-ih_y\\
h_x+ih_y&h;_b
\end{pmatrix}
\begin{pmatrix}
\psi_0\\
\psi_1
\end{pmatrix}
\end{align*}
\]
\[\qquad a,b,x,y\in\mathbb R\]
Four independent real parameters specify the generator.
\[ c=\frac{h_a+h_b}{2}, \ h_z=\frac{h_a-h_b}{2} \]
\[ \begin{align*} H=\begin{pmatrix} c+h_z&h;_x-ih_y\\ h_x+ih_y&c-h;_z \end{pmatrix} &= c\begin{pmatrix} 1&0\\ 0&1 \end{pmatrix} +h_x\begin{pmatrix} 0&1\\ 1&0 \end{pmatrix} +h_y\begin{pmatrix} 0&-i\\ i&0 \end{pmatrix} +h_z\begin{pmatrix} 1&0\\ 0&-1 \end{pmatrix} \\&\equiv cI + \underbracket{h_x\sigma_x +h_y\sigma_y +h_z\sigma_z}_{H'}, \quad \sigma_i \text{ :Pauli matrices} \end{align*} \]
\[U(T,0)=\mathcal T\exp\!\left[-\frac{i}{\hbar}\int_0^T H(t)\,dt\right],\]
\[|\psi(T)\rangle=U(T,0)|\psi(0)\rangle.\]
The Hamiltonian \(H\) is Hermitian, so \(U^\dagger(t)U(t)=I\) and total probability remains
one.
\[
\begin{align*}
i\hbar \partial_t |\psi \rangle
&= H |\psi_\rangle
\\
i\hbar \partial_t
\begin{pmatrix}
\psi_0\\
\psi_1
\end{pmatrix}
&=\begin{pmatrix}
H_{00}&H;_{01}\\
H_{10}&H;_{11}
\end{pmatrix}
\begin{pmatrix}
\psi_0\\
\psi_1
\end{pmatrix}
=\begin{pmatrix}
h_a&h;_x-ih_y\\
h_x+ih_y&h;_b
\end{pmatrix}
\begin{pmatrix}
\psi_0\\
\psi_1
\end{pmatrix}
\end{align*}
\]
\[\qquad a,b,x,y\in\mathbb R\]
Four independent real parameters specify the generator.
\[ c=\frac{h_a+h_b}{2}, \ h_z=\frac{h_a-h_b}{2} \]
\[ \begin{align*} H=\begin{pmatrix} c+h_z&h;_x-ih_y\\ h_x+ih_y&c-h;_z \end{pmatrix} &= c\begin{pmatrix} 1&0\\ 0&1 \end{pmatrix} +h_x\begin{pmatrix} 0&1\\ 1&0 \end{pmatrix} +h_y\begin{pmatrix} 0&-i\\ i&0 \end{pmatrix} +h_z\begin{pmatrix} 1&0\\ 0&-1 \end{pmatrix} \\&\equiv cI + \underbracket{h_x\sigma_x +h_y\sigma_y +h_z\sigma_z}_{H'}, \quad \sigma_i \text{ :Pauli matrices} \end{align*} \]
\[ e^{-itH}=e^{-it(cI+H')}=e^{-itc}e^{-itH'} \]
The factor \(e^{-itc}\) is a global phase. Observable state evolution therefore comes from \(H'\).
\[ \sigma_x=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \sigma_y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\qquad \sigma_z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}. \]
\[ \boxed{\sigma_i\sigma_j=\delta_{ij}I+i \epsilon_{ijk}\sigma_k} \]
\[ \sigma_i \sigma_j=- \sigma_j \sigma_i=i \epsilon_{ijk}\sigma_k , \qquad \sigma_x \sigma_x =\sigma_y \sigma_y =\sigma_z \sigma_z= I, \qquad \operatorname{Tr} (\sigma_i)=0. \]
\[ \sigma_x=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \sigma_y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\qquad \sigma_z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}. \]
\[ \boxed{\sigma_i\sigma_j=\delta_{ij}I+i \epsilon_{ijk}\sigma_k} \]
\[ \sigma_i \sigma_j=- \sigma_j \sigma_i=i \epsilon_{ijk}\sigma_k , \qquad \sigma_x \sigma_x =\sigma_y \sigma_y =\sigma_z \sigma_z= I, \qquad \operatorname{Tr} (\sigma_i)=0. \]
\[ \begin{align*} H&= cI + h_x\sigma_x +h_y\sigma_y +h_z\sigma_z \end{align*} \]
\[ \begin{align*} h_i =\frac{1}{2} \operatorname{Tr}(H\sigma_i) \end{align*} \]
For example, \[ \begin{align*} h_x = \frac{1}{2}\operatorname{Tr}(H\sigma_x) &= \frac{1}{2}\operatorname{Tr}\left[\left(cI + h_x\sigma_x +h_y\sigma_y +h_z\sigma_z\right)\sigma_x\right]\\ &=\frac{1}{2} \operatorname{Tr}\left(c \sigma_x + h_x\sigma_x \sigma_x +h_y\sigma_y \sigma_x +h_z\sigma_z \sigma_x\right)\\ &=\frac{1}{2} \operatorname{Tr}\left(c \sigma_x + h_x I -i h_y\sigma_z + i h_z\sigma_y \right) \end{align*} \]
\[ \sigma_x=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \sigma_y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\qquad \sigma_z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}. \]
\[ \boxed{\sigma_i\sigma_j=\delta_{ij}I+i \epsilon_{ijk}\sigma_k} \]
\[ \sigma_i \sigma_j=- \sigma_j \sigma_i=i \epsilon_{ijk}\sigma_k , \qquad \sigma_x \sigma_x =\sigma_y \sigma_y =\sigma_z \sigma_z= I, \qquad \operatorname{Tr} (\sigma_i)=0. \]
\[ \sigma_i^\dagger=\sigma_i,\qquad \sigma_i^2=I,\qquad \sigma_i^{-1}=\sigma_i \]
\[ \operatorname{spec}(\sigma_i)=\{+1,-1\}. \]
For any two state system with orthonormal basis \(|a \rangle, \ |b \rangle\) \[|\psi\rangle = c_0 |a \rangle + c_1 |b \rangle,\quad c_k=|c_k|e^{i\phi_k}\in \mathbb{C},\quad \langle a|b \rangle=0\] \[\left\{ \begin{array}{c} \langle \psi|\psi \rangle=1 \to |c_0|^2+|c_1|^2=1 \\ \text{unobservable global phase }\phi_0 \end{array} \right.\] \[|\psi(\theta,\phi)\rangle =\cos\!\left(\frac{\theta}{2}\right)|a\rangle +e^{i\phi}\sin\!\left(\frac{\theta}{2}\right)|b\rangle \]
\(0\leq\theta\leq\pi,\qquad 0\leq\phi< 2\pi\)
We normally choose \(|0 \rangle, \ |1 \rangle\) as our orthonormal basis \(|0 \rangle=\left( \begin{array}{c} 1 \\ 0 \end{array} \right), \ |1 \rangle =\left( \begin{array}{c} 0 \\ 1 \end{array} \right), \ |\psi \rangle =\left( \begin{array}{c} \cos\!\left(\frac{\theta}{2}\right) \\ e^{i\phi}\sin\!\left(\frac{\theta}{2}\right) \end{array} \right) \)
\[|\psi\rangle = c_0 |0 \rangle + c_1 |1 \rangle, c_k=|c_k|e^{i\phi_k}\in \mathbb{C}\]
\[|c_0|^2+|c_1|^2=1 \to \left\{ \begin{array}{c} |c_0|\equiv \cos \left( \frac{\theta}{2} \right) \\ |c_1|\equiv \sin \left( \frac{\theta}{2} \right) \end{array} \right.\]
\[|\psi\rangle = \cos \left( \frac{\theta}{2} \right)e^{i\phi_0}|0\rangle +\sin \left( \frac{\theta}{2} \right)e^{i\phi_1}|1\rangle\]
\[=e^{i\phi_0}\left[ \cos \left( \frac{\theta}{2} \right)|0\rangle +\sin \left( \frac{\theta}{2} \right)e^{i(\phi_1-\phi_0)}|1\rangle \right]\]
\[\equiv e^{i\phi_0}\left[ \cos \left( \frac{\theta}{2} \right)|0\rangle +\sin \left( \frac{\theta}{2} \right)e^{i\phi}|1\rangle \right] =e^{i\phi_0}\begin{pmatrix} \cos(\theta/2)\\ e^{i\phi}\sin(\theta/2) \end{pmatrix}\]
Density matrix \(\rho\):
\[\rho\equiv|\psi\rangle\langle\psi| =e^{i\phi_0}\begin{pmatrix} \cos(\theta/2)\\ e^{i\phi}\sin(\theta/2) \end{pmatrix} \otimes e^{-i\phi_0}\begin{pmatrix} \cos(\theta/2)&e;^{-i\phi}\sin(\theta/2) \end{pmatrix}\]
\[=\begin{pmatrix} \cos^2(\theta/2)&e;^{-i\phi}\sin(\theta/2)\cos(\theta/2)\\ e^{i\phi}\sin(\theta/2)\cos(\theta/2)&\sin^2(\theta/2) \end{pmatrix}\]
\[=\frac12\begin{pmatrix} 1+\cos\theta&e;^{-i\phi}\sin\theta\\ e^{i\phi}\sin\theta&1-\cos\theta \end{pmatrix}\]
\[|\psi\rangle = e^{i\phi_0}\left[ \cos \left( \frac{\theta}{2} \right) \ |0 \rangle + \sin \left( \frac{\theta}{2} \right) \ e^{i\phi} |1 \rangle \right] \]
Density matrix \(\rho\): \[ \rho \equiv |\psi \rangle \langle \psi | = \frac{1}{2}\begin{pmatrix} 1+\cos \theta & e^{-i\phi}\sin \theta \\ e^{i\phi}\sin \theta & 1-\cos \theta \end{pmatrix} \]
\[ =\frac{1}{2}\begin{pmatrix} 1+\cos \theta & \cos \phi \sin \theta-i\sin \phi \sin \theta \\ \cos \phi \sin \theta+i\sin \phi \sin \theta & 1-\cos \theta \end{pmatrix} \]
\[ =\frac{1}{2}\left[ \begin{pmatrix}1&0\\0&1\end{pmatrix} +\cos \phi \sin \theta\begin{pmatrix}0&1\\1&0\end{pmatrix} +\sin \phi \sin \theta\begin{pmatrix}0&-i\\i&0\end{pmatrix} +\cos \theta\begin{pmatrix}1&0\\0&-1\end{pmatrix} \right] \]
\[ \equiv\frac{1}{2}\left[ I+r_x\sigma_x+r_y\sigma_y+r_z\sigma_z \right] \]
\[ r_i=\operatorname{Tr}(\rho\sigma_i) \]
For example, \[ \begin{aligned} r_x=\operatorname{Tr}(\rho\sigma_x) &=\frac{1}{2}\operatorname{Tr}\left[\left(cI+ r_x\sigma_x+r_y\sigma_y+r_z\sigma_z\right)\sigma_x\right] \end{aligned} \]
\[ \begin{aligned} &=\frac{1}{2}\operatorname{Tr}\left(c \sigma_x+ r_x\sigma_x\sigma_x+r_y\sigma_y\sigma_x+r_z\sigma_z\sigma_x\right) \end{aligned} \]
\[ \begin{aligned} &=\frac{1}{2}\operatorname{Tr}\left(c \sigma_x+ r_x I-ir_y\sigma_z+ir_z\sigma_y\right) \end{aligned} \]
\[|\psi\rangle = e^{i\phi_0}\left[ \cos \left( \frac{\theta}{2} \right) \ |0 \rangle + \sin \left( \frac{\theta}{2} \right) \ e^{i\phi} |1 \rangle \right] \]
Density matrix \(\rho\):
\[\begin{align*}
\rho \equiv |\psi \rangle \langle \psi |
&=\frac{1}{2}\left[
I
+\cos \phi \sin \theta \ \sigma_x
+\sin \phi \sin \theta \ \sigma_y
+\cos \theta \ \sigma_z
\right]\\
&=
\frac{1}{2}\left[
I
+ r_x \sigma_x
+ r_y \sigma_y
+ r_z \sigma_z
\right]\end{align*}\]
\[\begin{align*}
r_i &=\operatorname{Tr}(\rho\sigma_i)
\end{align*}\]
Caution:
(1) \(|\psi\rangle\neq r_x|+\rangle+r_y|i\rangle+r_z|0\rangle\).
(2) \(|1\rangle\neq -|0\rangle,\ |-\rangle\neq-|+\rangle,\
|-i\rangle\neq -|i\rangle\).
(3) \(-|0\rangle=e^{-i\pi}|0\rangle\) differs from \(|0\rangle\) by a global phase.
\[ \begin{align*} H&= cI + h_x\sigma_x +h_y\sigma_y +h_z\sigma_z \end{align*} \]
\[ U(t)=e^{-itH}=e^{-it(cI +h_x\sigma_x +h_y\sigma_y +h_z\sigma_z)} \]
\(\hat{\mathbf n}_H=(\hat{\mathbf x}+\hat{\mathbf z})/\sqrt2\)
\[|\psi'\rangle=U|\psi\rangle\]
\[\boxed{\rho'=U\rho U^\dagger}\]
\[\rho'=\frac12\left(I+\mathbf r'\!\cdot\!\boldsymbol{\sigma}\right)\]
Since \(r_i'=\operatorname{Tr}(\rho'\sigma_i)\), cyclicity of the trace gives
\[ \boxed{ r_i'=\operatorname{Tr}(U\rho U^\dagger\sigma_i) =\operatorname{Tr}\!\left(\rho\,U^\dagger\sigma_iU\right)}. \]
\[|\psi'\rangle=U|\psi\rangle\]
\[\boxed{\rho'=U\rho U^\dagger}\]
\[\rho'=\frac12\left(I+\mathbf r'\!\cdot\!\boldsymbol{\sigma}\right)\]
Since \(r_i'=\operatorname{Tr}(\rho'\sigma_i)\), cyclicity of the trace gives
\[ \boxed{ r_i'=\operatorname{Tr}(U\rho U^\dagger\sigma_i) =\operatorname{Tr}\!\left(\rho\,U^\dagger\sigma_iU\right)}. \]
For example, \(U_x=R_x(\alpha)= e^{\left(-i\frac{\alpha}{2}\sigma_x\right)}\)
\[|\psi'\rangle=U_x|\psi\rangle\]
\[\boxed{\rho'=U_x\rho U^\dagger_x}\]
\[\rho'=\frac12\left(I+\mathbf r'\!\cdot\!\boldsymbol{\sigma}\right)\]
\[ e^{-i\frac\alpha2\sigma_x} =\cos\!\left(\frac\alpha2\sigma_x\right) -i\sin\!\left(\frac\alpha2\sigma_x\right) \]
\[ \begin{aligned} \cos\!\left(\frac\alpha2\sigma_x\right) &=I -\frac{1}{2!} \left(\frac\alpha2\sigma_x\right)^{2} +\frac{1}{4!} \left(\frac\alpha2\sigma_x\right)^{4}-... =I -\frac{1}{2!} \left(\frac\alpha2\right)^{2}\left(\sigma_x\right)^{2} +\frac{1}{4!} \left(\frac\alpha2\right)^{4}\left(\sigma_x\right)^{4}-... ,\\[2pt] \sin\!\left(\frac\alpha2\sigma_x\right) &=\left(\frac\alpha2\sigma_x\right) -\frac{1}{3!} \left(\frac\alpha2\sigma_x\right)^{3}+... =\left(\frac\alpha2\right)\sigma_x -\frac{1}{3!} \left(\frac\alpha2\right)^{3}\left(\sigma_x\right)^{3}+... \end{aligned} \]
\[ \sigma_x^{2}=I \quad\Longrightarrow\quad \sigma_x^{2m}=I, \qquad \sigma_x^{2m+1}=\sigma_x. \]
\[ \begin{aligned} \cos\!\left(\frac\alpha2\sigma_x\right) &=I -\frac{1}{2!} \left(\frac\alpha2\right)^{2}I +\frac{1}{4!} \left(\frac\alpha2\right)^{4}I-... =\cos\frac\alpha2\,I,\\[2pt] \sin\!\left(\frac\alpha2\sigma_x\right) &=\left(\frac\alpha2\right)\sigma_x -\frac{1}{3!} \left(\frac\alpha2\right)^{3}\sigma_x+... =\sin\frac\alpha2\,\sigma_x. \end{aligned} \]
\[ \boxed{\;e^{-i\frac\alpha2\sigma_x} =\cos\frac\alpha2\,I-i\sin\frac\alpha2\,\sigma_x\;} \]
\[ \rho=\frac12\left(I+r_x\sigma_x+r_y\sigma_y+r_z\sigma_z\right), \qquad U_x(\alpha)=\cos\tfrac\alpha2\,I-i\sin\tfrac\alpha2\,\sigma_x, \qquad r_x=\operatorname{Tr}(\rho'\sigma_x) \to r_x'=\operatorname{Tr}(\rho U^\dagger \sigma_x U). \]
\[ \rho=\frac12\left(I+r_x\sigma_x+r_y\sigma_y+r_z\sigma_z\right), \qquad U_x(\alpha)=\cos\tfrac\alpha2\,I-i\sin\tfrac\alpha2\,\sigma_x, \qquad r_y=\operatorname{Tr}(\rho'\sigma_y) \to r_y'=\operatorname{Tr}(\rho U^\dagger \sigma_y U). \]
\[ \rho=\frac12\left(I+r_x\sigma_x+r_y\sigma_y+r_z\sigma_z\right), \qquad U_x(\alpha)=\cos\tfrac\alpha2\,I-i\sin\tfrac\alpha2\,\sigma_x, \qquad r_z=\operatorname{Tr}(\rho'\sigma_z) \to r_z'=\operatorname{Tr}(\rho U^\dagger \sigma_z U). \]
\[ \rho=\frac12\left(I+r_x\sigma_x+r_y\sigma_y+r_z\sigma_z\right), \qquad U_x(\alpha)=\cos\tfrac\alpha2\,I-i\sin\tfrac\alpha2\,\sigma_x, \qquad r_i=\operatorname{Tr}(\rho'\sigma_i) \to r_i'=\operatorname{Tr}(\rho U^\dagger \sigma_i U). \]
\[ \begin{aligned} r_x'&=r_x,\\ r_y'&=r_y\cos\alpha-r_z\sin\alpha,\\ r_z'&=r_y\sin\alpha+r_z\cos\alpha. \end{aligned} \]
\[ \begin{pmatrix}r_x'\\r_y'\\r_z'\end{pmatrix} = \underbrace{\begin{pmatrix} 1&0&0\\ 0&\cos\alpha&-\sin\alpha\\ 0&\sin\alpha&\cos\alpha \end{pmatrix}}_{R_x(\alpha)} \begin{pmatrix}r_x\\r_y\\r_z\end{pmatrix}. \]
\[ \alpha=\frac\pi2:\qquad |0\rangle\longmapsto\frac{|0\rangle-i|1\rangle}{\sqrt2}=|-i\rangle, \]
\[ \alpha=\pi:\qquad |0\rangle\longmapsto-i|1\rangle\sim|1\rangle. \]
Generated by QuTiP Bloch and Matplotlib
FuncAnimation.
\(\begin{bmatrix}0&1\\1&0\end{bmatrix}\)
\(|0\rangle\leftrightarrow|1\rangle\)
\(X^2=I\)
\(\begin{bmatrix}0&-i\\i&0\end{bmatrix}\)
\(|0\rangle\to i|1\rangle\)
\(Y^2=I\)
\(\begin{bmatrix}1&0\\0&-1\end{bmatrix}\)
\(|0\rangle\to |0\rangle\)
\(|1\rangle\to -|1\rangle=e^{-i\pi}|1\rangle\)
\(Z^2=I\)
\(\frac1{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\)
\(|0\rangle\to|+\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\)
\(H^2=I\)
\[|0\rangle\xrightarrow{H}\frac{|0\rangle+|1\rangle}{\sqrt2} \xrightarrow{Z}\frac{|0\rangle-|1\rangle}{\sqrt2} \xrightarrow{H}|1\rangle.\]
\[\boxed{\text{superposition}+\text{phase control} +\text{interference}+\text{measurement}.}\]
\[ |a,b,c\rangle\longmapsto|a,b,c\oplus ab\rangle \]
Reversible Boolean control
\[ H|0\rangle=|+\rangle, \qquad H|1\rangle=|-\rangle \]
Basis change and interference
\(H\) and CCNOT only ever produce real numbers. So split each amplitude into its real and imaginary parts and let one extra qubit, \(\mathrm{RI}\), record which part you are looking at:
\[ \sum_x(a_x+i b_x)|x\rangle \longmapsto \sum_x\Bigl(a_x|x\rangle|0\rangle_{\mathrm{RI}} +b_x|x\rangle|1\rangle_{\mathrm{RI}}\Bigr) \]
\(|0\rangle_{\mathrm{RI}}\) tags the real part \(a_x\), \(|1\rangle_{\mathrm{RI}}\) tags the imaginary part \(b_x\) — so a complex circuit runs entirely on real gates.
Computationally universal, not strictly universal: \(H\) and CCNOT are real matrices; the extra encoding qubit represents complex amplitudes.
Sources: Shi (2003) · Aharonov (2003).
A universal gate set can express every Boolean function.
Because NAND reproduces NOT, AND, and OR, NAND alone can generate every Boolean circuit.
Figures: CUNY OpenLab, Lab 05 · CC BY-NC-SA 3.0 · resized.
\[ T(a,b,1)=(a,b,1\oplus ab)=(a,b,\neg(ab)) \]
| \(a\) | \(b\) | \(c=1\) | \(c'=1\oplus ab=\operatorname{NAND}(a,b)\) |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |
The target is 1 except when both controls are 1, exactly the NAND truth table.
Sources: Toffoli, Reversible Computing (1980) · Morita, Theorem 2.1 (2008).
A function \(f\) is computable if one finite algorithm returns the correct \(f(x)\) and halts for every valid input \(x\).
Quantum computers do not cross this boundary: classical and quantum models compute the same computable functions.
For an algorithm that halts, complexity asks how the required resources grow as the input size \(n\) increases.
Direct dense classical state: \(2^n\) complex amplitudes.
Quantum register: \(n\) qubits represent the state.
Classical: best known general algorithms are sub-exponential.
Quantum: Shor's algorithm runs in polynomial time.
Same computable functions; potentially different resource scaling.
An arbitrary pure state of \(n\) two-level systems is
\[|\psi\rangle=\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle,\qquad \sum_x|\alpha_x|^2=1.\]
A direct classical description contains \(2^n\) complex amplitudes. This does not prove that every quantum system is classically hard to simulate—structure, symmetry, sparsity, and approximation can help—but it identifies a serious scaling problem for generic many-body dynamics.
Feynman's proposal reverses the strategy: rather than forcing a classical machine to track every amplitude, construct a controllable quantum system whose own evolution represents the target dynamics.
Richard Feynman
Ref:
Wikipedia
There are \(2^3=8\) possible strings.
\(000,001,010,011,100,101,110,111\)
At one instant, the register contains only one of them, such as \(101\).
Memory needed: 3 bits
A general three-qubit state has \(2^3=8\) amplitudes:
\[ \begin{align*} \lvert\psi\rangle= &\sum_{k=0}^{7}c_k\lvert k\rangle\\ =&c;_0\lvert 000\rangle+c_1\lvert 001\rangle +c_2\lvert 010\rangle+c_3\lvert 011\rangle\\ &+c_4\lvert 100\rangle +c_5\lvert 101\rangle+c_6\lvert 110\rangle+c_7\lvert 111\rangle\\ \end{align*} \]
A simulator stores all 8 complex amplitudes, \(c_k=\alpha_k+i\beta_k\).
About 16 significant decimal digits. For example,
\(\alpha_k\approx0.1234567890123457\)
\(\beta_k\approx-0.3141592653589793\)
Real 8 B + imaginary 8 B = 16 B per amplitude.
3 qubits: \(8\times16\ \mathrm{B}=128\ \mathrm{B} \left(=1024 \mathrm{ bits} \right)\)
50-qubit state vector \(2^{50}\times16\ \mathrm{B}=16\ \mathrm{PiB}\approx18.0\ \mathrm{PB}\)
RSA publishes \(N=pq\), the product of two large secret primes. Multiplying is easy; recovering \(p\) and \(q\) from \(N\) is believed to be extremely costly classically — and once you have them, the private key follows.
Shor's key step: turn factoring into period finding, which a large fault-tolerant quantum computer does in polynomial time.
▲
Ref:
https://en.wikipedia.org/wiki/Peter_Shor
Keys in use today
2048 bits
\(\approx617\) decimal digits. NIST wants 3072 bits beyond 2030. The classical record is RSA-250 — only 250 digits, in 2020.
Perfect qubits Shor needs
\(\sim\)4,100 logical
About \(2n+3\) for an \(n\)-bit modulus. These are idealised, error-free qubits — nobody has one.
After error correction
\(10^{6}\)–\(10^{7}\) physical
The surface code spends thousands of physical qubits per logical one: 20 million qubits / 8 hours (Gidney & Ekerå 2021), cut to under 1 million / a few days by 2025.
Prototypes today
\(10^{2}\)–\(10^{3}\) physical
IBM Heron 156, Google Willow 105, IBM Condor 1,121 — all noisy, none fault-tolerant. Roughly four orders of magnitude short.
The Heron QPU never computes an energy. It samples electronic configurations — which orbitals are occupied. Fugaku then takes the configurations that came back, builds a small subspace out of them, and diagonalizes that classically. This is sample-based quantum diagonalization.
The \(N_2\) curve stays close to the reference right through bond breaking, where restricted CCSD falls apart. For the iron–sulfur clusters, hardware samples gave lower energies than uniformly random ones at the same subspace size — chemical signal survived a deep, noisy circuit.
Still a demonstration, not a quantum advantage. The paper claims no end-to-end speedup, and on the largest case — [4Fe–4S] at 77 qubits — leading classical methods still produced better solutions. What it shows is that a noisy QPU can be a useful sampler inside a classical workflow.

