# Quantum counting in Q#

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));
}

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.

• Are you able to print out the circuit that was performed? Seeing it visually would probably make the issue immediately obvious. – Craig Gidney Nov 16 '18 at 0:50
• 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. – nikojpapa Nov 16 '18 at 7:14
• 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. – Craig Gidney Nov 16 '18 at 15:53
• 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. – nikojpapa Nov 16 '18 at 16:02

• 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. – Chris Granade Nov 16 '18 at 23:32