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 classical algorithm, the Deutsch-Jozsa Algorithm can solve this problem with a single iteration, regardless of the input size.

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. Based off description in “Quantum Computation and Quantum Information” by Neilson and Chuang.

grove.alpha.deutsch_jozsa.deutsch_jozsa.deutsch_jozsa(oracle, qubits, ancilla)

Implementation of the Deutsch-Jozsa Algorithm.

Can determine whether a function f mapping {0,1}^n to {0,1} is constant or balanced, provided that it is one of them.

Parameters:
  • oracle (Program) – Program representing unitary application of function.
  • qubits (list) – List of qubits that enter as state \(\ket{x}\).
  • ancilla (Qubit) – Qubit to serve as input \(\ket{y}\).
Returns:

A program corresponding to the desired instance of the Deutsch-Jozsa Algorithm.

Return type:

Program

grove.alpha.deutsch_jozsa.deutsch_jozsa.integer_to_bitstring(x, n)

Converts a positive integer into a bitstring.

Parameters:
  • x (int) – The integer to convert
  • n (int) – The length of the desired bitstring
Returns:

x as an n-bit string

Return type:

str

grove.alpha.deutsch_jozsa.deutsch_jozsa.is_unitary(mat)

Checks if a matrix is unitary.

Parameters:mat (np.array) – The matrix to check.
Returns:Whether or not mat is unitary.
Return type:bool
grove.alpha.deutsch_jozsa.deutsch_jozsa.oracle_function(unitary_funct, qubits, ancilla)

Defines an oracle that performs the following unitary transformation:

\[\ket{x}\ket{y} \to \ket{x}\ket{f(x)\; \text{xor}\; y}\]

Allocates one scratch bit.

Parameters:
  • unitary_funct (np.array) – Matrix representation of the function f, i.e. the unitary transformation that must be applied to a state \(\ket{x}\) to put f(x) in qubit 0, where f(x) returns either 0 or 1 for any n-bit string x
  • qubits (np.array) – List of qubits that enter as input \(\ket{x}\).
  • ancilla (Qubit) – Qubit to serve as input \(ket\{y}\).
Returns:

A program that performs the above unitary transformation.

Return type:

Program

grove.alpha.deutsch_jozsa.deutsch_jozsa.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 (list) – List of the mappings of f(x) on all length n bitstrings. For example, the following mapping: { 00 -> 0, 01 -> 1, 10 -> 1, 11 -> 0 } Would be represented as [0, 1, 1, 0].
Returns:Matrix representing specified unitary transformation.
Return type:numpy array