Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913336433573888 |
|---|---|
| author | Belovs, Aleksandrs |
| author_facet | Belovs, Aleksandrs |
| contents | Up to now, relatively few exponential quantum speed-ups have been achieved. Out of them, the welded tree problem (Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman'2003) is one of the unusual examples, as the exponential speed-up is attained by a quantum walk. In this paper, we give a very short proof of the optimal linear hitting time for this problem by a discrete-time quantum walk, which is based on a simple modification of the electric quantum walk framework. The same technique can be applied to other 1-dimensional hierarchical graphs, yielding results similar to (Balasubramanian, Li, and Harrow'2023). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19476 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem Belovs, Aleksandrs Quantum Physics Up to now, relatively few exponential quantum speed-ups have been achieved. Out of them, the welded tree problem (Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman'2003) is one of the unusual examples, as the exponential speed-up is attained by a quantum walk. In this paper, we give a very short proof of the optimal linear hitting time for this problem by a discrete-time quantum walk, which is based on a simple modification of the electric quantum walk framework. The same technique can be applied to other 1-dimensional hierarchical graphs, yielding results similar to (Balasubramanian, Li, and Harrow'2023). |
| title | Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2404.19476 |