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
- Quantum-secure OWF ⇒ PRS: one-way functions secure against quantum adversaries yield PRS generators, by random phase states — JLS18.
- PRS ⇒ QM: with and verification by projection onto , a PRS generator is a private-key quantum money scheme with pure money states — JLS18.
- PRS ⇒ OWSG: a PRS generator, with verification by projection onto , is a pure one-way state generator — MY22a.
- If PRS generators with output length linear in the key exist, then non-interactive quantum bit commitments for classical messages with computational hiding and statistical binding exist, and so do one-time-secure digital signatures with quantum public keys — MY22a. The commitment uses only pseudorandomness for , still with for a constant — MY22a.
- No fully-black-box reduction from PRS to OWF: relative to a quantum oracle, PRS generators with exist and — Kre21.
- No relativizing reduction from single-copy PRS to OWF: relative to a classical oracle, and single-copy-secure PRS generators with , secure against uniform quantum adversaries, exist — KQST23.
- If , no PRS generator with exists — Kre21.
Participates in
Builds on Pseudorandom quantum state
- Exponential-dimension PRS ⇒ PRS (via PRS with exponential dimension)
- Linear-output PRS ⇒ Exponential-dimension PRS (via PRS with output length linear in the key)
- Linear-output PRS ⇒ Single-copy PRS (via PRS with output length linear in the key)
- PRS ⇒ OWSG (via PRS with output length linear in the key)
- PRS ⇒ QM (via PRS with exponential dimension)
Produces Pseudorandom quantum state
- Exponential-dimension PRS ⇒ PRS
- Linear-output PRS ⇒ Exponential-dimension PRS (via PRS with exponential dimension)
- Linear-output PRS ⇒ Single-copy PRS (via Single-copy security)
- Quantum-secure OWF ⇒ PRS (via PRS with output length linear in the key)
Barriers