deutsch_jozsa

deutsch_jozsa#

Functionality#

The Deutsch-Jozsa algorithm, first introduced in Reference [8], was the first example of a quantum algorithm that performs better than the best classical algorithm. It showed that there can be advantages to using a quantum computer as a computational tool for a specific problem.

The Deutsch-Jozsa problem is intriduced as follows: suppose we have a function \(f: \{0,1\}^n \rightarrow \{0,1\}\) that takes as input an \(n\)-bit binary string and outputs either 0 or 1. The function is guaranteed to be either constant (outputting the same value for all inputs) or balanced (outputting 0 for half of the inputs and 1 for the other half). Our task is to determine whether the given function is balanced or constant.

dj.py#

Callee: DeutschJozsa

Using a quantum computer, we can solve this problem with 100% confidence after only one call to the function \(f(x)\), provided we have the function \(f\) implemented as a quantum oracle, which maps the state \(\ket{y}\ket{x}\) to \(\ket{y \oplus f(x)}\ket{x}\), where \(\oplus\) is addition modulo 2. Below is the generic circuit for the Deutsch-Jozsa algorithm.

Deutsch-Jozsa algorithm circuit

Deutsch-Jozsa algorithm circuit (Source: Qiskit/textbook)

Now, let’s go through the steps of the algorithm:

  1. Prepare two quantum registers. The first is an \(n\)-qubit register initialized to \(\ket{0}^{\otimes n}\), and the second is a one-qubit register initialized to \(\ket{1}\)：

    \[ \ket{\psi_0} = \ket{1} \ket{0}^{\otimes n}. \]

  2. Apply a Hadamard gate to each qubit:

    \[ \ket{\psi_1} = \frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^{n}-1} (\ket{0}_1 - \ket{1}_1) \ket{x}_n. \]

  3. Apply the quantum oracle \(\ket{y}_1\ket{x}_n\) to \(\ket{y \oplus f(x)}_1 \ket{x}_n\):

    \[\begin{split} \begin{aligned} \ket{\psi_2} & = \frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^{n}-1} (\ket{0 \oplus f(x)}_1 - \ket{1 \oplus f(x)}_1) \ket{x}_n \\ & = \frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^{n}-1} (-1)^{f(x)} (\ket{0}_1 - \ket{1}_1) \ket{x}_n. \end{aligned} \end{split}\]

    since for each \(x\), \(f(x)\) is either \(0\) or \(1\).

  4. At this point the second single qubit register may be ignored. Apply a Hadamard gate to each qubit in the first register:

    \[\begin{split} \begin{aligned} \ket{\psi_3} & = \frac{1}{\sqrt{2^{n}}} \sum_{x=0}^{2^{n}-1} (-1)^{f(x)} \left[ \sum_{y=0}^{2^{n}-1} (-1)^{x \cdot y} \ket{y}_n \right] \\ & = \frac{1}{\sqrt{2^{n}}} \sum_{y=0}^{2^{n}-1} \left[ \sum_{x=0}^{2^{n}-1} (-1)^{f(x) + x \cdot y} \right] \ket{y}_n. \end{aligned} \end{split}\]

    where \(x \cdot y= x_0y_0 \oplus x_1y_1 \oplus \cdots \oplus x_{n-1}y_{n-1}\) is the sum of the bitwise product.

  5. Measure the first register. From Step (4), the amplitude of the basis state \(\ket{y}_n\) is \(\frac{1}{2^n} \sum_{x=0}^{2^n-1} (-1)^{f(x)+x\cdot y}.\) In particular, when \(y = 0^n\), since \(x \cdot 0^n = 0\) for all \(x\), the amplitude reduces to \(\frac{1}{2^n} \sum_{x=0}^{2^n-1} (-1)^{f(x)}\).

    Therefore, the probability of measuring \(\ket{0}^{\otimes n}\) is

    \[ P(0^n) = \left| \frac{1}{2^n} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \right|^2. \]

    • If \(f(x)\) is constant, all terms in the sum have the same sign, yielding \(\sum_x (-1)^{f(x)} = \pm 2^n\), and hence \(P(0^n)=1\).

    • If \(f(x)\) is balanced, exactly half of the terms are \(+1\) and half are \(-1\), so the sum vanishes and \(P(0^n)=0\).

    Thus, a single measurement suffices to determine whether \(f\) is constant or balanced.

Note:

In the implementation of the class DeutschJozsa, the preparation of the ancilia qubit in the \(\ket{1}\) state is included, while the measurement operations are not included. When designing test cases, there is no need to manually initialize the ancilla qubit by applying X gate.

Test expectations:

The result is determined by measuring the first \(n\) qubits. A non-zero bitstring is expected if \(f(x)\) is balanced, otherwise constant.

Doc references: [9]

API#

qolumbina.programs.deutsch_jozsa.dj#

class DeutschJozsa(case, input_qubits, name=None)[source]#

Bases: QuantumCircuit

Deutsch-Jozsa algorithm circuit.

Acts on \(n\) input qubits and \(1\) auxiliary qubit

Parameters:

  • case (Literal['balanced', 'constant']) – Type of oracle, either “balanced” or “constant”.

  • input_qubits (int) – Number of input qubits \(n\).

  • name (str | None) – Optional name for the circuit.

Raises:

ValueError – If case is not "balanced" or "constant".

Note

The oracle is randomly generated according to the specified case.

dj_oracle()[source]#

Construct the oracle gate based on the specified case (balanced or constant).

Return type:

Gate

Contents