The Deutsch-Jozsa Algorithm

Here is the link to the original paper: Deutsch-Jozsa algorithm. This algorithm is an earlier demonstration of the computational advantage of quantum algorithm over classical one. It addresses the problem of identifying the nature of a hidden Boolean function, which is provided as an oracle. The function is guaranteed to be either:

• Balanced, meaning it outputs 0 for exactly half of its possible inputs and 1 for the other half.

• Constant, meaning it outputs the same value (either 0 or 1) for all inputs.

Classically, determining whether the function is balanced or constant requires evaluating the oracle multiple times. In the worst-case scenario, one would need to query at least half of the inputs to distinguish a constant function. However, the Deutsch-Jozsa algorithm demonstrates quantum superiority by solving this problem with a single query to the oracle, regardless of the input size.

This notebook implements the Deutsch-Jozsa algorithm as described in Cleve et al. 1997. The input for the oracle function \(f\) is a \(n\)-bit string. It means that for \(x\ in \{0,1\}^n\), the value of \(f(x)\) is either constant, i.e., the same for all \(x\), or balanced, i.e., exactly half of the \(n\)-bit string whose \(f(x) = 0\).

The Theory

Here are the steps to implement the algorithm: 1. Start with initializing all input qubits and single auxiliary qubits to zero. The first \(n-1\) input qubits are used for querying the oracle, and the last auxiliary qubit is used for storing the answer of the oracle

\[|0\ldots 0\rangle |0\rangle\]

2. Create the superposition of all input qubits by applying the Hadamard gate to each qubit.

\[H^{\otimes^n} |0\ldots 0\rangle |0\rangle = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}|i\rangle |0\rangle\]

3. Apply the Pauli-X gate and apply the Hadamard gate to the auxiliary qubit. This is to store the answer of the oracle in the phase.

\[\frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}|i\rangle |0\rangle \rightarrow \frac{1}{\sqrt{2^{n+1}}}\sum_{i=0}^{2^n-1}|i\rangle ( |0\rangle - |1\rangle )\]

4. Query the oracle.

\[\frac{1}{\sqrt{2^{n+1}}}\sum_{i=0}^{2^n-1}|i\rangle ( |0\rangle - |1\rangle ) \rightarrow \frac{1}{\sqrt{2^{n+1}}}\sum_{i=0}^{2^n-1}(-1)^{f(i)}|i\rangle ( |0\rangle - |1\rangle )\]

5. Apply the Hadamard gate to all input gates. 6. Measure input gates. If measured values are non-zero, then the function is balanced. If not, then it is constant.

The Algorithm Implementation

Here is the CUDA-Q code following the steps outlined in the above theory section.

# Import the CUDA-Q package and set the target to run on NVIDIA GPUs.

import cudaq
import random
from typing import List

cudaq.set_target("nvidia")

# Number of qubits for the Deutsch-Jozsa algorithm, the last qubit is an auxiliary qubit
qubit_count = 3

# Set the function to be "constant" or "balanced"
function_type = 'constant'

# Initialize fx depending on whether the function is constant or balanced
if function_type == 'constant':
    # For a constant function, fx is either all 0's or all 1's
    oracleType = 0  # 0 for constant
    fx_value = random.choice([0, 1])  # Randomly pick 0 or 1
    oracleValue = fx_value  # In constant case, fx_value is passed, for balanced it's not used
    fx = [fx_value] * (qubit_count - 1)
else:
    # For a balanced function, half of fx will be 0's and half will be 1's
    oracleType = 1
    fx = [0] * ((qubit_count - 1) // 2) + [1] * ((qubit_count - 1) - (qubit_count - 1) // 2)
    random.shuffle(fx)  # Shuffle to randomize the positions of 0's and 1's

# If needed initialize fx, oracleType, and oracleValue manually
#oracleType = 0
#oracleValue = 0
#fx = [0,0]

print(f"Generated fx for function type = {function_type}: {fx}")
print ("oracleType = ", oracleType)
print ("oracleValue = ", oracleValue)

Generated fx for function type = constant: [1, 1]
oracleType =  0
oracleValue =  1

# Define kernel
@cudaq.kernel
def kernel(fx: List[int], qubit_count: int, oracleType: int, oracleValue: int):
    # Allocate two input qubits
    input_qubits = cudaq.qvector(qubit_count-1)
    # Allocate an auxiliary qubit (initially |0⟩)
    auxiliary_qubit = cudaq.qubit()

    # Prepare the auxiliary qubit
    x(auxiliary_qubit)
    h(auxiliary_qubit)

    # Place the rest of the register in a superposition state
    h(input_qubits)

    # Logic for oracleType == 0 (constant oracle)
    if oracleType == 0:
        if oracleValue == 1:
            # Apply X gate to the auxiliary qubit
            x(auxiliary_qubit)
        elif oracleValue == 0:
            # Apply identity gate (do nothing)
            pass

    # Logic for oracleType == 1 (balanced oracle)
    elif oracleType == 1:
        for i in range(len(fx)):
            if fx[i] == 1:
                x.ctrl(input_qubits[i], auxiliary_qubit)

    # Apply Hadamard to the input qubit again after querying the oracle
    h(input_qubits)

    # Measure the input qubit to yield if the function is constant or balanced.
    mz(input_qubits)

print(cudaq.draw(kernel, fx, qubit_count, oracleType, oracleValue))

result = cudaq.sample(kernel, fx, qubit_count, oracleType, oracleValue, shots_count=1)

# Debugging: Print the raw result dictionary
print(f"Input qubits measurement outcome and frequency = {result}")

# Define the expected constant results for '00' and '11' for the number of input qubits
expected_constant_results = ['0' * (qubit_count - 1), '1' * (qubit_count - 1)]

# Check if either '00' or '11' (or their equivalent for more qubits) appears in the result
is_constant = any(result_key in result for result_key in expected_constant_results)

if is_constant:
    print("The oracle function is constant.")
else:
    print("The oracle function is balanced.")

     ╭───╮╭───╮
q0 : ┤ h ├┤ h ├─────
     ├───┤├───┤
q1 : ┤ h ├┤ h ├─────
     ├───┤├───┤╭───╮
q2 : ┤ x ├┤ h ├┤ x ├
     ╰───╯╰───╯╰───╯

Input qubits measurement outcome and frequency = { 00:1 }

The oracle function is constant.

print(cudaq.__version__)