Paper detail

Non-Boolean Quantum Amplitude Amplification and Quantum Mean Estimation

This paper generalizes the quantum amplitude amplification and amplitude estimation algorithms to work with non-boolean oracles. The action of a non-boolean oracle $U_φ$ on an eigenstate $|x\rangle$ is to apply a state-dependent phase-shift $φ(x)$. Unlike boolean oracles, the eigenvalues $\exp(iφ(x))$ of a non-boolean oracle are not restricted to be $\pm 1$. Two new oracular algorithms based on such non-boolean oracles are introduced. The first is the non-boolean amplitude amplification algorithm, which preferentially amplifies the amplitudes of the eigenstates based on the value of $φ(x)$. Starting from a given initial superposition state $|ψ_0\rangle$, the basis states with lower values of $\cos(φ)$ are amplified at the expense of the basis states with higher values of $\cos(φ)$. The second algorithm is the quantum mean estimation algorithm, which uses quantum phase estimation to estimate the expectation $\langleψ_0|U_φ|ψ_0\rangle$, i.e., the expected value of $\exp(iφ(x))$ for a random $x$ sampled by making a measurement on $|ψ_0\rangle$. It is shown that the quantum mean estimation algorithm offers a quadratic speedup over the corresponding classical algorithm. Both algorithms are demonstrated using simulations for a toy example. Potential applications of the algorithms are briefly discussed.