Mar 12, 2026

What are Quantum Computers?

When you ask people what a Quantum Computer is, most will probably think of it as a faster computer.

But it is not that simple. Stick with me — I will try to explain what we know about them and what we don’t.

The Classical Foundation You Already Know

As a CS student you think in bits: every piece of data is ultimately a 0 or a 1. A classical processor manipulates billions of these bits per second using logic gates (AND, OR, NOT, XOR…). No matter how fast the hardware gets, each bit is always definitively 0 or 1 at any point in time.

That model works fantastically well. Modern CPUs run at ~5 GHz, GPUs parallelize millions of threads, and distributed systems coordinate across continents. Yet there are whole classes of problems — certain optimizations, simulations of chemistry and physics, and some cryptographic tasks — where classical machines hit a wall that more transistors alone cannot break through.

Quantum computers are built on a fundamentally different model of computation that sidesteps some of those walls.

Qubits: Bits That Can Be “Both”

The basic unit of a quantum computer is a qubit (quantum bit). Like a classical bit, when you measure a qubit you get either 0 or 1. The key difference is what happens before you measure it.

A qubit can exist in a superposition of 0 and 1 simultaneously. The standard mathematical notation for this is:

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

Analogy for the classically minded: A classical bit is like a coin lying flat — heads or tails. A qubit in superposition is like a coin spinning — it has a probability of landing on either side, but until it stops (is measured) it is neither.

The spinning coin analogy only goes so far though. The amplitudes are complex numbers, which means qubits carry phase information too — and that phase is what makes quantum algorithms tick.

Multiple Qubits: Exponential State Space

Here is where it gets interesting for a CS student.

Two classical bits can be in one of 4 states: 00, 01, 10, 11. At any moment, the system is in exactly one of those states.

Two qubits can be in a superposition of all four states at once:

$|\psi\rangle = \alpha_{00}|00\rangle + \alpha_{01}|01\rangle + \alpha_{10}|10\rangle + \alpha_{11}|11\rangle$

With $n$ qubits, the system’s state space has $2^n$ dimensions. A 300-qubit register can simultaneously represent $2^{300}$ states — more than the number of atoms in the observable universe.

This is often misunderstood as “a quantum computer tries all answers at once.” That’s not quite right. The trick is that quantum algorithms manipulate the amplitudes so that wrong answers destructively interfere (their amplitudes cancel) and correct answers constructively interfere (their amplitudes reinforce), making the right answer overwhelmingly likely when you finally measure.

Entanglement: Spooky Action at a Distance

Einstein famously called it spukhafte Fernwirkung — spooky action at a distance. Entanglement is a correlation between qubits that has no classical equivalent.

Two qubits are entangled when their state cannot be written as a product of two independent qubit states. The classic example is a Bell state:

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

If you measure the first qubit and get 0, the second qubit is guaranteed to also be 0 — instantly, regardless of the physical distance between them. If you get 1, the second is also 1.

This is not sending information faster than light (you cannot control which outcome you get), but it is a resource that quantum algorithms exploit heavily. Entanglement creates correlations that allow operations on one qubit to implicitly constrain others, enabling algorithms to coordinate computation across a register of qubits in ways classical systems cannot replicate.

Quantum Gates: The Logic of Quantum Circuits

Just as classical circuits are built from logic gates, quantum circuits are built from quantum gates — unitary matrix operations that transform qubit states.

A few important ones:

Gate	Symbol	What it does
Hadamard	$H$	Puts a $
Pauli-X	$X$	The quantum NOT gate: flips $
CNOT	$CX$	Flips target qubit if control qubit is $
Phase ( $S$ , $T$ )	$S$ , $T$	Rotate the phase of $

All quantum gates are reversible (their matrices are unitary: $UU^\dagger = I$ ). This is a hard requirement — unlike classical NAND/NOR gates, you can always “undo” a quantum gate. This connects quantum computing to thermodynamics (Landauer’s principle) and also means you cannot just copy an arbitrary qubit state (the no-cloning theorem).

Famous Algorithms: Why It Matters

Quantum computers are not universally faster. They provide a speedup only for specific problem structures. Here are the canonical examples every CS student should know:

Shor’s Algorithm (1994)

Peter Shor showed that a quantum computer can factor large integers in polynomial time — $O((\log N)^3)$ — versus the best known classical algorithm which runs in sub-exponential but still much slower time.

Why does this matter? RSA encryption relies on the hardness of factoring. A sufficiently large fault-tolerant quantum computer could break RSA. This is why post-quantum cryptography (lattice-based schemes, NIST PQC standards) is an active research area right now.

Grover’s Algorithm (1996)

Lov Grover’s algorithm searches an unstructured database of $N$ items in $O(\sqrt{N})$ operations versus the classical $O(N)$ . That is a quadratic speedup.

This is more modest than Shor’s exponential speedup, but it applies to a huge range of problems (any black-box search). For AES-128, Grover’s algorithm effectively halves the key strength — which is why NIST recommends AES-256 going forward.

Variational Quantum Eigensolvers (VQE) and Quantum Chemistry

Simulating a molecule’s electron configuration is exponentially expensive on a classical computer. A quantum computer can represent and evolve quantum states naturally, making chemical simulation a prime near-term application — with implications for drug discovery and materials science.

The Catch: Noise, Decoherence, and the NISQ Era

If quantum computers are so powerful, why aren’t we using them for everything?

Decoherence. Qubits are exquisitely sensitive to their environment. Thermal vibrations, electromagnetic interference, even cosmic rays can collapse a superposition prematurely. Maintaining qubit coherence long enough to run a useful algorithm requires near-absolute-zero temperatures (~15 millikelvin for superconducting qubits — colder than outer space).

Gate error rates. Current quantum gates have error rates on the order of 0.1%–1%. Classical transistors have error rates many orders of magnitude lower. An algorithm requiring millions of gate operations accumulates errors quickly.

Quantum Error Correction (QEC). To run fault-tolerant algorithms like Shor’s at scale, you need to encode one logical qubit using many physical qubits (current estimates: ~1,000 physical qubits per logical qubit). We are in the NISQ era (Noisy Intermediate-Scale Quantum) — machines with 50–1000 noisy physical qubits, not yet fault-tolerant.

This means:

Near-term quantum advantage is limited to specific tasks where noise can be tolerated.
Full Shor-scale cryptographic attacks require millions of physical qubits — not available today.
The field is actively researching better error correction codes (surface codes, color codes) and more coherent qubit technologies (superconducting, trapped ion, photonic, topological).

Hardware: How Qubits Are Actually Built

There is no single “standard” qubit technology. Current approaches include:

Superconducting qubits (IBM, Google): Tiny circuits cooled to near absolute zero; fast gate times (~nanoseconds); leading in qubit count today.
Trapped ions (IonQ, Quantinuum): Individual ions held in electromagnetic traps; slower but very low error rates and high connectivity.
Photonic qubits (PsiQuantum): Qubits encoded in photons; operates at room temperature; hard to make interact.
Topological qubits (Microsoft): Theoretically very low error rates due to physical fault tolerance; still largely experimental.

Each has different tradeoffs in coherence time, gate fidelity, qubit count, and connectivity.

Where Does This Leave Us?

Quantum computing is real, it is progressing rapidly, and it is not magic. As a CS student, the key mental model shifts are:

State space is exponential: $n$ qubits span $2^n$ dimensions simultaneously.
Interference is the algorithm: Quantum speedup comes from engineering amplitude cancellation, not brute-force parallelism.
Measurement is destructive: You only get one classical answer per circuit run — algorithm design is about maximizing the probability of the right answer.
Error is the enemy: The gap between a quantum circuit on paper and one that runs reliably on hardware is enormous.

Quantum computers will not replace your laptop. But for the right problems — factoring, search, quantum simulation, optimization — they represent a genuinely different computational paradigm, one that exploits the physics of the universe itself.