The Kolmogorov complexity of a string refers to a deterministic object. Here, I refer to the analogous "complexity of a distribution", or better, to the complexity of sampling from a distribution, in the sense defined this paper: the complexity of the distribution $P$ is the size of the smallest circuit that can generate the samples with (an approximate) probability $P$, having random bits as input.
Edited as requested by forky40 and jecado
Consider a family of quantum circuits $C_i$; the $i$-th is composed by $m_i$ one- and two-qubit gates and operates on $n_i$ qubits, respectively. I assume that $m_i < f(n_i)$ for a given polynomial $f$. Apply the circuits to the state $\left|0\right>$, obtaining $C_i\left|0\right>$. Call $P_i(x)$ the probability distribution of getting a classical string of bits $x$ from the measurement of the qubits.
I'm asking to give an upper bound of the complexity of $P(x)$, asymptotically in $n$. Of course, it is easy to find a quantum circuit family which gives a very trivial distribution $P(x)$, with small complexity, but here I'm asking to give an upper bound.
Please notice: the problem is subtly different from simulating a quantum circuit with a classical one. For example, take the quantum circuit used in Shor's algorithm. The outcome of the Shor's algorithm is difficult to calculate by classical computers, so probably it cannot be simulated by a classical circuit polynomial in $n$. However, it is still possible that, once the result of the whole algorithm (the factorization) is known, then a specific circuit (polynomial in $n$) can be built.
I think that a trivial upper bound can be found: it's exponential in $n$, independently on $m$. On the other hand, I found several examples of quantum circuits leading to distributions with complexity polynomial in $n$. Is there an example with larger asymptotic complexity?
