Showing quant-phShow all
2 papers · 1 filter
quant-ph2026
Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
Chandrima Kayal, Sayantan Sen, Dániel Szabó
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexit…
quant-ph2024
Quantum property testing in sparse directed graphs
Simon Apers, Frédéric Magniez, Sayantan Sen +1
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the out…