Quantum Oracle for Solving (Bounded) Knapsack Problem

[louiswmarquis]

Hello,

I would like to contribute by creating a Kata that involves a quantum oracle that can be used to solve the (Bounded) Knapsack Problem using Grover's Algorithm. I have already written most of the code for this oracle, and I have tested that it works. I will need some time to convert my code into a Kata format, though.

Could my proposed contribution be added to the roadmap? What are some first steps I need to do to transform my code into a Kata? Are there any specific guidelines on the formatting?

Please let me know if there are any questions. Thank you.

[jainvasu631]

I think the SolveSATWithGrover and GraphColoring Katas could provide you with a decent template/guideline on the layout of writing this Kata.

These are other Katas which aim to solve a classical problem (3SAT or Graph Coloring) with Grover's Algorithm.

You will have to write tests, reference implementations and other scaffolding to Kata. I guess, they could be done in a similar vein as to SolveSATWithGrover/GraphColoring Kata.

[tcNickolas]

Hi @emax-wenjun!

Sounds exciting! (Well, I might be biased, since I like Grover's algorithm and its applications a lot, but still exciting :-)) I added it to the Roadmap and linked it to this issue.

As @jainvasu631 mentioned, the good examples of the katas to base this one upon are SolveSATWithGrover and GraphColoring.

The biggest challenge is usually splitting the big task into a sequence of smaller ones that build up to it - making the steps too large makes the kata very hard to approach. It might be a good idea to discuss the sequence of steps here before you spend a week or more implementing them. I haven't thought about how I would approach building this kata yet, but I should be able to follow your sequence and suggest possible additional steps or places in which the complexity increase is too steep.

Thank you! I'm looking forward to solving your kata! (I don't get nearly enough katas to enjoy solving :-))

[louiswmarquis]

Thank you, @jainvasu631 for the reference. I will probably use GraphColoring, since I'm more familiar with it, having solved it before.

@tcNickolas, for the splitting of the task into smaller parts, I currently have split the oracle into many operations and layers, but I will need to further decompose them to an extent that works for a kata. I have, however, calculated an estimation for the complexity, and from this estimate, the increase is not too steep, if the oracle is designed correctly.
As of current, my oracle's sequence of steps goes as follows (each step is an individual operation):

1. Less-than-or-equal-to comparator (To compare a Qubit[] representing an integer, with an Int. I don't believe there exists an operation for these particular datatypes in the API, but if there is, please let me know).
2. Greater-than comparator (could skip, since it's the same as the above comparator + inverter)
3. Bounds Checking module (uses comparators to evaluate if qubits satisfy bounds requirement in Knapsack Problem)
4. Addition operation (Increases a Qubit[] representing an integer by an Int value. Again, if there's an existing operation in the API that does this, please let me know).
5. Multiplication operation (repeated additions, to increase the value of a Qubit[] by the product of an Int and a different Qubit[] representing an integer )
6. An operation to calculate a summation, that will be used for the total profit and total weight in the Knapsack Problem.
7. Weight Checking: returns whether the total weight satisfies the constraint
8. Profit Checking: returns whether the total profit is greater than a threshold value
9. KnapsackValidationOracle: performs Step 3 (Bounds), Step 7 (Weight), and Step 8 (Profit), and performs a Toffoli gate to return whether all three conditions are satisfied.

Please let me know if anyone has comments, suggestions, or questions about my approach. In addition, I can also explain how specifically the Knapsack Validation Oracle will be used with Grover's Algorithm to solve the Knapsack Problem.

[msoeken]

@emax-wenjun I have a suggestion for an alternative implementation of the oracle, which potentially makes it a bit simpler to create the Kata.

Imagine we have a qubit register for the oracle input (in the length of the number of available items) and a target register for the oracle. Then we have a register of size W, where W is the sum over all item weights. Think of this register being partitioned for all items, each in the length of the item's weight. Then we can apply X operations to a partition, controlled by the qubit from the input register for the corresponding item. Then the sum of all active qubits in W is the total weight and can be compared with the Less-than-or-equal comparator you are describing.

This avoid constant addition and constant multiplication.

[louiswmarquis]

@msoeken Thank you for your proposal, which will be of great value if it can avoid constant addition and multiplication. First, I would like to make sure we are on the same page regarding the problem. The version of the Knapsack Problem that I'm aiming to solve is the Bounded Knapsack Problem, in which there are n types of items, and each type can have multiple instances. Specifically, the i^th type can have up to b_i instances (e.g. Object type 5 can have up to 20 instances).
Thus, the oracle input would not be just n qubits, but rather consist of log₂ b_i qubits for each of n types of items.

In light of the item types having multiple instances, partitioning a register of size W, as you describe, would require b_iw_i qubits for the i^th object type (w_i is the item's weight). Note that currently the QDK can handle up to 30 qubits at a time, including input, output, and ancilla qubits. It may be difficult to implement the described register within this range and be able to run reasonably large values of b_i and w_i at the same time. However, I will definitely keep in mind your idea and consider how it can be effectively implemented to avoid constant addition and multiplication, while conserving qubit usage.

Please let me know if I have misunderstood your suggested implementation, or if you have any other questions or comments.

[louiswmarquis]

7/31/2020 Updates on the Kata:

• I discovered that the IncrementByInteger operation, which may have been added recently, performs the same task as the custom adder that I had previously described, except more efficiently. Therefore, the kata will no longer need a custom adder, instead using this operation.

• I have essentially finished writing the ReferenceImplementation.qs for the kata, although I'm still trying to implement the quantum counting algorithm for calculating M for Grover Iterations. If anyone already knows how to implementation the quantum counting algorithm in Q#, that would be very helpful for this task. Otherwise, I will need to do some light research to write a Q# implementation.

[tcNickolas]

There is a PR covering quantum counting at #168, though I still haven't gotten to reviewing it :-(

Speaking of the difference in approaches described by you vs @msoeken, it seems that they are solving different problems, and the main difference is the number of instances of each item type that can be used. If this is so, would it make sense to cover the single-instance problem in the first part of the kata, as the easier one, and the multi-instance in the second part? This looks like it could be a nice build up in complexity

[louiswmarquis]

@tcNickolas That is a fantastic idea! I had been worrying that my kata would build up in complexity too quickly, and doing the single-instance problem first easily resolves this issue. Thank you very much for your suggestion. I will look into the quantum counting, as well.

[louiswmarquis]

8/9/2020 Updates:
I have finished writing all of the tasks, tests, and reference implementation for the kata, with the exception of quantum counting. Although I am able to implement quantum counting if necessary, I feel that its complexity requires its own kata to be covered efficiently. I would be willing to help create that kata, but I would like to finalize this kata first, since it is nearly finished. Thus, I will likely put a "placeholder" for quantum counting in this kata, such as the iteration method used in GraphColoring. If anyone else has a suggestion, or a different way to "place-hold" for quantum counting, please let me know.

Finally, once I am finished, how would I incorporate the BoundedKnapsack kata into the repository? I assume I might need to create a branch and a pull request, but I can't find where to create a branch. Do I need permissions to do so? If so, could I be granted these permissions?

[louiswmarquis]

@tcNickolas, @msoeken, @jainvasu631 I have finished writing the code for the Knapsack Problem kata, which can be found in the pull request I created. I would appreciate any feedback and any suggestions for improvement so that it can be incorporated into the repository. Thank you.