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

Module for the Bernstein-Vazirani Algorithm. For more information, see [Loceff2015]

[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
Return type: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
Return type: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
Return type:

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\)
Returns:

A dictionary containing all possible bitstring of length equal to \(a\) and the function value \(f\)

Return type:

Dict[String, String]

References

[1]http://pages.cs.wisc.edu/~dieter/Courses/2010f-CS880/Scribes/04/lecture04.pdf