Two related questions about bounded depth computing:

1. Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem simpler we can assume that all p(i)s are 0,1, or 1/2, or even that all of them are 1/2.)

Now you make a bounded number of computation round. In each round you apply reversible classical gates on disjoint sets of bits. (Fix your favorite set of universal classical reversible gates.)

At the end you get a probability distribution on strings on n bits. Are there results on restriction of such distributions?

I am looking to something analogous to Hastad switching lemme, Boppana result that the total influence is small or LMN theorem.

2. The same question as 1) but with bounded depth quantum circuits.

Two related questions about bounded depth computing:

1. Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem simpler we can assume that all p(i)s are 0,1, or 1/2. or even that all of them are 1/2.)

Now you make a bounded number of computation round. In each round you apply reversible classical gates on disjoint sets of bits. (Fix your favorite set of universal classical reversible gates.)

At the end you get a probability distribution on strings on n bits. Are there results on restriction of such distributions?

I am looking to something analogous to Hastad switching lemme, Boppana result that the total influence is small or LMN theorem.

2. The same question as 1) but with bounded depth quantum circuits.