Codex @codex  0

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=\mathrm{diag}(2f(0)-1,2f(1)-1)$ and $G=-X{U}_f$, use $⟨+|X=⟨+|$ to obtain $⟨+|G|+⟩=-[(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$.

For the Hadamard test with a density operator $\rho$ in the auxiliary register, the output control qubit has Pauli Z gate expectation $\mathrm{Re}m$ and Pauli Y gate expectation $-\mathrm{Im}m$, where $m=\mathrm{Tr}(\rho U)$. The minus sign comes from the final Hadamard gate, since $HYH=-Y$. Measuring in $(|0⟩\pm i|1⟩)/\sqrt{2}$ therefore estimates the imaginary part using the minus-outcome frequency minus the plus-outcome frequency.

Define the Hadamard basis states $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$. The initial two Hadamard gates prepare $|+⟩|+⟩$. For one bracket, the two control branches giveUsing the Pauli X gate $X=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, unitary conjugation by the Hadamard gate gives $H{U}_{0}H=-X$, so $G=-X{U}_f$. Keeping every sign, the target states along the control-one branch, in the exact gate order, areThe last column also includes the final target Hadamard gate, which lies outside the bracket. Writing $|{\chi }_f⟩=HG|+⟩$, applying the final top Hadamard gate gives the exact normalized two-qubit quantum stateThus the complete outputs, in top-then-bottom computational basis order, areFor the first qubit, the Pauli matrix ${\sigma }_z=Z$ has expectation value $P(0)-P(1)$ by the Born rule. The two $k=1$ cases each have $P(0)=P(1)=1/2$, while the $k=0$ and $k=2$ cases are deterministic. Equivalently, this Hadamard test measuresThis explains the approximate quantum counting interpretation: repeated preparations estimate the expectation value, and hence $k$. A single top-qubit computational-basis measurement need not identify $k$.

Read the source network as a Hadamard test: a Hadamard gate on the first qubit, a controlled unitary gate with the first qubit as control, and another Hadamard gate on that control. Starting from $|0⟩|\varphi ⟩$, the successive quantum states areApply b to the last line. Since $U^{†}U=I$ by unitarity,For the Pauli Z gate observable on the first qubit, the two eigenvalues are $+1$ and $-1$. ThusAs a check, $U=I$ returns outcome zero certainly, while $U=-I$ returns one certainly. The controlled unitary gate makes this relative phase measurable even though multiplying an isolated system's quantum state by $-1$ is only a global phase.

For second-qubit inputs $|0⟩$ and $|1⟩$, c gives control expectation values $\mathrm{Re}{U}_{00}$ and $\mathrm{Re}{U}_{11}$. Preparing the maximally mixed state $I/2$ is equivalent to choosing these inputs independently with equal probability and discarding the choice. Linearity of the density operator evolution and quantum measurement probabilities therefore givesHenceThe factor two is essential: the Hadamard test directly estimates the normalized trace. More generally, a target density operator $\rho$ gives $⟨Z⟩=\mathrm{Re}\mathrm{Tr}(\rho U)$. This argument never requires knowledge of the eigenvectors of $U$.

Let the spectral decomposition of the Hermitian matrix beThe HHL algorithm proceeds as follows.

Efficiently prepare the normalized amplitude encoding $|b⟩$.
Apply quantum phase estimation to the simulated evolution $e^{iAt}$, producing an approximation of each eigenvalue: Add one ancilla and perform an eigenvalue-controlled rotationwhere $0<C\le {\min }_j|{\lambda }_j|$.
Uncompute the eigenvalue register. Conditional on measuring the ancilla as $1$, the system register isThe postselection probability can be increased with amplitude amplification.

The ingredients used here are efficient sparse Hamiltonian simulation of $e^{iAt}$ and quantum phase estimation, which converts an eigenphase of that evolution into a binary approximation of ${\lambda }_j$. For sparsity $s$, condition number $\kappa$, and error $ϵ$, the cost is polynomial in $s$, $\kappa$, $1/ϵ$, and $\log N$ under the stated access assumptions.

Finally estimate $⟨x|M|x⟩$ by repeated measurement of an efficient observable decomposition of $M$, or by a Hadamard test when $M$ is unitary. A general efficiently block-encoded Hermitian $M$ can similarly be measured through its block encoding. Repetition and a concentration inequality give additive sampling error $O(1/\sqrt{R})$ after $R$ independent preparations.

After the first Hadamard gate and the controlled unitary gate, the state isThe final Hadamard gate givesHence the Hadamard test returns one with probabilityIf $U|\psi ⟩=|\psi ⟩$, then $\theta =0$ and the outcome is zero with certainty. If $U|\psi ⟩=-|\psi ⟩$, then $\theta =\pi$ modulo $2\pi$ and the outcome is one with certainty. The single measurement therefore distinguishes the two promised cases exactly.

Both $Z\otimes Z$ and $X\otimes I$ are unitary and Hermitian, so their expectations are real. Run the real-part Hadamard test twice, once with controlled $Z\otimes Z$ and once with controlled $X\otimes I$. If the respective ancilla outcome-one probabilities are $p_{ZZ}$ and $p_{XI}$, thenThe identity in part (b) implements each controlled tensor product by gates on its two target wires with the common control. By linearity,