Quantum sampling algorithms for quantum state preparation and matrix block-encoding

Understand

The problems of quantum state preparation and matrix block-encoding are ubiquitous in quantum computing: they are crucial parts of various quantum algorithms for the purpose for initial state preparation as well as loading problem relevant data.

• We first present an algorithm based on QRS that prepares a quantum state $|\psi_f\rangle \propto \sum^N_{x=1} f(x)|x\rangle$.
• When combined with efficient reference states the algorithm reduces the cost of quantum state preparation substantially, if certain criteria on $f$ are met.
• When the preparation of the reference state is not the dominant cost, and the function $f$ and relevant properties are efficiently computable or provided otherwise with cost $o(N)$, the QRS-based method outperforms the generic state preparation algorithm, which has cost $O(N)$.