Quantum partial search algorithm with smaller oracles for multiple target items
Quantum partial search algorithm with smaller oracles for multiple target items
复制标题
针对多个目标项具有较小预言机的量子部分搜索算法
DOI：
10.1007/s11128-022-03496-8
复制
发表时间：
2022-04
影响因子：
2.5
通讯作者：
Yuguang Yang
中科院分区：
文献类型：
--
作者：
Dan Li;Ling Qian;Yuqian Zhou;Yuguang Yang
量子搜索是一种最重要的量子算法，也是目前对后量子密码的唯一威胁。在本文中，我们考虑了部分搜索问题，即我们对被搜索项目的部分信息感兴趣。在此基础上，提出了一种具有较小预言机的量子部分搜索算法，降低了设计无错误预言机的难度。在实际应用中，该算法的时间复杂度小于Grover搜索算法。此外，我们提出了一个标点版本的量子部分搜索算法与更小的预言器，使算法更实用，通过进一步减少迭代次数。标点算法可以在多台量子计算机上并行运行。考虑到这些因素，对于多目标项目，具有较小预言器的量子部分搜索算法对于在量子计算机上运行和解决许多实际问题是可行的，例如哈密顿电路问题和求解非线性方程组。
Quantum search is one kind of the most important quantum algorithms, which is the only threat to postquantum cryptography till now. In this paper, we consider the problem of partial searching, where we are interested in part of the information of the item being searched. Then, we present the quantum partial search algorithm with smaller oracles, which reduces the difficulty of designing oracles without errors. The time complexity of this algorithm is smaller than that of the Grover search algorithm in practical instances. Furthermore, we present a punctuated version of the quantum partial search algorithm with smaller oracles to make the algorithm more practical by decreasing the number of iterations further. The punctuated algorithm could be running on several quantum computers in parallel. Taking these factors into consideration, the quantum partial search algorithm with smaller oracles for multiple target items is practical for running on a quantum computer and solving many real problems, such as the Hamiltonian circuit problem and solving systems of nonlinear equations.
登录
查看更多内容
DOI：
10.1109/tkde.2019.2937491
发表时间：
2017-07
影响因子：
8.9
作者：
Chao-Hua Yu;F. Gao;Q. Wen
通讯作者：
Chao-Hua Yu;F. Gao;Q. Wen
视觉跟踪的量子算法
影响因子：
2.9
作者：
Yu Chao Hua;Gao Fei;Liu Chenghuan;Du Huynh;Reynolds Mark;Wang Jingbo
通讯作者：
Wang Jingbo
影响因子：
2.5
作者：
Panjin Kim;Daewan Han;Kyung Chul Jeong
通讯作者：
Panjin Kim;Daewan Han;Kyung Chul Jeong
影响因子：
2.9
作者：
R. Gingrich;Colin P. Williams;Nicolas Cerf Caltech;J. P. Laboratory;Universit́e Libre de Bruxelles
通讯作者：
R. Gingrich;Colin P. Williams;Nicolas Cerf Caltech;J. P. Laboratory;Universit́e Libre de Bruxelles
影响因子：
2.5
作者：
Guangbao Xu;D. Jiang
通讯作者：
Guangbao Xu;D. Jiang