O(log<i>N</i>) Algorithm for Amplitude Amplification and O(log<i>N</i>) Algorithms for Amplitude Transfer in Grover&#8217;s Algorithm

Abstract

Grover&#8217;s algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grover&#8217;s algorithm is <i>T</i> = O(<math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'> <mrow> <msqrt> <mi>N</mi> </msqrt> </mrow> </math> ). This paper introduces two new algorithms for Amplitude Amplification in Grover&#8217;s algorithm with a time complexity of <i>T</i> = O(log<i>N</i>), aiming to improve efficiency in quantum computing. The difference between Grover&#8217;s algorithm and our first algorithm is that the Amplitude Amplification ratio in Grover&#8217;s algorithm is an arithmetic series and ours, a geometric one. Because our Amplitude Amplification ratios converge much faster, the time complexity is improved significantly. In our second algorithm, we introduced a new concept, Amplitude Transfer where the marked state is transferred to a new set of qubits such that the new qubit state is an eigenstate of measurable variables. When the new qubit quantum state is measured, with high probability, the correct solution will be obtained.