Search papers, labs, and topics across Lattice.
This paper investigates the relationship between statistical and computational pseudorandomness in quantum information, revealing that statistical pseudorandomness is not a prerequisite for computationally pseudorandom unitaries (PRUs). By introducing ensembles that are distinct but not statistically random, the authors construct new non-adaptively secure PRU ensembles that achieve computational pseudorandomness without relying on unitary designs. The study characterizes distinctness through an entangled analogue of anticoncentration, providing insights into coherence and imaginarity constraints of PRUs and identifying conditions for real-valued PRUs in certain entangled states.
Statistical randomness isn't needed for computational pseudorandomness in quantum unitaries, challenging existing assumptions in the field.
Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary $2$-design layer in the existing constructions with ensembles that are not even state $1$-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a $2$-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.
