Quadratic acceleration of multistep probabilistic algorithms for state preparation
Hirofumi Nishi, Taichi Kosugi, Yusuke Nishiya, Yu‐ichiro Matsushita · Physical Review Research · 2024
Quantum state preparation is a fundamental building block for various problems on a quantum computer. A nonunitary operator is typically designed to decay unwanted states contained in an initial state using ancilla qubits and a probabilistically action. In this Letter, we clarify that this probabilistic nature is a drag for quantum advantages: The probabilistic algorithms do not accelerate the computational process compared to classical ones. Combining quantum amplitude amplification (QAA) with multistep probabilistic algorithms is proposed to address this drawback, achieving quadratic acceleration and quantum advantages. We also find that the multistep probabilistic method with QAA exhibits advantages over quantum phase estimation in terms of infidelity. We also demonstrate it to confirm the quadratic acceleration, using a probabilistic imaginary-time evolution method as an example. Published by the American Physical Society 2024