In this paper, we describe an alternative circuit implementation for the Grover search algorithm by replacing the amplitude amplification part with a non-unitary gate which can be implemented by using an additional ancilla register. We show that the final quantum state in the Grover search algorithm is the normalized marked quantum state in the Gram-Schmidt process. Therefore, one can try to generate this vector by using a non-unitary gate or an approximation of this non-unitary gate. Since we still use the marking part of the original algorithm, $U_{mark}$, the complexity of the algorithm is bounded by the complexity of this operator. We discuss how the implementation of the non-unitary may not be easy task and show the approximations to this operator e.g. through linear combination of unitary matrices or similar methods. Finally we discuss, how these approximations may change the complexity.
翻译:暂无翻译