I cannot seem to get an estimate for the number of solutions using the quantum counting algorithm described in Nielsen and Chuang, i.e. phase estimation with the Grover iteration acting as $U$.

I try doing the following with control and target as allocated qubit registers:

let controlBE = BigEndian(control);
let ancilla = target[0];

ApplyToEachCA(H, control + target);
for (i in 0..Length(control) - 1) {
    Controlled GroverPow([control[Length(control) - 1 - i]], (2 ^ i, target));
Adjoint QFT(controlBE);

let fiBE = MeasureInteger(controlBE);
let numSolutionsD = PowD(Sin(ToDouble(fiBE) / 2.0), 2.0) * ToDouble(2 ^ Length(inputQubits));

Message("numSolutions: " + Round(numSolutionsD));

My GroverPow is a discrete oracle that is supposed to perform the Grover iteration to the power defined by the given integer.

operation GroverPow(power: Int, qubits: Qubit[]): Unit {
    let ancilla = qubits[0];
    let inputQubits = qubits[1..Length(qubits) - 1];
    let aug = Tail(inputQubits);
    let ans = Most(inputQubits);

    for (i in 1..power) {
        Oracle(ans, database, ancilla, aug);  // Grover iteration
        ApplyToEachCA(H, inputQubits);
        ApplyToEachCA(X, inputQubits);
        Controlled Z(Most(inputQubits), Tail(inputQubits));
        ApplyToEachCA(X, inputQubits);
        ApplyToEachCA(H, inputQubits);

This just doesn't give the correct answer, even when I have the oracle do absolutely nothing. Is there an obvious bug that I'm missing? I've tried using various combinations of my home-grown functions as well as the built-in AmpAmpByOracle and QuantumPhaseEstimation functions and various initial/target states but to no avail. I've tried absolutely everything I can think of, and am almost starting to get suspicious of the validity of this algorithm...obviously it's sound but that's where I'm at! Just doesn't seem to work.

  • $\begingroup$ Are you able to print out the circuit that was performed? Seeing it visually would probably make the issue immediately obvious. $\endgroup$ – Craig Gidney Nov 16 '18 at 0:50
  • $\begingroup$ How do you mean? You can see a visual of the circuit I'm attempting to implement here en.wikipedia.org/wiki/Quantum_counting_algorithm. I am using Q# in Visual Studio Code. $\endgroup$ – nikojpapa Nov 16 '18 at 7:14
  • $\begingroup$ I don't mean a diagram of the intended circuit, I mean a diagram of the actual circuit executed by the code. The goal is to compare them. $\endgroup$ – Craig Gidney Nov 16 '18 at 15:53
  • $\begingroup$ I understand, I'm just not sure how I would print that out...hence I mentioned I'm using Q# in Visual Studio Code in case you knew of a method. $\endgroup$ – nikojpapa Nov 16 '18 at 16:02

Looking at the implementation of GroverPow only, it seems that the issue might be the same as in this 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 in my 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 other question). I will give this a shot. $\endgroup$ – nikojpapa Sep 30 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 Oct 1 at 0:36

Comparing your code to the reference implementation for the Grover 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, act Oracle on one half of the pair, then dump the register containing both. This will give you what's called a vectorization of the unitary implemented by Oracle, in this case, a flattening of the unitary to a vector. $\endgroup$ – Chris Granade Nov 16 '18 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 Nov 20 '18 at 0:00

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.