The Bounded Knapsack quantum kata is a series of exercises designed to teach you to use Grover search to solve the knapsack problem.
The kata covers the following topics:
Each task is wrapped in one operation preceded by the description of the task.
Your goal is to fill in the blank (marked with the // ...
comments)
with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).
Within each section, tasks are given in approximate order of increasing difficulty.
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$.
However, we will slightly modify the problem: the total profit must be strictly greater than $P$, rather than at least $P$.
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.
Input: An array of $n$ qubits, which are guaranteed to be in one of the $2^n$ basis states.
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.
Example: For $n = 3$ and the qubits state $|101\rangle$, return [true, false, true]
.
%kata T11_MeasureCombination01
operation MeasureCombination01 (selectedItems : Qubit[]) : Bool[] {
// ...
return [];
}
Input: An array of $n$ positive integers, describing the value (the weight or the profit) of each item.
Output: The minimum number of (qu)bits needed to store the maximum total value of the items.
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.
%kata T12_NumBitsTotalValue01
function NumBitsTotalValue01 (itemValues : Int[]) : Int {
// ...
return 0;
}
Inputs:
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.
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.
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₂
.
%kata T13_CalculateTotalValueOfSelectedItems01
operation CalculateTotalValueOfSelectedItems01 (
itemValues : Int[],
selectedItems : Qubit[],
total : Qubit[]
) : Unit is Adj+Ctl {
// ...
}
Inputs:
D
qubits representing an integer in little-endian format.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.
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}$.
%kata T14_CompareQubitArrayGreaterThanInt
operation CompareQubitArrayGreaterThanInt (qs : Qubit[], b : Int, target : Qubit) : Unit is Adj+Ctl {
// ...
}
Inputs:
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.
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}$.
%kata T15_CompareQubitArrayLeqThanInt
operation CompareQubitArrayLeqThanInt (qs : Qubit[], b : Int, target : Qubit) : Unit is Adj+Ctl {
// ...
}
Inputs:
itemWeights[i] = wᵢ
.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.
%kata T16_VerifyTotalWeight01
operation VerifyTotalWeight01 (W : Int, itemWeights : Int[], selectedItems : Qubit[], target : Qubit) : Unit is Adj+Ctl {
// ...
}
Inputs:
itemProfits[i] = pᵢ
.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.
%kata T17_VerifyTotalProfit01
operation VerifyTotalProfit01 (P : Int, itemProfits : Int[], selectedItems : Qubit[], target : Qubit) : Unit is Adj+Ctl {
// ...
}
Inputs:
itemWeights[i] = wᵢ
.itemProfits[i] = pᵢ
.Goal: Flip the state of the target qubit if the selection of the items in selectedItems satisfies both constraints:
The input qubits can be in superposition. Leave the qubits in the qubit array in the same state they started in.
%kata T18_VerifyKnapsackProblemSolution01
operation VerifyKnapsackProblemSolution01 (
W : Int, P : Int,
itemWeights : Int[],
itemProfits : Int[],
selectedItems : Qubit[],
target : Qubit
) : Unit is Adj+Ctl {
// ...
}
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$.
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.
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.
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$.
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$.
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.
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$).
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.
Example: For state selectedItemCounts = [|101⟩, |1110⟩, |0100⟩]
, return [5, 7, 2]
.
%kata T21_MeasureCombination
operation MeasureCombination (selectedItemCounts : Qubit[][]) : Int[] {
// ...
return [];
}
This task is temporarily not available in Notebook format; please use Q# project version of the BoundedKnapsack kata to complete it.
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.
Inputs:
T
(T
could be qubits or classical bits).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$.
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⟩]
.
Inputs:
itemCountLimits[i] = bᵢ
.selectedItemCounts[i]
represents the number of items $x_i$ in little-endian format.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.
%kata T23_VerifyLimits
operation VerifyLimits (itemCountLimits : Int[], selectedItemCounts : Qubit[][], target : Qubit) : Unit is Adj+Ctl {
// ...
}
Inputs:
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.
%kata T24_IncrementByProduct
operation IncrementByProduct (x : Int, y : Qubit[], z : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Inputs:
Output: The minimum number of (qu)bits needed to store the maximum total value of the items.
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.
%kata T25_NumBitsTotalValue
function NumBitsTotalValue (itemValues : Int[], itemCountLimits : Int[]) : Int {
// ...
return 0;
}
Inputs:
selectedItems[i]
represents the number of items of type $i x_i$ in little-endian format.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.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.
%kata T26_CalculateTotalValueOfSelectedItems
operation CalculateTotalValueOfSelectedItems (
itemValues : Int[],
selectedCounts : Qubit[][],
total : Qubit[]
) : Unit is Adj+Ctl {
// ...
}
Inputs:
itemWeights[i] = wᵢ
.selectedCounts[i]
represents $x_i$ in little-endian format.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.
%kata T27_VerifyTotalWeight
operation VerifyTotalWeight (
W : Int,
itemWeights : Int[],
itemCountLimits : Int[],
selectedCounts : Qubit[][],
target : Qubit
) : Unit is Adj+Ctl {
// ...
}
Inputs:
itemProfits[i] = pᵢ
.selectedCounts[i]
represents $x_i$ in little-endian format.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.
%kata T28_VerifyTotalProfit
operation VerifyTotalProfit (
P : Int,
itemProfits : Int[],
itemCountLimits : Int[],
selectedCounts : Qubit[][],
target : Qubit
) : Unit is Adj+Ctl {
// ...
}
Inputs:
itemWeights[i] = wᵢ
.itemProfits[i] = pᵢ
.itemCountLimits[i] = bᵢ
.Goal: Flip the state of the target qubit if the selection of the items in selectedCountsRegister
satisfies both constraints:
The input qubits can be in superposition. Leave the qubits in register in the same state they started in.
%kata T29_VerifyKnapsackProblemSolution
operation VerifyKnapsackProblemSolution (
W : Int, P : Int,
itemWeights : Int[],
itemProfits : Int[],
itemCountLimits : Int[],
selectedCountsRegister : Qubit[],
target : Qubit
) : Unit is Adj+Ctl {
// ...
}
Coming soon...