The Entire Quantum Computer on a Classical Leash
Yael Tauman Kalai, Dakshita Khurana, Justin Raizes
Resolves two named open problems with a general classical-client quantum 2PC from LWE and yields a broad toolkit of applications, tempered by ε-simulation and heavy proof dependence on very recent primitives.
Abstract
We show that a classical client with no quantum hardware can use a single untrusted and potentially malicious quantum server as if it were its own trusted quantum computer. Through the server, the client can privately choose and run quantum computations, prepare quantum states, and process quantum states supplied by other parties. It can also keep quantum memory on the server, hidden from the server itself, and use that memory in later computations so its quantum state persists across rounds of interaction. Together, these capabilities let a purely classical party act as a quantum party in a variety of interactive protocols. We expect this virtual quantum computer to be a broadly useful tool. As immediate applications, we resolve two known open problems: (1) classical verification of quantum sampling with negligible computational soundness error, and (2) remote state preparation of arbitrary efficiently preparable quantum states. Underlying all of these results is a general-purpose, maliciously secure two-party computation protocol between a classical client and a quantum server, which we construct assuming only the post-quantum hardness of learning with errors.
AI Impact Assessments
(1 model)Core Contribution
The paper gives a general-purpose, maliciously secure (against the quantum party) two-party computation protocol between a classical client and a single untrusted quantum server. It assumes only post-quantum LWE. The functionality is "state-preserving": the client privately chooses a circuit, the server supplies a quantum input, and the client gets classical outputs while the server gets quantum outputs. Sequential composition adds persistent private quantum memory on the server. In effect, a classical party gets a "virtual trusted quantum computer".
Two headline open problems are resolved:
The security notion is ε-simulation. For every inverse-polynomial ε there is a poly(1/ε)-time simulator, while the protocol itself is independent of ε. This suffices for any efficiently falsifiable game, which gives negligible loss in applications. It falls short of full negligible simulation.
The technical stack is layered:
1. An input-preserving 2PC for constant-degree F2 polynomials, built from NTCFs plus witness-preserving arguments (KKR26) with indistinguishable extraction (LMS22-style). A multi-column attack is fixed by a randomized redundant input encoding, and Lemma 10 gives a "distinguishing-gap transport" argument.
2. A remote state preparation protocol for coset states with simulation security given membership oracles. It uses a three-round R⊂S⊂T trick and avoids the poly(1/N) loss of earlier rigidity-based approaches.
3. Classical commitments to quantum states with continual ideal binding and recovery, obtained by RSP-ing the BBV24/HT25 coset authentication code and using teleportation.
4. Certified history-state commitments, combined with circuit-private QFHE, for general quantum circuits.
5. Persistent memory via authentication under fresh keys.
Applications include:
Methodological Rigor
The proofs follow standard cryptographic hybrid arguments, and the structure looks careful. Examples include the explicit handling of the simulation-error parameter, the query-preserving continual-binding simulator, and the gentle-measurement bounds in the history-state analysis. The coset-RSP hybrids (Hyb0–Hyb12) are detailed and plausible.
Several caveats limit confidence:
Potential Impact
If correct, this is a major capstone result in the "classical control of quantum devices" line (Mahadev, GV19, CLLW22, GKNV25, KKR26). It shows that essentially any quantum-cryptographic protocol with a quantum party can be dequantized on the client side, at least for falsifiable security. This should become a reusable compiler in quantum cryptography: unclonable cryptography, quantum money, key leasing, obfuscation, certified deletion, and proofs of quantumness-style protocols. It also directly closes two named open problems and gives a cleaner conceptual framing ("virtual quantum computer"). Practical impact is limited by the use of QFHE, NTCFs, and history states, which are far from implementable. The audience is mainly theoretical cryptographers and quantum complexity theorists.
Timeliness
Classical-client quantum cryptography is an active frontier, and the negligible-error barrier was an acknowledged bottleneck. The paper builds on very recent advances: witness-preserving arguments, coset-state authentication, and continual-binding commitments. Its timing and fit are excellent.
Strengths
Limitations
Other observations
The paper is purely theoretical, so reproducibility is not applicable in the empirical sense. The protocol is fully specified, but it is intricate.
Generated Oct 26, 2026
Comparison History (0)
Resolves two named open problems with a general classical-client quantum 2PC from LWE and yields a broad toolkit of applications, tempered by ε-simulation and heavy proof dependence on very recent primitives.