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.

  • 4
    $\begingroup$ I may be missing something, but isn't the question 1 with all $p(i)$ equal to $1/2$ trivial? You start with a uniform distribution on $\{0,1\}^n$, which is invariant under bijections. $\endgroup$ Commented Nov 30, 2012 at 16:20
  • $\begingroup$ Is the following a useful transformation of your problem? Transform your input (a vector $p_0,p_1,\dots$), to a $2^n$-length vector representing a probability distribution over binary strings of length $n$. Now any computation is a square stochastic matrix acting on (say) the left to produce a probability distribution over output strings of length $n$. WLOG we may suppose all entries are binary. The only question is what is the class of stochastic binary matrices that can be produced via a bounded number of matrix multiplications of our basis matrices (reversible gates). $\endgroup$
    – usul
    Commented Dec 5, 2012 at 16:35
  • $\begingroup$ Sorry, I should be more precise. By a basis matrix here I mean not a reversible gate, but rather some set of reversible gates acting in parallel, and it doesn't seem immediately obvious to me what such matrices would look like given a set of gates. $\endgroup$
    – usul
    Commented Dec 5, 2012 at 17:32
  • $\begingroup$ Both answers deserve the bounty, I will see what I can do $\endgroup$
    – Gil Kalai
    Commented Dec 11, 2012 at 20:59
  • $\begingroup$ what do you mean by "disjoint sets" of bits? $\endgroup$
    – vzn
    Commented Dec 12, 2012 at 22:55

2 Answers 2


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

  • $\begingroup$ Many thanks, Massimo! this looks very relevant. $\endgroup$
    – Gil Kalai
    Commented Nov 30, 2012 at 7:30
  • $\begingroup$ (Also I am as interested in the non reversible case.) $\endgroup$
    – Gil Kalai
    Commented Dec 1, 2012 at 19:36

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.


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$).

  • 1
    $\begingroup$ Dear Niel, Very interesting! Thanks! I am especially interested in the distributions. Can you explain why "This, of course, does not tell you..."? $\endgroup$
    – Gil Kalai
    Commented Dec 9, 2012 at 22:28
  • 1
    $\begingroup$ The constant-factor-inapproximability result holds via PostQNC⁰ = PostBQP = PP. Postselection is used here to "force the success" of a long string of teleportations, to simulate a quantum-poly-depth distribution via a quantum-constant-depth distribution conditioned on an event of extremely low but non-zero probability. Any constant factor of approximation would hold just as well for a poly-depth circuit. But this doesn't tell you, e.g. an upper bound on how much amplitude, in absolute (and asymptotic) terms, is concentrated (or could be projected onto) any particular subspace. $\endgroup$ Commented Dec 10, 2012 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.