基于量子计算机的数据库搜索

Grover提出的量子搜索算法,可以用O(N1/2)的时间复杂度完成对规模为N的非结构化数据集的搜索,这在经典计算机上需要O(N)的复杂度。其中量子黑盒(又称为Oracle)依赖于具体问题,根据数据库搜索的要求,设计了量子黑盒的内部结构和相应的量子线路,给出了适合于数据库搜索的量子算法。

Database Searching In Quantum Computers

For a structureless dataset whose module is N, the time complexity of Grover's quantum searching algorithm is O(N1/2), while it is O(N) on classical computers. The black box(Oracle) depends on particular problem. According to the requirement of database searching, the internal structure and quantum circuit of black box is designed, and the quantum algorithm for database searching is given.