What Is Quantum Computing?

Quantum computing represents a paradigm shift in our computational understanding of physical reality. Rather than encoding information into binary transistors constrained by Boolean logic, a quantum computer manipulates fundamental quantum physical systems—such as superconducting circuits, trapped atomic ions, or neutral Rydberg atoms, whose behaviors are governed by the linear algebra of quantum mechanics.

As the physicist Richard Feynman famously observed in 1981:

“Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical, and by golly it’s a wonderful problem, because it doesn’t look so easy.”

1. The Breakdown of the Church-Turing Thesis

For over half a century, the Extended Church-Turing thesis postulated that any physically realizable computing model could be simulated by a deterministic Turing machine with at most polynomial overhead.

Quantum mechanics fundamentally challenges this premise. Because quantum systems evolve within exponentially expanding Hilbert spaces, simulating an $n$-qubit quantum register classically requires tracking $2^n$ complex probability amplitudes. For a modest register of just 50 to 100 qubits:

$2^{50} \approx 1.125 \times 10^{15} \text{ complex coefficients}$ $2^{100} \approx 1.267 \times 10^{30} \text{ complex coefficients}$

No classical supercomputer constructed from all the silicon on planet Earth could store or manipulate the state vector of an ideal 300-qubit processor.

2. Core Pillars of Quantum Computation

Quantum algorithms achieve exponential or polynomial advantages through three non-classical phenomena:

2.1 Superposition and the State Vector

In classical computation, a bit takes a definite state: $b \in \{0, 1\}$. In contrast, a quantum bit (or qubit) resides in a normalized two-dimensional complex Hilbert space $\mathbb{C}^2$:

$|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$

where $\alpha, \beta \in \mathbb{C}$ represent complex probability amplitudes satisfying the normalization constraint:

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

Geometrically, any single-qubit state can be represented as a coordinate on the unit surface of a Bloch sphere defined by the polar angle $\theta$ and azimuthal phase angle $\varphi$:

$|\psi\rangle = \cos\left(\frac{\theta}{2}\right)|0\rangle + e^{i\varphi}\sin\left(\frac{\theta}{2}\right)|1\rangle$

2.2 Quantum Entanglement

When two or more qubits interact, they can form joint composite states that cannot be decomposed into individual tensor products of their constituents:

$|\psi_{AB}\rangle \neq |\psi_A\rangle \otimes |\psi_B\rangle$

The canonical example is the maximally entangled Bell state:

$|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$

Measuring the first qubit immediately dictates the state of the second qubit with 100% correlation, regardless of physical separation.

2.3 Quantum Interference

Contrary to a common misconception, a quantum computer does not simply “try every possible answer simultaneously” in parallel. When a measurement occurs, the wave function collapses to a single eigenstate.

The real power of quantum algorithms (such as Shor’s factoring algorithm or Grover’s search) lies in constructive and destructive interference. The quantum circuit is designed so that computational paths leading to incorrect solutions interfere destructively (canceling out their amplitudes to 0), while paths leading to the correct solution interfere constructively (amplifying its probability amplitude toward 1).

3. A Minimal Quantum Circuit

To illustrate how quantum transformations occur, consider applying a Hadamard gate ($H$) to a ground state qubit $|0\rangle$, followed by a Pauli-$Z$ phase flip:

# Minimal Qiskit quantum circuit representation
from qiskit import QuantumCircuit

# Initialize 1-qubit circuit with 1 classical readout bit
qc = QuantumCircuit(1, 1)

# Apply Hadamard gate to create equal superposition: (|0> + |1>)/sqrt(2)
qc.h(0)

# Measure into classical register
qc.measure(0, 0)

print(qc.draw(output='text'))

The matrix transformation for the Hadamard operator is given by:

$H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

Applying $H$ onto $|0\rangle$:

$H |0\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix} = \frac{|0\rangle + |1\rangle}{\sqrt{2}} = |+\rangle$

4. Where Quantum Computing Will Matter

Quantum advantages are domain-specific. They will not accelerate everyday web browsing or word processing, but rather targeted classes of mathematically intractable problems:

1. Quantum Chemistry and Materials Simulation: Designing room-temperature superconductors, catalytic nitrogen fixation enzymes (Haber-Bosch efficiency), and next-generation solid-state battery electrolytes.
2. Cryptanalysis and Lattice Security: Shor’s algorithm renders RSA and elliptic-curve cryptography vulnerable, necessitating post-quantum cryptography (PQC) standards.
3. Combinatorial Optimization: Portfolio optimization, logistics routing, and constrained Hamiltonian energy minimization.

References & Further Reading

• Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press.
• Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. Quantum, 2, 79.
• Feynman, R. P. (1982). Simulating physics with computers. International Journal of Theoretical Physics, 21(6), 467-488.