A simple quantum algorithm to efficiently prepare sparse states

Understand

State preparation is a fundamental routine in quantum computation, for which many algorithms have been proposed.

• Among them, perhaps the simplest one is the Grover-Rudolph algorithm.
• In this paper, we analyse the performance of this algorithm when the state to prepare is sparse.
• We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits.