How Does Grover's Algorithm Work (Mathematically Speaking)

Quantum computing has a habit of inflating cryptographic math into folklore that borders on myth. One week, investors hear that quantum machines will "break crypto". The next week, they hear that quantum computing is just a science fair project rather than a risk to actually be aware of.

The reality of the situation depends on which algorithm is being discussed, of which two pertain: 

• Grover's algorithm: Speeds up brute-force style searching in large, unstructured spaces

• Shor's algorithm: Efficiently solves factoring and discrete logs 

While the others have their place in the discussion around quantum security, the following article covers the first, breaking down the math behind Grover's algorithm so that you'll at least understand that portion of the problem in more detail.

Why Grover's shows up in crypto risk disclosures

Investors keep hearing about Grover’s algorithm because it changes the economics of a brute-force style search, and resilience against such brute force approaches underpins several important security assumptions today.

Before we touch any of the real math, let's define "search" in the specific sense that Grover's algorithm uses. 

The mental model to use here is that you have an efficient method for checking whether a single candidate solution to the problem is actually a solution , and you want to find an actual solution with as few calls to a checking function as possible. It's still necessary to actually check the solution afterward, which for now requires using a classical computer. 

More concretely, imagine you’re searching through N candidates. Classically, you’d test candidates one by one with a function f(x) that returns 1 if x is a solution and 0 otherwise. In Grover’s context, the oracle is the quantum version of that test, implemented as a reversible circuit you can call on a superposition of all x.

In Grover’s algorithm, an "oracle" is thus a black-box subroutine that can recognize a correct answer without telling you what it is. The oracle doesn’t recognize anything in the human sense, it flips a phase (or a flag qubit) conditional on f(x)=1.

In that oracle model, a classical brute-force approach on the order of N evaluations (at most) needs to find one marked item in a space of size N, with N/2 being the average number of evaluations. Grover’s algorithm changes the runtime to roughly √N evaluations. 

Using Grover's algorithm with a quantum computer means attaining a quadratic speedup of the process of finding the marked item in the search space. In contrast, using Shor's algorithm confers an exponential speedup, making keys crackable in polynomial time, unlike Grover's, which does not change the complexity class.

For now, just understand that using Grover's with a quantum computer is a large improvement over what's possible with classical computing because it effectively halves the security level. 

The danger, however, is that this is also where people overreach when thinking about what this algorithm (and the quantum computer running it) can actually accomplish. Even if the asymptotics improve, the predicate still has to be implemented as a coherent quantum circuit, and that cost can outweigh the speedup that's possible.

In the same vein, there are two cryptography-adjacent places Grover-style speedups are most often discussed:

• Symmetric key search, where the question is “does this key decrypt correctly?”

• Hash preimage search, where the question is “does this input hash to the target?”

Those categories matter for Bitcoin specifically, because Bitcoin uses both hashes and public-key signatures, and they do not face the same quantum attack. On that note, if you picture the quantum state as a unit vector of amplitudes, Grover’s algorithm is a controlled rotation that increases the amplitude on the answer while decreasing amplitude elsewhere.

The standard setup uses n qubits to represent N = 2^n basis states, and it begins from a uniform superposition over all candidates. From there, the algorithm repeats a two-part iteration, which we'll get into shortly in mathematical terms. 

For now, understand that the iteration stays inside a two-dimensional subspace, so you can reason about it with flat plane geometry even though the full state space is enormous. This is the core trick. The algorithm looks high-dimensional, but the dynamics you care about are two-dimensional.

In plainer terms, you start with the problem that all guesses within the problem space are equally likely. Then, each step of the iterate nudges the likelihood away from wrong guesses, and toward the right one. After about √N nudges, the right guess dominates the space. Then you look.

The math is not any easier than it looks 

Now, we're going to dig in deeper and write down the operators. Grover’s algorithm is basically two flat plane reflections, the first around the target and the second around the diagonal. The composition of these two reflections becomes a rotation towards the target.

Assume there is exactly one marked basis state, |w>. The standard oracle acts as a phase flip on that state and leaves every other basis state unchanged, which can be written as O_w = I − 2|w><w|.

Nothing is measured here. The oracle does not reveal the answer, it only changes a sign so that later interference can do useful work.

The second operation is the diffusion operator, which is the reflection about the uniform superposition |s>. In the common textbook form it is written as D = 2|s><s| − I.

The Grover iterate is G = D O_w. In the two-dimensional subspace spanned by |w> and the component of |s> orthogonal to |w>, G acts as a rotation.

After each iteration, the state vector is rotated closer to the marked direction, and after √N iterations, measurement returns the solution with high probability.

In case you got lost, here's a reference with all of the variables involved:

And, with that in hand, you can now unpack each of the elements of the algorithm itself: 

Now let's put it all together. Grover's algorithm is the following function: 

1. Let N = 2^n and start in |s> = (1/√N) Σ_x |x>. 

2. Define an oracle O|x> = (−1)^{f(x)}|x> and a diffusion operator D = 2|s><s| − I. 

3. One Grover iteration step is G = D O, and after k iterations the state is |ψ_k> = G^k|s>. 

4. With angle θ , sin θ = √(1/N) and P(success) = sin^2((2k+1)θ), maximized near k ≈ (π/4)√N.

Now that you're an expert at Grover's algorithm (just kidding), let's dive into the practical implications it has for Bitcoin. 

What this means for Bitcoin

Right off the bat, there are two constraints regarding the user of Grover's algorithm that investors should actually know about. 

• First, Grover’s algorithm is optimal up to constants for the purpose of unstructured search, so, while it still might be possible somehow, you probably should not expect anyone to have a secret and superior algorithm that beats √N in the same oracle model. 

• Second, the practical feasibility of the entire approach used by the algorithm depends on fault-tolerant quantum computing resources, which is exactly why NIST presentations focus on the practical cost. A quantum oracle for SHA-256 x 2 has many gates, making a single iteration of Grover's quite slow even when assuming zero error rates.

On that note, Bitcoin uses hashes for proof-of-work (PoW) and public-key signatures for authorization, and those map to different quantum algorithms.

The proof-of-work side is built on the properties of SHA-256, and the overall mining process is described in the Bitcoin whitepaper. The signature side is different; transaction authorization in Bitcoin relies on ECDSA over secp256k1, which is why the most serious quantum risk discussions are about signature migration rather than about hashing.

To keep the surfaces distinct, the table below maps Bitcoin components to the relevant quantum pressure and the mitigation lever. Think of it as a way to keep yourself from paying attention to the wrong threat narrative.

Before the table, one warning: the speedups here are asymptotic. Real-world attacks are gated by error correction, circuit depth, and the cost of implementing the predicate as a reversible quantum circuit.

Thus, Grover’s algorithm implies different safety margins than Shor's for keys and lower costs for the computers needed to perform the attack. It does not magically bypass Bitcoin’s defenses, at least not until there are fault-tolerant machines at sufficient scale.

In closing, treat Grover’s algorithm as a pressure on cryptographic conservatism and an influence on the quantum computing industry's competitive dynamics. The math might be hard, but you probably don't need to understand every element of it to appreciate that it's a vector for risk. 

Sources:

• Quantum mechanics helps in searching for a needle in a haystack

• Applying Grover’s algorithm to AES: quantum resource estimates

• Quantum-Safe Cryptography: Quantum key distribution

• Quantum Computing Lecture 8

• Lecture 22: Grover’s Algorithm

• Quantum Amplitude Amplification and Estimation

• Grover’s quantum searching algorithm is optimal

• Practical Cost of Grover for AES Key Recovery

• FIPS 180-4 Secure Hash Standard

• Bitcoin: A Peer-to-Peer Electronic Cash System

• Transactions

• A fast quantum mechanical algorithm for database search

• FIPS 197 Advanced Encryption Standard

• Algorithms for quantum computation: discrete logarithms and factoring