Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
40 lines (26 sloc) 1.41 KB

Bernstein-Vazirani Algorithm


This module emulates the Bernstein-Vazirani Algorithm.

The problem is summarized as follows. Given a function \(f\) such that

$$f:\{0,1\}^n \rightarrow \{0,1\} \\ \mathbf{x} \rightarrow \mathbf{a}\cdot\mathbf{x} + b\pmod{2} \\ (\mathbf{a}\in\{0,1\}^n, b\in\{0,1\})$$

determine \(\mathbf{a}\) and \(b\) with as few queries to \(f\) as possible.

Classically, \(n+1\) queries are required: \(n\) for \(\mathbf{a}\) and one for \(b\). However, using a quantum algorithm, only \(2\) queries are required: just one each both \(\mathbf{a}\) and \(b\).

This module is able to generate and run a program to determine \(\mathbf{a}\) and \(b\), given an oracle. It also has the ability to prescribe a way to generate an oracle out of quantum circuit components, given \(\mathbf{a}\) and \(b\).

More details about the Bernstein-Vazirani Algorithm can be found in reference [1].

Source Code Docs

Here you can find documentation for the different submodules in bernstein_vazirani.


.. automodule:: grove.bernstein_vazirani.bernstein_vazirani