Saachi Mutreja

Published Papers

1.  Parallel Quantum Advantage with Limited Adaptivity Requires Structure

with Qipeng Liu

SODA 2027

2. Classical Obfuscation of Quantum Circuits via Publicly Verifiable QFHE

with James Bartusek, Aparna Gupte, and Omri Shmueli

FOCS 2026, Talk at TQC 2026

3. CountCrypt: Quantum Cryptography between QCMA and PP

with Eli Goldin, Tomoyuki Morimae, and Takashi Yamakawa

TCC 2026

4. Covert Quantum Learning: Privately and Verifiably Learning from Quantum Data

with Abhishek Anand, Matthias C. Caro, and Ari Karchmer

QTML 2026

5. Revocable Encryption, Programs, and More: The Case of Multi-Copy Security

with Prabhanjan Ananth and Alexander Poremba

ITC 2025

6.  Quantum State Group Actions

with Mark Zhandry

CRYPTO 2025

7. QMA vs. QCMA and Pseudorandomness

with Jiahui Liu and Henry Yuen

STOC 2025

8.  On black-box separations of quantum digital signatures from pseudorandom states

with Andrea Coladangelo

TCC 2024

9. On the Communication Complexity of Secure Multi-Party Computation With Aborts

with James Bartusek, Thiago Bergamaschi, Seri Khoury, and Orr Paradise

PODC 2024

10. Extracting Randomness from Samplable Distributions, Revisited

with Marshall Ball, Eli Goldin, and Dana Dachman-Soled

FOCS 2023 (Invited Highlights Talk at ITC 2024)

11.  Robustness for Space-Bounded Statistical Zero Knowledge

with Eric Allender, Jacob Gray, Harsha Tirumala, and Pengxiang Wang

RANDOM 2023

12. PAC Verification of Statistical Algorithms

with Jonathan Shafer

COLT 2023

13. Improved Semi-Quantum Key Distribution with Two Almost-Classical User

with Walter Krawec

Quantum Information Processing, Volume 21

Manuscripts

14. Certified Randomness with Optimal Rate

with Siddhartha Jain, Bhaskar Roberts

15. Unconditional Certified Randomness without Structure

with Andrea Coladangelo, Dakshita Khurana, Bhaskar Roberts, Joseph Slote, Avishay Tal

16. A classical oracle separation between QMA and QMA(2)

with Sabee Grewal, Kabir Tomer