qbraid_algorithms.bernstein_vazirani

Bernstein-Vazirani Algorithm

Bernstein-Vazirani

This module provides a complete implementation of the Bernstein-Vazirani algorithm, a quantum algorithm that demonstrates quantum parallelism by determining a hidden bit string with a single query. The algorithm works by preparing a superposition of all possible inputs, applying an oracle that encodes the hidden bit string, then using the inverse quantum Fourier transform to extract the hidden string. This achieves exponential speedup over classical algorithms that require n queries for an n-bit string.

FORMULATION

For a hidden n-bit string \(s\) and oracle function \(f(x) = s \cdot x \pmod{2}\):

1. State Preparation: Initialize \(n\) qubits in superposition and ancilla in \(|-\rangle\):

   \(H^{\otimes n}|0\rangle^{\otimes n} \otimes |-\rangle = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |x\rangle \otimes |-\rangle\)

2. Oracle Application: Apply \(U_f\) implementing phase kickback:

   \(U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle = (-1)^{s \cdot x}|x\rangle|-\rangle\)

3. Hadamard Transform: Apply \(H^{\otimes n}\) to extract the hidden string:

   \(H^{\otimes n} \left[\frac{1}{\sqrt{2^n}} \sum_{x} (-1)^{s \cdot x}|x\rangle\right] = |s\rangle\)

Direct measurement yields the hidden string \(s\) with probability 1, demonstrating quantum parallelism through superposition and interference.

Functions

generate_program(bitstring)	Load the Bernstein-Vazirani circuit as a pyqasm module.
save_to_qasm(bitstring[, quiet, path])	Creates a Bernstein-Vazirani subroutine module with user-defined hidden bitstring.
generate_oracle(bitstring[, quiet, path])	Creates a Bernstein-Vazirani oracle encoded with user-defined hidden bitstring.