Simon's Algorithm - Rishan Solutions

Simon’s Algorithm is a quantum algorithm that solves a very specific type of problem exponentially faster than any classical algorithm can.

It was proposed by Daniel Simon in 1994 and became the first quantum algorithm to demonstrate exponential speedup over classical computers.

This algorithm later inspired Shor’s Algorithm, which can factor large numbers efficiently—a big deal in cryptography.

The Problem: Simon’s Problem

Imagine someone gives you a black box (also called an oracle) that takes an input (like a bitstring) and gives an output (another bitstring).

This black box has a secret inside:
There is a special pattern hidden in the inputs and outputs.
You are told:

Either every input gives a unique output,
Or some inputs share the same output, and these inputs are always related by a special hidden value, called s.

Your goal is to find this hidden value s.

This hidden string s is what Simon’s Algorithm reveals, much faster than classical algorithms.

Classical Solution (Why It’s Hard)

In the classical world:

You would keep inputting values into the black box and checking outputs.
You’d look for repeated outputs and try to figure out what inputs led to the repetition.
You might have to check exponentially many inputs to be sure.

It’s like trying to solve a massive jigsaw puzzle with very few clues.

So, it’s not efficient at all.

Quantum Solution (Simon’s Algorithm)

Now enter the quantum world.

Simon’s algorithm cleverly uses quantum principles like:

Superposition: Being in many states at once.
Interference: Canceling out wrong answers and enhancing the right ones.
Measurement: Collapsing quantum states to get useful info.

By leveraging these, the quantum solution reduces the number of queries drastically—from exponential to polynomial time.

Let’s walk through it step-by-step.

Step-by-Step: How Simon’s Algorithm Works

Step 1: Set Up the Quantum System

You begin by preparing two quantum registers:

The first register is for the input (n qubits).
The second register is for the output of the black box.

All qubits start in a known default state, which is essentially like a blank slate.

Step 2: Create Superposition

You apply quantum operations to put the input qubits into superposition.

This means:

The input register now represents all possible input combinations at once.

Imagine you have a deck of 1000 cards. Instead of flipping one card at a time, quantum superposition lets you flip all cards at once.

Step 3: Query the Black Box (Oracle)

You now send this superposition of all possible inputs through the black box.

The black box maps each input to an output based on a secret rule. If it has a hidden string s, then two different inputs related by s will give the same output.

This step entangles the input and output registers. Think of it like pairing socks—you don’t know which socks match until you’ve seen the result of the pairing.

Step 4: Measure the Output Register

You now measure the output register. This collapses it into a specific value.

Due to quantum entanglement, this also affects the input register. The input register is now left in a state that only includes the two inputs that corresponded to the same output.

This step reduces possibilities to a useful pattern — a step classical computers can’t do efficiently.

Step 5: Apply Quantum Interference

Now, apply a special transformation (known as a Hadamard transform) to the input qubits.

This transformation creates a pattern of constructive and destructive interference, which enhances the quantum states that are related to the secret string s.

Step 6: Measure the Input Register

Now, you measure the input register.

You don’t get the secret string s directly, but you get a result that has a mathematical relationship to s.

This result gives you clues—like partial fingerprints.

Step 7: Repeat Multiple Times

You repeat the whole process multiple times (usually n times, where n is the number of bits).

Each time, you get a new piece of information related to s. Once you’ve collected enough of these results, you can combine them to figure out s.

This final step is classical (simple math), and now you’ve cracked the secret.

Why Simon’s Algorithm Is Special

Feature	Classical Approach	Quantum (Simon’s Algorithm)
Number of queries	Exponential (2ⁿ⁄²)	Polynomial (O(n))
Reveals hidden pattern	Slowly, inefficiently	Quickly, with fewer steps
Uses interference	No	Yes
Real-world influence	Minimal	Inspired Shor’s Algorithm

Real-World Analogy

Imagine you’re in a dark room with 1000 switches. One switch is connected to another by a hidden wire (the secret s), and flipping both gives the same result.