A weight register is a quantum register that stores the total weight associated with each encoded item selection. In a knapsack circuit, it works alongside a key register for selections and a value register for total values. section 10.1.2 section 11.3.1
Build the register and encode the weight function with these implementation steps:
- Choose the register size to represent the weights required by the algorithm; the example starts with three qubits and later uses four. section 10.1.2 section 11.3.2
- Initialize the weight register in equal superposition with Hadamard gates, alongside the selection and value registers. section 11.3.1
- Represent each weight contribution as a coefficient and the selection qubit controlling that contribution. section 10.1.2
- Apply controlled phase rotations for each term, then apply the inverse quantum Fourier transform to convert the encoded phases into integer weights. section 10.1.2 section 11.3.1
- Use the resulting register values to identify selections whose weights satisfy a constraint. section 11.3.2
Three-item knapsack
For item weights 3, 2, and 1, encode the terms [(3, [0]), (2, [1]), (1, [2])]. Selection 011 produces weight 5, while selection 101 produces weight 4. To enforce a capacity of 4, encode w′ = 4 − w; feasible selections then have nonnegative values in the adjusted weight register. section 10.1.2 section 11.3.2
Table 10.3 Each possible selection of items and the corresponding value and weight
|
Selection
|
Value
|
Weight
|
|---|---|---|
|
000
|
0
|
0
|
|
001
|
2
|
3
|
|
010
|
3
|
2
|
|
011
|
5
|
5
|
|
100
|
1
|
1
|
|
101
|
3
|
4
|
|
110
|
4
|
3
|
|
111
|
6
|
6
|
Compare every binary item selection with its corresponding total weight and value before applying search constraints. section 10.1.2
