Quantum Search on Bipartite Multigraphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913797139070976 |
|---|---|
| author | Bezerra, Gustavo Alves Ambainis, Andris Portugal, Renato |
| author_facet | Bezerra, Gustavo Alves Ambainis, Andris Portugal, Renato |
| contents | Quantum walks provide a powerful framework for achieving algorithmic speedup in quantum computing. This paper presents a quantum search algorithm for 2-tessellable graphs, a generalization of bipartite graphs, achieving a quadratic speedup over classical Markov chain-based search methods. Our approach employs an adapted version of the Szegedy quantum walk model (adapted SzQW), which takes place on bipartite graphs, and an adapted version of Staggered Quantum Walks (Adapted StQW), which takes place on 2-tessellable graphs, with the goal of efficiently finding a marked vertex by querying an oracle. The Ambainis, Gilyén, Jeffery, and Kokainis' algorithm (AGJK), which provides a quadratic speedup on balanced bipartite graphs, is used as a subroutine in our algorithm. Our approach generalizes existing quantum walk techniques and offers a quadratic speedup in the number of queries needed, demonstrating the utility of our adapted quantum walk models in a broader class of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_12586 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Search on Bipartite Multigraphs Bezerra, Gustavo Alves Ambainis, Andris Portugal, Renato Quantum Physics Data Structures and Algorithms Quantum walks provide a powerful framework for achieving algorithmic speedup in quantum computing. This paper presents a quantum search algorithm for 2-tessellable graphs, a generalization of bipartite graphs, achieving a quadratic speedup over classical Markov chain-based search methods. Our approach employs an adapted version of the Szegedy quantum walk model (adapted SzQW), which takes place on bipartite graphs, and an adapted version of Staggered Quantum Walks (Adapted StQW), which takes place on 2-tessellable graphs, with the goal of efficiently finding a marked vertex by querying an oracle. The Ambainis, Gilyén, Jeffery, and Kokainis' algorithm (AGJK), which provides a quadratic speedup on balanced bipartite graphs, is used as a subroutine in our algorithm. Our approach generalizes existing quantum walk techniques and offers a quadratic speedup in the number of queries needed, demonstrating the utility of our adapted quantum walk models in a broader class of graphs. |
| title | Quantum Search on Bipartite Multigraphs |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.12586 |