1 citations · 1 across the 12 of their papers we have counts for
14 papers
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…
Covert Quantum Learning: Privately and Verifiably Learning from Quantum Data
Abhishek Anand, Matthias C. Caro, Ari Karchmer +1
Quantum learning from remotely accessed quantum compute and data must address two key challenges: verifying the correctness of data and ensuring the privacy of the learner's data-c…
Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE
James Bartusek, Aparna Gupte, Saachi Mutreja +1
A classical obfuscator for quantum circuits is a classical program that, given the classical description of a quantum circuit , outputs the classical description of a functional…
QMA vs. QCMA and Pseudorandomness
Jiahui Liu, Saachi Mutreja, Henry Yuen
We study a longstanding question of Aaronson and Kuperberg on whether there exists a classical oracle separating from . Settling this question in eith…
Quantum State Group Actions
Saachi Mutreja, Mark Zhandry
Cryptographic group actions are a leading contender for post-quantum cryptography, and have also been used in the development of quantum cryptographic protocols. In this work, we e…
CountCrypt: Quantum Cryptography between QCMA and PP
Eli Goldin, Tomoyuki Morimae, Saachi Mutreja +1
We construct a unitary oracle relative to which but quantum-computation-classical-communication (QCCC) commitments and QCCC multiparty non-interactive…
Revocable Encryption, Programs, and More: The Case of Multi-Copy Security
Prabhanjan Ananth, Saachi Mutreja, Alexander Poremba
Fundamental principles of quantum mechanics have inspired many new research directions, particularly in quantum cryptography. One such principle is quantum no-cloning which has led…
On the Communication Complexity of Secure Multi-Party Computation With Aborts
James Bartusek, Thiago Bergamaschi, Seri Khoury +2
A central goal of cryptography is Secure Multi-party Computation (MPC), where parties desire to compute a function of their joint inputs without letting any party learn about t…
On black-box separations of quantum digital signatures from pseudorandom states
Andrea Coladangelo, Saachi Mutreja
It is well-known that digital signatures can be constructed from one-way functions in a black-box way. While one-way functions are essentially the minimal assumption in classical c…
PAC Verification of Statistical Algorithms
Saachi Mutreja, Jonathan Shafer
Goldwasser et al. (2021) recently proposed the setting of PAC verification, where a hypothesis (machine learning model) that purportedly satisfies the agnostic PAC learning objecti…
Improved Semi-Quantum Key Distribution with Two Almost-Classical Users
Saachi Mutreja, Walter O. Krawec
Semi-quantum key distribution (SQKD) protocols attempt to establish a shared secret key between users, secure against computationally unbounded adversaries. Unlike standard quantum…