Real-Valued Somewhat-Pseudorandom Unitaries

ePrint Report: Real-Valued Somewhat-Pseudorandom Unitaries

Zvika Brakerski, Nir Magrafta

We explore a very simple distribution of unitaries: random (binary) phase -- Hadamard -- random (binary) phase -- random computational-basis permutation.
We show that this distribution is statistically indistinguishable from random Haar unitaries for any polynomial set of orthogonal input states (in any basis) with polynomial multiplicity.
This shows that even though real-valued unitaries cannot be completely pseudorandom (Haug, Bharti, Koh, arXiv:2306.11677), we can still obtain some pseudorandom properties without giving …

binary computational distribution eprint report input random real report simple states