Looking at the implementation ofGroverPow only, it seems that the issue might be the same as inthis question, though implemented in a slightly different way.

This section of the code

ApplyToEachCA(X, inputQubits);Controlled Z(Most(inputQubits), Tail(inputQubits));ApplyToEachCA(X, inputQubits);

implements conditional phase shift by flipping the phase only for the$|0...0\rangle$ state. This yields a global phase difference of -1 compared to Nielsen and Chuang presentation which flips phase of all states except for the$|0...0\rangle$ state. This is detected by phase estimation algorithm, so that quantum counting ends up reporting the number of solutions equal to$N - M$ instead of just$M$ (I did the detailed math inmy answer).

• $\begingroup$Interesting. I was under the assumption that a global phase difference had no practical effect (and was reinforced by the answer to my otherquestion). I will give this a shot.$\endgroup$

  nikojpapa

  – nikojpapa

  2019-09-30 21:11:43 +00:00

  CommentedSep 30, 2019 at 21:11
• $\begingroup$Yes, that's the fun part - it has no effect when you're doing Grover search itself (where the introduced phase is global indeed), but in phase estimation this phase becomes relative (since the algorithm uses controlled version of the unitary) and observable.$\endgroup$

  Mariia Mykhailova

  – Mariia Mykhailova

  2019-10-01 00:36:04 +00:00

  CommentedOct 1, 2019 at 0:36

Comparing your code to the reference implementation for theGrover search quantum kata, I think the problem might be in the way you're using your oracle in GroverPow. It's a little hard to tell, but if your Oracle is flipping the state of the ancilla based on whether or not the state is a "hit", you're then not including the ancilla in the rest of the iteration. In the kata, there's a step that transforms a "marking" oracle into a "phase flip" oracle; might you need to do that as well?

Sorry I can't be more certain! Sharing the code for your oracle might help.

• 1
  $\begingroup$As a quick follow-up, one thing that can often be very helpful in debugging is to dump what unitary operator is implemented by an operation. This can be done straightforwardly using DumpRegister (docs.microsoft.com/qsharp/api/prelude/…) and the Choi–Jamiłkowski isomorphism: prepare an entangled pair, actOracle on one half of the pair, then dump the register containing both. This will give you what's called avectorization of the unitary implemented byOracle, in this case, a flattening of the unitary to a vector.$\endgroup$

  Chris Granade

  – Chris Granade

  2018-11-16 23:32:29 +00:00

  CommentedNov 16, 2018 at 23:32
• $\begingroup$@Chris, thank you for the insight. I will see if that sheds any light. Alan, thanks for pointing me towards the kata. I'm sure that will be useful. However, I don't think what you're describing is the problem. I can use GroverPow successfully when tested using the number of iterations calculated when the number of solutions is known. I've also tried converting to a phase flip oracle, as you suggested, but it still does not give the correct answer when counting. As before, even when the oracle does absolutely nothing, the number of solutions counted is incorrect.$\endgroup$

  nikojpapa

  – nikojpapa

  2018-11-20 00:00:52 +00:00

  CommentedNov 20, 2018 at 0:00

• quantum-algorithms
• programming
• q#