Quantum Computing Fundamentals

1. Why Quantum Computing? (Classical Limits and Foundations)

Classical computing relies on transistors that represent definite binary states (\(0\) or \(1\)). For decades, processing capability scaled according to Moore's Law, the empirical observation that the number of transistors on a microchip doubles roughly every two years. As components shrink toward atomic and molecular scales, classical physics breaks down. At this level, quantum mechanical effects dominate and set severe physical limits on classical scaling.

As Richard Feynman observed in his 1959 address "There's Plenty of Room at the Bottom", manipulating matter at the scale of single atoms opens fundamentally different opportunities, because microscopic particles obey quantum mechanics rather than classical rules.

Classical Mechanics vs. Quantum Mechanics

Classical mechanics: Governs macroscopic particles through Newton's laws of motion and Maxwell's electromagnetism. Energy is emitted or absorbed continuously, and a system's trajectory is deterministic: exact positions and velocities predict future states with complete certainty.
Quantum mechanics: Governs microscopic systems (photons, electrons, atoms, molecules) through the Schrödinger equation:

\[i\hbar \frac{\partial \vert\psi\rangle}{\partial t} = \hat{H}\vert\psi\rangle\]

Energy exists only in discrete packets (Planck's quantum hypothesis). Because of the Heisenberg uncertainty principle and de Broglie's wave-particle duality, exact simultaneous measurement of position and momentum is impossible. States are described probabilistically by wavefunctions (\(\vert\psi\rangle\)).

2. Core Concepts: The Pillars of Quantum Mechanics

A quantum computer uses the laws of quantum mechanics to run massively parallel operations using qubits, superposition, entanglement and unitary transformations.

The Qubit (Quantum Bit)

The fundamental unit of quantum information is described by the state vector \(\vert\psi\rangle\). A classical bit can only be \(0\) or \(1\), but a qubit can exist in a combination of both states:

\[\vert\psi\rangle = \alpha_0\vert 0\rangle + \alpha_1\vert 1\rangle\]

Here \(\alpha_0\) and \(\alpha_1\) are complex probability amplitudes, normalized so that \(\vert\alpha_0\vert^2 + \vert\alpha_1\vert^2 = 1\). The value \(\vert\alpha_0\vert^2\) is the probability of measuring \(\vert 0\rangle\), and \(\vert\alpha_1\vert^2\) is the probability of measuring \(\vert 1\rangle\).

Geometrically, a single qubit is a point on the surface of a unit sphere called the Bloch sphere, described by the angles \((\theta, \varphi)\):

\[\vert\psi\rangle = e^{i\gamma}\left(\cos\frac{\theta}{2}\vert 0\rangle + e^{i\varphi}\sin\frac{\theta}{2}\vert 1\rangle\right)\]

Superposition

Because the Schrödinger equation is linear, any linear combination of valid state solutions is also a valid state. A qubit can exist in several basis states at once until it is observed.

The analogy: Schrödinger's cat in a closed box is described as an equal superposition of two states: \(\vert\psi_{\text{cat}}\rangle = \frac{1}{\sqrt{2}}\vert\psi_{\text{alive}}\rangle + \frac{1}{\sqrt{2}}\vert\psi_{\text{dead}}\rangle\).
Exponential dimensionality: A register of \(n\) qubits spans \(2^n\) computational states. A classical \(n\)-bit register holds one of those states at a time, so working over \(2^n\) inputs takes \(2^n\) operations, whereas an \(n\)-qubit register can act on all \(2^n\) amplitudes in a single step. For example, a 64-qubit processor works in a Hilbert space of \(2^{64}\) (about \(1.8 \times 10^{19}\)) dimensions.

Entanglement

Entanglement occurs when two or more particles share a state description that cannot be factored into independent parts. For two independent qubits:

\[(\alpha\vert 0\rangle + \beta\vert 1\rangle)(\alpha'\vert 0\rangle + \beta'\vert 1\rangle) = \alpha\alpha'\vert 00\rangle + \alpha\beta'\vert 01\rangle + \beta\alpha'\vert 10\rangle + \beta\beta'\vert 11\rangle\]

An entangled state, such as the Bell state \(\frac{1}{\sqrt{2}}(\vert 00\rangle + \vert 11\rangle)\), cannot be written as a product of individual states. Measuring one entangled particle gives a result correlated with its partner, regardless of distance. Albert Einstein called this "spooky action at a distance".

Decoherence and Measurement

Measurement: Quantum measurement is projective. When observed, a superposition collapses probabilistically into a single classical basis state (\(\vert 0\rangle\) or \(\vert 1\rangle\)), destroying the superposition.
Decoherence: Quantum states are fragile. Unwanted interactions with the environment (thermal noise, stray electromagnetic fields) make the system lose its quantum phase coherence and leak quantum information into the surroundings. Preventing decoherence long enough to finish a calculation is the central engineering problem of quantum computing.

Classical Bits vs. Quantum Bits

Feature	Classical bit	Quantum bit (qubit)
Allowed states	Distinct \(0\) or \(1\)	\(\vert 0\rangle\), \(\vert 1\rangle\), or any linear superposition
Measurement	Non-destructive, complete reading	Destructive projection; gives probabilistic outcomes
Copying / erasure	Freely copyable and erasable	Protected by the No-Cloning and No-Deletion theorems
Scaling	Power grows linearly with added bits	The state space doubles with each added qubit

3. Quantum Gates and Circuits

Quantum algorithms work by applying sequences of reversible, unitary transformations to quantum registers, followed by measurement.

Preparation: |Ψ(0)⟩  --->  Unitary gates: U(t)  --->  Measurement / collapse: P(Φ) = |⟨Φ|Ψ⟩|²

Because the state must stay normalized (\(\langle\psi\vert\psi\rangle = 1\)), every quantum gate \(U\) must be a unitary matrix:

\[U U^\dagger = U^\dagger U = I\]

This makes every quantum gate reversible: any computation can be undone, or "uncomputed".

Fundamental Quantum Gates

Pauli-X gate: Flips the state (\(\vert 0\rangle \to \vert 1\rangle\) and \(\vert 1\rangle \to \vert 0\rangle\)). It is the quantum bit-flip (NOT) gate.

\[X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\]

Pauli-Y gate: A bit-flip combined with a complex phase shift.

\[Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}\]

Pauli-Z gate: Flips the sign of the \(\vert 1\rangle\) amplitude and leaves \(\vert 0\rangle\) unchanged.

\[Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\]

Hadamard gate (\(H\)): Maps basis states into equal superpositions.

\[H = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\]

It turns definite inputs into superpositions: \(\vert 0\rangle \to \frac{\vert 0\rangle+\vert 1\rangle}{\sqrt{2}}\) and \(\vert 1\rangle \to \frac{\vert 0\rangle-\vert 1\rangle}{\sqrt{2}}\). Applying it twice gives the identity (\(H^2 = I\)), so a randomized state returns to a definite one.

Phase gates (\(S\) and \(T\)): Rotate the phase about the \(Z\)-axis. The \(S\) gate satisfies \(S^2 = Z\), and the \(T\) (\(\pi/8\)) gate is a finer rotation.

\[S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix}, \qquad T = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{bmatrix}\]

Controlled-NOT (CNOT) gate: A two-qubit entangling gate. If the control qubit is \(1\), it flips the target qubit (an XOR operation). If the control qubit is \(0\), the target is unchanged.

\[\text{CNOT} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\]

Other multi-qubit gates: Controlled-Z (\(CZ\)), SWAP, and the three-qubit Toffoli gate (CCNOT).

Generating Entanglement (The Bell State Circuit)

Entanglement is produced deterministically by a Hadamard gate followed by a CNOT gate:

Start with two qubits in the ground state: \(\vert\psi_0\rangle = \vert 00\rangle\).
Apply \(H\) to the first qubit to create a superposition: \(\vert\psi_1\rangle = \frac{1}{\sqrt{2}}(\vert 0\rangle + \vert 1\rangle)\vert 0\rangle = \frac{1}{\sqrt{2}}(\vert 00\rangle + \vert 10\rangle)\).
Apply a CNOT with qubit 1 as the control and qubit 2 as the target. This entangles them into an EPR (Bell) pair:

\[\vert\psi_2\rangle = \frac{\vert 00\rangle + \vert 11\rangle}{\sqrt{2}}\]

4. Hardware Implementations and System Architecture

A working quantum computer must satisfy five basic requirements: a scalable physical qubit medium, precise control over unitary evolution, fast initial state preparation, high-fidelity measurement, and coherence times that are long compared with gate times.

           [ Classical host computer (300 K) ]
                          │  (submits job queue)
                          ▼
    [ Memory: cryo-CMOS interconnects (77 K) ]
                          │
                          ▼
 [ Control processor: Josephson junction logic (4 K) ]
                          │  (microwave pulse control)
                          ▼
      [ Dilution fridge stages (0.1 K / 100 mK) ]
                          │
                          ▼
 [ Quantum substrate: superconducting qubits (20 mK) ]

Leading Physical Implementations

Superconducting loops / transmons (IBM, Google, Rigetti): Lithographic Josephson junctions form non-linear electrical oscillators operated at millikelvin temperatures.
- Pros: Fast gate speeds, and they can be made with scalable integrated-circuit (VLSI) techniques.
- Cons: Short coherence times (about \(10^{-6}\text{ s}\)), a need for dilution refrigeration at \(0.015\text{–}0.05\text{ K}\), and fabrication variations that make each qubit slightly different.
Trapped-ion systems (IonQ, Honeywell): Ionized atoms are held in high vacuum by electromagnetic fields and driven with laser pulses.
- Pros: Identical atomic qubits, all-to-all connectivity, and long coherence times (\(> 1\text{ s}\)).
- Cons: Slower gates, complex optical setups, and laser-routing bottlenecks.
Silicon quantum dots / spin qubits (Intel, HRL): Single-electron spins are confined in modified semiconductor (CMOS-like) transistor structures.
Photonic processors (for example the USTC 76-qubit system): States are encoded in photon polarization or waveguide paths, at room temperature.
Topological qubits (Microsoft): A theoretical design that braids non-Abelian anyons to give hardware-level protection against local noise.
Other approaches: Liquid and solid-state NMR, nitrogen-vacancy (NV) centers in diamond, and neutral atoms held in optical lattices.

5. Metrics, Scaling Laws and the NISQ Era

Today's quantum processors are in the NISQ era (Noisy Intermediate-Scale Quantum), a term coined by John Preskill in 2018.

What Defines the NISQ Era?

Intermediate scale: Processors have roughly 50 to a few hundred physical qubits. That is enough to beat classical supercomputers on some specially designed benchmarks, but too small for full fault tolerance.
Noisy: Physical error rates are above the error-correction thresholds, so computations run directly on physical qubits with short circuits and error-mitigation techniques instead of full error correction.
Timeline to maturity:
1. NISQ era (3–5 years): Error mitigation, early materials and chemistry simulations.
2. Broad advantage (10+ years): Error-corrected logical operations, near-real-time financial risk modeling.
3. Fault-tolerant era (20+ years): Scalable modular machines that can run deep algorithms such as Shor's, for new drug and materials discovery.

Performance Metrics: Qubit Count vs. Quantum Volume

Qubit count alone can mislead when error rates are high. To capture both scale and quality, IBM introduced Quantum Volume (\(V_Q\)), which accounts for gate fidelity, connectivity, cross-talk and circuit depth \(d\):

\[\log_2 V_Q = \arg\max_{n \le N}\{\min[n, d(n)]\}\]

A small register of high-fidelity, well-connected qubits can have a higher Quantum Volume than a larger register with high error rates. For example, Honeywell's 10-qubit H1 reached \(V_Q = 128\).

Scaling Expectations: Neven's Law

Classical scaling follows Moore's Law. Google's Quantum AI Lab observed that quantum computing power can grow at a doubly exponential rate (\(2^{2^t}\)), a trend called Neven's Law. If this holds, advances in error mitigation and hardware density shorten the timeline and pose near-term risks to standard public-key cryptography.

6. Real-World Applications and Algorithms

Quantum computers gain speed through three main mechanisms: quantum parallelism (processing superpositions of states), Hilbert space dimensionality (\(2^n\) state spaces), and interference and entanglement (cancelling wrong outcomes while amplifying correct ones).

1. Shor's Factoring Algorithm (1994)

Impact: Solves prime factorization exponentially faster than the best known classical methods.
Complexity: The classical number field sieve takes sub-exponential time, about \(O(\exp(n^{1/3}))\), which would be up to roughly 150,000 years for a 2048-bit number. Shor's algorithm needs polynomial time, \(O(n^3 \log n)\), which on an ideal machine is seconds.
Mechanism: It reduces factoring to an order-finding (period-finding) problem for \(f(s) = x^s \pmod N\) and finds the period with the Quantum Fourier Transform (QFT).

2. Grover's Database Search (1996)

Impact: Searches an unsorted database of size \(N\) with a quadratic speedup.
Complexity: A classical linear search takes \(O(N)\) evaluations. Grover's algorithm finds the target in \(O(\sqrt{N})\) steps. It speeds up unstructured search, collision finding and NP-complete constraint-satisfaction problems.

3. Variational Quantum Eigensolver (VQE)

Concept: A hybrid quantum-classical algorithm for NISQ processors that finds the ground-state energy of molecular Hamiltonians.
Workflow:
1. Classical setup: Convert the molecular orbital operators into a qubit Hamiltonian \(H = \sum_i c_i \sigma_i\).
2. Quantum step: Prepare a parameterized ansatz state \(\vert\psi(\vec{\theta})\rangle\) using single-qubit rotations and entangling gates, then measure the expectation value \(\langle\psi(\vec{\theta})\vert H\vert\psi(\vec{\theta})\rangle\).
3. Classical feedback: A classical optimizer adjusts the parameters \(\vec{\theta}\) to lower the energy until it converges.
4. Benchmarks: Used to model bond dissociation and energy curves of molecules such as \(\text{H}_2\), \(\text{LiH}\) and \(\text{BeH}_2\) to chemical accuracy.

4. Quantum Optimization

Maps hard real-world problems (the Traveling Salesperson Problem, supply-chain logistics, portfolio risk, VLSI routing) onto quadratic unconstrained binary optimization (QUBO) and Ising spin-glass problems, using quantum tunneling to escape local minima.

5. Quantum Communication and Cryptography

Quantum Key Distribution (BB84 protocol): Alice sends single photons polarized at random in one of two conjugate bases: rectilinear \(\{\vert 0\rangle, \vert 1\rangle\}\) or diagonal \(\{\vert +\rangle, \vert -\rangle\}\). Bob measures each photon in a randomly chosen basis. They then compare their bases over a classical channel and discard the mismatches, and the remaining bits form a shared private key. An eavesdropper ("Eve") can only intercept by disturbing the photons, which produces detectable errors.
Quantum teleportation: Transfers an unknown quantum state \(\vert\psi\rangle\) to a distant location without moving the particle itself. It uses shared Bell-state entanglement, a joint measurement, two classical bits of communication and Pauli correction gates. The state is rebuilt at the destination, and the original state collapses.

7. The Post-Quantum World, Software and Roadmap

The Post-Quantum Cryptography Threat

Current internet security (RSA-2048, Diffie-Hellman, ECC) relies on the difficulty of prime factorization and discrete logarithms. A fault-tolerant quantum computer running Shor's algorithm with roughly 8,000 logical qubits could break RSA-2048.

Because adversaries can record encrypted traffic today and decrypt it once quantum computers mature ("harvest now, decrypt later"), governments and financial institutions are moving toward lattice-based algorithms, hash-based signatures and quantum key distribution (QKD).

Software Ecosystem and Development Tools

Quantum circuits are written in high-level frameworks and compiled down to calibrated microwave and laser control pulses:

Qiskit (IBM): An open-source Python SDK for writing, compiling and running quantum code on real superconducting chips through the IBM Quantum cloud.
Cirq (Google): A Python library for building and running NISQ-era circuits.
Other frameworks: QCL (an early C-like language), pyQuil/Forest (Rigetti), OpenFermion (quantum chemistry), ProjectQ, Strawberry Fields (photonic computing) and D-Wave Ocean.

Key Challenges Ahead

Decoherence: Keeping fragile superpositions intact against thermal and environmental noise long enough to complete deep circuits.
Quantum error correction (QEC): Getting around the no-cloning theorem by entangling many physical qubits in topological surface codes, which can take thousands of physical qubits to make one fault-tolerant logical qubit.
Hardware scaling and control: Routing dense coaxial wiring and control electronics into sub-kelvin refrigerators without adding heat.
Algorithm development: Finding new quantum algorithms with provable, practical speedups over classical computing.