Pseudorandomness Properties of Random Reversible Circuits

Motivated by cryptography, quantum information theory, and circuit complexity, there has been significant recent progress in the study of random permutations resembling a completely random permutation of n-bit strings. Of particular interest is the case where the measure of "resemblance" is approximation of the k-th moments of the matrix representations. Such random permutations are known as approximate k-wise independent permutations.

In this talk I will discuss some recent results that show that small random reversible circuits compute approximate k-wise independent permutations:

i) We show that a random reversible circuit with \tilde{O}(nk) gates computes a constant-approximate k-wise independent permutation. This result implies a generalization of Shannon's circuit lower bound argument.

ii) We show that a random reversible circuit with \tilde{O}(nk^2) layers of 1D-local gates arranged in a brickwork architecture computes a n exp(-nk)-approximate k-wise independent permutation. Using this, we show that a random reversible circuit with \tilde{O}(\sqrt{n}k^3) layers of 2D-local gates arranged in a brickwork architecture computes a exp(-n^{1/2} k)-approximate k-wise independent permutation.