Non-Boolean Quantum Amplitude Amplification and Machine Learning applications

Amplitude amplification involving boolean oracles provides a quadratic speedup over naive measurement-based techniques and is an essential subroutine for many quantum algorithms. This work generalizes the quantum amplitude amplification and amplitude estimation algorithms to work with non-boolean oracles. It also introduces a new, fully quantum technique for training quantum neural networks, based on non-boolean amplitude amplification.

The action of a non-boolean oracle U_ϕ on an eigenstate |x⟩ is to apply a state-dependent phase-shift ϕ(x). 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 basis states based on the value of cos(ϕ(x)). More specifically, the basis states with lower values of cos(ϕ) are iteratively amplified at the expense of states with higher values of cos(ϕ). The second algorithm is the quantum mean estimation algorithm, which uses quantum phase estimation to estimate the expectation ⟨ψ₀ | U_ϕ | ψ₀⟩. It is shown that the quantum mean estimation algorithm offers a quadratic speedup over the corresponding classical algorithm.

Both algorithms will be briefly described in the context of their application to Quantum Machine Learning.