Quantum pseudorandom states differ fundamentally from pseudorandom unitaries

Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States

Cryptography and Security

Summary

Quantum computers can create special random-like objects called pseudorandom states and pseudorandom unitaries, which are important for cryptography and computing. This paper finds that the strongest forms of pseudorandomness for quantum states do not automatically give you the simplest forms of pseudorandomness for quantum unitaries, even if you have a lot of extra resources. The authors use a new idea of studying changes (derivatives) in how these quantum operations work to prove this difference. This shows a basic separation between two kinds of quantum pseudorandomness that was not clear before.

What this means in practice

  • For quantum cryptography engineers: Clarify the limits of generating quantum pseudorandom unitaries from pseudorandom state sources to ensure secure protocol design.
  • For quantum algorithm designers: Identify that certain pseudorandom quantum states cannot be converted into pseudorandom unitaries, guiding algorithmic resource choices.

A theory result. No direct application yet.

Authors

Minki Hhan

Abstract

Quantum computation gives rise to new pseudorandom primitives for states and unitaries, including pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs), and pseudorandom unitaries (PRUs). In this paper, we show a full unitary oracle separation between PRFSGs and PRUs. The separation holds between the strongest state notion and the weakest unitary notion: even adaptively secure, quantum-accessible PRFSGs do not imply non-adaptively secure, forward-only PRUs, even when their implementations are allowed to be non-unitary and use an arbitrary number of ancillary qubits. This reveals a fundamental distinction between pseudorandomness for quantum states and for quantum unitaries. Our main technical idea is to view a candidate PRU construction with access to state generation oracles as a map from the underlying oracle states to implemented unitaries, and to study the derivatives of this map. These derivatives are inherently low rank, and we exploit this low-rank structure to distinguish the resulting unitaries from truly random ones. We believe this differential perspective may be useful for studying other structural questions about quantum states and unitaries.
View PDFOpen arXiv