Turing Machines, Computability, and What Quantum Computing Actually Changes
A quantum computer computes exactly the same set of functions as a Turing machine, no more and no fewer. It cannot solve the halting problem. What it changes is efficiency, not computability, and this tutorial draws the line precisely.
Popular writing about quantum computing loves the phrase “breaks the limits of computation.” It is wrong, and it is wrong in a way that matters. A quantum computer does not compute anything a 1936 Turing machine cannot compute. Not one extra function. It cannot solve the halting problem, it cannot decide an undecidable language, and it does not put a dent in Gödel.
What it plausibly breaks is a different and much younger claim, one about how long computation takes. That claim is worth understanding precisely, because the difference between “quantum computers can compute more” and “quantum computers can compute some things faster” is the difference between science fiction and the actual research field.
This tutorial draws that line, carefully.
What a Turing machine actually is
A Turing machine is deliberately, almost insultingly simple. It has:
- An infinite tape divided into cells, each holding a symbol from a finite alphabet (say 0 and 1).
- A head parked on one cell, which can read the symbol there and write a new one.
- A finite set of internal states, one of which is the current state.
- A transition table: given (current state, symbol under the head), it says which symbol to write, whether to move the head left or right, and which state to enter next.
That is the entire machine. No memory hierarchy, no arithmetic unit, no instruction set. Here is one, implemented in full:
from collections import defaultdict
def run_turing_machine(rules, start="A", max_steps=1000):
"""rules[(state, symbol)] = (write_symbol, move, next_state); 'H' halts."""
tape = defaultdict(int) # the infinite tape, blank (0) everywhere by default
head = 0 # the head position
state = start # the internal state (the finite control)
steps = 0
while state != "H" and steps < max_steps:
write, move, state = rules[(state, tape[head])]
tape[head] = write # 1. write a symbol
head += 1 if move == "R" else -1 # 2. move one cell left or right
steps += 1 # 3. repeat from the new state
return tape, steps, state
# The 3-state, 2-symbol "busy beaver": the halting 3-state machine that writes
# the most 1s (Sigma(3) = 6). The longest-*running* 3-state machine is a different
# one, and it halts after 21 steps. Nobody designed this to be useful; it is here
# to show that these six-line rules are the whole machine.
busy_beaver = {
("A", 0): (1, "R", "B"),
("A", 1): (1, "R", "H"),
("B", 0): (0, "R", "C"),
("B", 1): (1, "R", "B"),
("C", 0): (1, "L", "C"),
("C", 1): (1, "L", "A"),
}
tape, steps, final = run_turing_machine(busy_beaver)
print(f"halted in state {final} after {steps} steps")
print(f"ones written to the tape: {sum(tape.values())}")
print("tape:", "".join(str(tape[i]) for i in range(min(tape), max(tape) + 1)))
halted in state H after 14 steps
ones written to the tape: 6
tape: 111111
Six rules, and this shape of machine is a universal model of computation. Everything your laptop does, every program ever written in any language, can be carried out by a machine of exactly this shape given a big enough transition table and enough tape. That is not a metaphor. It is a theorem, and it has been reproved in a dozen equivalent formalisms.
Why this is the definition of “computable”
In the 1930s several people, working independently, tried to formalise what it means for a function to be “effectively calculable” by a mechanical procedure. Turing gave his machines. Alonzo Church gave the lambda calculus. Kurt Gödel and Jacques Herbrand gave general recursive functions. Emil Post gave a rewriting system.
All of them turned out to define exactly the same class of functions. Not similar classes. The same one. Every model anyone has since invented that is not obviously cheating (register machines, cellular automata, your CPU, Conway’s Game of Life) computes that identical class.
This is the Church-Turing thesis: the intuitive notion of “effectively computable by a mechanical procedure” is captured precisely by “computable by a Turing machine.”
Note that it is a thesis, not a theorem. It cannot be proved, because one side of it (“intuitively computable”) is informal. It is an empirical claim about the nature of mechanical computation, and ninety years of failed attempts to violate it are the evidence.
The payoff is that “computable” is now a sharp, model-independent word. And once you have a sharp definition, you can prove things are outside it.
The halting problem
The most famous of those things: no Turing machine can take an arbitrary program plus an input and decide whether that program eventually halts.
The proof is a two-line diagonal argument. Suppose halts(prog, input) exists and always returns correctly. Build:
def paradox(prog):
if halts(prog, prog):
loop_forever()
else:
return
Now ask: does paradox(paradox) halt? If it halts, then by its own code halts(paradox, paradox) returned True, so it loops forever. If it loops forever, then halts returned False, so it returns immediately. Both branches are contradictions, so halts cannot exist.
The halting problem is undecidable. Not “hard.” Not “takes too long.” No procedure, given unlimited time and unlimited tape, can do it. And Rice’s theorem generalises this brutally: essentially every non-trivial semantic question about what a program computes is undecidable too.
The central point: quantum does not touch any of this
Here is the claim that most popular writing gets wrong, stated as bluntly as I can manage:
A quantum computer computes exactly the same set of functions as a Turing machine. It decides no undecidable language. It cannot solve the halting problem. Quantum mechanics changes the efficiency of computation, not the boundary of what is computable at all.
And the argument is embarrassingly simple: a Turing machine can simulate any quantum circuit. A quantum circuit on n qubits is a state vector of 2ⁿ complex amplitudes, and each gate is a matrix multiplication. Matrix multiplication is something a classical computer does perfectly well. It is slow, exponentially slow in n, but slowness is not the issue here. Computability does not care how long you take, only whether you finish.
You can watch a Turing machine simulate a quantum computer right now. The following is plain numpy, ordinary classical code, running on an ordinary classical CPU, reproducing a three-qubit entangling circuit exactly:
import numpy as np
I2 = np.eye(2, dtype=complex)
H = np.array([[1, 1], [1, -1]], dtype=complex) / np.sqrt(2)
X = np.array([[0, 1], [1, 0]], dtype=complex)
P0 = np.array([[1, 0], [0, 0]], dtype=complex) # |0><0|
P1 = np.array([[0, 0], [0, 1]], dtype=complex) # |1><1|
def embed(n, placements):
"""Tensor a dict {qubit: 2x2 matrix} into the full 2^n operator.
Qiskit is little-endian: qubit 0 is the RIGHTMOST factor in the kron."""
m = np.array([[1]], dtype=complex)
for q in reversed(range(n)): # q = n-1 ... 0
m = np.kron(m, placements.get(q, I2))
return m
def cnot(n, control, target):
# Control off: do nothing. Control on: flip the target. Add the two branches.
return embed(n, {control: P0}) + embed(n, {control: P1, target: X})
# Build a 3-qubit GHZ state, plus a rotation, entirely by matrix multiplication.
n = 3
state = np.zeros(2 ** n, dtype=complex)
state[0] = 1.0 # |000>
state = embed(n, {0: H}) @ state # H on qubit 0
state = cnot(n, 0, 1) @ state # entangle qubit 1
state = cnot(n, 1, 2) @ state # entangle qubit 2
RY = lambda t: np.array([[np.cos(t / 2), -np.sin(t / 2)],
[np.sin(t / 2), np.cos(t / 2)]], dtype=complex)
state = embed(n, {2: RY(np.pi / 3)}) @ state # a non-Clifford rotation on qubit 2
print("amplitudes from plain numpy (i.e. from a Turing machine):")
for i, a in enumerate(state):
if abs(a) > 1e-9:
print(f" |{i:03b}> {a.real:+.4f}")
# Now the same circuit in Qiskit, and check they agree.
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
qc = QuantumCircuit(3)
qc.h(0)
qc.cx(0, 1)
qc.cx(1, 2)
qc.ry(np.pi / 3, 2)
qiskit_state = Statevector(qc).data
print("\nmax difference vs Qiskit:", f"{np.abs(state - qiskit_state).max():.2e}")
print("identical to numerical precision:", np.allclose(state, qiskit_state))
amplitudes from plain numpy (i.e. from a Turing machine):
|000> +0.6124
|011> -0.3536
|100> +0.3536
|111> +0.6124
max difference vs Qiskit: 0.00e+00
identical to numerical precision: True
(Bit labels are Qiskit’s little-endian convention: in |100⟩ the leftmost bit is qubit 2.)
There is no approximation here. The classical simulation is not “close.” It is bit-for-bit identical. Scale n to 300 and the same code needs more memory than there are atoms in the observable universe, so you would never finish, but nothing in principle stops the computation. A Turing machine with an unbounded tape and unbounded time does finish.
Formally: BQP ⊆ PSPACE ⊆ EXP. Every quantum computation can be simulated classically in polynomial space (Bernstein and Vazirani, 1997, by summing over computational paths rather than storing the whole vector), which certainly means it can be simulated in finite time. The quantum Turing machine that David Deutsch defined in 1985 is exactly as powerful, in computability terms, as Turing’s original.
The one honest caveat. If you permit gates whose amplitudes are uncomputable real numbers, you can smuggle uncomputable information into the machine and get nonsense results. But that is cheating and it is not quantum: you can play the identical trick classically by handing a Turing machine an oracle tape containing an uncomputable constant. No physically buildable device has infinitely precise uncomputable gate angles, and every serious model restricts to a computable gate set. Nothing in real quantum computing escapes here.
What quantum does threaten: the extended thesis
Now the interesting part. There is a second, stronger claim, and it is much less safe:
The extended (or “strong”) Church-Turing thesis: any physically realisable computational model can be simulated by a probabilistic Turing machine with at most polynomial overhead.
Read that carefully. The original thesis is about what can be computed. The extended thesis adds a claim about cost: the Turing machine is not just universal, it is universal efficiently. That makes a class like BPP a fact about physics rather than a quirk of one machine model.
This is the thesis quantum computing attacks, and only this one.
Shor’s algorithm factors an n-bit integer in roughly O(n³) quantum operations. The best known classical algorithm, the general number field sieve, is sub-exponential but super-polynomial. If factoring genuinely has no polynomial-time classical algorithm, then a working quantum computer is a physically realisable device that outruns every probabilistic Turing machine by a super-polynomial factor, and the extended thesis is false.
Note the “if.” We have no proof that factoring is classically hard. Nobody has proved factoring is outside P. So Shor’s algorithm is strong evidence against the extended Church-Turing thesis, not a refutation of it. A clever classical factoring algorithm tomorrow would leave the original Church-Turing thesis untouched and quietly rescue the extended one. This distinction is routinely glossed over and it should not be.
P, NP, BQP, and the claim nobody should make
Since complexity classes are where the real action is, get them straight.
- P: decidable by a classical computer in polynomial time.
- BPP: same, but with randomness and a bounded error probability. This is the honest model of “classically efficient.”
- NP: solutions can be verified in polynomial time. Contains the NP-complete problems (SAT, travelling salesman, graph colouring), the hardest problems in the class.
- BQP: decidable by a quantum computer in polynomial time with error probability at most 1/3. This is “quantumly efficient.”
What is actually known:
P ⊆ BPP ⊆ BQP ⊆ PSPACE. A quantum computer can do anything a classical computer can do efficiently, because quantum circuits can implement classical reversible logic. BQP contains P. That direction is settled.
BQP is not known to contain NP. Read that twice, because the internet says otherwise constantly. There is no known efficient quantum algorithm for any NP-complete problem, and essentially nobody in the field expects one. The widespread belief is that NP ⊄ BQP.
BQP is not known to be contained in NP either. The two classes are, as far as anyone can prove, incomparable. BQP is not simply “a bigger NP.”
Why Grover is not the loophole
Grover’s algorithm searches an unstructured space of N candidates in O(√N) queries instead of O(N). Surely, people reason, you point that at SAT and NP falls over?
No. For an n-variable problem, N = 2ⁿ, so Grover takes about 2^(n/2) steps. That is a quadratic speedup on an exponential, and a quadratic speedup on an exponential is still an exponential. Look at what that actually buys you:
OPS_PER_SEC = 1e9 # a generous billion oracle calls per second
def human_time(seconds):
if seconds < 1:
return "< 1 second"
if seconds < 86400:
return f"{seconds / 3600:.1f} hours"
if seconds < 3.15e7:
return f"{seconds / 86400:.1f} days"
years = seconds / 3.15e7
return f"{years:,.0f} years" if years < 1e5 else f"{years:.1e} years"
print(f"{'n':>4} {'classical 2^n':>12} {'Grover 2^(n/2)':>15} {'Grover runtime':>16}")
for n in [20, 40, 60, 80, 100, 128, 256]:
classical = 2 ** n
grover = 2 ** (n / 2) # ~(pi/4)*sqrt(N), constant dropped
print(f"{n:>4} {classical:>12.1e} {grover:>15.1e} {human_time(grover / OPS_PER_SEC):>16}")
n classical 2^n Grover 2^(n/2) Grover runtime
20 1.0e+06 1.0e+03 < 1 second
40 1.1e+12 1.0e+06 < 1 second
60 1.2e+18 1.1e+09 0.0 hours
80 1.2e+24 1.1e+12 0.3 hours
100 1.3e+30 1.1e+15 13.0 days
128 3.4e+38 1.8e+19 586 years
256 1.2e+77 3.4e+38 1.1e+22 years
Grover halves the exponent, and that is genuinely valuable, but a 256-variable brute-force search still takes 10²² years on a perfect noiseless machine at a billion oracle calls a second. It has not become tractable. It has become slightly less astronomically intractable. And this is before you pay for error correction, which in practice erodes a good part of that quadratic advantage.
Worse for the loophole theory: the √N is provably optimal. Bennett, Bernstein, Brassard and Vazirani proved in 1997 that any quantum algorithm needs Ω(√N) queries to search an unstructured black box. Grover is not merely the best algorithm we have found. It is the best that can exist. Quantum mechanics offers no further help on unstructured search, ever.
So why does Shor work?
Because factoring is not unstructured. It has hidden periodic structure, and Shor’s algorithm reduces factoring to period finding, which the quantum Fourier transform extracts efficiently via interference. The exponential speedup is bought with number theory, not with raw parallelism. (For the mechanism, see how quantum algorithms actually work and why quantum computers are faster.)
And the crucial rider: factoring is not known to be NP-complete, and is widely believed not to be. It sits in NP ∩ co-NP, which is strong evidence against NP-completeness. So Shor is not a crack in the NP wall. It is an exploit against one specific problem that happened to have exactly the structure a quantum computer can see. RSA is broken by it; SAT is not.
That is the general shape of every known exponential quantum speedup: find a problem with hidden algebraic or physical structure (quantum simulation is the other big one), and exploit it. There is no known general-purpose exponential speedup, and there is good reason to think there is no such thing.
The scorecard
| Claim | Status |
|---|---|
| Quantum computers can solve the halting problem | False. No machine can, quantum or otherwise. |
| Quantum computers compute functions Turing machines cannot | False. Identical computable class. BQP ⊆ PSPACE. |
| Quantum computers violate the Church-Turing thesis | False. They are a perfect fit for it. |
| Quantum computers threaten the extended Church-Turing thesis | Plausibly true, on the strength of Shor. Not proved, because factoring is not proved classically hard. |
| BQP contains P | True and proved. |
| BQP contains NP / solves NP-complete problems efficiently | Not known, and widely disbelieved. No such algorithm exists today. |
| Grover breaks NP-complete problems | False. Quadratic only, provably optimal, still exponential. |
| Shor breaks factoring | True, given a large fault-tolerant machine, because factoring has exploitable structure. It is not NP-complete. |
Two other limits worth naming, both of which cut against the “infinite parallelism” story: the no-cloning theorem means you cannot copy an unknown quantum state, and the Holevo bound means n qubits can deliver at most n classical bits of accessible information no matter how much amplitude you stuffed into them. The 2ⁿ amplitudes are real, but you do not get to read them out. Measurement hands you one string.
The honest summary
Turing drew a line in 1936 around what any mechanical process can compute, and quantum mechanics has not moved that line by a millimetre. Every quantum algorithm ever run could, in principle, have been run on a machine with a paper tape and a rubber stamp, given absurd amounts of time.
What quantum computing genuinely attacks is the second line, drawn much later, around what can be computed efficiently. That line does look movable, and factoring, discrete logarithms and quantum simulation are the strongest candidates for where it moves first. That is a profound claim about physics and complexity, and it is more than enough to justify the field.
It is just not the same thing as computing the uncomputable, and anyone who tells you otherwise is selling something. The frontier of quantum computing has never been the boundary of the computable. It is the boundary of the tractable, and it is being redrawn one structured problem at a time.
Was this tutorial helpful?