1.5k citations · 3.1k across the 34 of their papers we have counts for
39 papers
Classical Adversarial Fault-Tolerance and PCPs
Anurag Anshu, Nikolas P. Breuckmann, Louis Golowich +2
We show how to compile an arbitrary classical circuit into a fault-tolerant circuit, which performs the desired computation even when an almost-linear number of bits are adversaria…
Fault-Tolerant Quantum Computation with Adversarial Errors
Nikolas P. Breuckmann, Louis Golowich, Umesh Vazirani
We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on logical qudits of depth , we construct a fault…
A polynomial-time classical algorithm for noisy random circuit sampling
Dorit Aharonov, Xun Gao, Zeph Landau +2
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse poly…
Quantum Pseudoentanglement
Scott Aaronson, Adam Bouland, Bill Fefferman +4
Entanglement is a quantum resource, in some ways analogous to randomness in classical computation. Inspired by recent work of Gheorghiu and Hoban, we define the notion of "pseudoen…
Efficient Certifiable Randomness from a Single Quantum Device
Urmila Mahadev, Umesh Vazirani, Thomas Vidick
Brakerski et. al [BCM+18] introduced the model of cryptographic testing of a single untrusted quantum device and gave a protocol for certifiable randomness generation. We use the l…
Deniable Encryption in a Quantum World
Andrea Coladangelo, Shafi Goldwasser, Umesh Vazirani
(Sender-)Deniable encryption provides a very strong privacy guarantee: a sender who is coerced by an attacker into "opening" their ciphertext after-the-fact is able to generate "fa…