Speaker
Description
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⟩ 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 ±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⟩, 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 ⟨ψ0|Uφ|ψ0⟩, i.e., the expected value of exp(iφ(x)) for a random x sampled by making a measurement on |ψ0⟩. 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.