umma.dev

Quantum computing gets talked about mostly in physics terms; superposition, entanglement, interference. What quantum computers can and can’t do is closely linked to theoretical computer science and it turns out the abstract machinery TCS developed over decades - from automata theory, complexity classes, coding theory, cryptography.

Automata Theory and Computational Models

Before you can ask what a quantum computer can do, you need a formal model of computation to reason about.

In the 1930s before electronic computers existed, Alan Turing’s 1936 paper “On Computable Numbers” introduced what we now call the Turing machine - an imaginary device with an infinite tape, a read/write head and a finite set of transition rules. In the same period, Alonzo Church developed the lambda calculus, a completely different-looking formalism that turned out to be equivalent. The Church-Turing thesis of that any reasonable model of computation is equivalent in power to a Turing machine became the foundational assumption of the entire field.

In the 1940s and 50s, researchers started asking what you could do with less than a Turing machine. McCulloch and Pitts had introduced a model of neural computation in 1943 that looked like a finite state machine. Kleene formalised this in 1951 with regular expressions. Mealy and Moore gave us the two canonical formulations of finite automata (machines with states but no tape) in 1955-56. Rabin and Scott’s 1959 paper proved that nondeterministic finite automata (where multiple transitions are allowed) are equivalent in expressive power to deterministic ones - a genuinely surprising result, and a template for the kind of equivalence proofs that would recur throughout TCS.

Chomsky’s hierarchy (1956-59) organised formal languages into a clean taxonomy: regular languages (recognisable by finite automata), context-free languages (pushdown automata), context-sensitive languages, and recursively enumerable languages (full Turing machines). This wasn’t just linguistics - it became the conceptual skeleton of compilers, parsing theory, and later complexity theory.

Formally, a deterministic finite automaton (DFA) is a 5-tuple:

$M = (Q,\; \Sigma,\; \delta,\; q_0,\; F)$

$Q$ is a finite set of states, $\Sigma$ is the input alphabet, $\delta: Q \times \Sigma \to Q$ is the transition function, $q_0$ is the start state, and $F \subseteq Q$ is the set of accepting states. A string is accepted if running $\delta$ on each character ends in a state $q \in F$.

Here’s a minimal DFA that accepts binary strings with an even number of 1s:

def dfa_even_ones(string: str) -> bool:
    # States: 0 = even count (accepting), 1 = odd count
    state = 0
    transitions = {
        (0, '0'): 0, (0, '1'): 1,
        (1, '0'): 1, (1, '1'): 0,
    }
    for char in string:
        state = transitions[(state, char)]
    return state == 0

print(dfa_even_ones("1100"))  # True  — two 1s
print(dfa_even_ones("101"))   # False — three 1s

The state diagram for this DFA:

The model of computation determines what’s possible

Different machines recognise fundamentally different classes of languages. This matters for quantum computing for a specific reason. When physicists proposed quantum computation in the early 1980s, there was no rigorous answer to “what, precisely, can a quantum computer compute?” because there was no formal model. Automata theory provided the tools to build one. Deutsch’s quantum Turing machine borrowed directly from Turing’s 1936 paper; same tape, same structure but with a unitary transition function instead of a deterministic one. The question, “is quantum computation more powerful than classical?” immediately became a question TCS had been developing methods to answer for fifty years of, how do you compare two computational models?

Quantum computing adds a new column to this table. Deutsch’s 1985 paper introduced the quantum Turing machine (QTM), a Turing machine whose transition function is a unitary operation acting on a superposition of configurations, rather than a deterministic rule. This is polynomially equivalent to the quantum circuit model - qubits acted on by unitary gates, measured at the end. That equivalence proof is structurally identical to the DFA = NFA equivalence proof Rabin and Scott gave in 1959, two different-looking machines, shown to be equal in power via a simulation argument.

The whole toolkit automata theory built transferred directly into quantum complexity theory. The proof that a universal gate set for quantum circuits exists uses the same universality arguments as for Boolean circuits. The definitions of BQP, QMA and every other quantum complexity class are written in terms of quantum Turing machines.

Quantum finite automata (QFAs) replace the deterministic transition $\delta(q, \sigma) = q'$ with a unitary matrix $U_\sigma$ acting on the state vector. Where a classical state is a single active state, a quantum state is a vector of probability amplitudes over all states:

$U_\sigma \begin{pmatrix} \alpha_0 \\ \alpha_1 \end{pmatrix} = \begin{pmatrix} \alpha_0' \\ \alpha_1' \end{pmatrix} \quad \text{where} \quad |\alpha_0'|^2 + |\alpha_1'|^2 = 1$

The machine can be in a superposition of states simultaneously, with measurement collapsing it probabilistically.

QFAs can recognise some languages with fewer states than their classical counterparts because quantum interference can cancel out wrong-path amplitudes. This is a microcosm of the larger pattern. Just as NFA-DFA equivalence showed that the same computational power can be achieved with exponentially fewer states using nondeterminism. QFA results show quantum superposition can compress state requirements further still. The mechanism of amplitude interference cancelling the “wrong” paths is the same mechanism behind the exponential speedups in Shor’s and Grover’s algorithms, operating at the smallest possible scale.

Quantum Church-Turing thesis

A quantum Turing machine can efficiently simulate any physically realisable model of computation - a conjecture that would be falsified if someone found a physical process computing outside BQP. Whether this holds is one of the deepest open questions at the intersection of physics and TCS.

Cryptography

Modern public-key cryptography rests on a bet made in 1976. Diffie and Hellman’s landmark paper introduced asymmetric cryptography. A key pair where encryption is public but decryption requires a private key. The security depends on a computational hardness assumption - certain operations are easy in one direction and hard to reverse.

Without complexity theory’s reduction framework, you can’t express what cryptographic security means precisely, let alone prove it. The entire rigour of modern cryptography is built on TCS foundations.

RSA (1977) uses integer factoring. Pick two large primes $p$ and $q$, set $n = pq$, and compute Euler’s totient $\phi(n) = (p-1)(q-1)$. Choose public exponent $e$ coprime to $\phi(n)$, then find private key $d$ satisfying:

$ed \equiv 1 \pmod{\phi(n)}$

Encryption and decryption then become:

$c = m^e \bmod n \qquad\qquad m = c^d \bmod n$

The trap: factoring $n$ back into $p$ and $q$ has no known polynomial-time classical algorithm. Multiplying two 2048-bit primes takes microseconds; factoring the result takes longer than the age of the universe with the best known classical methods.

from math import gcd

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

def rsa_keygen(p: int, q: int, e: int):
    n = p * q
    phi = (p - 1) * (q - 1)
    assert gcd(e, phi) == 1
    _, d, _ = extended_gcd(e % phi, phi)
    return (e, n), (d % phi, n)  # public_key, private_key

pub, priv = rsa_keygen(p=61, q=53, e=17)
print(pow(pow(65, pub[0], pub[1]), priv[0], priv[1]))  # 65

Shor’s algorithm (1994) broke this bet, in principle. Factoring $N$ reduces to finding the period $r$ of the function $f(x) = a^x \bmod N$. Once you have the period, the factors fall out:

$\gcd(a^{r/2} \pm 1,\; N)$

gives a non-trivial factor of $N$ with high probability (provided $r$ is even and $a^{r/2} \not\equiv -1$). Classical period-finding is exponentially hard. The Quantum Fourier Transform finds it in polynomial time.

The significance of Shor’s algorithm is that it’s that it’s a complexity class result. It places integer factoring inside BQP. The entire threat to RSA flows from that single fact; factoring moved from a problem that appeared to sit outside efficient computation into a class quantum computers can solve in polynomial time.

The periodicity is visible in the chart below - what Shor’s algorithm exploits by transforming this pattern into the Fourier domain:

from math import gcd

def find_period(a: int, N: int) -> int:
    r, val = 1, a % N
    while val != 1:
        val = (val * a) % N
        r += 1
    return r

def shor_factor(N: int, a: int):
    r = find_period(a, N)        # quantum computer does this in O(n²) gates
    if r % 2 != 0: return None
    x = pow(a, r // 2, N)
    if x == N - 1: return None
    p = gcd(x + 1, N)
    return (p, N // p) if 1 < p < N else None

print(shor_factor(15, 7))  # (3, 5)

The Quantum Fourier Transform is what makes the period-finding fast. Applied over $N = 2^n$ states:

$\text{QFT}|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk / N} |k\rangle$

Classical FFT runs in $O(N \log N)$. QFT on $n$ qubits runs in $O(n^2)$ gates - an exponential improvement because $N = 2^n$.

This not only weakens RSA, it breaks it completely. The response has been post-quantum cryptography of NIST standardised CRYSTALS-Kyber and CRYSTALS-Dilithium in 2024, based on the hardness of lattice problems (the shortest vector problem in high-dimensional lattices), which appear to resist quantum attack.

Symmetric cryptography is in better shape. Grover’s algorithm gives a quadratic speedup on unstructured search, halving the effective key security - AES-256 provides AES-128-equivalent protection against a quantum adversary. Doubling key lengths is sufficient.

Quantum key distribution (QKD) goes further still. BB84 (Bennett and Brassard, 1984) achieves information-theoretic security - not resting on any computational hardness assumption but on the no-cloning theorem. An eavesdropper measuring Alice’s qubits must choose a basis; choosing wrong introduces detectable errors. The catch: QKD requires a physical quantum channel and doesn’t scale the way mathematical cryptography does.

Cryptography is about the asymmetry between a problem and its inverse. Quantum complexity theory changes which asymmetries hold. The consequence is one of the largest infrastructure transitions in computing history.

Complexity Theory

BQP (Bounded-error Quantum Polynomial time) is the quantum analogue of P. The key relationships:

$\mathbf{P} \subseteq \mathbf{BQP} \subseteq \mathbf{PSPACE}$

Integer factoring sits inside BQP (Shor’s algorithm) but is not known to be NP-hard - which is why breaking RSA wouldn’t resolve P vs NP. The relationship between BQP and NP is unknown; it’s believed neither contains the other.

QMA (Quantum Merlin Arthur) is the quantum analogue of NP. Problems where a quantum witness can convince a quantum verifier. The local Hamiltonian problem - finding the ground state energy of a quantum system - is QMA-complete, which is why quantum chemistry is a natural target for quantum hardware.

Coding Theory

Classical codes add redundancy so errors can be corrected. Quantum error correction has to do the same for qubits, with two constraints that don’t exist classically, the no-cloning theorem (you can’t copy an unknown quantum state) and the measurement problem (checking for errors disturbs the state).

The stabiliser formalism (Gottesman, 1990s) resolves this. A quantum code is defined by a group of commuting Pauli operators whose elements fix every valid codeword:

$S|\psi\rangle = |\psi\rangle \quad \text{for all } S \in \mathcal{S}$

Errors are detected by measuring stabiliser generators - an error anticommutes with some generator, giving a non-trivial syndrome without collapsing the encoded information.

CSS codes (Calderbank-Shor-Steane) showed that two classical codes $C_1, C_2$ with $C_2^\perp \subseteq C_1$ can be lifted to a quantum code, with separate check matrices $H_X$ and $H_Z$ satisfying:

$H_X H_Z^T = 0$

This orthogonality condition is the bridge from classical coding theory into quantum codes. The current frontier is quantum LDPC codes - sparse check matrices, tractable decoding, lower qubit overhead. Finding good ones is exactly what the bivariate bicycle code paper is about.

Algorithm Design

Quantum algorithm design adds two genuinely new primitives to the classical toolkit of divide-and-conquer, dynamic programming, and greedy methods.

Grover’s algorithm (1996) searches an unstructured set of $N$ items for a target. The comparison:

$O(N^{1/2}) \text{ quantum queries} \quad \text{vs} \quad O(N) \text{ classically}$

The mechanism is amplitude amplification. Each iteration flips the phase of the target state via an oracle, then a diffusion step reflects all amplitudes around their mean. After $O(N^{1/2})$ iterations the target’s amplitude has grown close to 1. The database is unstructured by assumption. The advantage is purely quantum, coming from interference between paths.

The Quantum Fourier Transform is the engine behind most exponential quantum speedups, including Shor’s algorithm. The circuit for $n$ qubits uses $O(n^2)$ gates. Compare that to the classical FFT:

$\text{Classical FFT: } O(N \log N) \quad \text{vs} \quad \text{QFT: } O(n^2) \text{ gates}$

Where $N = 2^n$ an exponential improvement in terms of input size $n$. You don’t need to recall all $N$ amplitudes at once (measurement collapses the state), so the QFT is only useful when the structure you need is in the Fourier domain. Factoring, as Shor showed, is exactly that kind of problem.

The TCS framework for measuring these speedups is query complexity, how many oracle queries does an algorithm need? This strips away implementation details and asks a fundamental question - how many times do you need to touch the input to solve a problem? Query complexity has clean, provable separations. The Deutsch-Jozsa problem requires $O(2^n)$ classical queries worst-case but exactly 1 quantum query, a proven exponential gap not a conjecture.