Quantum counting in Q#

Question

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];

X(ancilla);
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.

Answer 1

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

Answer 2

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.