PRS ⇒ OWSG
Statement
If pseudorandom quantum state generators with -bit keys and output length for a constant exist, then pure one-way state generators exist — MY22a. The generator keeps and , and accepts with probability , by projecting onto .
Sketch
The projection is efficient: running as a unitary on yields for some junk state , and replacing the first register by and undoing the unitary returns with probability . A distinguisher given copies runs the inverter on of them and projects the last onto ; on PRS copies it accepts with the inverter’s success probability. On copies of a Haar-random it accepts with probability at most , so the inverter’s success probability is negligible — MY22a.
Notes
- The same generator is a pure one-way state generator for output length : with the projector onto the symmetric subspace of , the average of over Haar-random is and , so the distinguisher above accepts Haar-random copies with probability at most — standard.
- Output length suffices for the generator that outputs , verified by projection onto — MY22.