{ "cells": [ { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "# Distributed Quantum Phase Estimation Algorithm\n", "\n", "Quantum phase estimation is a quantum algorithm which is used to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. If we consider a unitary matrix $U$ and a quantum state $|\\psi \\rangle$ such that $U|\\psi \\rangle =e^{2\\pi i\\theta }$, the algorithm estimates the value of $\\theta$ with high probability within additive error $\\varepsilon$.\n", "\n", "The below is the circuit diagram for quantum phase estimation with the Unitary $U$ and eigenstate $|\\psi\\rangle$.\n", "\n", "![alt text](../images/quantum_phase_estimation_diagram.png \"Quantum Phase Estimation\")\n", "\n", "Here, we will explain the execution of distributed quantum phase estimation algorithm with two computing hosts and one controller host using Interlin-q. We let the first computing host `QPU_1` possess all the qubits which are set in the state $|0\\rangle$ from the above image and the second computing host `QPU_2` would possess the single qubit which is set in the eigenstate $|\\psi\\rangle$.\n", "\n", "# Introduction of Interlin-q\n", "\n", "## Simulated Architechture\n", "\n", "The simulated architechture of Interlin-q can be seen in the image below:\n", "\n", "![alt text](../images/simulated_architechture.png \"Simulated Architechture\")\n", "\n", "The controller host gets the monolithic circuit as an input from the client, converts it to a distributed circuit and generates schedules from it for individual computing hosts and broadcasts it to them. The controller host and all the computing hosts share a global clock. When the computing hosts receive the broadcast, they extract their schedule from it and perform the operations in the schedules according to the global clock and the timestamps on the operations. The final results are sent over to the controller host from all the computing hosts for further processing.\n", "\n", "## Conversion of monolithic to distributed circuit\n", "\n", "The monolithic circuit is a circuit which is designed to be implemented by a single quantum computer. To implement this same algorithm using multiple interlinked quantum computers, this monolithic circuit needs to be converted to a distributed circuit over a given topology of the interlinked quantum computers.\n", "\n", "This distribution is performed by the controller host, by analysing the input monolithic circuit and searching for any control gates where the control and target qubits lie in separate computing host. If any such control gate is found, it is replaced by using a Cat-circuit shown in the image below. The controller host generates the distributed circuit by replacing all such control gates.\n", "\n", "![alt text](../images/cat-circuit.png \"Cat circuit\")\n", "\n", "Here the quantum state $|\\psi_1\\rangle$ lies with the first computing host and the quantum state $|\\psi_2\\rangle$ lies with the second computing host. A control gate with $|\\psi_1\\rangle$ as control qubit and $|\\psi_2\\rangle$ as the target qubit is replaced with the circuit shown, which implement a non-local control gate. It is necessary for both the computing hosts to share an EPR pair.\n", "\n", "## Distributed Scheduler and Broadcasting\n", "\n", "The controller host forms a distributed schedule of operations according to timestamps for individual computing hosts using the distributed circuit. The operations are timestamped after considering the amount of time the operation would take to be performed on the specific computing hosts. These operations are then broadcasted to all the computing hosts.\n", "\n", "## Executing the distributed algorithm\n", "\n", "The computings hosts receive the broadcasted schedules and extract their schedule from it. The controller hosts and all the computing hosts share a Clock object, which enable them to perform operations according to the schedule in synchronization. Once the operations are performed, and resulting error or successful measurements are reported back to the controller host, who further processes the output for the client.\n", "\n", "# Code implementation\n", "\n", "Now we discuss how to implement distributed quantum phase estimation algorithm using Interlin-q" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 1: Import libraries.\n", "\n", "First we import all the necessary libraries. Interlin-q is build using the python framework [QuNetSim](https://arxiv.org/abs/2003.06397) which is a python software framework that can be used to simulate quantum networks up to the network layer." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import sys\n", "import numpy as np\n", "sys.path.append(\"../\")\n", "\n", "from qunetsim.components import Network\n", "from qunetsim.objects import Logger\n", "\n", "from interlinq import (ControllerHost, Constants, Clock,\n", "Circuit, Layer, ComputingHost, Operation)\n", "\n", "Logger.DISABLED = True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 2: Create monolithic circuit of Quantum Phase Estimation\n", "\n", "### Instructions on creating a circuit\n", "\n", "The below are the functions used to create a monolithic circuit in Interlin-q framework, which will act as the client input. `Circuit` objects in Interlin-q are constructed from different `Layer` objects, where every layers contains `Operation` objects which are to be performed together.\n", "\n", "#### 1. Operations\n", "\n", "`Operation` objects are commands which instruct the computing hosts regarding the operations to be executed. The different types of `Operation` objects are `PREPARE_QUBITS`, `SINGLE`, `TWO_QUBIT`, `CLASSICAL_CTRL_GATE`, `MEASURE`, `SEND_ENT`, `REC_ENT`, `SEND_CLASSICAL` and `REC_CLASSICAL`.\n", "\n", "A sample operation to implement a `CNOT` gate across one computing host is shown below:\n", "\n", "```\n", "op = Operation(\n", " name=Constants.TWO_QUBIT,\n", " qids=[control_qubit_id, target_qubit_id],\n", " gate=Operation.CNOT,\n", " computing_host_ids=[computing_host_id])\n", "```\n", "\n", "A sample operation to implement a `CNOT` gate across two computing host is shown below:\n", "\n", "```\n", "op = Operation(\n", " name=Constants.TWO_QUBIT,\n", " qids=[control_qubit_id, target_qubit_id],\n", " gate=Operation.CNOT,\n", " computing_host_ids=[computing_host_id_1, computing_host_id_2])\n", "```\n", "\n", "#### 2. Layers\n", "\n", "Layers are composed of multiple operations which are to be performed across different computing hosts at the same time. A `Layer` object that would consist of `Operation` objects `op1`, `op2` and `op3` can be created using the command below:\n", "\n", "```\n", "layer_1 = Layer([op1, op2, op3])\n", "```\n", "\n", "#### 3. Circuit \n", "\n", "A `Circuit` object is composed of multiple layers of operations and we also provide the topology of the distributed circuit as an input. A `Circuit` object that would consist of `Layer` objects `layer1`, `layer2` and `layer3` can be created using the command below. In this command, `q_map` is the topology of the distributed circuit, which informs us regarding the computing hosts and the corresponding qubits that are involved in the circuit.\n", "\n", "```\n", "q_map = {\n", " 'QPU_1': ['q_0_0', 'q_0_1', 'q_0_2', 'q_0_3'],\n", " 'QPU_2': ['q_1_0']\n", " }\n", "\n", "circuit = Circuit(q_map, [layer1, layer2, layer3])\n", "```\n", "\n", "### Creating the circuit for Quantum Phase Estimation Algorithm\n", "\n", "![alt text](../images/quantum_phase_estimation_diagram.png \"Quantum Phase Estimation\")\n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def phase_gate(theta):\n", " return np.array([[1, 0], [0, np.exp(1j * theta)]])\n", "\n", "\n", "def inverse_quantum_fourier_transform(q_ids, computing_host_ids, layers):\n", " \"\"\"\n", " Performs inverse quantum fourier transform\n", " \"\"\"\n", "\n", " q_ids.reverse()\n", "\n", " for i in range(len(q_ids)):\n", " target_qubit_id = q_ids[i]\n", "\n", " for j in range(i):\n", " control_qubit_id = q_ids[j]\n", "\n", " op = Operation(\n", " name=Constants.TWO_QUBIT,\n", " qids=[control_qubit_id, target_qubit_id],\n", " gate=Operation.CUSTOM_CONTROLLED,\n", " gate_param=phase_gate(-np.pi * (2 ** j) / (2 ** i)),\n", " computing_host_ids=[computing_host_ids[0]])\n", " layers.append(Layer([op]))\n", "\n", " op = Operation(\n", " name=Constants.SINGLE,\n", " qids=[target_qubit_id],\n", " gate=Operation.H,\n", " computing_host_ids=[computing_host_ids[0]])\n", " layers.append(Layer([op]))\n", " return layers" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def quantum_phase_estimation_circuit(q_map, client_input_gate):\n", " \"\"\"\n", " Returns the monolithic circuit for quantum phase estimation\n", " algorithm\n", " \"\"\"\n", " layers = []\n", " computing_host_ids = list(q_map.keys())\n", "\n", " # Prepare the qubits on both computing hosts\n", " ops = []\n", " for host_id in computing_host_ids:\n", " op = Operation(\n", " name=Constants.PREPARE_QUBITS,\n", " qids=q_map[host_id],\n", " computing_host_ids=[host_id])\n", " ops.append(op)\n", "\n", " layers.append(Layer(ops))\n", "\n", " # Setup the qubits by apply Hadamard gates on qubits of QPU_1\n", " # and applying X gate to initialise qubit on QPU_2\n", " ops = []\n", " for q_id in q_map[computing_host_ids[0]]:\n", " op = Operation(\n", " name=Constants.SINGLE,\n", " qids=[q_id],\n", " gate=Operation.H,\n", " computing_host_ids=[computing_host_ids[0]])\n", " ops.append(op)\n", "\n", " op = Operation(\n", " name=Constants.SINGLE,\n", " qids=[q_map[computing_host_ids[1]][0]],\n", " gate=Operation.X,\n", " computing_host_ids=[computing_host_ids[1]])\n", " ops.append(op)\n", "\n", " layers.append(Layer(ops))\n", "\n", " # Apply controlled unitaries\n", " for i in range(len(q_map[computing_host_ids[0]])):\n", " max_iter = 2 ** i\n", " control_qubit_id = q_map[computing_host_ids[0]][i]\n", " target_qubit_id = q_map[computing_host_ids[1]][0]\n", "\n", " for _ in range(max_iter):\n", " op = Operation(\n", " name=Constants.TWO_QUBIT,\n", " qids=[control_qubit_id, target_qubit_id],\n", " gate=Operation.CUSTOM_CONTROLLED,\n", " gate_param=client_input_gate,\n", " computing_host_ids=computing_host_ids)\n", " layers.append(Layer([op]))\n", "\n", " # Inverse Fourier Transform circuit\n", " q_ids = q_map[computing_host_ids[0]].copy()\n", " layers = inverse_quantum_fourier_transform(\n", " q_ids,\n", " computing_host_ids,\n", " layers)\n", "\n", " # Measure the qubits\n", " ops = []\n", " for q_id in q_ids:\n", " op = Operation(\n", " name=Constants.MEASURE,\n", " qids=[q_id],\n", " cids=[q_id],\n", " computing_host_ids=[computing_host_ids[0]])\n", " ops.append(op)\n", " layers.append(Layer(ops))\n", "\n", " circuit = Circuit(q_map, layers)\n", " return circuit" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 3: Define Standard protocols for controller and computing hosts.\n", "\n", "Here, we defined the standard protocols for the controller and the computing hosts. The controller host gets the monolithic circuit as an input from the client, converts it to a distributed circuit and generates schedules from it for individual computing hosts and broadcasts it to them. The controller host and all the computing hosts share a global clock. When the computing hosts receive the broadcast, they extract their schedule from it and perform it according to the global clock. The final results are sent over to the controller host from all the computing hosts for further processing.\n", "\n", "### Controller host\n", "\n", "For the controller host, the below is the list of functions that are involved in the protocol:\n", "\n", "* `host.generate_and_send_schedules`: Here we provide the monolithic `Circuit` object as the input and this function carries the task of created a distributed circuit from the monolithic circuit, creating a distributed schedule for all the computing hosts involved and broadcasting the schedule to all the computing hosts connected to this controller host.\n", "* `host.receive_results`: Here, the controller host waits for the algorithm to be completed on all the computing hosts's end and then receives the final result from them, which could either be a reported error or successful measurement result.\n", "\n", "Depending on the algorithm, the results received from the computing host can be further processed to provide a final output. In the case of distributed quantum phase estimation algorithm, the final measurement results from the two computing hosts are processed to calculate the phase of the unitary gate.\n", "\n", "### Computing host\n", "\n", "For the computing host, the below is the list of functions that are involved in the protocol:\n", "\n", "* `host.receive_schedule`: Here the computing hosts receive the broadcasted schedule from the controller host, extract their individual schedule and starting perform the operations according to the schedule and the shared Clock object. \n", "* `host.send_results`: Here, the computing hosts share the final result with the controller host, which could either be a reported error or successful measurement result.\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "def controller_host_protocol(host, q_map, client_input_gate, monolithic_circuit):\n", " \"\"\"\n", " Protocol for the controller host\n", " \"\"\"\n", "\n", " host.generate_and_send_schedules(monolithic_circuit)\n", " host.receive_results()\n", "\n", " results = host.results\n", " computing_host_ids = host.computing_host_ids\n", "\n", " print('Final results: \\n')\n", "\n", " # This is the final processing perfomed in the controller host where\n", " # we take the final measurement results from the computing hosts and\n", " # calculate the estimated value of the phase from those results.\n", " decimal_value = 0\n", " for computing_host_id in computing_host_ids:\n", " i = 0\n", " bits = results[computing_host_id]['bits']\n", " for bit_id, bit in bits.items():\n", " print(\"{0}: {1}\".format(bit_id, bit))\n", " decimal_value += (2 ** i) * bit\n", " i += 1\n", " if bits:\n", " phase = decimal_value/(2 ** len(bits.keys()))\n", " print(\"\\nThe estimated value of the phase is {0}\".format(phase))\n", "\n", "\n", "def computing_host_protocol(host):\n", " \"\"\"\n", " Protocol for the computing hosts\n", " \"\"\"\n", "\n", " host.receive_schedule()\n", " host.send_results()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 4: Provide inputs\n", "\n", "Here we provide the actual inputs to run the algorithm. First we provide the phase which would be estimated by the algorithm. Next, we set number of qubits per host. The greater number of qubits would provide a closer estimate to the actual answer." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "# Try phase like 1/8 or 1/3\n", "phase_input = 1/5\n", "\n", "# Set number of qubits per host\n", "num_qubits_per_host = 4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 5: Execute the distributed algorithm and analyse the results\n", "\n", "Here, we first initiate the Network via QuNetSim as well as initiate all the Hosts required to perform the algorithm. \n", "\n", "Once `ControllerHost` object is initiated, the function `controller_host.create_distributed_network` is a template function which is used to initiate `ComputingHost` objects with the provided number of qubits, provide a topology as well as to connect the nodes internally.\n", "\n", "We provide the monolithic circuit input to the `ControllerHost` protocol and start running the protocol for the controller hosts and the computing hosts involved.\n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "starting...\n", "\n", "The Actual value of the phase is: 0.2\n", "\n", "Final results: \n", "\n", "q_0_3: 1\n", "q_0_2: 1\n", "q_0_1: 0\n", "q_0_0: 0\n", "\n", "The estimated value of the phase is 0.1875\n" ] } ], "source": [ "def main():\n", " # initialize network\n", " network = Network.get_instance()\n", " network.delay = 0\n", " network.start()\n", "\n", " clock = Clock()\n", "\n", " controller_host = ControllerHost(\n", " host_id=\"host_1\",\n", " clock=clock,\n", " )\n", "\n", " computing_hosts, q_map = controller_host.create_distributed_network(\n", " num_computing_hosts=2,\n", " num_qubits_per_host=num_qubits_per_host)\n", " controller_host.start()\n", "\n", " network.add_hosts([\n", " computing_hosts[0],\n", " computing_hosts[1],\n", " controller_host])\n", "\n", " print('starting...\\n')\n", " \n", " print('The Actual value of the phase is: {0}\\n'.format(phase_input))\n", " # For phase = 1/8\n", " #client_input_gate = np.array([[1, 0], [0, np.exp(1j * np.pi / 4)]])\n", " # For phase = 1/3\n", " client_input_gate = np.array([[1, 0], [0, np.exp(1j * 2 * np.pi * phase_input)]])\n", " monolithic_circuit = quantum_phase_estimation_circuit(q_map, client_input_gate)\n", "\n", " t1 = controller_host.run_protocol(\n", " controller_host_protocol,\n", " (q_map, client_input_gate, monolithic_circuit))\n", " t2 = computing_hosts[0].run_protocol(computing_host_protocol)\n", " t3 = computing_hosts[1].run_protocol(computing_host_protocol)\n", "\n", " t1.join()\n", " t2.join()\n", " t3.join()\n", " network.stop(True)\n", "\n", "\n", "if __name__ == '__main__':\n", " main()" ] } ], "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.6.3" } }, "nbformat": 4, "nbformat_minor": 2 }