7 papers
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…
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…
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 .…
Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem
Jin-Yi Cai, Ben Young
Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets and of tensors (a.k.a. const…
Quantum Algorithms for Discrete Log Require Precise Rotations
Jin-Yi Cai, Ben Young
Recently, Cai showed that Shor's quantum factoring algorithm fails to factor large integers when the algorithm's quantum Fourier transform (QFT) is corrupted by a vanishing level o…
Jack combinatorics of the equivariant edge measure
Kyla Pohl, Ben Young
We study the equivariant edge measure: a measure on partitions which arises implicitly in the edge term in the localization computation of the Donaldson-Thomas invariants of a tori…
The Converse of the Real Orthogonal Holant Theorem
Ben Young
The Holant theorem is a powerful tool for studying the computational complexity of counting problems. Due to the great expressiveness of the Holant framework, a converse to the Hol…