Explore more graph coloring problems about quantumkatas HOT 11 CLOSED

I would like to work Triangle-free edge coloring.

from quantumkatas.

Yes you can use the Oracle designed in Task 2.2. However you will have to fix the inputs for V and edges to make the oracle work for a particular graph

from quantumkatas.

@tcNickolas Oh it resolved by itself, I can fully run the graph coloring solve in vs code so that I can finish my student report 😀.

from quantumkatas.

Sorry for the delay replying! You're definitely welcome to work on weak coloring!

I'm not sure about reorganizing the kata, though. The advantage of the current organization is that it verifies the learner's results, and while the individual task can be time-consuming, I think there is value for the learner in doing this verification for them.

I would keep parts 1 and 2 as is, then add part 3 for weak coloring, part 4 for triangle-free coloring (I have all the code from QCHack event, just need to add it to this kata), and so on. We don't even need to add a lot of code for each part, most of testing frameworks from part 2 will be reusable.

from quantumkatas.

Yes, plus any sub-tasks you feel can make the implementation easier for the learner.
For example, triangle-free coloring will have a sub-task to check whether the given triangle's coloring is a triangle or not. Weak coloring might have a sub-task to check whether at least one of the qubits is in state 1?

from quantumkatas.

Hello, I normally open new issues when I have questions about the kata, but I this time I will comment here. I am currently trying to implement finding the graph coloring solution with Grover Algorithm completely (I finished the kata completely). I did everything apart from the oracle. Can I simply use the oracle from Task 2.2 ? I kind of find it strange the whole algorithm knows the edges, with the whole black box function/oracle deal. Are there any modifications I need to make ? I tried to look at the Test.qs file but there some references to functions I simply can't find (VS code either). Quite a lot of questions but I don't really know where to ask them, quantum stack exchange doesn't seem right either.

from quantumkatas.

@BrokenDuck The whole algorithm will know the edges, since that's the input to the algorithm, same as in the classical case. Grover's algorithm itself treats the oracle as a black box, but, as @jainvasu631 pointed out, to solve an instance of the problem for a specific graph you need to pass that graph as an argument and build the oracle for it.

Which functions are you having trouble with? Everything is contained either in the "backend" files from the Q# project GraphColoring.csproj, in the Common project which defines the custom simulator used for counting operations used, or in the Q# libraries.

from quantumkatas.

@tcNickolas I finished everything and passed the test correctly. I am now trying to put everything on a Q# file with a python host. However, I recieved a lot of errors when I import qsharp, and the importing doesn't recognise the Q# namespace. I found a couple of related issues on the iqsharp repo and will look further there. I think it has to do with my .csproj file being broken.

from quantumkatas.

@BrokenDuck Somehow I missed your last question, terribly sorry about that! Did you resolve the issue successfully? If not, can you share the repro so that we can check it?

from quantumkatas.

Hi @tcNickolas , I would like to work on weak coloring.
I have a doubt, do we re-organise the structure of the GraphColoring kata? I was thinking that perhaps I could add the classical and quantum parts for weak coloring as tasks 2.3 and tasks 2.4 and move Grover's algorithm implementation to part 3 and follow a approach similar to Grovers algorithm kata. So, the current task 2.3 GroversAlgorithm would then become 3.1 GroversAlgorithm. A new open ended task 3.2 could be added for the learner to experiment with new colorings such as the weak coloring. I was thinking of this approach because the current implementation of Grovers algorithm is too much time consuming and adding another heavy computation to it seems like a bad idea.

from quantumkatas.

Does that mean that Part 3 would be having 3 tasks similar to Part 2?

Task 3.1, Classical check : IsWeakColouringValid
Task 3.2, Quantum Oracle : Weak ColouringOracle
Task 3.3, Grover's algorithm : FindWeakColoringWithGroversAlgorithm

from quantumkatas.