Part1/Task1_QuantumOracleQsharp.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Task 1: Implement a Quantum Oracle\n",
        "\n",
        "*In this task, you should implement your solution in Q# in the first cell of the notebook. The rest of the cells contain the testing harness used to verify your solution. You can use them when working on your solution, but any modifications to them will not be evaluated.*\n",
        "\n",
        "*To submit this task, update this notebook with your solution code in the first cell and commit it in your challenge repository. You don't need to modify anything else in the notebook, or save cell execution results (unlike in the later tasks!)*"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### <span style=\"color:blue\">Task 1</span>: Implement a quantum oracle\n",
        "\n",
        "**Inputs:**\n",
        "\n",
        "  1. $N$ qubits in an arbitrary state $|x\\rangle$ (input/query register)\n",
        "    \n",
        "  2. A qubit in an arbitrary state $|y\\rangle$ (target qubit)\n",
        "\n",
        "**Goal:**\n",
        "\n",
        "Implement a marking oracle for function $f(x) = 1\\text{ if x modulo 4 is 0 or 3}$.\n",
        "\n",
        "That is, if both inputs are in a basis state, flip the state of the output qubit \n",
        "if and only if the number written in the array \"x\" modulo 4 equals 0 or 3,\n",
        "and leave the state of the array \"inputs\" unchanged.\n",
        "The effect of the oracle on superposition states should be defined by its linearity.\n",
        "\n",
        "The array \"inputs\" uses little-endian encoding, i.e., the least significant bit of the integer is stored first.\n",
        "\n",
        "Don't use measurements; the implementation should use only X and controlled X gates.\n",
        "This task will be tested using ToffoliSimulator.\n",
        "\n",
        "**Example:**\n",
        "\n",
        "The result of applying the oracle to a state \n",
        "$$\\frac1{\\sqrt3}\\big(|001\\rangle + |100\\rangle + |111\\rangle\\big) \\otimes |0\\rangle$$\n",
        "will be \n",
        "$$\\frac1{\\sqrt3}\\big(|001\\rangle \\otimes |1\\rangle + |100\\rangle \\otimes |0\\rangle + |111\\rangle \\otimes |1\\rangle\\big)$$"
      ],
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": [
        "operation Task1 (x : Qubit[], y : Qubit) : Unit is Adj + Ctl {\n",
        "    X(x[0]);\n",
        "    X(x[1]);\n",
        "    Controlled X([x[0], x[1]], y);\n",
        "    X(x[0]);\n",
        "    X(x[1]);\n",
        "    Controlled X([x[0], x[1]], y);\n",
        "}"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 5,
          "data": {
            "text/plain": "Task1",
            "text/html": "<ul><li>Task1</li></ul>",
            "application/x-qsharp-data": "[\"Task1\"]"
          },
          "metadata": {}
        }
      ],
      "execution_count": 5,
      "metadata": {}
    },
    {
      "cell_type": "markdown",
      "source": [
        "### <span style=\"color:blue\">Testing Harness</span>\n",
        "\n",
        "*To test your solution, execute the second and the third code cells. The third cell will produce the test result - a message \"Success!\" if your solution is correct, or an error message explaining the test case on which it fails.*\n",
        "\n",
        "*You need to re-run all the cells every time you update your solution - otherwise you'll be testing the old version of your solution!*"
      ],
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": [
        "open Microsoft.Quantum.Arithmetic;\n",
        "open Microsoft.Quantum.Convert;\n",
        "open Microsoft.Quantum.Diagnostics;\n",
        "open Microsoft.Quantum.Measurement;\n",
        "\n",
        "operation VerifySingleOutputFunction(\n",
        "    numInputs : Int, \n",
        "    op : (Qubit[], Qubit) => Unit is Adj+Ctl, \n",
        "    predicate : Int -> Bool\n",
        ") : Unit {\n",
        "    for assignment in 0 .. 2^numInputs - 1 {\n",
        "        use (inputs, output) = (Qubit[numInputs], Qubit());\n",
        "        within {\n",
        "            ApplyXorInPlace(assignment, LittleEndian(inputs));\n",
        "            AllowAtMostNCallsCA(0, Measure, \"You are not allowed to use measurements\");\n",
        "        } apply {\n",
        "            op(inputs, output);\n",
        "        }\n",
        "\n",
        "        // Check that the result is expected\n",
        "        let actual = ResultAsBool(MResetZ(output));\n",
        "        let expected = predicate(assignment);\n",
        "        Fact(actual == expected,\n",
        "            $\"Oracle evaluation result {actual} does not match expected {expected} for assignment {IntAsBoolArray(assignment, numInputs)}\");\n",
        "\n",
        "        // Check that the inputs were not modified\n",
        "        Fact(MeasureInteger(LittleEndian(inputs)) == 0, \n",
        "            $\"The input states were modified for assignment {assignment}\");\n",
        "    }\n",
        "}\n",
        "\n",
        "\n",
        "// ------------------------------------------------------\n",
        "function Is03ModFour (input : Int) : Bool {\n",
        "    return input % 4 == 0 or input % 4 == 3;\n",
        "}\n",
        "\n",
        "// ------------------------------------------------------\n",
        "operation TestIs03ModFour() : Unit {\n",
        "    for i in 2 .. 5 {\n",
        "        VerifySingleOutputFunction(i, Task1, Is03ModFour);\n",
        "    }\n",
        "    Message(\"Success!\");\n",
        "}\n"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 6,
          "data": {
            "text/plain": "VerifySingleOutputFunction, Is03ModFour, TestIs03ModFour",
            "text/html": "<ul><li>VerifySingleOutputFunction</li><li>Is03ModFour</li><li>TestIs03ModFour</li></ul>",
            "application/x-qsharp-data": "[\"VerifySingleOutputFunction\",\"Is03ModFour\",\"TestIs03ModFour\"]"
          },
          "metadata": {}
        }
      ],
      "execution_count": 6,
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": [
        "%toffoli TestIs03ModFour"
      ],
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": "Success!\n"
        },
        {
          "output_type": "execute_result",
          "execution_count": 7,
          "data": {
            "text/plain": "()",
            "application/x-qsharp-data": "{\"@type\":\"tuple\"}"
          },
          "metadata": {}
        }
      ],
      "execution_count": 7,
      "metadata": {
        "tags": [
          "multicell_solution"
        ]
      }
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "iqsharp",
      "language": "qsharp",
      "display_name": "Q#"
    },
    "language_info": {
      "name": "qsharp",
      "version": "0.14",
      "mimetype": "text/x-qsharp",
      "file_extension": ".qs"
    },
    "kernel_info": {
      "name": "iqsharp"
    },
    "nteract": {
      "version": "nteract-front-end@1.0.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}