$\require{cancel} \newcommand{\Ket}[1]{\left|{#1}\right\rangle} \newcommand{\Bra}[1]{\left\langle{#1}\right|} \newcommand{\Braket}[1]{\left\langle{#1}\right\rangle} \newcommand{\Rsr}[1]{\frac{1}{\sqrt{#1}}} \newcommand{\RSR}[1]{1/\sqrt{#1}} \newcommand{\Verti}{\rvert} \newcommand{\HAT}[1]{\hat{\,#1~}} \DeclareMathOperator{\Tr}{Tr}$

Bernstein-Vazirani Algorithm

^{First created in February 2020}

Ref:

• https://qiskit.org/textbook/ch-algorithms/bernstein-vazirani.html

The Bernstein-Vazirani problem is to find a secret pattern $s$ presented as a function $f_s(\bullet)$ such that $f_s(x)=s\cdot x\mod 2$.

A classical algorithm will need to try all $n$ bits from $2^0,2^1,2^2,\ldots,$ to $2^{n-1},$ feeding into $f_s(\bullet)$ and see if the result is 0 or 1.

With quantum algorithm, function $f_s(\bullet)$ is encoded as the oracle operator $U_s$, which behaves like $U_s\Ket q=(-1)^{s\cdot q}\Ket q$.

---

Here is an interesting relationship: $\boxed{\displaystyle H^{\otimes n}\Ket q =\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}(-1)^{q\cdot x}\Ket x .}$

Proof: $\displaystyle \mathrm{LHS} =H^{\otimes n}\Ket{q_0~q_1~\ldots~q_{n-1}} =\frac{1}{\sqrt{2^n}}\prod_{k=0}^{n-1}\big(\Ket 0+(-1)^{q_k}\Ket 1\big) =\mathrm{RHS} .$

Note: After expanding the bracket, one will have each of the $2^n$ terms with a minus sign when there are odd number of $q_k$ and $x_k$ pairs that are both 1, which is effectively $(-1)^{q\cdot x}$, matching the pattern on the $\mathrm{RHS}$.

---

Based on the above relation, we can use a simple quantum algorithm to find $s$ in one operation:

$H^{\otimes n}~U_s~H^{\otimes n}\Ket 0=\Ket s.$

Proof: $\displaystyle \mathrm{LHS} =H^{\otimes n}~U_s\left(\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}\Ket x\right) =H^{\otimes n}\left(\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}U_s\Ket x\right) =H^{\otimes n}\left(\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}(-1)^{s\cdot x}\Ket x\right) =H^{\otimes n}\left(H^{\otimes n}\Ket s\right) =\Ket s =\mathrm{RHS} .$

Code Section

# Initialisation

import sys
sys.path.append('../')
from qtol import *

# Iteration

# Number of qubits
qbNum = 1

# Define the Quantum and Classical Registers
q = QuantumRegister(qbNum)
c = ClassicalRegister(qbNum)

qc = QuantumCircuit(q, c)

# Preparation
qc.iden(q)

# Circuit building
# ...

# Finalisation
# ...

show_me(qc, q, c, show_latex=True, show_bloch_vector=True, show_histogram=True)

circuit_drawer(qc)

Raw vector:   [1.+0.j 0.+0.j]
Normalised:   [1.+0.j 0.+0.j]
Text form:    |0>

$$\text{LaTeX form:}\quad\Ket{0}$$

Bloch Vector: [ 0.002  -0.0508  1.    ]

$$\cos(0.0\pi)\Ket0 + e^{i~0.0\pi}\sin(0.0\pi)\Ket1$$