Table of Contents

1. Introduction
2. The Unstructured Search Problem
3. Classical Complexity
4. Quantum Speedup with Grover’s Algorithm
5. Problem Statement
6. Oracle Design in Grover’s Algorithm
7. Amplitude Amplification Intuition
8. High-Level Steps of the Algorithm
9. Initial State Preparation
10. Applying the Oracle
11. Diffusion Operator Explained
12. Geometric Interpretation
13. Number of Iterations
14. Mathematical Formulation
15. Grover Operator Definition
16. Proof of Quadratic Speedup
17. Circuit Diagram Overview
18. Example: Searching in 4 Elements
19. Visualization on the Bloch Sphere
20. Implementation in Qiskit
21. Limitations and Assumptions
22. Grover’s Algorithm for Multiple Solutions
23. Comparison with Classical Random Search
24. Generalizations and Real-World Impact
25. Conclusion

---

1. Introduction

Grover’s Algorithm is one of the most significant quantum algorithms, providing a quadratic speedup for unstructured search problems. It’s applicable to any scenario where we need to search for a marked item among many without knowing the structure of the data.

---

2. The Unstructured Search Problem

Suppose we are given a function \( f : \{0,1\}^n \rightarrow \{0,1\} \) such that:

• \( f(x) = 1 \) for a single (or few) unknown input(s) \( x_0 \)
• \( f(x) = 0 \) otherwise

The goal is to find \( x_0 \).

---

3. Classical Complexity

A classical algorithm requires \( \mathcal{O}(2^n) \) queries in the worst case to find the marked item. With randomness, expected queries are \( \mathcal{O}(2^n) \) as well.

---

4. Quantum Speedup with Grover’s Algorithm

Grover’s algorithm finds the marked input in \( \mathcal{O}(\sqrt{2^n}) \) queries — a quadratic speedup.

---

5. Problem Statement

Given black-box access to \( f(x) \), find the unique \( x_0 \) such that \( f(x_0) = 1 \), assuming such \( x_0 \) exists.

---

6. Oracle Design in Grover’s Algorithm

The oracle flips the phase of the marked state:

\[
U_f |x\rangle = (-1)^{f(x)} |x\rangle
\]

So the marked item acquires a negative amplitude, while all others remain unchanged.

---

7. Amplitude Amplification Intuition

Grover’s algorithm amplifies the amplitude of the solution state using constructive interference, and reduces the amplitude of non-solution states via destructive interference.

---

8. High-Level Steps of the Algorithm

1. Prepare uniform superposition of all \( 2^n \) inputs
2. Apply oracle \( U_f \)
3. Apply diffusion operator
4. Repeat \( \mathcal{O}(\sqrt{2^n}) \) times
5. Measure and retrieve the solution

---

9. Initial State Preparation

Start with:

\[
|0\rangle^{\otimes n} \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_x |x\rangle
\]

This is the equal superposition over all inputs.

---

10. Applying the Oracle

Oracle flips the sign of the marked state \( |x_0\rangle \):

\[
|x\rangle \rightarrow
\begin{cases}
-|x\rangle & \text{if } x = x_0 \
|x\rangle & \text{otherwise}
\end{cases}
\]

---

11. Diffusion Operator Explained

The diffusion operator reflects the state about the average amplitude:

\[
D = 2|\psi\rangle\langle \psi| – I
\]

This step increases the amplitude of the solution state.

---

12. Geometric Interpretation

Each iteration is a rotation in 2D space:

• One axis for solution \( |x_0\rangle \)
• One axis for non-solutions
• Each iteration brings the state closer to \( |x_0\rangle \)

---

13. Number of Iterations

Optimal number of iterations:

\[
k \approx \frac{\pi}{4} \sqrt{N} \quad \text{where } N = 2^n
\]

Going beyond the optimum reduces success probability.

---

14. Mathematical Formulation

Let \( |\alpha\rangle \) be the solution state, and \( |\beta\rangle \) the equal superposition of the rest. Then Grover iteration rotates the state vector closer to \( |\alpha\rangle \).

---

15. Grover Operator Definition

\[
G = D \cdot U_f
\]

Where:

• \( U_f \): oracle (phase flip)
• \( D \): diffusion operator (inversion about mean)

---

16. Proof of Quadratic Speedup

After \( \mathcal{O}(\sqrt{N}) \) applications of \( G \), amplitude of solution approaches 1, and measurement yields \( x_0 \) with high probability.

---

17. Circuit Diagram Overview

|0⟩ — H —■— D —■— ... — M
         │     │
         f     f

Here:

• H: Hadamard
• f: oracle
• D: diffusion
• M: measurement

---

18. Example: Searching in 4 Elements

Let \( f(x) = 1 \) for \( x = 10 \)

• Start in equal superposition of 4 states
• Apply Grover operator once
• Measurement yields \( x = 10 \) with high probability

---

19. Visualization on the Bloch Sphere

The state evolves on a 2D plane toward the marked state, with each Grover iteration rotating it closer via amplitude amplification.

---

20. Implementation in Qiskit

from qiskit import QuantumCircuit, Aer, execute
from qiskit.circuit.library import ZGate, MCXGate

n = 2
qc = QuantumCircuit(n, n)
qc.h(range(n))

# Oracle for x=2 (binary 10)
qc.cz(0, 1)  # simple placeholder

# Diffusion operator
qc.h(range(n))
qc.x(range(n))
qc.h(n-1)
qc.mcx(list(range(n-1)), n-1)
qc.h(n-1)
qc.x(range(n))
qc.h(range(n))

qc.measure(range(n), range(n))
backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
print(result.get_counts())

---

21. Limitations and Assumptions

• Oracle must be available
• Assumes one or few marked states
• Too many iterations will overshoot

---

22. Grover’s Algorithm for Multiple Solutions

For \( t \) solutions:

\[
k \approx \frac{\pi}{4} \sqrt{\frac{N}{t}}
\]

If \( t \) is unknown, amplitude estimation or quantum counting is used.

---

23. Comparison with Classical Random Search

• Classical: \( \mathcal{O}(N) \)
• Grover: \( \mathcal{O}(\sqrt{N}) \)

Applicable in brute-force search, cryptanalysis, NP-complete problems (in principle).

---

24. Generalizations and Real-World Impact

Grover’s framework applies to:

• Constraint satisfaction
• Cryptography (e.g., key search)
• Data mining
• Machine learning models

---

25. Conclusion

Grover’s Algorithm is a powerful demonstration of quantum advantage, offering a quadratic speedup for unstructured search problems. Its concepts of amplitude amplification and quantum iteration are foundational in quantum algorithm design and optimization.

---

Table of Contents

1. Introduction
2. Problem Overview
3. Classical vs Quantum Approach
4. Mathematical Formulation
5. The Oracle Promise
6. Simon’s Problem Statement
7. High-Level Idea of Simon’s Algorithm
8. Oracle Structure and Functionality
9. Input and Output Qubit Registers
10. Quantum Circuit Overview
11. Step-by-Step Execution
12. Initial State and Superposition
13. Oracle Application and Entanglement
14. Measurement of Output Register
15. Collapse and Hidden Information
16. Final Hadamard Transform on Input
17. Interference and Orthogonality
18. Solving the Linear Equations
19. Number of Queries Required
20. Quantum Speedup Analysis
21. Geometric and Algebraic Intuition
22. Simon’s Algorithm vs Bernstein-Vazirani
23. Qiskit Implementation Example
24. Limitations and Real-World Impact
25. Conclusion

---

1. Introduction

Simon’s Algorithm was the first to demonstrate an exponential separation between classical and quantum computation. It laid the groundwork for later breakthroughs such as Shor’s Algorithm and provided early evidence of quantum advantage.

---

2. Problem Overview

Simon’s problem asks us to find a hidden binary string \( s \in \{0,1\}^n \) that characterizes a special function’s behavior.

---

3. Classical vs Quantum Approach

• Classical deterministic approach: Requires \( \Omega(2^{n/2}) \) queries
• Quantum approach: Solves with O(n) queries

This exponential gap makes Simon’s algorithm a landmark in quantum computing.

---

4. Mathematical Formulation

Let \( f: \{0,1\}^n \rightarrow \{0,1\}^n \) be a function such that:

\[
\forall x, x’: f(x) = f(x’) \iff x = x’ \oplus s
\]

That is, the function is 2-to-1, and \( s \) is the period or hidden string we want to find.

---

5. The Oracle Promise

The oracle \( f \) is guaranteed to satisfy:

• If \( s = 0^n \): function is one-to-one
• Otherwise: \( f(x) = f(x \oplus s) \) and only these two share output

This “promise” distinguishes Simon’s algorithm from general function learning.

---

6. Simon’s Problem Statement

Find the secret string \( s \) given query access to a black-box function \( f \) satisfying the above conditions.

---

7. High-Level Idea of Simon’s Algorithm

The algorithm uses:

• Superposition to query multiple inputs at once
• Interference to encode \( s \)
• Measurement + linear algebra to extract \( s \) from sampled bitstrings orthogonal to it

---

8. Oracle Structure and Functionality

The oracle \( U_f \) acts as:

\[
U_f |x\rangle|0\rangle = |x\rangle|f(x)\rangle
\]

It entangles input and output registers based on the secret period \( s \).

---

9. Input and Output Qubit Registers

• Input: \( n \) qubits initialized to \( |0\rangle \)
• Output: \( n \) qubits initialized to \( |0\rangle \)

Total: \( 2n \) qubits used.

---

10. Quantum Circuit Overview

1. Apply Hadamard to input qubits
2. Apply oracle \( U_f \)
3. Measure output register
4. Apply Hadamard again to input
5. Measure input register
6. Repeat to gather \( n-1 \) independent equations

---

11. Step-by-Step Execution

Initial state:

\[
|\psi_0\rangle = |0\rangle^{\otimes n} \otimes |0\rangle^{\otimes n}
\]

---

12. Initial State and Superposition

After applying Hadamard to the input:

\[
|\psi_1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x} |x\rangle |0\rangle
\]

---

13. Oracle Application and Entanglement

Apply the oracle:

\[
|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_x |x\rangle|f(x)\rangle
\]

Each input becomes entangled with its output.

---

14. Measurement of Output Register

Measurement collapses the output state to some \( f(x_0) \). The input register is now in a superposition of:

\[
\frac{1}{\sqrt{2}}(|x_0\rangle + |x_0 \oplus s\rangle)
\]

---

15. Collapse and Hidden Information

The measurement restricts the input state to a 2-dimensional subspace defined by the period \( s \).

---

16. Final Hadamard Transform on Input

Apply Hadamard again to input:

\[
H^{\otimes n} \left( \frac{|x\rangle + |x \oplus s\rangle}{\sqrt{2}} \right)
\]

Using identity:

\[
H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}} \sum_y (-1)^{x \cdot y} |y\rangle
\]

Results in:

\[
\frac{1}{\sqrt{2^{n+1}}} \sum_y \left[ (-1)^{x \cdot y} + (-1)^{(x \oplus s) \cdot y} \right] |y\rangle
\]

---

17. Interference and Orthogonality

Only those \( y \) for which \( s \cdot y = 0 \mod 2 \) remain with non-zero amplitude. Each measurement yields a \( y \) such that:

\[
y \cdot s = 0 \mod 2
\]

---

18. Solving the Linear Equations

After collecting \( n – 1 \) independent such \( y \), solving the linear system over \( \mathbb{F}_2 \) yields the secret string \( s \).

---

19. Number of Queries Required

Expected number of iterations to find \( n – 1 \) linearly independent vectors is O(n).

---

20. Quantum Speedup Analysis

• Quantum: O(n)
• Classical: Requires \( \Omega(2^{n/2}) \) queries

This provides exponential speedup.

---

21. Geometric and Algebraic Intuition

Each query reveals a hyperplane orthogonal to \( s \). With enough hyperplanes, the only vector satisfying all orthogonality constraints is \( s \).

---

22. Simon’s Algorithm vs Bernstein-Vazirani

• BV: Dot product function \( f(x) = a \cdot x \)
• Simon: 2-to-1 mapping with hidden XOR mask
• BV needs 1 run, Simon needs O(n) runs but solves exponentially harder problem

---

23. Qiskit Implementation Example

from qiskit import QuantumCircuit, Aer, execute
from qiskit.visualization import plot_histogram

n = 3
qc = QuantumCircuit(2*n, n)

# Step 1: Hadamard on input
qc.h(range(n))

# Step 2: Oracle
# Sample oracle with s = 101: f(x) = f(x ⊕ 101)
qc.cx(0, n+0)
qc.cx(2, n+0)

# Step 3: Hadamard on input
qc.h(range(n))

# Step 4: Measure input
qc.measure(range(n), range(n))

backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
counts = result.get_counts()
print(counts)

---

24. Limitations and Real-World Impact

Simon’s problem is contrived and has limited direct application. However, it:

• Demonstrates exponential quantum speedup
• Inspired Shor’s factoring algorithm

---

25. Conclusion

Simon’s Algorithm is a pivotal quantum algorithm that showcases exponential advantage over classical methods. It uses clever entanglement and measurement strategies to infer hidden structure from a black-box function — a fundamental example of the quantum computing paradigm shift.

---

Table of Contents

1. Introduction
2. Problem Statement
3. Classical Complexity
4. Quantum Speedup Overview
5. Mathematical Formulation
6. Structure of the Oracle
7. Quantum Circuit Layout
8. Initial State Preparation
9. Hadamard Transform
10. Oracle Encoding of the Secret String
11. Final Hadamard and Measurement
12. Output Interpretation
13. Example with n = 3
14. Understanding Phase Kickback
15. Why It Works: Interference Explained
16. Comparison to Deutsch-Jozsa Algorithm
17. Gate-Level Decomposition
18. Circuit Diagram Overview
19. Geometric Interpretation on the Bloch Sphere
20. Algebraic Breakdown
21. Use in Learning Algorithms
22. Implementation in Qiskit
23. Scalability and Limitations
24. Educational Value
25. Conclusion

---

1. Introduction

The Bernstein-Vazirani algorithm is a foundational quantum algorithm that showcases how quantum computation can solve certain problems exponentially faster than classical approaches. It finds a hidden binary string using just one query to a quantum oracle.

---

2. Problem Statement

Given a function \( f: \{0,1\}^n \rightarrow \{0,1\} \) defined as:

\[
f(x) = a \cdot x \mod 2
\]

where \( a \in \{0,1\}^n \) is an unknown hidden bit string, the goal is to determine \( a \) using only one query to \( f \).

---

3. Classical Complexity

Classically, determining all bits of \( a \) requires \( n \) evaluations of \( f \), each with a unique basis vector \( x \).

---

4. Quantum Speedup Overview

The Bernstein-Vazirani Algorithm solves this problem with a single query using quantum parallelism and phase interference — demonstrating linear to constant query complexity reduction.

---

5. Mathematical Formulation

The oracle is defined as:

\[
U_f |x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle
\]

The function evaluates \( f(x) = a \cdot x \mod 2 \), where \( a \cdot x \) is the bitwise dot product.

---

6. Structure of the Oracle

The oracle applies a phase flip if \( a \cdot x = 1 \):

\[
U_f |x\rangle \left( \frac{|0\rangle – |1\rangle}{\sqrt{2}} \right) = (-1)^{a \cdot x} |x\rangle \left( \frac{|0\rangle – |1\rangle}{\sqrt{2}} \right)
\]

This encoding moves \( f(x) \) into the phase of the quantum state.

---

7. Quantum Circuit Layout

Steps:

1. Prepare input qubits in \( |0\rangle^{\otimes n} \)
2. Output qubit in \( |1\rangle \)
3. Apply Hadamard to all qubits
4. Apply the oracle \( U_f \)
5. Apply Hadamard to input qubits again
6. Measure input qubits

---

8. Initial State Preparation

\[
|\psi_0\rangle = |0\rangle^{\otimes n} \otimes |1\rangle
\]

After Hadamard transforms:

\[
|\psi_1\rangle = \left( \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n – 1} |x\rangle \right) \otimes \left( \frac{|0\rangle – |1\rangle}{\sqrt{2}} \right)
\]

---

9. Hadamard Transform

Applies a uniform superposition over all \( x \in \{0,1\}^n \), while output qubit becomes a phase-encoding ancilla.

---

10. Oracle Encoding of the Secret String

\[
U_f: |x\rangle \rightarrow (-1)^{a \cdot x} |x\rangle
\]

The output qubit is unchanged and can be ignored. The phase encodes information about \( a \).

---

11. Final Hadamard and Measurement

Applying Hadamard gates to each input qubit:

\[
H^{\otimes n} \sum_x (-1)^{a \cdot x} |x\rangle = |a\rangle
\]

This constructive interference causes all amplitudes to cancel except at the position corresponding to \( a \).

---

12. Output Interpretation

Measuring the input qubits yields the hidden string \( a \) with 100% probability — in just one oracle call.

---

13. Example with n = 3

Let \( a = 101 \)

• \( f(x) = x_0 \oplus x_2 \)
• Circuit yields \( |101\rangle \) with certainty
• Classically: requires 3 evaluations

---

14. Understanding Phase Kickback

The oracle’s output qubit acts as a phase reservoir, kicking back the function value as a phase factor onto the input register.

---

15. Why It Works: Interference Explained

Each \( x \) accumulates a phase \( (-1)^{a \cdot x} \), and the final Hadamard maps this interference uniquely to \( |a\rangle \).

---

16. Comparison to Deutsch-Jozsa Algorithm

• Both algorithms use a final Hadamard to extract phase-encoded data
• Deutsch-Jozsa distinguishes balanced vs constant
• Bernstein-Vazirani extracts a binary string

---

17. Gate-Level Decomposition

The oracle can be implemented using:

• CNOT gates for each bit \( a_i = 1 \)
• Controlled-Z or phase flip if implementing in phase

---

18. Circuit Diagram Overview

q0: ──H──────■────H────M──
q1: ──H───────┼────H────M──
q2: ──H──────■────H────M──
            │
anc: ──X────H──────────────

This assumes \( a = 101 \), where qubits 0 and 2 are connected to the output ancilla.

---

19. Geometric Interpretation on the Bloch Sphere

Each Hadamard prepares an equator superposition. Oracle flips phase across Bloch sphere equator. Final Hadamard projects to Z-axis basis — revealing \( a \).

---

20. Algebraic Breakdown

Final amplitude of outcome \( z \):

\[
\frac{1}{2^n} \sum_x (-1)^{a \cdot x + x \cdot z}
\]

Constructive interference at \( z = a \), destructive elsewhere.

---

21. Use in Learning Algorithms

A toy model for parity function learning. It underlies concepts in:

• Quantum machine learning
• Query complexity
• Fourier sampling

---

22. Implementation in Qiskit

from qiskit import QuantumCircuit, Aer, execute

a = '101'
n = len(a)
qc = QuantumCircuit(n+1, n)
qc.x(n)
qc.h(range(n+1))
for i, bit in enumerate(reversed(a)):
    if bit == '1':
        qc.cx(i, n)
qc.h(range(n))
qc.measure(range(n), range(n))

backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
print(result.get_counts())

---

23. Scalability and Limitations

Scales well for demonstration purposes but assumes:

• Perfect oracle
• No noise
• Non-adaptive query model

Still valuable pedagogically and for benchmark testing.

---

24. Educational Value

Helps learners grasp:

• Phase kickback
• Quantum parallelism
• Exact extraction of encoded information

---

25. Conclusion

The Bernstein-Vazirani Algorithm is a landmark quantum algorithm that elegantly demonstrates how phase-based encoding and interference allow quantum computers to outperform classical ones in structured problems. It remains one of the best examples for teaching quantum speedup and oracle-based computation.

---