Fast Black-Box Quantum State Preparation Based on Linear Combination of
  Unitaries
Black-box quantum state preparation is a fundamental primitive in quantum
algorithms. Starting from Grover, a series of techniques have been devised to
reduce the complexity. In this work, we propose to perform black-box state
preparation using the technique of linear combination of unitaries (LCU). We
provide two algorithms based on a different structure of LCU. Our algorithms
improve upon the existed best results by reducing the required additional
qubits and Toffoli gates to 2log(n) and n, respectively, in the bit precision
n. We demonstrate the algorithms using the IBM Quantum Experience cloud
services. The further reduced complexity of the present algorithms brings the
black-box quantum state preparation closer to reality.
Shengbin Wang Zhimin Wang Guolong Cui Shangshang Shi Ruimin Shang Lixin Fan Wendong Li Zhiqiang Wei Yongjian Gu