  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. Here we use 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 a
precision parameter. The gate complexity of our method is also comparable to
that of the phase estimation approach in a certain limit of interest. Like
phase estimation, our method requires the implementation of controlled unitary
operations. 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 also provide a lower bound
on the query complexity of implementing approximate reflection operators on a
quantum computer.
