Efficient quantum algorithm for solving structured problems via multistep quantum computation

Abstract

In classical computation, a problem can be solved in multiple steps where the calculated results of each step can be copied and used repeatedly. However, in quantum computation, it is difficult to realize a similar multistep computation process because the no-cloning theorem forbids making copies of an unknown quantum state perfectly. We find a method based on a quantum resonant transition to protect and reuse an unknown quantum state that encodes the calculated results of an intermediate step without copying it, and present a quantum algorithm that solves a problem via multistep quantum computation. We demonstrate that this algorithm can solve a type of structured search problems efficiently.