Showing 2026Show all
3 papers · 1 filter
quant-ph2026
A Sharp Noise Threshold for Shor's Quantum Factoring and Discrete Log Algorithms
Jin-Yi Cai, Ben Young
We study the asymptotic behavior of Shor's quantum factoring and discrete log algorithms when noise affects the precise controlled rotation gates in their quantum Fourier transform…
cs.LO2026
A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability
Radu Curticapean, Daniel Neuen, Amir Nikabadi +2
Two graphs and are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph in . A wide…
cs.CC2026
Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
Jin-Yi Cai, Ashwin Maran, Ben Young
We study the complexity of counting (weighted) planar graph homomorphism problem parametrized by an arbitrary symmetric non-negative real valued matrix .…