Pseudorandom quantum state

A pseudorandom quantum state (PRS) generator maps a uniformly random classical key to an -qubit pure state such that, for every polynomial , no efficient quantum adversary distinguishes copies of from copies of a Haar-random -qubit state — JLS18.

Syntax

A PRS generator is a pair of quantum polynomial-time algorithms with output length :

  • , sampling a key ;
  • , a quantum algorithm that on every run outputs the same -qubit pure state .

This is the definition of JLS18, who write the keyed family and its generation algorithm.

Properties

Pseudorandomness

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{prs}}_{\mathsf{PRS},\calA,t}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$; $k \gets \KeyGen(1^\secpar)$
\State run $\mathsf{StateGen}(k)$ $t$ times; $\rho_0 := |\phi_k\rangle\langle\phi_k|^{\otimes t}$
\State sample $|\psi\rangle$ from the Haar measure on $n$-qubit states; $\rho_1 := |\psi\rangle\langle\psi|^{\otimes t}$
\Comment{the ideal world; the challenger need not be efficient}
\State $b' \gets \calA(1^\secpar, \rho_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

is pseudorandom if for all efficient quantum and all polynomials ,

is negligible — JLS18. The ideal state , averaged over , is the maximally mixed state on the symmetric subspace of — standard. The quantum money and one-way state generator results below are proved for the output lengths of the variations below, and the same arguments work for : given copies of a Haar-random -qubit state , every algorithm succeeds with probability at most both at outputting registers that all pass the projection onto and at outputting a classical description of a state such that a fresh copy of passes the projection onto — standard.

Variations

PRS with exponential dimension

A PRS generator has exponential dimension if its output dimension is exponential in : there is a constant with for all sufficiently large . The quantum money theorem of JLS18 assumes it (PRS ⇒ QM). Every such generator is a PRS generator (Exponential-dimension PRS ⇒ PRS) — folklore.

PRS with output length linear in the key

A PRS generator with -bit keys has output length linear in the key if there is a constant with for all sufficiently large , so that . The one-way state generator theorem of MY22a assumes it (PRS ⇒ OWSG). Every such generator has exponential dimension (Linear-output PRS ⇒ Exponential-dimension PRS) — folklore.

Single-copy security

A PRS generator is single-copy secure if its output length satisfies for all sufficiently large and it satisfies pseudorandomness for — KQST23 (Definition 7; MY22a define the notion). The ideal state is then the maximally mixed state . The length condition excludes trivial instances: for , satisfies pseudorandomness for with advantage — MY22a. Every PRS generator with output length linear in the key is single-copy secure (Linear-output PRS ⇒ Single-copy PRS) — folklore.

Other results

Participates in

Builds on Pseudorandom quantum state

Produces Pseudorandom quantum state

Barriers