Quantum counting

[friguzzi]

Dear all,
I wrote a quantum counting kata but I'm encountering problems, it works for some functions and doesn't for others, should I submit a pull request?

Best
Fabrizio

[tcNickolas]

Sure, if you need help figuring out how to make the kata work, you can open a pull request, describe what works and what doesn't work, and we can discuss it. I might not answer very fast (and I apologize for that in advance), as I'm working on bringing in the currently open PRs and on porting some of the katas to Jupyter Notebook format, but I'll try to not disappear altogether :-)

[friguzzi]

Hi Mariia,
before submitting the kata, I would like to get the implmentation right.
I have this program
https://gist.github.com/friguzzi/84fbba72f7b6ba7bd58b0c4f8a8be60f
https://gist.github.com/friguzzi/3c7b836d572c26450efbdc2380cbc97e
for counting the solutions of the 3 bits formula
(not reg[0] or reg[2]) and (not reg[1] or reg[2]) and (not reg[0] or not reg[1])
This formula has 4 solutions.
I consider an extended formula with 7 bits that is true when the first three bit satisfy the above formula and the other three bits are at 0. The extended formula this has 4 solutions as well but i can increase easily the number of solutions by excluding variables from the formula.
I compute the phase \phi with the linked program, then I compute \theta/2 as 2PI\phi/2=PI*\phi
Now the number of solutions should be 128sin(\theta/2)^2 right?
I get the correct number of solutions if I compute 128(1-sin(\theta/2)^2).
It's as if the formula is negated but I can't find where the negation is.
This same formula with GroverSearch returns correct solutions.

Any help is appreciated.

best
Fabrizio
The linked program

[tcNickolas]

Sorry for the delay replying, I'll need to dig deeper into this topic to answer, and so far I haven't had time for it. I'll try to figure it out in the next couple of days.

[friguzzi]

Hi Mariia,
have you had the chance to have a look at the code?

[tcNickolas]

I spent a couple of hours today looking into the algorithm for quantum counting and your code for it - so far everything you do looks reasonable. Why the answer diverges from the expected one, I don't know yet - I'll have to keep looking. Sorry it's taking me so long!

[friguzzi]

Thanks Mariia

[olivia-fl]

I'm also writing an implementation of quantum counting (in quipper rather than C# though), and ran into the exact same problem. When I replaced sin²(θ) with 1-sin²(θ) it worked as expected. This means there's probably some shared issue between both of our implementations, rather than just a bug in yours. My current hypothesis is that θ is off by π/2, since 1-sin²(θ)=cos²(θ).

My implementation is here for comparison.

[tcNickolas]

I think I found the issue - I wrote it up as an answer to your StackExchange question, since GitHub doesn't really do formulas. Sorry it took so long - it was a well-hidden bug!

@Benjamin-L - I don't know enough Quipper to check whether your implementation has the same issue, but an extra global phase of -1 on Grover iteration will manifest in this way. In this case it came from the conditional phase flip stage: in Nielsen and Chuang you're supposed to flip all phases except the |0...0⟩ state, and Q# implementation flipped only the phase of the |0...0⟩ state. Hope that helps!

[tcNickolas]

@friguzzi Are you still working on the quantum counting kata? It would be an interesting one to have, especially the approximate counting.

[friguzzi]

I submitted a pull request with quantum counting

[tcNickolas]

We're moving the discussion to the pull request #168, so I'll close this issue to keep the discussion in a single place.