# Bernstein-Vazirani Algorithm¶

## Overview¶

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.

### grove.bernstein_vazirani.bernstein_vazirani¶

 [Loceff2015] Loceff, M. (2015), “A Course in Quantum Computing for the Community College”, Volume 1, Chapter 18, p 484-541.
class grove.bernstein_vazirani.bernstein_vazirani.BernsteinVazirani

Bases: object

This class contains an implementation of the Bernstein-Vazirani algorithm using pyQuil. For more references see the documentation

check_solution()

Checks if the the found solution correctly reproduces the input.

Returns: True if solution correctly reproduces input bitstring map Bool
get_solution()

Returns the solution of the BV algorithm

Returns: a tuple of string corresponding to the dot-product partner vector and the bias term Tuple[String, String]
run(cxn, bitstring_map)

Runs the Bernstein-Vazirani algorithm.

Given a connection to a QVM or QPU, find the $$\mathbf{a}$$ and $$b$$ corresponding to the function represented by the oracle function that will be constructed from the bitstring map.

Parameters: cxn (Connection) – connection to the QPU or QVM String] bitstring_map (Dict[String,) – a truth table describing the boolean function, whose dot-product vector and bias is to be found BernsteinVazirani
grove.bernstein_vazirani.bernstein_vazirani.create_bv_bitmap(dot_product_vector, dot_product_bias)

This function creates a map from bitstring to function value for a boolean formula $$f$$ with a dot product vector $$a$$ and a dot product bias $$b$$

\begin{align}\begin{aligned}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\})\end{aligned}\end{align} Parameters: dot_product_vector (String) – a string of 0’s and 1’s that represents the dot-product partner in \(f dot_product_bias (String) – 0 or 1 as a string representing the bias term in $$f$$ A dictionary containing all possible bitstring of length equal to $$a$$ and the function value $$f$$ Dict[String, String]

References