Imagine a bizarre promise oracle that contains a secret bitstring, $s$, of length $n$. This oracle promises that for any input $x$, its output $f(x)$ will be the same as $f(x \oplus s)$. This is known as a ‘two-to-one’ function. The challenge is to find the secret string $s$.
On a classical computer, solving this problem can take an exponentially long time. However, Simon’s algorithm, a hybrid quantum-classical approach, provides an exponential speedup, solving the problem in a time that grows linearly with $n$.
Simon’s algorithm was the first to prove that quantum computers could outperform classical computers so dramatically, making it a groundbreaking moment in quantum information science.
🧩 A Hybrid Approach for a Complex Problem
Unlike the algorithms we’ve seen so far, Simon’s algorithm doesn’t give you the answer in a single run. Instead, it’s a hybrid algorithm with two parts. The first part is a quantum circuit that you run multiple times. Each run produces a measured bitstring that contains a piece of information about the secret string $s$.
The second part is a classical algorithm that takes these measured outputs and combines them to solve for $s$. The elegance of this approach is that the difficult, time-consuming part of the problem is handled by the quantum computer, and the rest is left to the classical computer, which is much better at processing the results.
⚛️ The Quantum Circuit and Its Unpredictable Output
The quantum circuit for Simon’s algorithm is very similar to the ones for Deutsch-Jozsa and Bernstein-Vazirani. It uses a register of $n$ qubits and a second auxiliary register of $n$ qubits, both initialized to $|0\rangle$.
After applying Hadamard gates to the first register, the qubits are sent into the oracle. A key insight of Simon’s algorithm is that the measured output, let’s call it $z$, always satisfies the condition $s \cdot z = 0$. This means that the dot product of the secret string and your measured string is always even. This single piece of information isn’t enough to solve for $s$, but after a few more runs, you’ll have enough equations to solve for the secret string using a classical algorithm like Gaussian elimination. The number of runs required grows linearly with $n$, providing a dramatic speedup over any known classical approach.
—
Glassner, Andrew. Quantum Computing: From Concepts to Code. No Starch Press, 2025.
More Topics
- The Quantum Threat: How Shor’s Algorithm Puts Modern Encryption at Risk
- Cracking the Code: How Quantum Parallelism Solves Deutsch’s Problem in One Step
- The Deutsch-Jozsa Algorithm: An Exponential Leap in Quantum Problem Solving
- The Bernstein-Vazirani Algorithm: Unmasking a Secret With a Single Query
- The ‘Spooky Action’: What Happens When Qubits Entangle?
- The Quantum Enigma: Why Measurement is the Most Unpredictable Step
- Can You Teleport a Qubit? The Amazing Alice & Bob Experiment
