Introduction to Quantum Computing

Quantum computing gets talked about like it’s some kind of magic trick: a machine that tries every answer at once and just knows the right one. That’s a fun story, but it’s not really what’s happening, and understanding why it’s not what’s happening is the fastest way to actually get quantum computing instead of just repeating buzzwords about it. So let’s slow down and build this up from the physics, piece by piece, and see how it turns into something you can actually run algorithms on.

Quantum Bits (Qubits) and Quantum Superposition

A classical bit is a light switch. It’s either off or on, 0 or 1, full stop, and every operation you can do to it (AND, OR, NOT, whatever) is just a different way of flipping switches around. A qubit is not a switch with more positions. It’s a two-dimensional complex vector space, and its state is a point on (or really, a point associated with) something called the Bloch sphere. We write it like this:

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

Here α and β are complex numbers called probability amplitudes, and they’re constrained by $|\alpha|^2 + |\beta|^2 = 1$. That constraint isn’t decoration, it’s the whole ballgame: it’s what turns amplitudes into something you can interpret as probabilities. If you measure the qubit in the standard basis, you get 0 with probability $|\alpha|^2$ and 1 with probability $|\beta|^2$, and after that measurement the qubit collapses into whichever state you found it in. Before you measure, though, the qubit genuinely is in a combination of both, not “secretly 0 or 1 and we just don’t know which yet.” That distinction between ignorance (a coin under a cup that already landed) and superposition (a coin that hasn’t landed) is the single most important conceptual leap in this whole subject, and it’s the thing classical intuition fights hardest against.

Here’s the part people usually skip: superposition alone doesn’t buy you computational power. A classical probabilistic bit, one that’s “70% likely to be 0,” also lives in a continuum of states in some sense. What makes qubits different is that α and β are complex numbers, not just probabilities, which means they carry a phase as well as a magnitude. That phase is what lets quantum states interfere with each other, amplitudes from different computational paths can reinforce (constructive interference) or cancel out (destructive interference) before you ever measure anything. Every quantum algorithm that beats its classical counterpart is, underneath the hood, an exercise in engineering interference so that wrong answers cancel out and the right answer survives. Keep that idea in your back pocket, because it’s the thread that ties superposition, gates, and algorithms together into one coherent story instead of three disconnected topics.

Scale this up to $n$ qubits and the state lives in a $2^{n$-dimensional space, with one complex amplitude for every possible bit string of length $n$. That exponential blow-up is exactly why classical computers struggle to simulate quantum systems (you need $2}n$ numbers just to describe the state), and it’s also exactly why you can’t just read off “the answer” by peeking at all $2^n$ amplitudes: a single measurement only gives you one $n$-bit string, chosen randomly according to those amplitudes, and then the superposition is gone. Designing a quantum algorithm is largely about arranging the interference so that the measurement you’re allowed to make (just one shot at reading out $n$ bits) is overwhelmingly likely to land on something useful.

Quantum Entanglement

If superposition is one qubit being weird, entanglement is what happens when multiple qubits get weird together. Two qubits are entangled when the combined system’s state can’t be written as a simple product of each qubit’s individual state, meaning there’s no way to describe “what qubit A is doing” without also talking about qubit B. This isn’t just correlation in the classical sense (like two coins that were secretly set to match before you separated them). It’s a stronger kind of connection that shows up as violations of Bell inequalities, correlations that are provably too strong to be explained by any theory where each particle carries its own independent, predetermined set of properties.

The classic example, and the one you’ll see in every textbook and every real quantum circuit you write, is the Bell state:

$$ \lvert \psi \rangle = \frac{\lvert 00 \rangle + \lvert 11 \rangle}{\sqrt{2}} $$

Read this carefully: it says the two qubits are in a superposition of “both 0” and “both 1,” with zero amplitude on “01” or “10.” Measure the first qubit and you’ll get 0 or 1 with 50/50 odds, totally random. But the instant you do, the second qubit’s outcome is now fixed: measure it and you’ll get the same result, every single time, even though nothing physically traveled between them and even if they’re light-years apart. This is not a communication channel (you can’t use it to send information faster than light, because the first measurement’s outcome is random and neither party controls it), but it is a genuinely nonclassical resource, and it’s what makes a lot of quantum protocols possible:

• Quantum teleportation, which uses a shared entangled pair plus two classical bits of communication to transmit an unknown quantum state from one location to another, without ever physically moving the particle itself.
• Superdense coding, the flip side of teleportation, where a shared entangled pair lets you send two classical bits of information by physically transmitting just one qubit.
• Quantum cryptography, where protocols like E91 use entangled pairs and the statistical signature of Bell inequality violations to detect eavesdropping: any attempt to intercept and measure the qubits disturbs the entanglement in a way that’s mathematically guaranteed to be noticeable.

Entanglement is also, not coincidentally, the resource that quantum computers burn through to get their speedups. Circuits that never generate entanglement between qubits can, in general, be simulated efficiently on a classical computer. So when you see a CNOT gate in a circuit diagram, that’s not just “some gate,” it’s usually the moment where the computation stops being something a classical machine could easily fake.

Quantum Gates and Circuits

Classical logic gates (AND, OR, NAND) are mostly irreversible: given the output of an AND gate, you can’t reconstruct the two inputs, information got thrown away. Quantum gates can’t do that. Because quantum mechanics evolves states via unitary operators, every quantum gate has to be reversible: it’s represented by a unitary matrix $U$, satisfying $U^\dagger U = I$, and that property guarantees the gate preserves the total probability (the norm of the state vector stays 1) and that you can always run it backward. This isn’t a stylistic choice by hardware designers, it’s forced on us by the underlying physics of how closed quantum systems evolve over time.

A handful of gates show up constantly, and it’s worth knowing what each one physically does rather than just memorizing the matrix:

The Hadamard gate is usually the very first thing applied in a circuit, because it takes a qubit that’s cleanly in $\lvert 0 \rangle$ or $\lvert 1 \rangle$ and spreads it into an equal superposition of both, which is how you get from a boring classical starting point into the genuinely quantum regime where interference can do work for you. Pauli-X is the quantum analogue of a classical NOT, it swaps the amplitudes of $\lvert 0 \rangle$ and $\lvert 1 \rangle$. Pauli-Z is more subtle and has no classical counterpart at all: it leaves $\lvert 0 \rangle$ untouched but flips the sign of $\lvert 1 \rangle$’s amplitude, a “phase flip” that does nothing to measurement probabilities on its own but changes how that qubit interferes with others down the line. And CNOT is the gate that actually creates entanglement: apply a Hadamard to one qubit, then CNOT it into a second qubit, and you’ve just built the Bell state from two lines up. Any single-qubit gate together with CNOT (or an equivalent two-qubit entangling gate) is enough, in principle, to approximate any quantum computation to arbitrary precision, a fact known as universality, which is the quantum equivalent of NAND being a universal classical gate.

Quantum Algorithms

Knowing the gates doesn’t tell you what to build with them. The interesting question is: given that you can create superposition and entanglement, how do you actually arrange interference so that a hard problem gets easier? Two algorithms answer that question so cleanly that they’ve become the standard demonstrations of “why quantum computing matters,” and it’s worth understanding what each one is actually exploiting.

Shor’s Algorithm

Factoring large numbers into their prime components is easy to state and (as far as anyone has proven) exponentially hard to do on a classical computer, which is precisely why RSA encryption leans on it: multiply two big primes together and the product is trivial to compute but brutally hard to factor back apart. Shor’s algorithm breaks that asymmetry. It reduces factoring to a subproblem called period finding (finding the period $r$ of the function $f(x) = a^x \bmod N$), and it solves that subproblem efficiently using the quantum Fourier transform, which is essentially a superposition-and-interference trick for extracting periodicity out of a signal. Classically, period finding on an $n$-bit number takes exponential time; on a quantum computer, it takes polynomial time. That gap is the entire reason Shor’s algorithm is treated as a genuine threat to modern public-key cryptography rather than just an academic curiosity.

def shors_algorithm(N):
    a = random.randint(2, N-1)
    if math.gcd(a, N) != 1:
        return math.gcd(a, N)
    r = find_period_quantum(a, N)
    if r % 2 == 0 and pow(a, r//2, N) != N-1:
        factor1 = math.gcd(pow(a, r//2) - 1, N)
        factor2 = math.gcd(pow(a, r//2) + 1, N)
        return factor1, factor2
    return shors_algorithm(N)

Notice what’s doing the heavy lifting here: everything outside find_period_quantum is ordinary classical number theory that you could run on a pocket calculator. The quantum computer only has to solve the one subroutine that’s classically expensive. That pattern (offload the one genuinely hard step to a quantum subroutine, do the rest classically) shows up again and again in quantum algorithm design, and it’s a big part of why near-term “quantum advantage” tends to focus on narrow subroutines rather than entire end-to-end programs.

Grover’s Algorithm

Searching an unsorted list of $N$ items for one that matches some condition takes, on average, $O(N)$ checks classically: there’s no shortcut, you just have to look. Grover’s algorithm gets this down to $O(\sqrt{N})$, which is a real speedup but a much more modest one than Shor’s exponential leap, and that difference matters. Grover works by repeatedly applying two operations, an “oracle” that flips the sign (the phase) of the amplitude on the target item, and a “diffusion” step that reflects all amplitudes about their average. Do that combination roughly $\frac{\pi}{4}\sqrt{N}$ times and the amplitude on the correct answer has been amplified, through constructive interference, to the point where measuring the register is very likely to return it. Overshoot that number of iterations and, counterintuitively, you start rotating past the answer and your odds get worse again, so the algorithm isn’t “more iterations is always better,” it’s tuned to a specific, calculable sweet spot.

def grovers_algorithm(database, target_condition):
    state = create_equal_superposition(len(database))
    iterations = int(math.pi/4 * math.sqrt(len(database)))
    for _ in range(iterations):
        state = apply_oracle(state, target_condition)
        state = apply_diffusion(state)
    result = measure(state)
    return database[result]

It’s been proven that $O(\sqrt{N})$ is optimal for this kind of unstructured search, quantum mechanics can’t do better than a quadratic speedup here, which is a useful reminder that “quantum” doesn’t mean “unlimited speedup.” Some problems get exponential gains (Shor’s), some get quadratic gains (Grover’s), and plenty of problems get no meaningful quantum speedup at all. Part of doing good work in this field is knowing which bucket your problem falls into before you go looking for a quantum solution.

Quantum Computing Platforms and Languages

All of this is abstract until you can actually write a circuit and run it, either on a simulator or on real hardware sitting in a lab somewhere. A handful of frameworks have become the standard way to do that, and while they differ in syntax, they’re all describing the same underlying thing: a sequence of unitary gates applied to a register of qubits, followed by measurement.

Qiskit (IBM)

Qiskit is IBM’s Python SDK, and it’s probably the most widely used entry point into practical quantum programming, partly because IBM backs it with real cloud-accessible quantum hardware you can submit circuits to. Here’s the Bell state circuit from earlier, built and simulated in Qiskit:

from qiskit import QuantumCircuit, Aer, execute
qc = QuantumCircuit(2, 2)
qc.h(0)
qc.cx(0, 1)
qc.measure([0, 1], [0, 1])
simulator = Aer.get_backend('qasm_simulator')
result = execute(qc, simulator, shots=1000).result()
counts = result.get_counts(qc)
print(counts)

Run this a thousand times (that’s what shots=1000 is doing) and you should see roughly half the outcomes land on “00” and half on “11,” with essentially nothing on “01” or “10”, exactly the correlation structure the Bell state math predicted earlier. If you ran this on real IBM hardware instead of the simulator, you’d also see a small sprinkle of “01” and “10” results that shouldn’t theoretically be there at all, and that’s not a bug in the code, it’s decoherence and gate noise leaking into the answer, which is a preview of the hardware challenges we’ll get to below.

Q# (Microsoft)

Q# takes a different approach: instead of a Python library bolted onto classical code, it’s a purpose-built domain-specific language where quantum operations and qubit allocation are first-class citizens of the language itself, which makes certain classes of mistakes (like forgetting to reset a qubit before releasing it) something the compiler can catch for you.

operation BellTest() : (Int, Int) {
    using (qubits = Qubit[2]) {
        H(qubits[0]);
        CNOT(qubits[0], qubits[1]);
        let result0 = M(qubits[0]);
        let result1 = M(qubits[1]);
        Reset(qubits[0]);
        Reset(qubits[1]);
        return (result0 == One ? 1 | 0, result1 == One ? 1 | 0);
    }
}

Same Bell state, same Hadamard-then-CNOT pattern, just expressed with Q#’s more structured, statically-typed idioms. The explicit Reset calls aren’t optional busywork either, allocated qubits in Q# are expected to be returned to a known state before the using block ends, which forces you to think about qubit lifecycle in a way that Python-embedded frameworks sometimes let you gloss over.

Cirq (Google)

Cirq is Google’s Python framework, and it leans hard into being explicit about hardware topology, which qubits are physically adjacent, what gates a given chip actually supports, because Google’s own superconducting processors (like the Sycamore chip mentioned below) care a lot about that kind of detail.

import cirq
q0, q1 = cirq.LineQubit.range(2)
circuit = cirq.Circuit(
    cirq.H(q0),
    cirq.CNOT(q0, q1),
    cirq.measure(q0, q1, key='result')
)
simulator = cirq.Simulator()
result = simulator.run(circuit, repetitions=1000)
print(result.histogram(key='result'))

Three frameworks, three syntaxes, but if you squint, it’s the same four lines of “physics” every time: allocate qubits, put one into superposition, entangle it with a CNOT, measure and count. Once that pattern is second nature, reading circuits in any of these tools gets a lot faster.

Practical Applications of Quantum Computing

It’s easy to get lost in Bell states and toy circuits and lose sight of why anyone’s spending billions of dollars on this. The honest answer is that quantum computers aren’t going to replace your laptop, they’re not faster at everything, or even most things. What they’re good at is a narrow but genuinely important class of problems where the underlying structure is quantum-mechanical or where interference can be engineered to do useful work.

Cryptography

This is where quantum computing cuts both ways, threat and opportunity in the same breath. On the threat side, Shor’s algorithm doesn’t just weaken RSA and elliptic-curve cryptography (ECC), it breaks them outright once a sufficiently large, fault-tolerant quantum computer exists, because the entire security assumption behind those schemes is that factoring and discrete-log problems are classically intractable. That’s not a hypothetical worry for cryptographers; it’s the reason “post-quantum cryptography” (new classical algorithms believed to resist quantum attack) is already being standardized and rolled out today, years before anyone expects the hardware to actually exist, precisely because encrypted data harvested today could be decrypted retroactively once quantum computers catch up.

On the opportunity side, Quantum Key Distribution (QKD) uses the physics of entanglement and measurement itself as the security mechanism, rather than computational hardness. Because measuring a quantum state generally disturbs it, an eavesdropper trying to intercept a QKD key exchange leaves a statistical fingerprint that the legitimate parties can detect, which is a fundamentally different (and in principle unconditional, not just computationally hard) security guarantee than anything classical cryptography can offer.

Quantum Machine Learning

Quantum machine learning takes classical ML architectures and asks: what happens if we let the internal representations live in a quantum state space instead of a classical vector space? The hope is that the exponentially large state space of $n$ qubits could represent or process data in ways that are expensive to replicate classically. A few directions have gotten the most attention:

• Quantum Support Vector Machines, which use quantum circuits to compute kernel functions (measures of similarity between data points) that would be expensive to evaluate classically.
• Quantum Neural Networks, parameterized quantum circuits trained the way classical neural nets are, by adjusting gate parameters to minimize a loss function, often using classical optimizers in a hybrid loop.
• Quantum Principal Component Analysis, which can, under certain assumptions about how data is loaded into the quantum computer, extract the dominant components of a dataset exponentially faster than the classical algorithm.

def quantum_neural_network_layer(input_data, weights):
    quantum_state = encode_data_to_quantum(input_data)
    for i, weight in enumerate(weights):
        quantum_state = apply_rotation(quantum_state, i % n_qubits, weight)
        if i % n_qubits == n_qubits - 1:
            quantum_state = apply_entanglement(quantum_state)
    output = measure_quantum_state(quantum_state)
    return output

That caveat, “under certain assumptions about how data is loaded”, is doing a lot of work and is worth taking seriously rather than glossing over. A lot of proposed quantum ML speedups quietly assume you already have an efficient way to load classical data into a quantum state (something called a QRAM), and building that loading step efficiently is itself an unsolved problem in many cases. It’s a good example of why you should read “exponential speedup” claims in this field carefully: sometimes the speedup is real and sometimes it’s been smuggled into an assumption nobody’s actually built yet.

Quantum Chemistry and Materials Science

This is arguably the application quantum computing is most naturally suited for, because the problem you’re trying to solve (simulating a quantum mechanical system) and the tool you’re using (a quantum mechanical computer) are made of the same stuff. Classically simulating a molecule means tracking the wavefunction of every electron, and that cost grows exponentially with the number of electrons, which is why exact classical simulation of anything beyond small molecules is hopeless. A quantum computer, in principle, can represent that same wavefunction natively, using $n$ qubits to represent a system whose classical description would need $2^n$ numbers. That opens the door to:

• Molecular structure determination, working out the actual electronic configuration and bonding of complex molecules instead of relying on classical approximations.
• Drug discovery, simulating how candidate molecules bind to biological targets far more accurately than the approximate methods pharmaceutical research currently relies on.
• Materials design, predicting the properties of new materials (superconductors, catalysts, battery chemistries) before anyone has to synthesize them in a lab.

Challenges and Future Directions

None of this works yet at the scale you’d need for most of the applications above, and it’s worth being honest about why, because the obstacles aren’t engineering nuisances that’ll get ironed out with a firmware update. They’re deep physical problems.

Quantum decoherence is the big one. Qubits only stay in a clean superposition as long as they’re isolated from their environment, and in practice they’re never fully isolated: stray photons, thermal vibrations, tiny fluctuations in control electronics, all of it leaks information out of the qubit and into the environment, and that leakage destroys the delicate phase relationships that superposition and interference depend on. This isn’t like classical noise corrupting a bit flip that you can just retry, decoherence actively erases the quantum information the algorithm needs to function, and it happens on timescales that range from microseconds to a few milliseconds depending on the hardware, which is why quantum circuits have to complete their work fast.

Error correction is the proposed fix, and it comes at a brutal cost. Classical error correction can just copy a bit three times and take a majority vote, but you can’t copy an unknown quantum state (that’s the no-cloning theorem, a hard limit imposed by the linearity of quantum mechanics, not an engineering shortfall). So quantum error correction instead spreads one logical qubit’s information redundantly across many physical qubits in an entangled code, detecting and fixing errors without ever directly measuring (and thus collapsing) the protected information. The overhead is steep: current estimates suggest anywhere from dozens to over a thousand physical qubits per error-corrected logical qubit, depending on the code and the physical error rate you’re starting from.

Scalability ties both of the above together into the central engineering problem of the field. You need enough physical qubits to do error correction, but adding qubits generally makes it harder to keep everything coherent and precisely controlled, more wires, more control electronics, more opportunities for one qubit’s noise to bleed into its neighbors. Building a large-scale, fault-tolerant quantum computer means solving decoherence and error correction and control complexity all at once, and no one has done it yet at the scale needed for the big applications like breaking RSA-2048 or simulating industrially relevant molecules.

Quantum Supremacy and Advantage

In 2019, Google announced that its 53-qubit Sycamore processor had achieved “quantum supremacy”, it performed a specific, deliberately contrived sampling task in about 200 seconds that Google estimated would take the world’s most powerful classical supercomputer roughly 10,000 years. It’s worth being precise about what that milestone actually showed, because it’s often misreported. The task (sampling from the output distribution of a random quantum circuit) was chosen specifically because it’s hard to simulate classically and has essentially no practical use on its own; it wasn’t factoring a number or solving a real-world optimization problem. IBM also pushed back on the 10,000-year estimate, arguing a classical supercomputer could do it in days with enough cleverness and storage. Even so, the experiment mattered: it was concrete evidence that a real, physical quantum device could do something, anything, that classical computers genuinely struggle with, which is a different and more modest claim than “useful quantum advantage,” but it was the first time that modest claim had been demonstrated outside of theory. The field has since been chasing the harder, more meaningful goal: quantum advantage on problems people actually care about, and closing that gap between “we built something classically hard to simulate” and “we built something classically hard to simulate that also helps cure a disease or design a battery” is the real work ahead.