Author

Saachi Mutreja

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Aug 2026

Unconditional Certified Randomness without Structure

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 Yamakawa and Zhandry's proof of quantumness [JACM'24]. We prove unconditional security of this protocol against adversaries making subexponenti...

A. Coladangelo, Dakshita Khurana, Saachi Mutreja et al. · 0 citations

Preprint Aug 2026

Parallel Quantum Advantage with Limited Adaptivity Requires Structure

Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any $T$-query quantum algorithm, its acceptance probability can be approximated on a $(1-\delta)$ fraction of inputs, up to $\epsilon$ additive error, using $\mathrm{po...

Qi-Peng Liu, Saachi Mutreja · 1 citation · ⚡1