Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2511.06867 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914146557100032 |
|---|---|
| author | Zhou, Si-Qi Liang, Jin-Min Ding, Ziheng Chen, Zhihua Fei, Shao-Ming Ma, Zhihao |
| author_facet | Zhou, Si-Qi Liang, Jin-Min Ding, Ziheng Chen, Zhihua Fei, Shao-Ming Ma, Zhihao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_06867 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks Zhou, Si-Qi Liang, Jin-Min Ding, Ziheng Chen, Zhihua Fei, Shao-Ming Ma, Zhihao Quantum Physics 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. |
| title | Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2511.06867 |