1.5k citations · 3.1k across the 34 of their papers we have counts for
36 papers · 1 filter
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…
Interactive Protocols for Classically-Verifiable Quantum Advantage
Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis +15
Achieving quantum computational advantage requires solving a classically intractable problem on a quantum device. Natural proposals rely upon the intrinsic hardness of classically…