{ "cells": [ { "cell_type": "markdown", "id": "7aa9cc8f-4e42-401f-a1fd-665e5cda19c7", "metadata": {}, "source": [ "# The Deutsch-Jozsa Algorithm\n", "\n", "Here is the link to the original paper: [Deutsch-Jozsa algorithm](http://rspa.royalsocietypublishing.org/content/439/1907/553). 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:\n", "\n", "- **Balanced**, meaning it outputs 0 for exactly half of its possible inputs and 1 for the other half.\n", "- **Constant**, meaning it outputs the same value (either 0 or 1) for all inputs.\n", "\n", "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.\n", "\n", "This notebook implements the Deutsch-Jozsa algorithm as described in [Cleve et al. 1997](https://arxiv.org/pdf/quant-ph/9708016.pdf). 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$." ] }, { "cell_type": "markdown", "id": "6edbe9a5-2a81-42e4-ac0c-50a0ef4a0dda", "metadata": {}, "source": [ "## The Theory\n", "\n", "Here are the steps to implement the algorithm:\n", "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\n", "$$\n", "|0\\ldots 0\\rangle |0\\rangle\n", "$$\n", "2. Create the superposition of all input qubits by applying the Hadamard gate to each qubit.\n", "$$\n", "H^{\\otimes^n} |0\\ldots 0\\rangle |0\\rangle = \\frac{1}{\\sqrt{2^n}}\\sum_{i=0}^{2^n-1}|i\\rangle |0\\rangle \n", "$$\n", "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.\n", "$$\n", "\\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 )\n", "$$\n", "4. Query the oracle.\n", "$$\n", "\\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 ) \n", "$$\n", "5. Apply the Hadamard gate to all input gates.\n", "6. Measure input gates. If measured values are non-zero, then the function is balanced. If not, then it is constant." ] }, { "cell_type": "markdown", "id": "5449f9a7-7b1a-4212-8b26-3edaae1fcabd", "metadata": {}, "source": [ "## The Algorithm Implementation\n", "\n", "Here is the CUDA-Q code following the steps outlined in the above theory section." ] }, { "cell_type": "code", "execution_count": 31, "id": "08e04d22-535c-4368-a495-dfe7ed5ff567", "metadata": {}, "outputs": [], "source": [ "# Import the CUDA-Q package and set the target to run on NVIDIA GPUs.\n", "\n", "import cudaq\n", "import random\n", "from typing import List\n", "\n", "cudaq.set_target(\"nvidia\")\n", "\n", "# Number of qubits for the Deutsch-Jozsa algorithm, the last qubit is an auxiliary qubit\n", "qubit_count = 3" ] }, { "cell_type": "code", "execution_count": 32, "id": "4d16e25e-d3df-4d07-9e75-a6a046680caa", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Generated fx for function type = constant: [1, 1]\n", "oracleType = 0\n", "oracleValue = 1\n" ] } ], "source": [ "# Set the function to be \"constant\" or \"balanced\"\n", "function_type = 'constant'\n", "\n", "# Initialize fx depending on whether the function is constant or balanced\n", "if function_type == 'constant':\n", " # For a constant function, fx is either all 0's or all 1's\n", " oracleType = 0 # 0 for constant\n", " fx_value = random.choice([0, 1]) # Randomly pick 0 or 1\n", " oracleValue = fx_value # In constant case, fx_value is passed, for balanced it's not used\n", " fx = [fx_value] * (qubit_count - 1)\n", "else:\n", " # For a balanced function, half of fx will be 0's and half will be 1's\n", " oracleType = 1\n", " fx = [0] * ((qubit_count - 1) // 2) + [1] * ((qubit_count - 1) - (qubit_count - 1) // 2)\n", " random.shuffle(fx) # Shuffle to randomize the positions of 0's and 1's\n", "\n", "# If needed initialize fx, oracleType, and oracleValue manually\n", "#oracleType = 0\n", "#oracleValue = 0\n", "#fx = [0,0]\n", "\n", "print(f\"Generated fx for function type = {function_type}: {fx}\")\n", "print (\"oracleType = \", oracleType)\n", "print (\"oracleValue = \", oracleValue)" ] }, { "cell_type": "code", "execution_count": 33, "id": "caa90b54-16d3-419d-910f-7a36e4e14829", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " ╭───╮╭───╮ \n", "q0 : ┤ h ├┤ h ├─────\n", " ├───┤├───┤ \n", "q1 : ┤ h ├┤ h ├─────\n", " ├───┤├───┤╭───╮\n", "q2 : ┤ x ├┤ h ├┤ x ├\n", " ╰───╯╰───╯╰───╯\n", "\n", "Input qubits measurement outcome and frequency = { 00:1 }\n", "\n", "The oracle function is constant.\n" ] } ], "source": [ "# Define kernel\n", "@cudaq.kernel\n", "def kernel(fx: List[int], qubit_count: int, oracleType: int, oracleValue: int):\n", " # Allocate two input qubits\n", " input_qubits = cudaq.qvector(qubit_count-1)\n", " # Allocate an auxiliary qubit (initially |0⟩)\n", " auxiliary_qubit = cudaq.qubit()\n", "\n", " # Prepare the auxiliary qubit\n", " x(auxiliary_qubit)\n", " h(auxiliary_qubit)\n", "\n", " # Place the rest of the register in a superposition state\n", " h(input_qubits)\n", "\n", " # Logic for oracleType == 0 (constant oracle)\n", " if oracleType == 0:\n", " if oracleValue == 1:\n", " # Apply X gate to the auxiliary qubit\n", " x(auxiliary_qubit)\n", " elif oracleValue == 0:\n", " # Apply identity gate (do nothing)\n", " pass\n", "\n", " # Logic for oracleType == 1 (balanced oracle)\n", " elif oracleType == 1:\n", " for i in range(len(fx)):\n", " if fx[i] == 1:\n", " x.ctrl(input_qubits[i], auxiliary_qubit)\n", " \n", " # Apply Hadamard to the input qubit again after querying the oracle\n", " h(input_qubits)\n", "\n", " # Measure the input qubit to yield if the function is constant or balanced.\n", " mz(input_qubits)\n", "\n", "print(cudaq.draw(kernel, fx, qubit_count, oracleType, oracleValue))\n", "\n", "result = cudaq.sample(kernel, fx, qubit_count, oracleType, oracleValue, shots_count=1)\n", "\n", "# Debugging: Print the raw result dictionary\n", "print(f\"Input qubits measurement outcome and frequency = {result}\")\n", "\n", "# Define the expected constant results for '00' and '11' for the number of input qubits\n", "expected_constant_results = ['0' * (qubit_count - 1), '1' * (qubit_count - 1)]\n", "\n", "# Check if either '00' or '11' (or their equivalent for more qubits) appears in the result\n", "is_constant = any(result_key in result for result_key in expected_constant_results)\n", "\n", "if is_constant:\n", " print(\"The oracle function is constant.\")\n", "else:\n", " print(\"The oracle function is balanced.\")\n" ] }, { "cell_type": "code", "execution_count": null, "id": "278c6b13-e3a0-4f61-a25b-eed75494b376", "metadata": {}, "outputs": [], "source": [ "print(cudaq.__version__)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.12" } }, "nbformat": 4, "nbformat_minor": 5 }