Multiparticle quantum walks for distinguishing hard graphs
Sachin Kasture, Shaheen Acheche, Loic Henriet, Louis-Paul Henry · 2025
Read Multiparticle quantum walks for distinguishing hard graphs by Sachin Kasture, Shaheen Acheche, Loic Henriet, Louis-Paul Henry (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-03683.txt.
Description
Sachin Kasture, Shaheen Acheche, Loic Henriet, and Louis-Paul Henry use quantum walks to tell look-alike graphs apart, in a 2025 paper. Deciding whether two networks are truly the same shape — the graph isomorphism problem — is a classic hard nut. Standard classical tests fail on crafted families of graphs that mimic each other closely.
A quantum walk sends particles wandering a graph under quantum rules, and their interference pattern betrays the graph's structure. The team prove that walks with several particles, started in spread-out states, can separate the hard CFI graph family that fools classical tests. Localized starts also work with one fewer particle. Extra results cover highly symmetric graphs, adding quantum tools to a long-running contest.
Catalog record
| CREATOR | Sachin Kasture, Shaheen Acheche, Loic Henriet, Louis-Paul Henry |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-03683