# 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}$$. A program corresponding to the desired instance of the Deutsch-Jozsa Algorithm. 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 x as an n-bit string str
grove.alpha.deutsch_jozsa.deutsch_jozsa.is_unitary(mat)

Checks if a matrix is unitary.

Parameters: mat (np.array) – The matrix to check. Whether or not mat is unitary. 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}$$. A program that performs the above unitary transformation. 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]. Matrix representing specified unitary transformation. numpy array