<h3>Short answer.</h3>

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

<p>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 <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=811">Håstad’s Switching Lemma</a>, is not likely to be in the offing for classical simulation of these circuits.</p>

<h3>Details</h3>

<p>We may consider the definition of polylog-depth quantum circuits as given by <a href="http://arxiv.org/abs/quant-ph/0312209">Fenner et al. (2005)</a>:</p>

<blockquote>
  <p><em>Definition.</em> $\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))$.</p>
</blockquote>

<p>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.&nbsp;a&nbsp;single qubit for boolean functions).</p>

<p><a href="http://arxiv.org/abs/1005.1407">Bremner, Jozsa, and Sheppard (2010)</a> note (see Section 4) that, using an adaptation of the gate-teleportation technique due to <a href="http://arxiv.org/abs/quant-ph/0205133">Terhal and DiVincenzo (2004)</a>, 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$). </p>

CC BY-SA 3.0
2012-12-09T22:28:40.217Z
Dear Niel, Very interesting! Thanks! I am especially interested in the distributions. Can you explain why "This, of course, does not tell you..."?
Gil Kalai
CC BY-SA 3.0
2012-12-10T15:10:34.210Z
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.
Niel de Beaudrap
CC BY-SA 3.0
2012-12-09T20:46:22.403Z
2012-12-09T20:46:22.403Z
Niel de Beaudrap
<p>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.</p>

<p>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.</p>

<p><a href="http://link.springer.com/article/10.1007/s00037-012-0039-3">Bounded-Depth Circuits Cannot Sample Good Codes</a></p>

<p><a href="http://epubs.siam.org/doi/abs/10.1137/100814998?journalCode=smjcat">The complexity of Distributions</a></p>

CC BY-SA 3.0
2012-11-30T07:30:08.580Z
Many thanks, Massimo! this looks very relevant.
Gil Kalai
CC BY-SA 3.0
2012-12-01T19:36:57.027Z
(Also I am as interested in the non reversible case.)
Gil Kalai
CC BY-SA 3.0
2012-11-30T01:22:02.050Z
2012-11-30T08:00:39.437Z
2012-11-30T08:00:39.437Z
MassimoLauria
<p>Two related questions about bounded depth computing:</p>

<p>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. <del>or even that all of them are 1/2.</del>)</p>

<p>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.)</p>

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

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

<p>2) The same question as 1) but with bounded depth quantum circuits. </p>

CC BY-SA 3.0
2012-11-30T16:20:31.057Z
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.
Klaus Draeger
CC BY-SA 3.0
2012-12-05T16:35:24.173Z
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).
usul
CC BY-SA 3.0
2012-12-05T17:32:36.423Z
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.
usul
CC BY-SA 3.0
2012-12-11T20:59:30.630Z
Both answers deserve the bounty, I will see what I can do
Gil Kalai
CC BY-SA 3.0
2012-12-12T22:55:53.740Z
what do you mean by "disjoint sets" of bits?
vzn
CC BY-SA 3.0
2012-12-13T00:30:29.737Z
this reminds me of matrix rigidity which can be related to circuit depth/complexity by an interesting thm of razborov
vzn
CC BY-SA 3.0
2012-12-13T23:17:27.180Z
@GilKalai: You are quite generous, thank-you.
Niel de Beaudrap
<cc.complexity-theory><quantum-computing><circuit-complexity><randomness><circuit-depth>
Bounded depth probability distributions
Gil Kalai
# Bounded depth probability distributions

(Asked by: username_0 on 2012-11-29)

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.

**Tags:** cc.complexity-theory, quantum-computing, circuit-complexity, randomness, circuit-depth
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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).  
> **username_2**: 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.  
> **username_0**: Both answers deserve the bounty, I will see what I can do  
> **username_3**: what do you mean by "disjoint sets" of bits?  
> **username_3**: this reminds me of matrix rigidity which can be related to circuit depth/complexity by an interesting thm of razborov  
> **username_4**: @GilKalai: You are quite generous, thank-you.  

---

## 2 answers

### Answer by username_5 on 2012-11-30. Score: 14 | Accepted answer

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](http://link.springer.com/article/10.1007/s00037-012-0039-3)

[The complexity of Distributions](http://epubs.siam.org/doi/abs/10.1137/100814998?journalCode=smjcat)

> **Comments:**
> **username_0**: Many thanks, Massimo! this looks very relevant.  
> **username_0**: (Also I am as interested in the non reversible case.)  

---

### Answer by username_4 on 2012-12-09. Score: 12

### 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](http://www.contrib.andrew.cmu.edu/~ryanod/?p=811), 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)](http://arxiv.org/abs/quant-ph/0312209):

> *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)](http://arxiv.org/abs/1005.1407) note (see Section 4) that, using an adaptation of the gate-teleportation technique due to [Terhal and DiVincenzo (2004)](http://arxiv.org/abs/quant-ph/0205133), 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$).

> **Comments:**
> **username_0**: Dear Niel, Very interesting! Thanks! I am especially interested in the distributions. Can you explain why "This, of course, does not tell you..."?  
> **username_4**: 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.  

---

