Abstract
The combination of contextual side information and search is a powerful paradigm in the scope of artificial intelligence. The prior knowledge enables the identification of possible solutions but may be imperfect. Contextual information can arise naturally, for example in game AI where prior knowledge is used to bias move decisions. In this work we investigate the problem of taking quantum advantage of contextual information, especially searching with prior knowledge. We propose a new generalization of Grover’s search algorithm that achieves the optimal expected success probability of finding the solution if the number of queries is fixed. Experiments on small-scale quantum circuits verify the advantage of our algorithm. Since contextual information exists widely, our method has wide applications. We take game tree search as an example.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Change history
18 November 2024
An Erratum to this paper has been published: https://doi.org/10.1007/s11432-024-4206-3
31 October 2024
An Erratum to this paper has been published: https://doi.org/10.1007/s11432-024-4206-3
References
Wiener M J. Efficient DES Key Search. Technical Report TR-244, 1994
Daemen J, Rijmen V. AES proposal: rijndael. 1999. https://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/docs/rijndael.pdf
Coulom R. Efficient selectivity and backup operators in Monte-Carlo tree search. In: Proceedings of the International Conference on Computers and Games, 2006. 72–83
Bennett C H, Bernstein E, Brassard G, et al. Strengths and weaknesses of quantum computing. SIAM J Comput, 1997, 26: 1510–1523
Grover L K. Quantum mechanics helps in searching for a needle in a haystack. Phys Rev Lett, 1997, 79: 325–328
Grover L K. Quantum computers can search rapidly by using almost any transformation. Phys Rev Lett, 1998, 80: 4329–4332
Brassard G, Hoyer P, Mosca M, et al. Quantum amplitude amplification and estimation. 2002. ArXiv:quant-ph/0005055
Zalka C. Grover’s quantum searching algorithm is optimal. Phys Rev A, 1999, 60: 2746–2751
Grover L K. Fixed-point quantum search. Phys Rev Lett, 2005, 95: 150501
Mizel A. Critically damped quantum search. Phys Rev Lett, 2009, 102: 150501
Yoder T J, Low G H, Chuang I L. Fixed-point quantum search with an optimal number of queries. Phys Rev Lett, 2014, 113: 210501
He X Y, Sun X M, Yang G, et al. Exact quantum query complexity of weight decision problems via Chebyshev polynomials. Sci China Inf Sci, 2023, 66: 129503
Silver D, Schrittwieser J, Simonyan K, et al. Mastering the game of go without human knowledge. Nature, 2017, 550: 354–359
Silver D, Hubert T, Schrittwieser J, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 2018, 362: 1140–1144
Wang Y L, Li G X, Wang X. A hybrid quantum-classical Hamiltonian learning algorithm. Sci China Inf Sci, 2023, 66: 129502
Montanaro A. Quantum search with advice. In: Proceedings of the Conference on Quantum Computation, Communication, and Cryptography, 2010. 77–93
Figgatt C, Maslov D, Landsman K A, et al. Complete 3-qubit grover search on a programmable quantum computer. Nat Commun, 2017, 8: 1–9
Zheng Q L, Zhu P Y, Xue S C, et al. Quantum algorithm and experimental demonstration for the subset sum problem. Sci China Inf Sci, 2022, 65: 182501
Sun X, Tian G, Yang S, et al. Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis. IEEE Trans Comput-Aided Des Integr Circ Syst, 2023, 42: 3301–3314
Cross A. The IBM Q experience and QISKit open-source quantum computing software. Bull Am Phys Soc, 2018, 2018: 63
Nielsen M A, Chuang I. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2002
Rosin C D. Multi-armed bandits with episode context. Ann Math Artif Intell, 2011, 61: 203–230
Wang D, You X, Li T, et al. Quantum exploration algorithms for multi-armed bandits. 2020. ArXiv:2007.07049
Ambainis A, Kokainis M. Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017. 989–1002
Acknowledgements
This work was supported in part by National Natural Science Foundation of China (Grant Nos. 62325210, 62272441) and Strategic Priority Research Program of Chinese Academy of Sciences (Grant No. XDB28000000).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
He, X., Sun, X. & Zhang, J. Quantum search with prior knowledge. Sci. China Inf. Sci. 67, 192503 (2024). https://doi.org/10.1007/s11432-023-3972-y
Received:
Revised:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1007/s11432-023-3972-y