.png){kind=icon}
返回
Quantum algorithm for secret learning in Mastermind game
.png){kind=icon}
PRE
AI
DOI：10.1007/s11433-025-2752-7.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本研究探讨了量子加速在名为Mastermind的流行游戏中的应用，该游戏涉及两名参与者：选择秘密字符串的codemaker和提交查询字符串并接收codemaker回答的codebreaker。codebreaker的目标是在尽可能少的查询次数内学习到秘密字符串。本研究专注于使用不同类型的codemaker回答（如black count、ℓp distance和separable distance）在量子计算机上玩Mastermind游戏。我们证明了，codebreaker可以利用展示出查询次数显著减少的量子算法来确切地学习秘密，这些量子算法的查询次数相比其经典对应算法大幅降低。具体而言，我们的量子算法分别需要$${\cal O}(k \log k)$$次black-count查询、$${\cal O}(\log k)$$次ℓp-distance查询和$${\cal O}(\log M)$$次separable-distance查询来学习秘密s ∈ [k]n，其中M完全由k决定。因此，量子查询复杂度与秘密s的长度n无关，这与经典算法的查询复杂度呈线性于n的情况相反。
期刊
S
IF:
0
论文数:
2
被引数:
4
机构
引用论文
citation_journal_title=IEEE Trans. Inform. Theor.; citation_author=M T Goodrich; citation_volume=58; citation_publication_date=2012; citation_pages=6726; citation_doi=10.1109/TIT.2012.2208581; citation_id=CR5期刊名称：IEEE Trans. Inform. Theor.；作者：M T Goodrich；卷号：58；出版日期：2012；页码：6726；DOI：10.1109/TIT.2012.2208581；引用ID：CR5.png)
IF0
PREAI
分享收藏Query complexity of mastermind variants期刊名称：Discrete Math.；作者：A Berger, C Chute, M Stone；卷号：341；出版日期：2018；页码：665；DOI：10.1016/j.disc.2017.11.004；引用ID：CR9
PREAI
分享收藏
分享收藏Recovery From Non-Decomposable Distance Oracles期刊名称：IEEE Trans. Inform. Theor.；作者：Z Hu, X Li, D P Woodruff, H Zhang, S Zhang；卷号：69；发表日期：2023；页码：6443；DOI：10.1109/TIT.2023.3289981；文献ID：CR13
PREAI
分享收藏
Mastermind with a linear number of queries期刊名：Comb. Probab. Comp.; 作者：A Martinsson, P Su; 卷号：33; 发表日期：2024; 页码：143; DOI：10.1017/S0963548323000366; 引用ID：CR10
PREAI
分享收藏
查看更多内容