Deutsch-Jozsa Algorithm

Overview

The Deutsch-Jozsa algorithm can determine whether a function mapping all bitstrings to a single bit is constant or balanced, provided that it is one of the two. A constant function always maps to either 1 or 0, and a balanced function maps to 1 for half of the inputs and maps to 0 for the other half. Unlike any deterministic classical algorithm, the Deutsch-Jozsa Algorithm can solve this problem with a single iteration, regardless of the input size. It was one of the first known quantum algorithms that showed an exponential speedup, albeit against a deterministic (non-probabilistic) classical compuetwr, and with access to a blackbox function that can evaluate inputs to the chosen function.

Algorithm and Details

This algorithm takes as input \(n\) qubits in state \(\ket{x}\), an ancillary qubit in state \(\ket{q}\), and additionally a quantum circuit \(U_w\) that performs the following:

\[U_w: \ket{x}\ket{q}\to\ket{x}\ket{f(x)\oplus q}\]

In the case of the Deutsch-Jozsa algorithm, the function \(f\) is some function mapping from bitstrings to bits:

\[f: \{0,1\}^n\to\{0, 1\}\]

and is assumed to either be textit{constant} or textit{balanced}. Constant means that on all inputs \(f\) takes on the same value, and balanced means that on half of the inputs \(f\) takes on one value, and on the other half \(f\) takes on a different value. (Here the value is restricted to \(\{0, 1\}\))

We can then describe the algorithm as follows:

Input:
\(n + 1\) qubits
Algorithm:
  1. Prepare the textit{ancilla} (\(\ket{q}\) above) in the \(\ket{1}\) state by performing an \(X\) gate.
  2. Perform the \(n + 1\)-fold Hadamard gate \(H^{\otimes n + 1}\) on the \(n + 1\) qubits.
  3. Apply the circuit \(U_w\).
  4. Apply the \(n\)-fold Hadamard gate \(H^{\otimes n}\) on the data qubits, \(\ket{x}\).
  5. Measure \(\ket{x}\). If the result is all zeroes, then the function is constant. Otherwise, it is balanced.

Implementation Notes

The oracle in the Deutsch-Jozsa module is not implemented in such a way that calling Deutsch_Jozsa.is_constant() will yield an exponential speedup over classical implementations. To construct the quantum algorithm that is executing on the QPU we use a Quil defgate, which specifies the circuit \(U_w\) as its action on the data qubits \(\ket{x}\). This matrix is exponentially large, and thus even generating the program will take exponential time.

Source Code Docs

Here you can find documentation for the different submodules in deutsch-jozsa.

grove.deutsch_jozsa.deutsch_jozsa.py

Module for the Deutsch-Jozsa Algorithm.

class grove.deutsch_jozsa.deutsch_jozsa.DeutschJosza

Bases: object

is_constant(cxn, bitstring_map)
Computes whether bitstring_map represents a constant function, given that it is constant
or balanced. Constant means all inputs map to the same value, balanced means half of the inputs maps to one value, and half to the other.
Parameters:
  • cxn (QVMConnection) – The connection object to the Rigetti cloud to run pyQuil programs.
  • bitstring_map – A dictionary whose keys are bitstrings, and whose values are bits represented as strings.
Returns:

True if the bitstring_map represented a constant function, false otherwise.

Return type:

bool

static unitary_function(mappings)

Creates a unitary transformation that maps each state to the values specified in mappings.

Some (but not all) of these transformations involve a scratch qubit, so room for one is always provided. That is, if given the mapping of n qubits, the calculated transformation will be on n + 1 qubits, where the 0th is the scratch bit and the return value of the function is left in the 1st.

Parameters:mappings (Dict[String, Int]) –

Dictionary of the mappings of f(x) on all length n bitstrings, e.g.

>>> {'00': '0', '01': '1', '10': '1', '11': '0'}
Returns:ndarray representing specified unitary transformation.
Return type:np.ndarray