search

microsoft / QuantumKatas

Tutorials and programming exercises for learning Q# and quantum computing
MIT License
4.54k stars 1.22k forks source link

Troubles undertanding the last graph coloring task #439

Closed BrokenDuck closed 4 years ago

BrokenDuck commented 4 years ago

In the last task, the parameters are the number of vertices and the oracle to test the validity of the coloring. We have to output a valid coloring. Formally, a vertex can be alone and not connected to any other vertex. Moreover, how do you test if the returned coloring is correct without knowing the edges. Do we have to return these too ?

There is clearly something that I am missing. I don't want to look at the solution without having given a thorough attempt to the problem.

jainvasu631 commented 4 years ago

Task 2.2 and Task 2.3 go hand in hand.

In Task 2.2 we are given the task of implementing an Oracle which takes input the Vertices V and Edges E of the graph, alongwith a candidate coloring. This coloring has one color for each vertex and each color is encoded using 2 qubits hence size of colorsRegister is 2V. If we create a new oracle by fixing the inputs V and edges of VertexColoringOracle we are left with a Bit-Flip Oracle which tells us if a given coloring is valid or not. This oracle is exactly what is given as input in Task 2.3

Grover's Algorithm is essentially a search over all states to find one which satisfies the conditions encoded in it oracle. We need V to create the search space - superposition of all computation basis states of size 2V. Hence these 2 inputs are sufficient to solve this task and the oracle can be used to confirm the validity of the answer. However since it is an classical answer, we can also verify the solution classically.

In essence the information about the graph is present in the oracle. In this task the user may not be directly privy to it but he can use the oracle to find the answer. This also explains why oracle is an apt description of the operation.

I hope I haven't given away too much of the solution.

Note: The reason for the 2 qubits per vertex (2bits can represent 4 different colors) limit is probably because of the Four Color Theorem

BrokenDuck commented 4 years ago

Ok, I understand now. Thanks, I kinda had trouble linking everything together. I forgot that the oracle was meant to be a black box. I simply have to generate all the possibilities in a superposition. Thanks, the note on the Four Color Theorem is really good.