Quantum algorithms have demonstrated provable speedups over classical counterparts,yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge.In this work,we de...Quantum algorithms have demonstrated provable speedups over classical counterparts,yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge.In this work,we decode the quantum search advantage by investigating the critical role of quantum state properties in random-walk-based algorithms.We propose three distinct variants of quantum random-walk search algorithms and derive exact analytical expressions for their success probabilities.These probabilities are fundamentally determined by specific initial state properties:the coherence fraction governs the first algorithm’s performance,while entanglement and coherence dominate the outcomes of the second and third algorithms,respectively.We show that increased coherence fraction enhances success probability,but greater entanglement and coherence reduce it in the latter two cases.These findings reveal fundamental insights into harnessing quantum properties for advantage and guide algorithm design.Our searches achieve Grover-like speedups and show significant potential for quantum-enhanced machine learning.展开更多
基金supported by the Fundamental Research Funds for the Central Universities,the National Natural Science Foundation of China(Grant Nos.12371132,12075159,12171044,12071179,and 12405006)the specific research fund of the Innovation Platform for Academicians of Hainan Province.
文摘Quantum algorithms have demonstrated provable speedups over classical counterparts,yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge.In this work,we decode the quantum search advantage by investigating the critical role of quantum state properties in random-walk-based algorithms.We propose three distinct variants of quantum random-walk search algorithms and derive exact analytical expressions for their success probabilities.These probabilities are fundamentally determined by specific initial state properties:the coherence fraction governs the first algorithm’s performance,while entanglement and coherence dominate the outcomes of the second and third algorithms,respectively.We show that increased coherence fraction enhances success probability,but greater entanglement and coherence reduce it in the latter two cases.These findings reveal fundamental insights into harnessing quantum properties for advantage and guide algorithm design.Our searches achieve Grover-like speedups and show significant potential for quantum-enhanced machine learning.
