Where my explanation of Grover’s algorithm failed

Original Media · 16m · English · YouTube · 3Blue1Brown

TLDR

This follow-up video clarifies common misconceptions about Grover's algorithm, specifically addressing how the quantum oracle (verifier) works without knowing the solution in advance. It explains that the oracle is compiled from classical logic gates (like a Sudoku checker), uses linearity to flip the amplitude of the solution state within a superposition, and emphasizes that the algorithm offers only a quadratic speedup — making it impractical for breaking modern cryptography like SHA-256 even with ideal quantum hardware. The 2D visualization of the algorithm is a mathematical artifact, not a computational step.

For you

PRO members can sign in and request more information — or their own version of this digest, tuned to what they care about.

Sign in to unlock

Surprising Insights

•

The "black box" oracle in Grover's algorithm is literally built from the same logic gates (AND, OR, NOT) as a classical verifier — it doesn't hide the answer, it just marks it via phase flip.

•

Linearity does not imply the quantum computer literally tries all inputs at once; the hiker analogy (rotating northeast vs. rotating north and east separately) shows it's a mathematical property, not a computational mechanism.

•

Even with a perfect, large-scale quantum computer, Grover's algorithm cannot break SHA-256 or similar cryptographic hashes because 2^128 operations remain far out of reach.

•

The algorithm's geometric visualization in 2D is a post-hoc human interpretation; the quantum state evolves in a massive Hilbert space without any awareness of the visualization.

Key takeaways

•

Grover's algorithm provides a quadratic speedup for unstructured search, reducing N steps to ~√N, not an exponential speedup.

•

The quantum oracle is not a black box that knows the answer; it is compiled from a classical verification circuit (logic gates) that checks candidate solutions.

•

Quantum linearity means the oracle flips the sign of the solution component in a superposition without evaluating all inputs in parallel — it's a property of the transformation, not a parallel execution strategy.

•

The 2D plane visualization of Grover's algorithm emerges from the math; the algorithm does not actively choose or know this plane.

•

For SHA-256, Grover reduces brute force from 2^256 to 2^128 operations — still computationally infeasible.

•

Classical verifiers encode rules (e.g., Sudoku constraints), not the solution; quantum compilation translates these rules into a unitary that marks valid solutions.

Notable quotes

“how could you know how to do that without already knowing which axis you're searching for?”

▸ Notable quotes · 1:16

“The logic gates distill the rules of the game, but not the strategy.”

▸ Notable quotes · 3:53

“The linearity is a property of the transformation, it's not necessarily a set of instructions on how to do it.”

▸ Notable quotes · 11:58

“using Grover's algorithm, this would still take around 9 to the 30 steps, which is a much smaller number, but it's still enormous.”

▸ Notable quotes · 14:52

“This quadratic speedup is much more representative of what you get for most problems.”

▸ Notable quotes · 15:45

Chapters

•

0:00 — Introduction & Core Confusion: The creator acknowledges confusion from the previous video: viewers thought the oracle step required knowing the solution in advance, because it flips the amplitude along the solution's axis in the state vector.

•

1:27 — Concrete Example: Sudoku Verifier: Uses a Sudoku checker as a classical verifier: easy to write a function that validates a solution, but hard to find the solution. The function encodes rules, not the answer. SHA-256 is a stronger example where reversing is believed to require brute force.

•

3:06 — From Classical Logic to Quantum Oracle: Explains that the classical verifier (logic gates) is compiled into a quantum circuit. The quantum version flips the phase (multiplies by -1) of basis vectors that satisfy the verifier, leaving others unchanged — without knowing which input is the solution.

•

5:00 — Linearity, Superposition & the Oracle's Action: Details how linearity causes the oracle to act on a superposition: it flips the sign of the solution component while preserving the rest. Clarifies this is not "parallel evaluation" but a mathematical property of linear transformations.

•

13:42 — Visualization vs. Algorithm Reality: The 2D plane used to visualize Grover's rotations is an emergent property of the math, not a step the algorithm performs. The algorithm simply interleaves two operations in the full high-dimensional space.

•

14:20 — Practical Limits: Quadratic Speedup Is Not Enough: Even with ideal quantum hardware, Grover's quadratic speedup leaves problems like Sudoku (9^30 steps) and SHA-256 inversion (2^128 steps) infeasible. Warns against hype claiming quantum computers break all cryptography.

Speakers

•

Narrator — Educator/Content Creator

⋮