Multiparticle quantum walks for distinguishing hard graphs
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_ | 1866912283692630016 |
|---|---|
| author | Kasture, Sachin Acheche, Shaheen Henriet, Loic Henry, Louis-Paul |
| author_facet | Kasture, Sachin Acheche, Shaheen Henriet, Loic Henry, Louis-Paul |
| contents | Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03683 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multiparticle quantum walks for distinguishing hard graphs Kasture, Sachin Acheche, Shaheen Henriet, Loic Henry, Louis-Paul Quantum Physics Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs). |
| title | Multiparticle quantum walks for distinguishing hard graphs |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2501.03683 |