English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

Two Lineages of Quantum Algorithms: Amplitude Amplification vs. Hidden Subgroup

Forum topic · 小凯 · 2026-11-07

Summary

This article is part 40 of a Chinese quantum computing column ('From Coins to Error Correction') and serves as the capstone of the column's fourth batch on quantum algorithms. It organizes six previously covered algorithms—Deutsch-Jozsa, Bernstein-Vazirani, Grover, Simon, the Quantum Fourier Transform (QFT), and Shor—into two genealogical families. The amplitude amplification family (DJ, BV, Grover) works by marking target answers and reflecting around the mean, offering polynomial (quadratic) speedups for weakly promised, arbitrary black-box problems, and generalizes to Monte Carlo sampling, optimization, and estimation. The hidden subgroup family (Simon, Shor, QFT) exploits built-in symmetry: a Fourier transform converts repeated structure into frequency spikes, yielding exponential speedups for problems like period finding, cryptanalysis, and phase estimation. The article also maps honest limitations: efficient QFT circuits remain unknown for general groups (e.g., graph isomorphism), Grover's square-root speedup cannot rescue NP-hard problems, and the two-family taxonomy reflects today's textbook landscape rather than a final classification.

> Prerequisite navigation: You need posts 031–039 (all six tools from batch four) and 034 (lineage patterns). > Next episode preview: 041 (opening of batch five).

Two Lineages: Amplitude Amplification and the Hidden Subgroup

<svg xmlns="http://www.w3.org/2000/svg" width="760" height="400" viewBox="0 0 760 400" role="img"> <defs><linearGradient id="bg40" x1="0" y1="0" x2="1" y2="1"><stop offset="0" stop-color="#0b1220"/><stop offset="1" stop-color="#17233d"/></linearGradient><linearGradient id="gA" x1="0" y1="0" x2="0" y2="1"><stop offset="0" stop-color="#ffd76a"/><stop offset="1" stop-color="#d9a326"/></linearGradient><linearGradient id="gB" x1="0" y1="0" x2="0" y2="1"><stop offset="0" stop-color="#d6e8ff"/><stop offset="1" stop-color="#8fb3d9"/></linearGradient></defs> <rect width="760" height="400" rx="20" fill="url(#bg40)"/> <rect x="1.5" y="1.5" width="757" height="397" rx="19" fill="none" stroke="#2c3e5c" stroke-width="3"/> <text x="40" y="58" font-family="PingFang SC, Microsoft YaHei, sans-serif" font-size="16" fill="#8fa3c4">From Coins to Error Correction · Quantum Computing Column</text> <text x="40" y="110" font-family="PingFang SC, Microsoft YaHei, sans-serif" font-size="30" font-weight="bold" fill="#7fd4ff" opacity="0.9">040</text> <text x="128" y="110" font-family="PingFang SC, Microsoft YaHei, sans-serif" font-size="33" font-weight="bold" fill="#eef3fa">Two Lineages: Amplitude Amplification & Hidden Subgroup</text> <text x="40" y="150" font-family="PingFang SC, Microsoft YaHei, sans-serif" font-size="19" fill="#9fb3d4">Amplitude amplification and hidden subgroups</text> <line x1="40" y1="176" x2="720" y2="176" stroke="#3a4f73" stroke-width="2"/> <circle cx="230" cy="270" r="40" fill="none" stroke="#f5c542" stroke-width="3"/><circle cx="230" cy="270" r="22" fill="none" stroke="#f5c542" stroke-width="2"/><circle cx="230" cy="270" r="8" fill="#f5c542"/><rect x="420" y="222" width="10" height="96" rx="4" fill="url(#gB)" /><rect x="448" y="244" width="10" height="74" rx="4" fill="url(#gB)" /><rect x="476" y="222" width="10" height="96" rx="4" fill="url(#gB)" /><text x="580" y="270" font-family="PingFang SC, Microsoft YaHei, sans-serif" font-size="17" fill="#eef3fa" text-anchor="middle" font-weight="bold">Two Lineages</text><text x="230" y="340" font-family="PingFang SC, Microsoft YaHei, sans-serif" font-size="13" fill="#f5c542" text-anchor="middle">Periodicity</text><text x="455" y="340" font-family="PingFang SC, Microsoft YaHei, sans-serif" font-size="13" fill="#8fb3d9" text-anchor="middle">Amplification</text> <text x="40" y="380" font-family="PingFang SC, Microsoft YaHei, sans-serif" font-size="14" fill="#5d7396">Core Algorithms I</text> </svg>

When biologists face millions of species, the first thing they do is classify: kingdom, phylum, class, order—chaos resolved into order. This batch released six quantum algorithms in one go (DJ, BV, Grover, Simon, QFT, Shor), and this closing piece does the same thing: step back and turn the zoo into a map.

You will see that the six weapons actually come from just two lineages. Seeing the lineages clearly is worth more than memorizing ten more algorithms—it answers the more fundamental question: what are quantum computers actually good at, and what are they not?

Lineage One: The Amplitude Amplification Family—"Shake the Right Answer Bigger"

Patriarch: Grover. Its inherited technique (post 033): mark (flip the target arrow) → reflect around the mean (trade outliers for height) → repeat √N times.

DJ and BV are distant ancestors of this family—read together with Grover, the three posts are the gradual evolution of one move:

  • DJ: reads out a global property—"constant or not?"—via interference (one query, a 0/1 verdict);
  • BV: extends the read to n bits (one query, an entire string)—but the promise is locked to special black boxes;
  • Grover: upgrades "reading properties" into "amplifying targets"—no longer hoping for a single readout, instead growing a bit each shake, √N shakes, general to any black box.
  • The family's motto in one sentence: Is the answer's amplitude too small? Build a machine that only does work on "right answers" and shake the probability from a thousandth to nearly one. The speedup is fixed at polynomial level (the square root is the ceiling, post 034)—that's the family rule: weak promises, strong generality, moderate speedups.

    This family's territory goes far beyond search. Its generalized technique (literally named amplitude amplification) is the quantum version of a "Monte Carlo accelerator": any task of "sampling to estimate averages, maxima, or probabilities" can take a square-root speedup—many of the optimization and simulation techniques in batch five are distant descendants of this patriarch. "Shaking the right ones bigger" is the most general lever in quantum algorithms.

    Lineage Two: The Hidden Subgroup Family—"Flipping Out the Hidden Symmetry"

    Patriarch: the Quantum Fourier Transform (post 036). Two generals already on stage: Simon (035) and Shor (037/038).

    This family's shared premise: the problem hides a symmetric structure—some "translation" under which the structure repeats periodically. Mathematicians call this class of problems the hidden subgroup problem (no need to memorize the name; in plain words: "the answer hides a repetition—find the rhythm of the repeat"):

  • Simon: the rhythm is an XOR shift of bit strings (x and x⊕s share the same answer);
  • Shor: the rhythm is the period r of integer cycles (the power sequence replays every r steps);
  • QFT: both battles use the same engine—the axis-switcher flips repeated structure into frequency spikes (post 036), with each mathematical world equipped with its own Fourier transform.
  • The family rules are exactly the opposite of lineage one: strong promises (the problem must come with its own symmetry), fierce speedups (exponential), luxurious practical results (the final chapter of public-key cryptography, plus the chemical ground-state energies coming in batch five—phase estimation is this engine's second production line).

    The two families, side by side in one table:

    | | Amplitude Amplification Family | Hidden Subgroup Family | | :--- | :--- | :--- | | Core move | Mark → reflect around the mean → repeat | Axis switch (QFT) flips symmetry into frequencies | | Promise strength | Weak (any black box) | Strong (built-in symmetry) | | Speedup magnitude | Polynomial (√N ceiling) | Exponential | | On-stage representatives | Grover (DJ/BV as ancestors) | Simon, Shor | | Practical results | Search, sampling, optimization speedups | Cryptanalysis, phase estimation, chemistry simulation |

    The lineage pattern from post 034 (trading promises for speed) is here upgraded into the terrain law of the whole map: the boundary between the families is the exchange rate between "generality" and "raw acceleration."

    The Blank Spaces on the Map

    Three honest boundaries, lest the map become a poster:

    One, the hidden subgroup family has unconquered territory. The QFT engine has efficient circuits over "bit-string groups" and "integer-cycle groups," but over more general groups (e.g., groups of graph symmetries), efficient circuits have still not been built—several famous candidate hard problems (like graph isomorphism) are stuck at this frontier: the problem looks symmetric, but the engine won't connect. This is an official topic of the column's ninth batch, "unsolved mysteries."

    Two, the amplitude amplification family's speedup can't rescue hopeless cases. For the hardest problems that require brute-forcing 2^n candidates (NP-hard in complexity-theory terms), Grover only gives a square root—2^1000 becomes 2^500, despair in a different pose. Quantum is not a universal accelerator: when there is no symmetry to flip and no structure to amplify, it can only count alongside you. Post 046 will measure this boundary more precisely with the ruler of complexity classes.

    Three, the two-family classification is today's textbook terrain, not the universe's constitution. It would not be surprising for a third lineage to emerge in the future (a variational family specializing in simulation is already waiting in the wings for batch five)—taxonomy describes known species, not future ones.

    Taking the Analogy Apart

    Where the "family tree" analogy is borrowed from:

  • Disanalogy one: family trees rely on blood inheritance, while algorithm lineages rely on verifiable technical commonalities (the same engine, the same technique)—the commonalities are mathematical facts, not family legends.
  • Disanalogy two: extinct species never revive, but algorithms can "atavistically upgrade"—DJ's old move was re-packaged and re-released by Grover; the inheritance within lineage one is alive.

Luggage to Take Home

1. Two families of quantum algorithms: amplitude amplification (weak promises, √N ceiling, "shake the right ones bigger"—the general lever) and hidden subgroups (strong promises, exponential speedups, "flip the symmetry out"—luxurious results); DJ/BV/Grover belong to the former, Simon/QFT/Shor to the latter. 2. The terrain law: generality and speedup magnitude trade off against each other (the whole-map version of post 034's lineage pattern); in structureless despair, quantum only offers a despairing square root—what it excels at are worlds with symmetry to flip. 3. The map has blank spaces: the quantum Fourier transform over general groups (graph isomorphism, etc.) remains unsolved; new lineages keep emerging—classification is open.

Batch four ends here. Six weapons, two lineages, one map—from "spotting the cheating mint" to "the final chapter of cryptography," this batch walked the main road of the quantum algorithm world. At the opening of batch five, the patriarch's universal calling card gets its official biography: phase estimation—it is at once the heart of Shor, the stethoscope chemists use to measure molecular energies, and the most load-bearing beam of the entire "quantum applications" building. See you in 041.

Tags

#quantum-computing#quantum-algorithms#amplitude-amplification#hidden-subgroup-problem#grover-algorithm#quantum-fourier-transform#shor-algorithm#phase-estimation

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178636874