The success probability of searching an objective item from an unsorted database using standard Grover's algorithm is usually not exactly 1. It is exactly 1 only when it is used to find the target state from a dat...The success probability of searching an objective item from an unsorted database using standard Grover's algorithm is usually not exactly 1. It is exactly 1 only when it is used to find the target state from a database with four items. Exact search is always important in theoretical and practical applications. The failure rate of Grover's algorithm becomes big when the database is small, and this hinders the use of the commonly used divide-and-verify strategy. Even for large database, the failure rate becomes considerably large when there are many marked items. This has put a serious limitation on the usability of the Grover's algorithm. An important improved version of the Grover's algorithm, also known as the improved Grover algorithm, solves this problem. The improved Grover algorithm searches arbitrary number of target states from an unsorted database with full success rate. Here, we give the first experimental realization of the improved Grover algorithm, which finds a marked state with certainty, in a nuclear magnetic resonance system. The optimal control theory is used to obtain an optimized control sequence. The experimental results agree well with the theoretical predictions.展开更多
基金supported by the National Natural Science Foundation of China(Grant Nos.11175094 and 91221205)the National Basic Research Program of China(Grant No.2011CB9216002)the Fund of State Key Laboratory of Intense Pulsed Radiation Simulation and Effect
文摘The success probability of searching an objective item from an unsorted database using standard Grover's algorithm is usually not exactly 1. It is exactly 1 only when it is used to find the target state from a database with four items. Exact search is always important in theoretical and practical applications. The failure rate of Grover's algorithm becomes big when the database is small, and this hinders the use of the commonly used divide-and-verify strategy. Even for large database, the failure rate becomes considerably large when there are many marked items. This has put a serious limitation on the usability of the Grover's algorithm. An important improved version of the Grover's algorithm, also known as the improved Grover algorithm, solves this problem. The improved Grover algorithm searches arbitrary number of target states from an unsorted database with full success rate. Here, we give the first experimental realization of the improved Grover algorithm, which finds a marked state with certainty, in a nuclear magnetic resonance system. The optimal control theory is used to obtain an optimized control sequence. The experimental results agree well with the theoretical predictions.
