Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database |
| |
Authors: | SHANG Bin |
| |
Institution: | School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, China |
| |
Abstract: | An important and usual sort of search problems is to find all marked states from an unsorted database with a large
number of states. Grover's original quantum search algorithm is for
finding single marked state with uncertainty, and it has been
generalized to the case of multiple marked states, as well as been
modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and
with the precision that we demand. In the end we introduce an algorithm for the problem on a “duality computer” and show its advantage over other algorithms. |
| |
Keywords: | quantum algorithm unsorted database search problem quantum query complexity |
本文献已被 维普 等数据库收录! |
| 点击此处可从《理论物理通讯》浏览原始摘要信息 |
| 点击此处可从《理论物理通讯》下载免费的PDF全文 |
|