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

CREATORSachin Kasture, Shaheen Acheche, Loic Henriet, Louis-Paul Henry
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-03683

Browse the full library · About the Tower of Babel