Quantum Computing & Shor's Algorithm

Executive Summary: Quantum computing is fundamentally not about "trying all possibilities simultaneously," but rather about orchestrating constructive and destructive quantum phase interference across high-dimensional complex Hilbert spaces. While classical probabilistic algorithms manipulate probability vectors in the simplex ${\mathbb{R}}_{\ge 0}^N$ where $\sum p_i=1$, quantum computers manipulate state vectors in the complex projective space ${\mathbb{C}}^N$ where $\sum |{\alpha }_i{|}^2=1$. This essay establishes the complete mathematical architecture of quantum computing from first principles—covering Dirac linear algebra, unitary gate transformations, multi-qubit tensor product topologies, and entanglement non-separability—before culminating in the exact derivation of the Quantum Fourier Transform (QFT), Quantum Phase Estimation (QPE), and Peter Shor's polynomial-time integer factorization algorithm that shatters RSA cryptography.

---

1. The Linear Algebraic Foundations of Quantum Mechanics

Classical digital computers operate strictly on boolean logic: a bit is an element of the discrete binary set $\Sigma =\{0,1\}$. Its state space is zero-dimensional—it resides in one state or the other with probability $p\in \{0,1\}$. Even in randomized classical algorithms, a probabilistic bit is modeled as a 1-norm normalized probability distribution vector:

$\mathbf{p}=\left(\begin{array}{c}{p}_0\\ p_1\end{array}\right)\in {\mathbb{R}}^2,p_0,p_1\ge 0,\Vert \mathbf{p}{\Vert }_1=p_0+p_1=1$

Quantum computation replaces classical probability vectors with state vectors residing in a complex vector space equipped with an inner product—a Hilbert Space $\mathcal{H}$.

---

The Mathematical Structure of a Single Qubit

A single quantum bit (qubit) is a unit vector in a 2-dimensional complex Hilbert space ${\mathcal{H}}_2\cong {\mathbb{C}}^2$. In Dirac bra-ket notation:

1. A Ket $|\psi ⟩$ denotes a column vector in ${\mathcal{H}}_2$:

   $|\psi ⟩=\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)\in {\mathbb{C}}^2$

2. A Bra $⟨\psi |$ denotes the Hermitian adjoint (conjugate transpose) of $|\psi ⟩$, residing in the dual space ${\mathcal{H}}_2^{\ast }$:

   $⟨\psi |=|\psi {⟩}^{†}=\left(\begin{array}{cc}{\alpha }^{\ast }& {\beta }^{\ast }\end{array}\right)$

3. The standard computational basis (orthonormal basis vectors) $\{|0⟩,|1⟩\}$ corresponds to the standard Cartesian basis of ${\mathbb{C}}^2$:

   $|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right),|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$

Any arbitrary single-qubit pure state $|\psi ⟩$ is expressed as a linear superposition of the basis vectors:

$|\psi ⟩=\alpha |0⟩+\beta |1⟩=\alpha \left(\begin{array}{c}1\\ 0\end{array}\right)+\beta \left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)$

where the coefficients $\alpha ,\beta \in \mathbb{C}$ are probability amplitudes.

The Inner Product and Born's Rule

The inner product between two state vectors $|\varphi ⟩=\left(\begin{array}{c}\gamma \\ \delta \end{array}\right)$ and $|\psi ⟩=\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)$ is defined as:

$⟨\varphi |\psi ⟩=\left(\begin{array}{cc}{\gamma }^{\ast }& {\delta }^{\ast }\end{array}\right)\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)={\gamma }^{\ast }\alpha +{\delta }^{\ast }\beta \in \mathbb{C}$

The computational basis states are orthonormal under this inner product:

$⟨0|0⟩=1,⟨1|1⟩=1,⟨0|1⟩=0,⟨1|0⟩=0$

$⟨i|j⟩={\delta }_{ij}\forall i,j\in \{0,1\}$

By Born's Rule, measuring a closed quantum state $|\psi ⟩$ in the computational basis collapses the superposition into a definite classical state. The probability of measuring outcome $i\in \{0,1\}$ is given by the squared magnitude of the projection onto basis state $|i⟩$:

$P(\text{outcome }0)=|⟨0|\psi ⟩{|}^2=|\alpha {|}^2$

$P(\text{outcome }1)=|⟨1|\psi ⟩{|}^2=|\beta {|}^2$

Because the total probability of all mutually exclusive measurement outcomes must equal $1$, every physical state vector must satisfy the $L_2$-norm normalization condition:

$⟨\psi |\psi ⟩=\Vert \psi {\Vert }_2^2=|\alpha {|}^2+|\beta {|}^2=1$

---

The Geometric Representation: The Bloch Sphere

Because $\alpha ,\beta \in \mathbb{C}$, specifying two complex numbers requires 4 real parameters: $\alpha =r_0{e}^{i{\theta }_0}$, $\beta =r_1{e}^{i{\theta }_1}$. However, two fundamental physical constraints reduce the degrees of freedom to exactly 2:

1. Normalization Constraint: $r_0^2+r_1^2=1$. We can parameterize $r_0=\cos (\theta /2)$ and $r_1=\sin (\theta /2)$ for $\theta \in [0,\pi ]$.

2. Global Phase Invariance: Multiplying a quantum state by a global phase factor $e^{i\gamma }$ has no observable physical consequence on measurement probabilities or expectation values:

   $|⟨\varphi |e^{i\gamma }\psi ⟩{|}^2=|e^{i\gamma }⟨\varphi |\psi ⟩{|}^2=|e^{i\gamma }{|}^2|⟨\varphi |\psi ⟩{|}^2=1\cdot |⟨\varphi |\psi ⟩{|}^2=|⟨\varphi |\psi ⟩{|}^2$

Factoring out the global phase $e^{i{\theta }_0}$:

$|\psi ⟩=e^{i{\theta }_0}\left(\cos \frac{\theta }{2}|0⟩+e^{i({\theta }_1-{\theta }_0)}\sin \frac{\theta }{2}|1⟩\right)\sim \cos \frac{\theta }{2}|0⟩+e^{i\varphi }\sin \frac{\theta }{2}|1⟩$

where:

• $\theta \in [0,\pi ]$ represents the polar angle (latitude).
• $\varphi \in [0,2\pi )$ represents the azimuthal angle (longitude / relative phase).

This maps every single-qubit pure state to a unique point $(x,y,z)$ on the unit 2-sphere ${\mathbb{S}}^2\subset {\mathbb{R}}^3$, termed the Bloch Sphere:

$\mathbf{r}=\left(\begin{array}{c}x\\ y\\ z\end{array}\right)=\left(\begin{array}{c}\sin \theta \cos \varphi \\ \sin \theta \sin \varphi \\ \cos \theta \end{array}\right)$

| Bloch Sphere Coordinate | Quantum State $|\psi ⟩$ | Polar Angle $\theta$ | Phase Angle $\varphi$ | Probability $P(0)={\cos }^2(\theta /2)$ | Probability $P(1)={\sin }^2(\theta /2)$ | | :--- | :--- | :--- | :--- | :--- | :--- | | North Pole $(0,0,1)$ | $|0⟩$ | $0$ | $0$ | $1.0$ ($100\%$) | $0.0$ ($0\%$) | | South Pole $(0,0,-1)$ | $|1⟩$ | $\pi$ | $0$ | $0.0$ ($0\%$) | $1.0$ ($100\%$) | | $+X$ Axis $(1,0,0)$ | $|+⟩=\frac{|0⟩+|1⟩}{\sqrt{2}}$ | $\pi /2$ | $0$ | $0.5$ ($50\%$) | $0.5$ ($50\%$) | | $-X$ Axis $(-1,0,0)$ | $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$ | $\pi /2$ | $\pi$ | $0.5$ ($50\%$) | $0.5$ ($50\%$) | | $+Y$ Axis $(0,1,0)$ | $|+i⟩=\frac{|0⟩+i|1⟩}{\sqrt{2}}$ | $\pi /2$ | $\pi /2$ | $0.5$ ($50\%$) | $0.5$ ($50\%$) | | $-Y$ Axis $(0,-1,0)$ | $|-i⟩=\frac{|0⟩-i|1⟩}{\sqrt{2}}$ | $\pi /2$ | $3\pi /2$ | $0.5$ ($50\%$) | $0.5$ ($50\%$) |

Critical Architectural Insight: Notice that states $|+⟩$ and $|-⟩$ produce identical measurement statistics in the computational $Z$-basis ($50\%$ probability of $|0⟩$, $50\%$ probability of $|1⟩$). However, they differ radically in their relative phase $\varphi$ ($e^{i0}=+1$ vs. $e^{i\pi }=-1$). Quantum algorithms exploit these phase differences to cancel incorrect answers and amplify correct answers via quantum interference.

---

Quantum Logic Gates as Unitary Operators

Any deterministic physical operation on an isolated quantum state must map normalized state vectors to normalized state vectors. If $|{\psi }^{\prime }⟩=U|\psi ⟩$, then we require:

$⟨{\psi }^{\prime }|{\psi }^{\prime }⟩=⟨U\psi |U\psi ⟩=⟨\psi |U^{†}U|\psi ⟩=⟨\psi |\psi ⟩=1$

For this equality to hold for all state vectors $|\psi ⟩$, the operator $U$ must satisfy the Unitary Condition:

$U^{†}U=U{U}^{†}=I$

where $U^{†}=(U^{\ast }{)}^T$ is the conjugate transpose (adjoint) of $U$, and $I$ is the identity matrix.

Unitary operators possess crucial mathematical properties:

1. Invertibility & Reversibility: Every quantum logic gate is strictly reversible: $U^{-1}=U^{†}$. No information is lost during quantum computation prior to measurement.
2. Eigenvalues on the Complex Unit Circle: All eigenvalues ${\lambda }_k$ of a unitary matrix satisfy $|{\lambda }_k|=1$, expressible as ${\lambda }_k=e^{i{\theta }_k}$ for ${\theta }_k\in \mathbb{R}$.
3. Orthogonal Eigenspaces: Eigenvectors corresponding to distinct eigenvalues are strictly orthogonal.

Primary Single-Qubit Unitary Gates

1. The Pauli Gates (${\sigma }_x,{\sigma }_y,{\sigma }_z$):

   • Pauli-$X$ (Quantum NOT / Bit-Flip): $X=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),X|0⟩=|1⟩,X|1⟩=|0⟩$ Geometrically corresponds to a $\pi$ ($180^{\circ }$) rotation around the $X$-axis on the Bloch sphere.
   • Pauli-$Y$ (Bit & Phase-Flip): $Y=\left(\begin{array}{cc}0& -i\\ i& 0\end{array}\right),Y|0⟩=i|1⟩,Y|1⟩=-i|0⟩$
   • Pauli-$Z$ (Phase-Flip): $Z=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right),Z|0⟩=|0⟩,Z|1⟩=-|1⟩$ Leaves $|0⟩$ unchanged and flips the sign of $|1⟩$ by applying a relative phase shift of $\pi$.

2. The Hadamard Gate ($H$): The most fundamental gate in quantum computing. It transforms computational basis states into equal superpositions and vice versa:

   $H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

   $H|0⟩=\frac{|0⟩+|1⟩}{\sqrt{2}}=|+⟩,H|1⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}=|-⟩$

   $H|+⟩=|0⟩,H|-⟩=|1⟩$

   Notice that $H=H^{†}=H^{-1}$, meaning applying Hadamard twice returns the qubit to its initial state ($H^2=I$).

3. Phase-Shift Gates ($S,T,R_z(\theta )$):

   • $S$ Gate (Phase Gate / $\sqrt{Z}$): $S=\left(\begin{array}{cc}1& 0\\ 0& i\end{array}\right)=\left(\begin{array}{cc}1& 0\\ 0& e^{i\pi /2}\end{array}\right),S^2=Z$
   • $T$ Gate ($\pi /8$ Gate / $\sqrt{S}$): $T=\left(\begin{array}{cc}1& 0\\ 0& e^{i\pi /4}\end{array}\right),T^2=S,T^4=Z$
   • Arbitrary $Z$-Rotation $R_z(\theta )$: $R_z(\theta )=\exp \left(-i\frac{\theta }{2}Z\right)=\left(\begin{array}{cc}{e}^{-i\theta /2}& 0\\ 0& e^{i\theta /2}\end{array}\right)\sim \left(\begin{array}{cc}1& 0\\ 0& e^{i\theta }\end{array}\right)$

---

Multi-Qubit Systems & Tensor Products ($⨂$)

When multiple quantum systems are combined, their composite state space is NOT the direct sum (${\mathcal{H}}_1\oplus {\mathcal{H}}_2$), but the Kronecker Tensor Product (${\mathcal{H}}_1\otimes {\mathcal{H}}_2$).

For an $n$-qubit register, the state vector resides in an exponentially large $2^n$-dimensional Hilbert space:

${\mathcal{H}}^{\otimes n}=\underset{n\text{ times}}{\underbrace{{\mathbb{C}}^2\otimes {\mathbb{C}}^2\otimes \cdots \otimes {\mathbb{C}}^2}}\cong {\mathbb{C}}^{2^n}$

Tensor Product Algebra

Given two qubits $|{\psi }_1⟩=\left(\begin{array}{c}{\alpha }_1\\ {\beta }_1\end{array}\right)$ and $|{\psi }_2⟩=\left(\begin{array}{c}{\alpha }_2\\ {\beta }_2\end{array}\right)$, their joint composite state $|{\psi }_{12}⟩=|{\psi }_1⟩\otimes |{\psi }_2⟩\equiv |{\psi }_1{\psi }_2⟩$ is computed via the Kronecker product:

$|{\psi }_{12}⟩=\left(\begin{array}{c}{\alpha }_1\\ {\beta }_1\end{array}\right)\otimes \left(\begin{array}{c}{\alpha }_2\\ {\beta }_2\end{array}\right)=\left(\begin{array}{c}{\alpha }_1\left(\begin{array}{c}{\alpha }_2\\ {\beta }_2\end{array}\right)\\ {\beta }_1\left(\begin{array}{c}{\alpha }_2\\ {\beta }_2\end{array}\right)\end{array}\right)=\left(\begin{array}{c}{\alpha }_1{\alpha }_2\\ {\alpha }_1{\beta }_2\\ {\beta }_1{\alpha }_2\\ {\beta }_1{\beta }_2\end{array}\right)\in {\mathbb{C}}^4$

The 2-qubit computational basis consists of 4 orthonormal basis vectors:

$|00⟩=|0⟩\otimes |0⟩=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right),|01⟩=|0⟩\otimes |1⟩=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right)$

$|10⟩=|1⟩\otimes |0⟩=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right),|11⟩=|1⟩\otimes |1⟩=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)$

For an $n$-qubit system, a general pure state $|\Psi ⟩$ is a superposition over all $2^n$ basis states:

$|\Psi ⟩={\sum }_{x=0}^{2^n-1}{c}_x|x⟩=c_0|0\dots 00⟩+c_1|0\dots 01⟩+\cdots +c_{2^n-1}|1\dots 11⟩$

where $c_x\in \mathbb{C}$ and ${\sum }_{x=0}^{2^n-1}|c_x{|}^2=1$.

---

Quantum Entanglement & The Bell States

A multi-qubit state $|\Psi ⟩\in {\mathcal{H}}_A\otimes {\mathcal{H}}_B$ is defined as separable (product state) if and only if it can be factored into individual single-qubit states:

$|\Psi ⟩=|{\psi }_A⟩\otimes |{\psi }_B⟩$

If a state cannot be factored into independent subsystems, the qubits are entangled.

The Controlled-NOT (CNOT) Gate

Entanglement is generated via multi-qubit entangling gates. The fundamental two-qubit gate is the Controlled-NOT (CNOT / $CX$) gate:

• Control Qubit ($q_0$): Dictates whether the operation is triggered.
• Target Qubit ($q_1$): Inverts ($X$) if and only if $q_0=|1⟩$.

In the computational basis $\{|00⟩,|01⟩,|10⟩,|11⟩\}$, the CNOT unitary matrix is:

$\text{CNOT}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)$

Mapping: $\text{CNOT}|00⟩=|00⟩,\text{CNOT}|01⟩=|01⟩,\text{CNOT}|10⟩=|11⟩,\text{CNOT}|11⟩=|10⟩$

Algebraically, for basis states $|x,y⟩$ with $x,y\in \{0,1\}$:

$\text{CNOT}|x,y⟩=|x,x\oplus y⟩$

where $\oplus$ denotes bitwise XOR (addition modulo 2).

---

Derivation: Generating the Canonical Bell State $|{\Phi }^{+}⟩$

Let us trace the algebraic transformation of a 2-qubit register initialized to $|00⟩$ passing through a Hadamard gate on $q_0$ followed by a CNOT gate with $q_0$ as control and $q_1$ as target.

Step 1: Initial State Preparation

$|{\psi }_0⟩=|0⟩\otimes |0⟩=|00⟩=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)$

Step 2: Apply Hadamard on Qubit 0 ($H\otimes I$)

$|{\psi }_1⟩=(H\otimes I)|{\psi }_0⟩=(H|0⟩)\otimes (I|0⟩)=\left(\frac{|0⟩+|1⟩}{\sqrt{2}}\right)\otimes |0⟩=\frac{|00⟩+|10⟩}{\sqrt{2}}=\frac{1}{\sqrt{2}}\left(\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right)$

At this intermediate stage, the two qubits are completely separable (uncorrelated).

Step 3: Apply CNOT Gate

$|{\psi }_2⟩=\text{CNOT}|{\psi }_1⟩=\text{CNOT}\left(\frac{|00⟩+|10⟩}{\sqrt{2}}\right)=\frac{1}{\sqrt{2}}\left(\text{CNOT}|00⟩+\text{CNOT}|10⟩\right)$

Substituting the CNOT transformations $\text{CNOT}|00⟩=|00⟩$ and $\text{CNOT}|10⟩=|11⟩$:

$|{\Phi }^{+}⟩=\frac{|00⟩+|11⟩}{\sqrt{2}}=\frac{1}{\sqrt{2}}\left(\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right)$

---

Formal Proof of Non-Separability (Entanglement)

To rigorously prove that $|{\Phi }^{+}⟩$ is an entangled state, we demonstrate by contradiction that no single-qubit states $|{\psi }_A⟩={\alpha }_1|0⟩+{\beta }_1|1⟩$ and $|{\psi }_B⟩={\alpha }_2|0⟩+{\beta }_2|1⟩$ can satisfy $|{\psi }_A⟩\otimes |{\psi }_B⟩=|{\Phi }^{+}⟩$.

Proof:

Assume $|{\Phi }^{+}⟩$ is separable:

$|{\psi }_A⟩\otimes |{\psi }_B⟩=({\alpha }_1|0⟩+{\beta }_1|1⟩)\otimes ({\alpha }_2|0⟩+{\beta }_2|1⟩)={\alpha }_1{\alpha }_2|00⟩+{\alpha }_1{\beta }_2|01⟩+{\beta }_1{\alpha }_2|10⟩+{\beta }_1{\beta }_2|11⟩$

Equating coefficients with $|{\Phi }^{+}⟩=\frac{1}{\sqrt{2}}|00⟩+0|01⟩+0|10⟩+\frac{1}{\sqrt{2}}|11⟩$:

undefined