Quantum Power: Grover's Algorithm

Let’s say you misplaced your car keys. What you do is check every possible place one by one until you find them. Congratulations - you just executed a classical search. It’s slow, it’s inefficient, and sometimes it makes you question your life choices.

What if you had a bunch of helpers who start searching for your keys at once starting from different places? You find your keys a lot faster, right? You may say, meh, but what if you had a helper for every specific place—literally an army of millions at your disposal? Now we’re talking, right?

The sound you hear is quantum computers laughing in the face of linear search. They use a quantum search method called Grover’s Algorithm, which searches unsorted databases much faster than any classical computer algorithm could.

If we just run a quantum search, we really won’t have a baseline to compare it to. So, let’s build a console application in C# where we can run a search on 1 billion records of integers and measure the execution time.

Q# does not have stopwatch code like C#, so we are going to call Q# from our C# console application so we can measure the execution time.

Searching for one record in a large dataset is something classical computers do every day. However, there is a difference between how classical search and quantum search handle the problem.

That means for 1 billion records (N = 10⁹):

• Classical search → ~1 billion steps

• Grover’s Algorithm → ~31,622steps (√N)

So, in theory, Grover’s Algorithm should be

$$\frac{N}{\sqrt{N}} = \sqrt{N} \approx 31,622$$

≈31,622 times faster. But how does this hold up in practice? Let’s find out.

The Plan

We’ll create two projects:

1. A C# console application that uses classical search using Array.IndexOf()

2. A Q# quantum search using Grover’s Algorithm

Our goal is to find a random number in a dataset of 1 billion records and measure how long each approach takes. Fair enough? Let’s go then.

Classical Search

Our code for this search is simple:

using System;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main()
    {
        const int N = 1_000_000_000; // 1 billion records

        Console.WriteLine($"Generating {N:N0} random numbers for classical search...");
        Random random = new Random();
        int[] data = Enumerable.Range(0, N).Select(_ => random.Next(N)).ToArray();

        int target = data[random.Next(N)]; // Pick a random number from the dataset
        Console.WriteLine($"Searching for: {target}");

        Stopwatch stopwatch = Stopwatch.StartNew();
        int index = Array.IndexOf(data, target); // Linear search
        stopwatch.Stop();
        double classicalTimeMs = stopwatch.ElapsedTicks / (Stopwatch.Frequency / 1_000.0);

        Console.WriteLine($"Classical search found index {index} in {classicalTimeMs:F3} ms.");
    }
}

This code goes through everything until it finds a match. Naturally, it will be faster when the record we are looking for is closer to the beginning of the dataset and slower if it is towards the end.

Quantum Search

Since we’re not using real quantum hardware, let’s build a Q# project to simulate Grover’s Algorithm.

namespace QuantumSearch {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;

    // Oracle: Marks the correct answer in the superposition
    operation Oracle(qubits: Qubit[]) : Unit is Adj {
        // Apply phase flip to the marked state
        Controlled Z(qubits[0..14], qubits[15]);
    }

    operation GroversAlgorithm() : Int {
        use qubits = Qubit[16];

        // Step 1: Put all qubits into superposition
        for q in qubits { H(q); }

        // Step 2: Apply Grover’s Search Algorithm
        let iterations = 30;  // Roughly sqrt(2^16) for optimal search
        for _ in 1..iterations {
            Oracle(qubits);  // Apply Oracle (marks the solution)

            // Apply Grover Diffusion Operator
            for q in qubits { H(q); X(q); }
            Controlled Z(qubits[0..14], qubits[15]); // Multi-qubit phase flip
            for q in qubits { X(q); H(q); }
        }

        // Step 3: Measure all qubits and store results in a mutable array
        mutable results = [];
        for q in qubits {
            set results += [M(q)];
        }

        let resultInt = ResultArrayAsInt(results);

        ResetAll(qubits);
        return resultInt;
    }

    // Function to Convert Measurement Results to Integer
    function ResultArrayAsInt(results: Result[]) : Int {
        mutable value = 0;
        for i in 0..Length(results)-1 {
            if results[i] == One {
                set value = value + (1 <<< i);
            }
        }
        return value;
    }
}

Whoa, definitely more complex than the C# code. Let’s break it down.

Namespace and Imports

namespace QuantumSearch {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;

• open Microsoft.Quantum.Canon → Imports built-in quantum functions.

• open Microsoft.Quantum.Intrinsic → Gives access to quantum gates (Hadamard, X, Z, etc.).

• open Microsoft.Quantum.Measurement → Allows us to measure qubits (read their values).

Oracle Function: Marking the Correct Answer

operation Oracle(qubits: Qubit[]) : Unit is Adj {
        // Apply phase flip to the marked state
        Controlled Z(qubits[0..14], qubits[15]);
    }

The Oracle is a "black-box function" that tells us if we found the right solution by marking the correct answer by applying a phase flip (negative sign) to that state.

So, the question is why does a phase flip mark the correct answer?

Unlike the X gate, which flips a qubit between |0⟩ and |1⟩, the Z gate (phase flip) does not change the measurement result.

Instead, the Z gate flips the sign of the |1⟩ state:

• If the qubit is in |0⟩, nothing happens.

• If the qubit is in |1⟩, it gets a negative sign.

This doesn’t change the measurement outcome—it changes the wave interference pattern.

Yeah, I know what you’re thinking. Let’s take a little break and see what’s this wave interference thing is.

\=> Wave Interference <=

Wave interference is a phenomenon in physics where two waves overlap and combine. Depending on how they align, they can either reinforce or cancel each other out. Imagine two ripples in a pond. If two ripples meet in sync, they add up and create a bigger wave making that spot stronger and this is called constructive interference.

If one is up and the other is down then they cancel each other and the spot is weaker for it and this is called destructive interference.

This is exactly how Grover’s Algorithm amplifies the correct answer while suppressing the wrong ones.

Here is a representation of this phenomenon.

So, what happens is Grover’s Algorithm uses interference to make the correct answer stronger and wrong answers weaker. Then the Oracle flips the phase of the correct answer, making it negative. Finally, the Diffusion step flips everything around the average, reinforcing the correct answer’s probability.

This is useful in searching because at the beginning all answers have equal probability. Grover’s Algorithm uses interference to suppress wrong answers and boost the right one. After enough iterations, measuring gives us the correct answer with high probability.

This is why Grover’s Algorithm can find an answer in O(√N) instead of O(N). It steers the quantum state towards the correct answer instead of searching one by one. What this means is that every time you run a Grover iteration, the probability of the correct answer grows while others shrink. After approximately

$$\frac{\pi}{4} \sqrt{N}$$

iterations, the probability of measuring the correct answer becomes close to 100%.

Going back to the the code Controlled Z(qubits[0..14], qubits[15]); applies a Z gate (phase flip) to qubits[15] only if qubits[0..14] are all |1⟩. This ensures that only the correct answer gets flipped, helping Grover’s Algorithm amplify it later. It is kind of like a search engine highlighting the correct search result.

The Core of the Algorithm

operation GroversAlgorithm() : Int {
        use qubits = Qubit[16];

Here we allocate 16 qubits (so we can store 2¹⁶ = 65,536 possible states). Why 16 qubits you may ask? It’s simple really. We are running this on non-quantum hardware and classical hardware is not designed to run a large number of qubits. We just need to keep in mind that each state represents a possible search result.

Step 1: Superposition – Spread Out Across All Possibilities

// Step 1: Put all qubits into superposition
        for q in qubits { H(q); }

The Hadamard gate (H(q)) puts each qubit into superposition which means we now have all 65,536 possible answers encoded at once.

Step 2: Apply Grover’s Search Algorithm (Iterate 30 Times)

let iterations = 30;  // Using 30 iterations for simulation on classical hardware; 
                      // optimally, this would be around 201 for N = 65,536
        for _ in 1..iterations {

Grover's Algorithm works best when we run approximately π/4 √N iterations to maximize the probability of finding the correct answer. We already established that, with 16 qubits, our search space is N = 2^{16} = 65,536 possible states. Let’s calculate the optimal number of iterations:

$$\sqrt{65,536} = 256$$

The optimal number of iterations is roughly

$$\frac{\pi}{4} \times 256 \approx 0.785 \times 256 \approx 201$$

So, ideally, we would run around 201 iterations to maximize the probability of measuring the correct answer. However, since we’re simulating this quantum algorithm on a classical computer (my local PC), running 201 iterations would be computationally expensive. Each iteration involves multiple quantum gate operations, and simulating these for 16 qubits can quickly overwhelm a classical system. To make this simulation feasible on my hardware, I chose to run only 30 iterations instead. While this is fewer than the optimal number, it still allows us to demonstrate the principles of Grover’s Algorithm without crashing my computer. On real quantum hardware, we would use the full 201 iterations to achieve the best results.

Apply the Oracle (Mark the Correct State)

Oracle(qubits);  // Apply Oracle (marks the solution)

We call the Oracle function to mark the correct answer.

Apply Grover’s Diffusion Operator (Amplifies the Correct Answer)

// Apply Grover Diffusion Operator
            for q in qubits { H(q); X(q); }
            Controlled Z(qubits[0..14], qubits[15]); // Multi-qubit phase flip
            for q in qubits { X(q); H(q); }

The Grover Diffusion Operator boosts the probability of the correct answer by:

1. Applying Hadamard (H(q)) → Converts the problem back into a uniform superposition.

2. Applying X(q) → Flips all qubits (|0⟩ ↔ |1⟩).

3. Applying a controlled Z (Z(qubits[0..14], qubits[15])) to invert the marked state, so the next iteration increases its probability. You may ask why not just flip the correct qubit directly. If we did that we would swap the states but it wouldn’t affect interference patterns.

4. Undoing the previous steps (X(q), H(q)) to restore the superposition.

I know it sounds weird but think of this like repeatedly shaking a box of balls until the heaviest ball (the correct answer) rises to the top.

Step 3: Measure the Qubits

// Step 3: Measure all qubits and store results in a mutable array
        mutable results = [];
        for q in qubits {
            set results += [M(q)];
        }

This is where we measure all qubits (M(q)) to get an answer.

Convert the Measured Qubits to an Integer

let resultInt = ResultArrayAsInt(results);

ResultArrayAsInt(results) function below converts the binary measurement result into an integer. Why do we need to convert our results to integers? Well, our results come in binary, so we need something our C# code can understand. More on this in the next section.

Function: Convert Binary Qubit Output to an Integer

function ResultArrayAsInt(results: Result[]) : Int {
        mutable value = 0;
        for i in 0..Length(results)-1 {
            if results[i] == One {
                set value = value + (1 <<< i);
            }
        }
        return value;
    }

Remember, each qubit represents a binary digit (0 or 1). Our measurement results can be something like [Zero, One, One], and that’s 011 in binary.

We need to convert this to an integer 011 (binary) → 3 (decimal), so our C# app can understand it.

Final Step: Reset Qubits and Return the Result

 ResetAll(qubits);
 return resultInt;

Finally, we resets all qubits to |0⟩ for future computations and return the found index as an integer.

And that’s really it. Let’s quickly recap what we did in our Q# code.

TLDR;

Comparison

Let’s run and compare the results.

Generating 1,000,000,000 random numbers for classical search...
Searching for: 546031202
Classical search found index 356717552 in 155.892 ms.

Running Grover's Algorithm using Q#...
Grover’s Algorithm found: 9227
Quantum execution time: 48.791 ms.

Comparison of Classical vs Quantum Search:
-----------------------------------------------------
| Method                | Time Taken  | Complexity  |
|-----------------------|------------|--------------|
| Classical Search      | 155.892 ms  | O(N)        |
| Grover’s Algorithm    | 48.791 ms  | O(√N)        |
-----------------------------------------------------

Classical search takes about 155ms to find the result whereas Quantum search takes around 48ms - roughly 1/3 of the time.

The Quantum result, while much faster, is not earth shattering and there are a few reasons for that:

Quantum speedup happens at the hardware level, not just in the algorithm so simulating entanglement, superposition, and quantum gates on a classical CPU is extremely inefficient. Quantum simulators use classical brute-force math, which defeats the purpose of quantum speedups.

On top of that, .NET framework and C# is extremely optimized - especially for the hardware it is running on.

One thing we can do to even out the playing field a bit more and that is to get rid of any potential optimizations in our C# code made by the built-in method but in reality the framework is so optimized it may not make much of a difference. So, with that in mind, we will replace the following line;

 var index = Array.IndexOf(data, target);

with this code:

int index = -1;
for (int i = 0; i < N; i++)
{
    if (data[i] == target)
    {
        index = i;
        break;    
    }
}

After this change when we run our app we get the following result:

Generating 1,000,000,000 random numbers for classical search...
Searching for: 634394843
Classical search found index 454284875 in 203.032 ms.

Running Grover's Algorithm using Q#...
Grover’s Algorithm found: 54989
Quantum execution time: 47.998 ms.

Comparison of Classical vs Quantum Search:
-----------------------------------------------------
| Method                | Time Taken  | Complexity  |
|-----------------------|------------|--------------|
| Classical Search      | 203.032 ms  | O(N)        |
| Grover’s Algorithm    | 47.998 ms  | O(√N)        |  
-----------------------------------------------------

A bit better.

I know what you are thinking, “"Wait, I thought quantum was supposed to be thousands of times faster?".

On actual quantum hardware, Grover’s Algorithm would vastly outperform classical search, potentially executing in nanoseconds. Since we’re running a quantum simulation on classical hardware, we lose much of the quantum advantage. In fact, C# has the advantage here because it’s optimized for classical computers and chips.

Azure, IBM, and AWS all offer quantum computers you can try if you want to see the real difference. Without quantum hardware, we’re only simulating the process—no actual qubits are involved. While this is useful for learning, it’s not a substitute for the real thing.

You can find the source code here: https://github.com/tjgokken/QuantumDemo-Grover