Bounded depth probability distributions

Question

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.

Answer 1

There are some relatively recent papers by Emanuele Viola et al., which deal with the complexity of sampling distributions. They focus on restricted model of computations, like bounded depth decision trees or bounded depth circuits.

Unfortunately they don't discuss reversible gates. On the contrary there is often loss in the output length. Nevertheless these papers may be a good starting point.

Bounded-Depth Circuits Cannot Sample Good Codes

The complexity of Distributions

Answer 2

Short answer.

For quantum circuits, there is at least one non-limitation result: arbitrary bounded-depth quantum circuits are unlikely to be simulatable with small multiplicative error in the probability of the outcome, even for polynomial-depth classical circuits.

This, of course, does not tell you what resctrictions $\mathsf{QNC^0}$ circuits will actually have; particularly if you're interested in decision problems with bounded error, rather than probability distributions. However, it does mean that an analysis in terms of decision trees, as with Håstad’s Switching Lemma, is not likely to be in the offing for classical simulation of these circuits.

Details

We may consider the definition of polylog-depth quantum circuits as given by Fenner et al. (2005):

Definition. $\mathsf{QNC^k}$ is the class of quantum circuit families $\{C_n\}_{n\geqslant0}$ for which there exists a polynomial $p$ for which each $C_n$ contains $n$ input qubits and at most $p(n)$ fresh ancillas, uses only single-qubit gates and controlled-not gates, and has depth $O(\log^k(n))$.

The single-qubit gates must be from a fixed finite set, though this suffices to simulate any fixed unitary on a constant number of qubits to any fixed precision. We also allow any subset of the qubits at then end of the circuit to be used to represent the output of the circuit family (e.g. a single qubit for boolean functions).

Bremner, Jozsa, and Sheppard (2010) note (see Section 4) that, using an adaptation of the gate-teleportation technique due to Terhal and DiVincenzo (2004), post-selection on some of the qubits in a $\mathsf{QNC^0}$ circuit makes it possible to decide problems in $\mathsf{PostBQP = PP}$. Using their results on simulating postselected circuits, this implies that the problem of classically sampling from the output distribution of an arbitrary $\mathsf{QNC^0}$ circuit with boolean output, with multiplicative error at most $\sqrt 2$ in the sampling probability, is in impossible with random polynomial depth circuits unless the polynomial hierarchy partially collapses (specifically $\mathsf{PH} \subseteq \Delta_3$).