Fast Black-Box Quantum State Preparation

Quantum state preparation is an important ingredient for other higher-level quantum algorithms, such as Hamiltonian simulation, or for loading distributions into a quantum device to be used e.g. in the context of optimization tasks such as machine learning. Starting with a generic "black box" method devised by Grover in 2000, which employs amplitude amplification to load coefficients calculated by an oracle, there has been a long series of results and improvements with various additional conditions on the amplitudes to be loaded, culminating in Sanders et al.'s work which avoids almost all arithmetic during the preparation stage. In this work, we improve upon this routine in two aspects: we reduce the required qubit overhead from $g$ to $\log_2(g)$ in the bit precision $g$ (at a cost of slightly increasing the count of non-Clifford operations), and show how various sets of coefficients can be loaded significantly faster than in $O(\sqrt N)$ rounds of amplitude amplification, up to only $O(1)$ many. This exponential speedup translates beyond the black box case.