Fetching contributors…
Cannot retrieve contributors at this time
73 lines (55 sloc) 2.9 KB

Deutsch-Jozsa Algorithm


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:

n + 1 qubits
  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 :term:`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.

.. automodule:: grove.deutsch_jozsa.deutsch_jozsa