Grover量子搜索算法中的最速降线问题研究

Study on Brachistochrone Problem for Grover’s Quantum Search Algorithm

摘要: Grover量子搜索算法是近二十年最著名的量子算法，其已经被证明无法被任何经典算法所超越，展示出极强的量子加速特性。Grover量子搜索算法可以被两种等价的途径所实现，即线路模型Grover算法和绝热Grover算法。本文从绝热Grover算法的角度出发，运用变分法中广为人知的最速降线问题来探讨Grover量子搜索算法，得到了其量子加速特性的一个必要原因，这使得按照该算法的实质来设计其他量子算法成为可能。

Abstract: Grover’s quantum search algorithm is the most famous quantum algorithm in the last twenty years, which exhibits a strong quantum speedup and has been proved not to be able to be outperformed by any classical algorithm. Grover’s quantum search algorithm can be implemented by two equivalent ways, which are circuit model Grover’s algorithm and adiabatic Grover’s algorithm, and the latter is the start point of the paper. We here apply the well-known brachistochrone problem in calculus of variations to investigate and obtain a necessary condition of Grover’s quantum search algorithm, which makes possible to design new efficient quantum algorithms.