BoundedKnapsack/BoundedKnapsack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bounded Knapsack\n",
    "\n",
    "The Bounded Knapsack quantum kata is a series of exercises designed to teach you to use Grover search to solve the knapsack problem. \n",
    "\n",
    "* Learn more about the knapsack problem in the [Wikipedia article](https://en.wikipedia.org/wiki/Knapsack_problem).\n",
    "* [SolveSATWithGrover](./../SolveSATWithGrover/SolveSATWithGrover.ipynb) and [GraphColoring](./../GraphColoring/GraphColoring.ipynb) are the other katas covering oracle implementation for solving constraint satisfaction problems. This kata is more challenging, so you might want to try these two first.\n",
    "\n",
    "The kata covers the following topics:\n",
    " - writing operations to perform arithmetic tasks.\n",
    " - writing oracles to implement constraints based on:\n",
    "  - the 0-1 knapsack problem, a simple version of the knapsack problem;\n",
    "  - the bounded knapsack problem.\n",
    " - using the oracle with Grover's algorithm to solve the knapsack decision problem.\n",
    " - using Grover's algorithm repeatedly to solve the knapsack optimization problem.\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",
    "Within each section, tasks are given in approximate order of increasing difficulty."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. 0-1 Knapsack Problem\n",
    "\n",
    "You are given $n$ items, indexed $0$ to $n-1$. The item with index $i$ has a weight of $w_i$ and yields a profit of $p_i$. In the original 0-1 knapsack decision problem, we wish to determine whether we can put a subset of items in a knapsack to get a total profit of at least $P$, while not exceeding a maximum weight $W$.\n",
    "\n",
    "However, we will slightly modify the problem: the total profit must be *strictly greater than* $P$, rather than at least $P$.\n",
    "\n",
    "In the following tasks you will implement an oracle that evaluates whether a particular register of $n$ qubits, representing an item combination, satisfies the described conditions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. Read combination from a register\n",
    "\n",
    "**Input:** An array of $n$ qubits, which are guaranteed to be in one of the $2^n$ basis states.  \n",
    "\n",
    "**Output:** The item combination that this state represents, expressed as a boolean array of length $n$. The $i$-th element of the array should be `true` (indicating that $i$-th item is selected) if and only if the $i$-th qubit of the register is in the $|1\\rangle$ state. The operation should not change the state of the qubits.\n",
    "     \n",
    "**Example:** For $n = 3$ and the qubits state $|101\\rangle$, return `[true, false, true]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_MeasureCombination01\n",
    "\n",
    "operation MeasureCombination01 (selectedItems : Qubit[]) : Bool[] {\n",
    "    // ...\n",
    "    return [];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Calculate the number of (qu)bits necessary to hold the maximum total value\n",
    "\n",
    "**Input:** An array of $n$ positive integers, describing the value (the weight or the profit) of each item.\n",
    "\n",
    "**Output:** The minimum number of (qu)bits needed to store the maximum total value of the items.\n",
    "\n",
    "**Example:** For $n = 4$ and `itemValues = [1, 2, 3, 4]`, the maximum total value is $10$, which requires at least $4$ qubits to store it, so $4$ is returned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_NumBitsTotalValue01\n",
    "\n",
    "function NumBitsTotalValue01 (itemValues : Int[]) : Int {\n",
    "    // ...\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. Calculate the total value of selected items\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $n$ integers, describing the values (the weights or the profits) of the items.\n",
    "2. An array of $n$ qubits, describing whether each item is put into the knapsack.\n",
    "3. An array of qubits `total` in the $|0...0\\rangle$ state to store the total value of the selected items. \n",
    "It is guaranteed that there are enough qubits to store the total value.\n",
    "\n",
    "**Goal:** Transform the `total` array to represent, in little-endian format, the sum of the values of the items that are put in the knapsack. The input qubits can be in a superposition state. Leave the qubits in selectedItems in the same state they started in.\n",
    "\n",
    "**Example:** For $n = 4$ and `itemValues = [1, 2, 3, 4]`, the input state $|1001\\rangle|0000\\rangle$ should be transformed to $|1001\\rangle|1010\\rangle$, since items $0$ and $3$ are put in the knapsack, and `itemValues[0] + itemValues[3] = 1 + 4 = 5 = 1010₂`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_CalculateTotalValueOfSelectedItems01\n",
    "\n",
    "operation CalculateTotalValueOfSelectedItems01 (\n",
    "    itemValues : Int[], \n",
    "    selectedItems : Qubit[], \n",
    "    total : Qubit[]\n",
    ") : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.4. Compare an integer stored in a qubit array with an integer (>)\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of `D` qubits representing an integer in little-endian format.\n",
    "2. An integer $b$ ($0 \\le b \\le 2^D - 1$).\n",
    "3. A qubit in an arbitrary state (target qubit).\n",
    "     \n",
    "**Goal:** Flip the state of the target qubit if the integer represented by the qubit array is greater than $b$. The input qubits can be in superposition. Leave the qubits in the qubit array in the same state they started in.\n",
    "\n",
    "**Example:** For $b = 11$, the input state $|1011\\rangle|0\\rangle$ should be transformed to $|1011\\rangle|1\\rangle$, since $1101_2 = 13_{10} > 11_{10}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_CompareQubitArrayGreaterThanInt\n",
    "\n",
    "operation CompareQubitArrayGreaterThanInt (qs : Qubit[], b : Int, target : Qubit) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.5. Compare an integer stored in a qubit array with an integer (≤)\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of D qubits representing an integer in little-endian format.\n",
    "2. An integer $b$ ($0 \\le b \\le 2^D - 1$).\n",
    "3. A qubit in an arbitrary state (target qubit).\n",
    "\n",
    "**Goal:** Flip the state of the target qubit if the integer represented by the qubit array is less than or equal to $b$. The input qubits can be in superposition. Leave the qubits in the qubit array in the same state they started in.\n",
    "\n",
    "**Example:** For `b = 7`, the input state $|1010\\rangle|0\\rangle$ should be transformed to $|1010\\rangle|1\\rangle$, since $0101_2 = 5_{10} ≤ 7_{10}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T15_CompareQubitArrayLeqThanInt\n",
    "\n",
    "operation CompareQubitArrayLeqThanInt (qs : Qubit[], b : Int, target : Qubit) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.6. Verify that the total weight doesn't exceed the limit $W$\n",
    "**Inputs:**\n",
    "1. An integer $W$, the maximum weight the knapsack can hold.\n",
    "2. An array of $n$ integers, describing the weights of the items: `itemWeights[i] = wᵢ`.\n",
    "3. An array of $n$ qubits, describing whether each item is put into the knapsack.\n",
    "4. A qubit in an arbitrary state (target qubit).\n",
    "\n",
    "**Goal:** Flip the state of the target qubit if the total weight is less than or equal to $W$. The input qubits can be in superposition. Leave the qubits in the qubit array in the same state they started in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T16_VerifyTotalWeight01\n",
    "\n",
    "operation VerifyTotalWeight01 (W : Int, itemWeights : Int[], selectedItems : Qubit[], target : Qubit) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.7. Verify that the total profit exceeds the threshold $P$\n",
    "**Inputs:**\n",
    "1. An integer $P$, the threshold which the total profit must exceed.\n",
    "2. An array of $n$ integers, describing the profits of the items: `itemProfits[i] = pᵢ`.\n",
    "3. An array of $n$ qubits, describing whether each item is put into the knapsack.\n",
    "4. A qubit in an arbitrary state (target qubit).\n",
    "\n",
    "**Goal:** Flip the state of the target qubit if the total profit is greater than $P$. The input qubits can be in superposition. Leave the qubits in the qubit array in the same state they started in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T17_VerifyTotalProfit01\n",
    "\n",
    "operation VerifyTotalProfit01 (P : Int, itemProfits : Int[], selectedItems : Qubit[], target : Qubit) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.8. Verify the solution to the 0-1 knapsack problem\n",
    "\n",
    "**Inputs:**\n",
    "1. An integer $W$, the maximum weight the knapsack can hold.\n",
    "2. An integer $P$, the threshold which the total profit must exceed.\n",
    "3. An array of $n$ integers, describing the weights of the items: `itemWeights[i] = wᵢ`.\n",
    "4. An array of $n$ integers, describing the profits of the items: `itemProfits[i] = pᵢ`.\n",
    "5. An array of $n$ qubits, describing whether each item is put into the knapsack.\n",
    "6. A qubit in an arbitrary state (target qubit).\n",
    "\n",
    "**Goal:** Flip the state of the target qubit if the selection of the items in selectedItems satisfies both constraints:\n",
    "* the total weight of all items is less than or equal to $W$, and\n",
    "* the total profit of all items is greater than $P$.\n",
    "\n",
    "The input qubits can be in superposition. Leave the qubits in the qubit array in the same state they started in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T18_VerifyKnapsackProblemSolution01\n",
    "\n",
    "operation VerifyKnapsackProblemSolution01 (\n",
    "    W : Int, P : Int, \n",
    "    itemWeights : Int[], \n",
    "    itemProfits : Int[], \n",
    "    selectedItems : Qubit[], \n",
    "    target : Qubit\n",
    ") : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Bounded Knapsack Problem\n",
    "\n",
    "In this version of the problem we still consider $n$ items, indexed $0$ to $n-1$, the item with index $i$ has a weight of $w_i$ and yields a profit of $p_i$. \n",
    "But in the bounded knapsack version of the problem, unlike in the 0-1 knapsack problem, each type of item can have more than one copy, and can be selected multiple times. \n",
    "Specifically, there are $b_i$ copies of item type $i$ available, so this item type can be selected between $0$ and $b_i$ times, inclusive.\n",
    "Let $x_i$ represent the number of copies of index $i$ that are put into the knapsack; the constraint $0 ≤ x_i ≤ b_i$ must hold for all $i$. \n",
    "Thus, we seek a combination `xs = [x₀, x₁, ..., xₙ₋₁]` which has total weight at most $W$, and has total profit that is strictly greater than $P$.\n",
    "\n",
    "The comparators from Part I (tasks 1.4-1.5) can be reused, but the operations for calculating total weight and profit will need to be rewritten."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. Read combination from a jagged array of qubits\n",
    "\n",
    "**Input:** A jagged array of qubits of length $n$. Array `selectedItemCounts[i]` represents the binary notation of $x_i$ in little-endian format. Each qubit is guaranteed to be in one of the basis states ($|0\\rangle$ or $|1\\rangle$).\n",
    "\n",
    "**Output:** An integer array of length $n$, containing the combination that this jagged array represents. The $i$-th element of the output array should have value $x_i$. The operation should not change the state of the qubits.\n",
    "\n",
    "**Example:** For state `selectedItemCounts = [|101⟩, |1110⟩, |0100⟩]`, return `[5, 7, 2]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_MeasureCombination\n",
    "\n",
    "operation MeasureCombination (selectedItemCounts : Qubit[][]) : Int[] {\n",
    "    // ...\n",
    "    return [];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Convert an array into a jagged array\n",
    "\n",
    "<span style=\"color:red\"><b>This task is temporarily not available in Notebook format; please use Q# project version of the BoundedKnapsack kata to complete it.</b></span>\n",
    "\n",
    "To simplify access to the register as an array of integers within the oracle, we reorganize the register into several qubit arrays that represent, in little-endian format,  the number of copies of each item type. We can do the same transformation with arrays of other types, for example, arrays of classical bits (boolean or integer) that store binary notations of several integers. To make our code reusable, we can make it type-parameterized.\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of type `T` (`T` could be qubits or classical bits).\n",
    "2. An array of $n$ integers $b_i$.\n",
    "\n",
    "**Output:** A jagged array of n arrays of type `T`. $i$-th element of the return value should have enough bits to represent the integer $b_i$ in binary notation. The length of the input array of `T` is defined to be able to store all integers $b_i$.\n",
    "\n",
    "**Example:** For `b = [6, 15, 13]` and a register of qubits in state $|10111100100\\rangle$, you need to use $3$, $4$, and $4$ bits to represent the integers $b_i$, so you'll return an array of qubit arrays `[|101⟩, |1110⟩, |0100⟩]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. Verification of limits satisfaction\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $n$ integers `itemCountLimits[i] = bᵢ`.\n",
    "2. A jagged array of $n$ qubits. Each array `selectedItemCounts[i]` represents the number of items $x_i$ in little-endian format.\n",
    "3. A qubit in an arbitrary state (target qubit).\n",
    "\n",
    "**Goal:** Flip the state of the target qubit if $x_i ≤ b_i$ for all $i$. The input qubits can be in superposition. Leave the qubits in qubit array in the same state they started in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_VerifyLimits\n",
    "\n",
    "operation VerifyLimits (itemCountLimits : Int[], selectedItemCounts : Qubit[][], target : Qubit) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.4. Increment a quantum integer by a product of classical and quantum integers\n",
    "\n",
    "**Inputs:**\n",
    "1. An integer $x$.\n",
    "2. An array of $n$ qubits, representing an arbitrary integer $y$.\n",
    "3. An array of $m$ qubits, representing an arbitrary integer $z$.\n",
    "\n",
    "**Goal:** Increment register $z$ by the product of $x$ and $y$. Perform the increment modulo $2^m$ (you don't need to track the carry bit). The input qubits can be in superposition. Leave the qubits in register $y$ in the same state they started in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_IncrementByProduct\n",
    "\n",
    "operation IncrementByProduct (x : Int, y : Qubit[], z : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.5. Calculate the number of (qu)bits necessary to hold the maximum total value\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $n$ positive integers, describing the value (the weight or the profit) of each item.\n",
    "2. An array of $n$ positive integers, describing the $b_i$ - the limits on the maximum number of items of type $i$ that can be selected.\n",
    "\n",
    "**Output:** The minimum number of (qu)bits needed to store the maximum total value of the items.\n",
    "\n",
    "**Example:** For `n = 4`, `itemValues = [1, 2, 3, 4]`, and `itemCountLimits = [2, 5, 4, 3]`, the maximum possible total value is  $1 \\cdot 2 + 2 \\cdot 5 + 3 \\cdot 4 + 4 \\cdot 3 = 36$, which requires at least $6$ qubits, so $6$ is returned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_NumBitsTotalValue\n",
    "\n",
    "function NumBitsTotalValue (itemValues : Int[], itemCountLimits : Int[]) : Int {\n",
    "    // ...\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.6. Calculate total value of selected items\n",
    "\n",
    "**Inputs:**\n",
    "1. An array of $n$ integers, describing the values (the weights or the profits) of the items.\n",
    "2. A jagged array of qubits of length $n$. Array `selectedItems[i]` represents the number of items of type $i x_i$ in little-endian format.\n",
    "3. An array of qubits `total` in the $|0...0\\rangle$ state to store the total value of the selected items. It is guaranteed that there are enough qubits to store the total value.\n",
    "\n",
    "**Goal:** Transform the `total` array to represent, in little-endian format, the sum of the values of the items that are put in the knapsack. The input qubits can be in a superposition state. Leave the qubits in `selectedCounts` in the same state they started in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T26_CalculateTotalValueOfSelectedItems\n",
    "\n",
    "operation CalculateTotalValueOfSelectedItems (\n",
    "    itemValues : Int[], \n",
    "    selectedCounts : Qubit[][], \n",
    "    total : Qubit[]\n",
    ") : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.7. Verify that the total weight doesn't exceed the limit $W$\n",
    "\n",
    "**Inputs:**\n",
    "1. An integer $W$, the maximum weight the knapsack can hold.\n",
    "2. An array of $n$ integers, describing the weights of the items: `itemWeights[i] = wᵢ`.\n",
    "3. An array of $n$ positive integers, describing the $b_i$ - the limits on the maximum number of items of type $i$ that can be selected.\n",
    "4. A jagged array of qubits, describing the number of each item type put into the knapsack. Array `selectedCounts[i]` represents $x_i$ in little-endian format.\n",
    "5. A qubit in an arbitrary state (target qubit).\n",
    "\n",
    "**Goal:** Flip the state of the target qubit if the total weight is less than or equal to $W$. The input qubits can be in superposition. Leave the qubits in the `selectedCounts` array in the same state they started in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T27_VerifyTotalWeight\n",
    "\n",
    "operation VerifyTotalWeight (\n",
    "    W : Int, \n",
    "    itemWeights : Int[], \n",
    "    itemCountLimits : Int[], \n",
    "    selectedCounts : Qubit[][], \n",
    "    target : Qubit\n",
    ") : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.8. Verify that the total profit exceeds threshold $P$\n",
    "\n",
    "**Inputs:**\n",
    "1. An integer $P$, the threshold which the total profit must exceed.\n",
    "2. An array of $n$ integers, describing the profits of the items: `itemProfits[i] = pᵢ`.\n",
    "3. An array of $n$ positive integers, describing the $b_i$ - the limits on the maximum number of items of type $i$ that can be selected.\n",
    "4. A jagged array of qubits, describing the number of each item type put into the knapsack. Array `selectedCounts[i]` represents $x_i$ in little-endian format.\n",
    "5. A qubit in an arbitrary state (target qubit).\n",
    "\n",
    "**Goal:** Flip the state of the target qubit if the total profit is greater than $P$. The input qubits can be in superposition. Leave the qubits in the `selectedCounts` array in the same state they started in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T28_VerifyTotalProfit\n",
    "\n",
    "operation VerifyTotalProfit (\n",
    "    P : Int, \n",
    "    itemProfits : Int[], \n",
    "    itemCountLimits : Int[], \n",
    "    selectedCounts : Qubit[][], \n",
    "    target : Qubit\n",
    ") : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.9. Verify the solution to the bounded knapsack problem\n",
    "\n",
    "**Inputs:**\n",
    "1. An integer $W$, the maximum weight the knapsack can hold.\n",
    "2. An integer $P$, the threshold which the total profit must exceed.\n",
    "3. An array of $n$ integers, describing the weights of the items: `itemWeights[i] = wᵢ`.\n",
    "4. An array of $n$ integers, describing the profits of the items: `itemProfits[i] = pᵢ`.\n",
    "5. An array of $n$ integers, describing the maximum numbers of each type of item that can be selected: `itemCountLimits[i] = bᵢ`.\n",
    "6. An array of $Q$ qubits, describing the numbers of each type of item selected for the knapsack. ($Q$ is the minimum number of qubits necessary to store a concatenation of the numbers up to $b_i$.)\n",
    "7. A qubit in an arbitrary state (target qubit).\n",
    "\n",
    "**Goal:** Flip the state of the target qubit if the selection of the items in `selectedCountsRegister` satisfies both constraints:\n",
    "* the total weight of all items is less than or equal to $W$, \n",
    "* the total profit of all items is greater than $P$, and\n",
    "* the number of $i$-th type of item is less than or equal to $b_i$.\n",
    "\n",
    "The input qubits can be in superposition. Leave the qubits in register in the same state they started in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T29_VerifyKnapsackProblemSolution\n",
    "\n",
    "operation VerifyKnapsackProblemSolution (\n",
    "    W : Int, P : Int, \n",
    "    itemWeights : Int[], \n",
    "    itemProfits : Int[], \n",
    "    itemCountLimits : Int[], \n",
    "    selectedCountsRegister : Qubit[], \n",
    "    target : Qubit\n",
    ") : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III. Using Grover's algorithm for knapsack optimization problems\n",
    "\n",
    "Coming soon..."
   ]
  }
 ],
 "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
}