Part 7: The Shape of a Quantum Algorithm
Table of Contents
(Updated: July 2026)
This is Part 7 of Quantum Computing for Cybersecurity Professionals, an 11-part series that builds quantum computing from the ground up for security and IT professionals who know classical crypto but have no physics background. No lies-to-children, no hype, every claim checkable with arithmetic. Read the full series online or download the free ebook.
In 1985, David Deutsch published the first quantum algorithm. It answered a question nobody was asking, about a function nobody cared about, one bit at a time. It was also the blueprint for breaking RSA. Four decades of quantum algorithms later, from that toy to the machine your migration program exists to outrun, every single one of them is still Deutsch’s moves in the same order.
This part assembles the toolbox into that shape. You hold all the pieces: amplitudes that carry signs, the collision that makes signs count (Part 4‘s engine), a workspace of $$2^n$$ amplitudes behind an $$n$$-bit door (Part 5), and entanglement to bind registers together. What follows is how quantum algorithms work: the four-move template every one of them obeys, a complete worked example small enough to run at your desk, and the reason the recipe pays out only when a problem brings structure to the table. By the end, the casualty list from Part 1 stops being a claim and becomes a mechanism.
Four moves
Prepare. Hadamards on every qubit spread amplitude evenly across all $$2^n$$ input strings. This is the honest half of the parallelism myth, and it costs almost nothing: one gate per qubit and the workspace is open.
Imprint. Run the problem through the register once, writing what the problem knows into the amplitudes, typically as a pattern of signs. A circuit that evaluates a function $$f$$ can be compiled to flip the sign of every input string where $$f$$ says 1. After this move the register holds the problem’s entire truth table, encoded in signs. It also holds, per Part 3, nothing you can see: signs are invisible to measurement, and if you measured now you would draw one random input, exactly the dilution-refrigerator-as-random.choice fiasco of Part 5’s autopsy. Two moves in, nothing has been gained. This is worth saying plainly, because vendors never do.
Interfere. The closing transform. A second layer of gates makes the signed amplitudes collide, and here is the entire art form: the transform is chosen so that computational routes toward strings describing the problem’s global pattern arrive in agreement and reinforce, while routes toward everything else arrive in conflict and cancel. Part 4’s $$+1/2$$ against $$-1/2$$, scaled to millions of colliding routes. The transform is fixed in advance, built from the problem’s form alone, because nobody knows the answer yet.
Measure. The narrow door opens once and pays out $$n$$ bits. If the choreography was right, those bits name the global pattern, and the state is spent buying them.
That is the whole genre.
The whole game in one qubit
Deutsch’s problem sounds like a pentest constraint. You are handed an oracle for an unknown one-bit function $$f$$: feed it 0 or 1, it returns $$f(0)$$ or $$f(1)$$. There are four possible functions: two constant (always 0, always 1) and two balanced (the identity, and NOT). Your question: is $$f$$ constant or balanced? Your budget: one call.
Classically, one call is hopeless. Learn $$f(0) = 0$$ and the function could still be constant-zero or the identity; the question compares two values, and you have one. Any classical strategy needs both calls, full stop. The quantum run takes one, and it is the four moves verbatim. Prepare: a Hadamard puts the qubit at $$(1/\sqrt{2}, 1/\sqrt{2})$$. Imprint: one oracle call flips the sign of each input’s amplitude where $$f$$ outputs 1. Interfere: a second Hadamard. Measure: the bit reads 0 for constant, 1 for balanced, with certainty. The arithmetic box runs all four cases; it is sixteen additions, and I recommend actually doing them, because this is the smallest complete quantum algorithm that will ever exist and it fits on an index card.
Two details in the outcome repay attention. First, you have run this algorithm before: Part 4’s impossible coin was Deutsch’s algorithm applied to the laziest function on the menu, constant-zero, whose oracle does nothing. The impossible coin was never a stunt; it was the genre’s first rehearsal. Second, look at what you learned and what you paid. The output bit answers the comparison, constant versus balanced, a global property of $$f$$. Ask the algorithm what $$f(0)$$ actually was and it cannot tell you; that information fed the interference and was consumed by it. One call bought one bit, Holevo smiling in the background, and the algorithm’s genius was spending its single bit on the question that needed two classical calls: one call, one bit, certainty.
THE ARITHMETIC: All four functions, sixteen additions.
The oracle rule: flip the sign of the amplitude at input $$x$$ wherever $$f(x) = 1$$. Start every run at $$(1,0)$$, Hadamard to $$(1/\sqrt{2}, 1/\sqrt{2})$$, apply the oracle, Hadamard again using Part 4’s rule $$a_0′ = (a_0 + a_1)/\sqrt{2}$$, $$a_1′ = (a_0 – a_1)/\sqrt{2}$$, then measure.
Constant zero, no flips: $$(1/\sqrt{2}, 1/\sqrt{2}) \rightarrow (1, 0)$$. Output 0.
Constant one, both flipped: $$(-1/\sqrt{2}, -1/\sqrt{2}) \rightarrow (-1, 0)$$. The Born rule squares: output 0 with certainty. An overall minus sign in front of everything is invisible; only relative signs ever fight.
Identity, second amplitude flipped: $$(1/\sqrt{2}, -1/\sqrt{2}) \rightarrow (0, 1)$$. Output 1.
NOT, first amplitude flipped: $$(-1/\sqrt{2}, 1/\sqrt{2}) \rightarrow (0, -1)$$. Output 1, certainty again.
Constant functions output 0, balanced functions output 1, one oracle call each. (One import on credit, in this series’ tradition of labeling them: turning an ordinary circuit for $$f$$ into a sign-flipper is a standard compilation, one helper qubit and a trick called phase kickback, at the cost of exactly one evaluation of $$f$$.)
Credit where the history puts it: Deutsch’s 1985 version answered with certainty only half the time, saying “don’t know” otherwise; the crisp one-call form above is the 1998 refinement by Cleve, Ekert, Macchiavello, and Mosca. That last name is doing double duty in this series; you met Mosca’s inequality in Part 1, setting your migration deadline. The man tuning the first quantum algorithm and the man timing your response to it are the same person, which tells you something about how small and how serious this field is. Deutsch and Jozsa had already scaled the problem to $$n$$-bit functions in 1992, one call replacing up to $$2^{n-1}+1$$, and the template never changed.
Why structure is the entry fee
Now the constraint that shapes the entire casualty list. The interfere move is a fixed transform, designed before anyone knows the answer, from nothing but the problem’s form. For the design to exist at all, right answers must be distinguishable from wrong ones by their relationship to the whole input space: a period, a parity, a constant-versus-balanced split, some global regularity that a pre-committed transform can convert into concentrated amplitude. Deutsch’s problem is the minimal case, one bit of global pattern. Shor’s algorithm is the maximal one, where the pattern is the period hiding inside modular arithmetic, and the closing transform is a Fourier transform, the mathematical instrument whose one job is finding periods.
Take the structure away and the recipe starves. A generic search problem, find the preimage, guess the key, satisfy the formula, offers no global regularity: the right answer relates to the wrong ones by nothing but being right. No pre-committed transform can aim cancellation at “everything except the answer” without knowing the answer, so the choreography has nowhere to stand, and the only quantum recourse is a generic amplitude-nudging trick worth a quadratic speedup and no more, which is Part 9‘s whole story. This is the mechanism under the sentence Part 1 asserted on credit: structure is what the machine eats. The same fact is a compliment your field has earned. Symmetric cryptography holds up in the quantum era for the same reason it held up in the classical one: cryptographers spent half a century sanding every exploitable pattern off it. AES resists the choreography because there is nothing regular for the choreography to aim at. No pattern, no algorithm.
The myth’s replacement is now complete, in the final form Part 5 promised. The machine really does imprint every input’s contribution at once, and that costs one evaluation and buys nothing. Advantage exists exactly when a closing transform can convert the spread into one readable global fact, and the door lets exactly that fact out. Parallelism is free and worthless. Interference, aimed by structure, is the entire product.
WHERE THIS BREAKS: Two analogies, retired on schedule.
Choreography has carried this series since Part 1, and its limit is that dancers improvise while gates never do: every transform is a fixed, deterministic, linear operation, committed before the music starts. The art lives entirely at design time, in the mathematician’s choice of transform; at runtime the machine executes arithmetic with the creative latitude of a payroll system. And the noise-cancelling headphone, the other intuition on loan here, borrows a medium that does not exist: sound waves cancel in air, while amplitudes cancel in nothing at all. What interferes in a quantum computer is possibility itself, with no substance doing the waving, which is precisely why no classical wave gadget, however clever, reproduces Part 4’s bench.
FOR THE RECORD: What the machine cannot do, complexity edition.
One box of complexity theory, as promised, and then the series drops the subject. The problems quantum computers handle efficiently form a class called BQP. It contains everything classical computers do efficiently, and it is believed, on the strength of factoring, to reach beyond. It is not known, or seriously believed, to contain the NP-complete problems: scheduling, routing, generic SAT, the travelling salesman. No proof exists either way, but four decades of trying have produced no structured quantum attack on any NP-complete problem, and Part 9’s quadratic ceiling is the best generic result anyone has. When a pitch deck promises quantum computers will “solve optimization,” apply Part 1’s reflex: at what, exactly, and where is the closing transform?
FOR THE RECORD: The parallel-universes clause.
David Deutsch, who built the first algorithm above, holds that the honest reading of all this arithmetic is that the computations occur across parallel universes, and he argues it seriously; many-worlds is a real position held by serious physicists. This series takes no side, for an operational reason rather than a diplomatic one: interpretations are stories about what amplitudes mean, engineered to make identical predictions, and every one of them must reproduce the sixteen additions in the box above, digit for digit. The universes, if you keep them, are a picture attached to the arithmetic, never a mechanism added to it; nothing computes faster because a story got grander. Whatever story you attach, the table is the table.
ATTACKER’S-EYE VIEW: A targeting doctrine, and a fraud detector.
The template doubles as an evaluation framework, and I suggest running every “quantum threat to X” claim through it. Two questions: what global structure does X expose, and what closing transform converts that structure into a readable answer? RSA answers both, period and Fourier transform, and dies in Part 8. AES answers neither and gets a quadratic dent in Part 9. When the next paper claims a quantum attack on some protocol, find the imprint and find the transform; where there is no transform, there is no threat, only a press release wearing equations.
The same lens catches the most common accounting fraud in quantum claims. I read every quantum-speedup paper with one finger on the oracle, because the imprint step is where costs hide: if “loading the data” into the register quietly costs what the classical computation cost, the exponential speedup is a shell game, and a noticeable fraction of quantum machine-learning claims over the past decade have died in exactly that audit. The oracle is an assumption wearing a lab coat. Check its invoice.
What to remember
Every quantum algorithm is four moves: prepare a uniform superposition, imprint the problem into the signs at the cost of about one evaluation, interfere with a transform fixed in advance, and measure the one global fact the choreography concentrated. Deutsch’s problem runs the entire shape in one qubit, answering in one call a question that classically takes two, and paying for it precisely: the algorithm learns the comparison and forfeits the values. Advantage requires structure, because the closing transform must aim cancellation using the problem’s form alone, which is why RSA’s periodic arithmetic is fatal exposure and AES’s deliberate patternlessness is quantum resistance by fifty years of habit. Parallelism is free and buys nothing; interference aimed by structure is the entire product. And no interpretation, universes included, adds a single addition to the arithmetic.
Next, in Part 8, “Shor: Cryptanalysis by Physics”: Deutsch asked one bit about one toy function. Part 8 aims the same four moves at a 2048-bit modulus, where the global pattern is a period hiding inside modular exponentiation and the closing transform is the quantum Fourier transform. The casualty list stops being a table and becomes a walkthrough.
