1 citations · 1 across the 12 of their papers we have counts for
4 papers · 1 filter
A classical oracle separation between QMA and QMA(2)
Sabee Grewal, Saachi Mutreja, Kabir Tomer
We exhibit a classical oracle relative to which QMA \neq QMA(2). The separation is based on a separable Hamiltonian problem defined by signed edge constraints on a graph. The YES i…
Certified Randomness with Optimal Rate
Siddhartha Jain, Saachi Mutreja, Bhaskar Roberts
The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require ne…
Unconditional Certified Randomness without Structure
Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja +3
We obtain a certified randomness protocol in the quantum random oracle model. The protocol is non-interactive and publicly verifiable with a classical verifier, and is based on Yam…
Parallel Quantum Advantage with Limited Adaptivity Requires Structure
Qipeng Liu, Saachi Mutreja
Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any -query quantum algori…