9 papers
Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
William Gay, Fernando Granha Jeronimo, Abhi Shukul
In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capaci…
Asymptotically Good Quantum Locally Testable Codes
William Gay, Fernando Granha Jeronimo
We construct explicit families of asymptotically good quantum locally testable codes over qubits. More precseily, we construct explicit quantum LDPC CSS codes over qubits having co…
PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax
William Gay, Fernando Granha Jeronimo, Lenny Liu +3
Pure-state consistency problems naturally lead to quantum proof systems in which a single pure witness must satisfy many acceptance constraints. The corresponding class $\mathsf{Pu…
The Honeycomb Framework for Code Bounds
William Gay, Fernando Granha Jeronimo, Lenny Liu
We introduce the honeycomb hierarchy, a representation-theoretic framework that gives new asymptotic upper bounds on . Its first level is the two-row hyperoctahedral repres…
The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
William Gay, Fernando Granha Jeronimo
Interference and entanglement are among the most fundamental properties of quantum mechanics. In this work, we investigate the power of interference in the role of detecting entang…
Multipass Linear Sketches for Geometric LP-Type Problems
N. Efe Çekirge, William Gay, David P. Woodruff
LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinat…
Sampling and Identity-Testing Without Approximate Tensorization of Entropy
William Gay, William He, Nicholas Kocurek +1
Certain tasks in high-dimensional statistics become easier when the underlying distribution satisfies a local-to-global property called approximate tensorization of entropy (ATE).…
Pseudorandomness Properties of Random Reversible Circuits
William Gay, William He, Nicholas Kocurek +1
Motivated by practical concerns in cryptography, we study pseudorandomness properties of permutations on computed by random circuits made from reversible -bit gates…
Faster Mixing of Higher-Dimensional Random Reversible Circuits
William Gay, William He, Nicholas Kocurek
We continue the study of the approximate -wise independence of random reversible circuits as permutations of . Our main result is the first construction of a natural…