5 papers
Private Proofs of When and Where
Uma Girish, Greg Gluch, Shafi Goldwasser +3
Position verification schemes are interactive protocols where entities prove their physical location to others; this enables interactive proofs for statements of the form "I am at…
Computer Science Challenges in Quantum Computing: Early Fault-Tolerance and Beyond
Jens Palsberg, Jason Cong, Yufei Ding +7
Quantum computing is entering a period in which progress will be shaped as much by advances in computer science as by improvements in hardware. The central thesis of this report is…
Magic and communication complexity
Uma Girish, Alex May, Natalie Parham +1
We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communicatio…
Random Unitaries in Constant (Quantum) Time
Ben Foxman, Natalie Parham, Francisca Vasconcelos +1
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work ha…
QMA vs. QCMA and Pseudorandomness
Jiahui Liu, Saachi Mutreja, Henry Yuen
We study a longstanding question of Aaronson and Kuperberg on whether there exists a classical oracle separating from . Settling this question in eith…