11 papers
Conjugate queries can help
Ewin Tang, John Wright, Mark Zhandry
We give a natural problem over input quantum oracles which cannot be solved with exponentially many black-box queries to and , but which can be solved with const…
On Best-Possible One-Time Programs
Aparna Gupte, Jiahui Liu, Luowen Qian +3
One-time programs (OTPs) aim to let a user evaluate a program on a single input while revealing nothing else. Classical OTPs require hardware assumptions, and even with quantum inf…
Separating QMA from QCMA with a classical oracle
John Bostanci, Jonas Haferkamp, Chinmay Nirkhe +1
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly big…
Impersonating Quantum Secrets over Classical Channels
Luowen Qian, Mark Zhandry
We show that a simple eavesdropper listening in on classical communication between potentially entangled quantum parties will eventually be able to impersonate any of the parties.…
Unclonable Cryptography in Linear Quantum Memory
Omri Shmueli, Mark Zhandry
Quantum cryptography is a rapidly-developing area which leverages quantum information to accomplish classically-impossible tasks. In many of these protocols, quantum states are use…
A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
John Bostanci, Barak Nehoran, Mark Zhandry
Aaronson, Atia, and Susskind (2020) established that efficiently mapping between quantum states and is computationally equivalent to distinguishing their…