1 citations · 1 across the 4 of their papers we have counts for
5 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…
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…
Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
Jin-Yi Cai, Ashwin Maran
We introduce some polynomial and analytic methods in the classification program for the complexity of planar graph homomorphisms. These methods allow us to handle infinitely many l…