Improved implementation of reflection operators*

Quantum algorithms for diverse problems, including search and optimization problems, require the implementation of a reflection operator over a target state. Commonly, such reflections are approximately implemented using phase estimation. We provide a method that uses a linear combination of unitaries and a version of amplitude amplification to approximate reflection operators over eigenvectors of unitary operators using exponentially less ancillary qubits in terms of the precision of implementing the reflection The gate complexity of our method is comparable to that of the phase estimation approach. We then extend our results to the Hamiltonian case where the target state is an eigenvector of a Hamiltonian whose matrix elements can be queried. Our results are useful in that they reduce the resources required by various quantum algorithms in the literature. Our improvements also rely on an efficient quantum algorithm to prepare a quantum state with Gaussian-like amplitudes that may be of independent interest. We prove a lower bound which shows that the implementation of the reflection operator is optimal in terms of the query complexity.