MarkingOracles/MarkingOracles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Marking Oracles\n",
    "\n",
    "The Marking Oracles quantum kata is a series of exercises designed to teach you to implement marking oracles for classical functions in Q#.\n",
    "\n",
    "* [Oracles tutorial](./../tutorials/Oracles/Oracles.ipynb) introduces you to the concept of quantum oracles and gets you started on some simple examples.\n",
    "* The [Grover's Algorithm kata](./../GroversAlgorithm/GroversAlgorithm.ipynb) and the [Deutsch-Jozsa Algorithm kata](./../DeutschJozsaAlgorithm/DeutschJozsaAlgorithm.ipynb) include tasks on implementing marking oracles for simple classical functions in Q#. Those tasks are a good place to practice this topic before continuing to the more advanced tasks in this kata.\n",
    "* [SolveSATWithGrover](./../SolveSATWithGrover/SolveSATWithGrover.ipynb) is a kata covering marking oracle implementation for solving constraint satisfaction problems.\n",
    "* [GraphColoring](./../GraphColoring/GraphColoring.ipynb) is a kata covering marking oracle implementation for solving graph coloring problems.\n",
    "* [BoundedKnapsack](./../BoundedKnapsack/BoundedKnapsack.ipynb) is a kata covering marking oracle implementation for solving bounded knapsack problems.\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blank (marked with the `// ...` comments)\n",
    "with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).\n",
    "\n",
    "The tasks are given in approximate order of increasing difficulty."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1. Palindrome checker.\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $N$ qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which checks whether the input register is a palindrome, i.e., implements the function $f(x) = 1$ if $x$ is a palindrome, and $0$ otherwise. A bit string is a palindrome if it equal its reverse, or, in other words, its first bit equals its last bit, its second bit equals its second-to-last bit, and so on. \n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 3$, the input state $|101\\rangle$ is a palindrome, and $|001\\rangle$ is not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T01_PalindromeOracle\n",
    "\n",
    "operation PalindromeOracle (input : Qubit[], target : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2. Is the bit string periodic with period $P$?\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $N$ qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "3. An integer $P < N$.\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which checks whether the input register is periodic with period $P$, i.e., for all $j$ between $0$ and $N - P - 1$, inclusive, $x_j = x_{j+P}$.\n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 3$, a bit string `[false, true, false]` is periodic with period 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T02_PeriodicGivenPeriodOracle\n",
    "\n",
    "operation PeriodicGivenPeriodOracle (input : Qubit[], target : Qubit, P : Int) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3. Is the bit string periodic?\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $N$ qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which checks whether the input register is periodic with any period, i.e., whether there exists a value $P < N$ such that for all $j$ between $0$ and $N - P - 1$, inclusive, $x_j = x_{j+P}$.\n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 3$, a bit string `[false, true, false]` is periodic with period 2, so the bit string is periodic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T03_PeriodicOracle\n",
    "\n",
    "operation PeriodicOracle (input : Qubit[], target : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4. Does the bit string contain the given substring at the given position?\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $N$ qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "3. A bit pattern of length $K$ represented as a `Bool[]` ($1 \\le K \\le N$).\n",
    "4. An integer $0 \\le P < N - K$.\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which checks whether the input register contains the given pattern starting at the given position, i.e., for all $j$ between $0$ and $K - 1$, inclusive, $pattern_j = x_{j+P}$ (`false` and `true` values represent states $|0\\rangle$ and $|1\\rangle$, respectively).\n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 3$, a bit string `[false, true, false]` contains a pattern `[true, false]` starting at index 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T04_ContainsSubstringAtPositionOracle\n",
    "\n",
    "operation ContainsSubstringAtPositionOracle (input : Qubit[], target : Qubit, pattern : Bool[], P : Int) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5. Pattern matching.\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $N$ qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "3. An array of $K$ distinct indices in the input register.\n",
    "4. A bit pattern of length $K$ represented as a `Bool[]` ($1 \\le K \\le N$).\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which checks whether the input register matches the given pattern, i.e., the bits at the given indices match the corresponding bits in the pattern (`false` and `true` values represent states $|0\\rangle$ and $|1\\rangle$, respectively).\n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 3$, a pattern `[false, true]` at indices `[0, 2]` would match two basis states: $|001\\rangle$ and $|011\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T05_PatternMatchingOracle\n",
    "\n",
    "operation PatternMatchingOracle (input : Qubit[], target : Qubit, indices : Int[], pattern : Bool[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 6. Does the bit string contain the given substring?\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $N$ qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "3. A bit pattern of length $K$ represented as a `Bool[]` ($1 \\le K \\le N$).\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which checks whether the input register contains the given pattern, i.e., whether there exists a position $P$ such that for all $j$ between $0$ and $K - 1$, inclusive, $pattern_j = x_{j+P}$.\n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 3$, a bit string `[false, true, false]` contains a pattern `[true, false]` (starting at index 1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T06_ContainsSubstringOracle\n",
    "\n",
    "operation ContainsSubstringOracle (input : Qubit[], target : Qubit, pattern : Bool[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 7. Is the bit string balanced?\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $N$ qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which checks whether the input register is a balanced bit string, i.e., whether it contains exactly $N/2$ 0s and $N/2$ 1s.\n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 4$, basis states $|0011\\rangle$ and $|0101\\rangle$ are balanced, and $|0010\\rangle$ and $|1111\\rangle$ are not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T07_BalancedOracle\n",
    "\n",
    "operation BalancedOracle (input : Qubit[], target : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 8. Majority function\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of 7 qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which calculates the majority function, i.e., $f(x) = 1$ if most of the bits in the bit string are 1s, and $0$ otherwise.\n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 3$, majority function for basis states $|001\\rangle$ and $|000\\rangle$ is 0, and for $|101\\rangle$ and $|111\\rangle$ - 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T08_MajorityOracle\n",
    "\n",
    "operation MajorityOracle (input : Qubit[], target : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 9. Is the sum of bits in the bit string divisible by 3?\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $N$ qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which checks whether the sum of bits in the bit string is divisible by 3.\n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 3$, the only basis states that should be marked are $|000\\rangle$ and |111\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T09_BitSumDivisibleBy3Oracle\n",
    "\n",
    "operation BitSumDivisibleBy3Oracle (input : Qubit[], target : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 10. Is the number divisible by 3?\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $N$ qubits in an arbitrary state $|x\\rangle$ (input register).\n",
    "2. A qubit in an arbitrary state (target qubit).\n",
    "     \n",
    "**Goal:** Implement a quantum oracle which checks whether the number represented by the bit string is divisible by 3.\n",
    "Use little endian notation to convert the bit string to an integer, i.e., the least significant bit is stored in `input[0]`.\n",
    "\n",
    "Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.\n",
    "\n",
    "**Example:** For $N = 3$, the basis states that should be marked are $|000\\rangle$, $|110\\rangle$, and |011\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T10_DivisibleBy3Oracle\n",
    "\n",
    "operation DivisibleBy3Oracle (input : Qubit[], target : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.24"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}