Table of Contents
- Introduction
- Problem Statement
- Classical Complexity
- Quantum Speedup Overview
- Mathematical Formulation
- Structure of the Oracle
- Quantum Circuit Layout
- Initial State Preparation
- Hadamard Transform
- Oracle Encoding of the Secret String
- Final Hadamard and Measurement
- Output Interpretation
- Example with n = 3
- Understanding Phase Kickback
- Why It Works: Interference Explained
- Comparison to Deutsch-Jozsa Algorithm
- Gate-Level Decomposition
- Circuit Diagram Overview
- Geometric Interpretation on the Bloch Sphere
- Algebraic Breakdown
- Use in Learning Algorithms
- Implementation in Qiskit
- Scalability and Limitations
- Educational Value
- 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:
- Prepare input qubits in \( |0\rangle^{\otimes n} \)
- Output qubit in \( |1\rangle \)
- Apply Hadamard to all qubits
- Apply the oracle \( U_f \)
- Apply Hadamard to input qubits again
- 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.