1
$\begingroup$

for a student report about solving graph coloring with Grover's Algorithm, I have to talk about the performance of simulated Grover's Algorithm to solve graph coloring. I don't really know how to approach some of the points I have to talk about. I have many things to talk about :

  • The execution time : this is hard to measure for "big" graphs like 7/8 node graphs, as the runtime can take more than half an hour and I cannot average running the same program many times. I can still do something less rigorous but do you have any tips ?
  • The resources used : this is something I really don't know how to take on. I can guess the complexity can be calculated using Big-O notation, but how do I get this on a simulated problem ?
  • Testing operations : this is something I don't know how to do, but I know there is a method for. I know my program works, but is there any rigorous testing for operations in Q# ?
  • Estimate for a quantum computer. I know there is the quantum trace simulator, however I cannot see how to provide measurement probabilities for the graph coloring problem. This is pretty packed in big questions. This is new terrain for me so I hope someone can help. If you have more suggestions about how to test the program, I am open :).
$\endgroup$
2
$\begingroup$
  1. Validating your solution.

Q# offers a variety of methods to test your code, depending on what exactly you want to test. In this case, the main part seems to be validating the oracle you implemented for graph coloring problem. In the GraphColoring kata and other oracle-focused katas we usually rely on comparison of the quantum computation result with the classically computed result for all possible basis vectors. (That's how the oracles are defined - implement them using reversible operations only so that they act properly on the basis vectors, and you're guaranteed that they'll act properly on linear combinations of those.)

More specifically, in the test that covers graph coloring oracle we:

  • iterate over all possible classical inputs,
  • encode each of them as a basis state on the input qubits,
  • apply the oracle to the qubits to perform the computation,
  • read out the result,
  • and compare it to the result of the same computation done classically (i.e., validating the graph coloring classically).
  • You can also verify that the oracle application doesn't modify the input states by measuring the input qubits and verifying that their state is the same state you've encoded in the input, like we do in the RippleCarryAdder kata.

This doesn't guarantee that you haven't done something odd like introduce a phase or use a gate other than X and controlled-X; if you want to check for that as well, you can use Toffoli simulator instead of the typical full-state simulator: it will limit the pool of gates you can use, and give you an extra benefit of speeding up the oracle simulation.


  1. Resource estimation.

The other three questions are all tied to resource estimation of a quantum algorithm, so I'll bundle them together.

You probably don't really care about the actual runtime of a simulation on a classical computer that much, since it's not an indication of the runtime of the algorithm on a quantum computer. Small tweaks to the order in which you allocate qubits, for example, can reduce your simulation time quite dramatically without having impact on the quantum runtime, as I explored in this blog post. If you find a tweak like this, you'll probably want to report it, since it highlights interesting differences between simulation and actual quantum runtime, but otherwise I wouldn't aim for a very precise simulation runtime estimate - saying "around 35 minutes" would be fine.

Resource estimation is the best way to estimate the resources used without counting the gates manually. A neat way to work around the need to provide probabilities is to implement an operation that performs Grover's search loop alone (without the measurements) and to resource-estimate it, since the measurements will not add extra qubits or gates to the algorithm. Then you'll get values like the circuit depth in terms of 2-qubit gates, which will allow you to estimate the algorithm runtime on a quantum computer, once you make some assumptions about single gate speed.

$\endgroup$
4
  • $\begingroup$ Hello, thanks for the nice response, is there any difference between the two resource estimators ? Also how do I use both of them with a python host program, I couldn't find anything on the docs ? $\endgroup$ Oct 4 '20 at 11:46
  • 1
    $\begingroup$ The docs list all the ways to call it, including from Python: docs.microsoft.com/en-us/quantum/user-guide/machines/…. As the same page says, resource estimator is easier to use, trace simulator offers more functionality, but the core is the same. $\endgroup$ Oct 4 '20 at 18:00
  • $\begingroup$ I do not understand why you have to implement the oracle using reversible operations so that it only affects the basis states. For example, in graph coloring, I thought we uncomputed to leave the state as is. $\endgroup$ Oct 19 '20 at 16:28
  • $\begingroup$ @Jonathcraft This seems to be an orthogonal question, which is hard to do justice to in the 500 characters we have for a comment :-) I would suggest you to ask it as a separate question, so that it can be more discoverable and others can benefit from it as well $\endgroup$ Oct 19 '20 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.