- 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.
- 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.
