= Approximate quantum counting
{title2=$k=|\{x:f(x)=1\}|$}
Approximate quantum counting estimates the number $k$ of <satisfying assignments> of a <Boolean function>, using a <quantum oracle> and <quantum measurement>. Controlled repetitions of a <Grover search algorithm> iteration let <quantum interference> reveal the count. For one input <bit>, a <Hadamard test> can give <Pauli Z gate> <expectation value> $1-k$: with the complemented <phase oracle> $U_f=\operatorname{diag}(2f(0)-1,2f(1)-1)$ and $G=-XU_f$, use $\langle+|X=\langle+|$ to obtain $\langle+|G|+\rangle=-[(2f(0)-1)+(2f(1)-1)]/2=1-k$. Repeated preparations estimate this <expectation value>; one binary measurement result does not distinguish all three counts $0,1,2$.
Back to article page
