Commitments to Quantum States


Fermi Ma


Vinod Vaikuntanathan
What does it mean to commit to a quantum state? In this
talk, I will present a simple, but perhaps counterintuitive answer: a
quantum state commitment (QSC) is binding if sending the commitment
erases the committed message from the sender’s view. Using this new
definition, I will show how to construct the first succinct QSCs,
which can be seen as an analog of collision-resistant hashing for
quantum messages.

Commitments to quantum states open the door to many new cryptographic
possibilities. Our flagship application is a quantum-communication
version of Kilian's succinct arguments for any language that has
quantum PCPs with constant error and polylogarithmic locality.
Plugging in the PCP theorem, this yields succinct arguments for NP
under significantly weaker assumptions than required classically;
moreover, if the quantum PCP conjecture holds, this extends to QMA. At
the heart of our security proof is a new rewinding technique for
extracting quantum information.

Joint work with Sam Gunn, Nathan Ju, and Mark Zhandry.