This work investigates quantum speedups for the popular game named Mastermind,in which there are two participants:the codemaker who selects a secret string,and the codebreaker who submits query strings and receives an...This work investigates quantum speedups for the popular game named Mastermind,in which there are two participants:the codemaker who selects a secret string,and the codebreaker who submits query strings and receives answers from the codemaker.The codebreaker's objective is to learn the secret string in as few queries as possible.This work focuses on playing the Mastermind game on quantum computers using different types of codemaker's answers such as black count,l_(p) distance,and separable distance.We show that the codebreaker can learn the secret with certainty by using quantum algorithms which exhibit a sharp reduction in query numbers compared with their classical counterparts.Specifically,our quantum algorithms require O(klog k)black-count queries,O(logk)l_(p)-distance queries,and O(log M)separable-distance queries to learn the secret s∈[k]^(n),respectively,where M is completely determined by k.Thus,the quantum query complexity is independent of the length n of the secret s,as opposed to the query complexity linear in n of classical algorithms.展开更多
The pursuit of quantum supremacy in computational tasks has driven the exploration of quantum algorithms capable of surpassing classical counterparts.In the realm of image processing,a notable advancement towards this...The pursuit of quantum supremacy in computational tasks has driven the exploration of quantum algorithms capable of surpassing classical counterparts.In the realm of image processing,a notable advancement towards this objective is highlighted in the study by Cui et al.[1].Their work proposes a quantum image filtering(QImF)algorithm that exhibits exponential acceleration for a specific subset of images,offering a glimpse into the potential of quantum computing in image processing.展开更多
The paper“Fixed-point quantum continuous search algorithm with optimal query complexity”[1]presents another interesting application of quantum search algorithms by addressing one of the long-standing challenges in q...The paper“Fixed-point quantum continuous search algorithm with optimal query complexity”[1]presents another interesting application of quantum search algorithms by addressing one of the long-standing challenges in quantum computing:how to efficiently perform search over continuous domains.While Grover’s algorithm has been a cornerstone in discrete quantum search with its well-known quadratic speedup[2],many real-world problems—ranging from high-dimensional optimization to spectral analysis of infinite dimensional operators—require searching over continuous,uncountably infinite solution spaces.展开更多
基金supported by the National Key Research and Development Program of China(Grant No.2024YFB4504004)the National Natural Science Foundation of China(Grant Nos.92465202,62272492,and 12447107)+1 种基金the Guangdong Provincial Quantum Science Strategic Initiative(Grant Nos.GDZX2303007,and GDZX2403001)the Guangzhou Science and Technology Program(Grant No.2024A04J4892)。
文摘This work investigates quantum speedups for the popular game named Mastermind,in which there are two participants:the codemaker who selects a secret string,and the codebreaker who submits query strings and receives answers from the codemaker.The codebreaker's objective is to learn the secret string in as few queries as possible.This work focuses on playing the Mastermind game on quantum computers using different types of codemaker's answers such as black count,l_(p) distance,and separable distance.We show that the codebreaker can learn the secret with certainty by using quantum algorithms which exhibit a sharp reduction in query numbers compared with their classical counterparts.Specifically,our quantum algorithms require O(klog k)black-count queries,O(logk)l_(p)-distance queries,and O(log M)separable-distance queries to learn the secret s∈[k]^(n),respectively,where M is completely determined by k.Thus,the quantum query complexity is independent of the length n of the secret s,as opposed to the query complexity linear in n of classical algorithms.
文摘The pursuit of quantum supremacy in computational tasks has driven the exploration of quantum algorithms capable of surpassing classical counterparts.In the realm of image processing,a notable advancement towards this objective is highlighted in the study by Cui et al.[1].Their work proposes a quantum image filtering(QImF)algorithm that exhibits exponential acceleration for a specific subset of images,offering a glimpse into the potential of quantum computing in image processing.
文摘The paper“Fixed-point quantum continuous search algorithm with optimal query complexity”[1]presents another interesting application of quantum search algorithms by addressing one of the long-standing challenges in quantum computing:how to efficiently perform search over continuous domains.While Grover’s algorithm has been a cornerstone in discrete quantum search with its well-known quadratic speedup[2],many real-world problems—ranging from high-dimensional optimization to spectral analysis of infinite dimensional operators—require searching over continuous,uncountably infinite solution spaces.
