5 papers
Random-Oracle Unitary Synthesis is Impossible
Andrew Huang, Akshar Ramkumar, John Wright
A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any cla…
Does Not Relativize
Adam Bouland, Andrew Huang, Anand Natarajan +2
We construct an oracle relative to which , resolving a long-standing open question in quantum complexity theory. Together with recent work d…
A quantum oracle separation between QMA(2) and QMA
John Bostanci, Sabee Grewal, Jonas Haferkamp +4
We find a quantum oracle relative to which . As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every , any $(ε,…
Separating Quantum and Classical Advice with Good Codes
John Bostanci, Andrew Huang, Vinod Vaikuntanathan
We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof () and the class of languages that can…
A Simple and Efficient One-Shot Signature Scheme
Andrew Huang, Vinod Vaikuntanathan
One-shot signatures (OSS) are a powerful and uniquely quantum cryptographic primitive which allows anyone, given common reference string, to come up with a public verification key…