Bernstein–Vazirani and Simon’s Algorithm: Unlocking Hidden Information with Quantum Computing

Bernstein–Vazirani Problem

The Bernstein–Vazirani problem is a simple yet powerful example of how quantum computers can outperform classical ones.

The Problem

We are given a function based on a hidden binary string a∈{0,1}n. The function satisfies:

• 𝑥𝑖 = (𝑖 ⋅ 𝑎 ) mod 2

This means each output bit is computed as the dot product (modulo 2) of the input ( i ) and the hidden string 𝑎.

Goal: Determine the hidden string 𝑎.

The Quantum Solution

The quantum algorithm works similarly to the Deutsch–Jozsa algorithm, but with a surprising outcome.

After querying the function, the quantum state becomes:

Since 𝑥𝑖 = (𝑖 ⋅ 𝑎 ) mod 2, this can be rewritten as:

The Key Insight

Applying a Hadamard transform to each qubit converts this state directly into:

∣a⟩

This means we can read off the hidden string in a single measurement.

Efficiency Comparison

• ✅ Quantum algorithm: 1 query + O(n) operations
• ❌ Classical algorithm: Requires at least n queries

This is because each classical query reveals at most one bit of information, while the quantum algorithm extracts all bits at once.

Recursive Version

Bernstein and Vazirani also proposed a recursive version of the problem:

• Quantum solution: solvable in polynomial time
• Classical randomized solution: requires super-polynomial time

Simon’s Algorithm

Simon’s algorithm takes things further by demonstrating an exponential speed advantage over classical algorithms.

The Problem

We are given a function with a special hidden structure:

• There exists a secret string "s not equal to O^n" such that: xi=xj if and only (i=j or i=j⊕s)

This means:

• The function is 2-to-1
• Inputs come in pairs separated by the hidden string ( s )

Goal: Find the hidden string ( s ).

The Quantum Algorithm

Simon’s algorithm follows a sequence of steps similar to earlier quantum algorithms.

Step 1: Initialize and Create Superposition

Start with two registers:

Apply Hadamard gates to the first register:

Step 2: Query the Function

After querying the function:

Step 3: Measure the Second Register

Measuring the second register collapses the system into:

This is a superposition of two inputs that share the same output.

Step 4: Apply Hadamard Again

Applying Hadamard transforms to the first register produces a new state where only values ( j ) satisfying:

s⋅j=0 mod 2

have nonzero probability.

Step 5: Extract the Hidden String

Each measurement gives a linear equation about s.

• Repeat the process to collect multiple equations
• Solve them using classical methods (e.g., Gaussian elimination)

Eventually, you recover the hidden string s

Performance

• ✅ Quantum algorithm: O(n) queries
• ❌ Classical algorithm: Ω(sqrt{2^n}) queries

This represents an exponential speedup.

Classical Algorithms for Simon’s Problem

Upper Bound (Best Classical Strategy)

A classical randomized approach uses the birthday paradox idea:

• Make random queries
• Look for collisions (same output for different inputs)

After about:

sqrt{2^n}

queries, a collision is likely, which reveals:

s=i⊕j

Lower Bound

It can be proven that any classical algorithm needs at least:

Ω(sqrt{2^n})

queries to succeed with high probability.

This shows that the classical approach is fundamentally limited.

Why Simon’s Algorithm Matters

Simon’s algorithm was groundbreaking because:

• It provided the first proven exponential separation between quantum and classical algorithms (in query complexity)
• It inspired Peter Shor’s famous factoring algorithm
• It has influenced research in quantum cryptanalysis

Key Takeaways

• Bernstein–Vazirani: Finds a hidden string in one query
• Simon’s Algorithm: Achieves exponential speedup
• Both rely on: Superposition, Interference, and Extracting hidden structure efficiently