Quantum Counting

Grover's algorithm amplifies the amplitude of marked states in an unstructured search space through repeated application of a unitary operator G called the Grover operator. The operator is defined as G = (2|ψ⟩⟨ψ| - I) O, where O is the oracle that flips the phase of solution states, and (2|ψ⟩⟨ψ| - I) is the diffusion operator that reflects the state about the uniform superposition |ψ⟩. Geometrically, G acts as a rotation in the two-dimensional subspace spanned by the uniform superposition of solutions |α⟩ and the uniform superposition of non-solutions |β⟩.

In this subspace, the initial state |ψ⟩ = sin(θ/2)|α⟩ + cos(θ/2)|β⟩, where sin²(θ/2) = M/N. Each application of G rotates the state by angle θ toward the solution subspace |α⟩. Remarkably, the Grover operator has eigenvalues e^{iθ} and e^{-iθ} in this subspace, with corresponding eigenvectors |ψ_+⟩ and |ψ_-⟩. These eigenvalues encode the solution count M through the relation θ = 2 arcsin(sqrt(M/N)).

• •Grover Operator: G = (2|ψ⟩⟨ψ| - I) O combines oracle phase flipping with amplitude amplification.
• •Rotation Angle: Each Grover iteration rotates the state by θ = 2 arcsin(sqrt(M/N)) toward the solution subspace.
• •Eigenvalues: The eigenvalues of G are e^{±iθ}, directly encoding the unknown solution count M.
• •Two-Dimensional Subspace: All relevant dynamics occur in the plane spanned by |α⟩ (solutions) and |β⟩ (non-solutions).

Quantum counting applies Quantum Phase Estimation to the Grover operator G to estimate its eigenvalue phase θ. The procedure requires a counting register of m qubits and the n-qubit search register. We first initialize the search register to the uniform superposition |ψ⟩ = H^{⊗n}|0⟩^⊗n and the counting register to |0⟩^⊗m. Then we perform QPE by applying controlled-G^{2^k} operations for k = 0, 1, ..., m-1, followed by the inverse QFT on the counting register.

Measuring the counting register yields an estimate of the phase θ/2π, from which we compute θ and then M = N sin²(θ/2). The precision of the estimate depends on the number of counting qubits m: using m qubits gives a precision of roughly sqrt(N/2^m). To ensure the estimate is accurate to within one solution, it suffices to choose m such that 2^m > sqrt(3N). This yields a total gate complexity of O(sqrt(N) log N), dominated by the controlled Grover operations.

• •Counting Register Size: m counting qubits provide precision sufficient to distinguish nearby integer values of M.
• •Controlled Grover Iterations: The k-th counting qubit controls G^{2^k}, requiring up to 2^{m-1} Grover iterations in total.
• •Solution Count Extraction: After QPE, compute M = N sin²(π j / 2^m) from the measured integer j.
• •Total Complexity: The algorithm uses O(sqrt(N)) oracle queries and O(sqrt(N) log N) total gates.