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?

  • 1
    $\begingroup$ This might be more approachable if you ask about a specific circuit or family of circuits. A sequence of $m$ gates can describe just about any quantum circuit, including trivial ones that output only the all-zeros bitstring. $\endgroup$
    – forky40
    Nov 17, 2021 at 18:35
  • 1
    $\begingroup$ I think that you are implicitly assuming the $m$ quantum gates are arbitary one- or two-qubit gates? Of course an arbitrary $n$ qubit gate can prepare any $2^n$-state superposition, so applying $m$ such gates wouldn't change the upper bound. $\endgroup$
    – jecado
    Nov 17, 2021 at 21:49
  • 1
    $\begingroup$ Yes! For arbitrary $n$ qubit gates, the upper bound is likely the trivial one, exponential in $n$. I further edit the text. $\endgroup$ Nov 17, 2021 at 21:56
  • 1
    $\begingroup$ Just spitballing, a problem outside of NP but still in BQP might work. Factoring is in both NP and BQP - because it's in NP we can use the NP certificate to build our polynomially-sized circuit as you suggest. Perhaps having a circuit that samples from a distribution related to the Jones polynomial might be superpolynomial. $\endgroup$
    – Mark S
    Nov 19, 2021 at 21:07
  • $\begingroup$ The idea looks sound. In any case, discussing the complexity for the circuit used for Jones polynomial would be valuable: whatever is the answer (polynomial or superpolynomial) we learn something. Could you please expand a bit the concept, maybe as an answer? It's a hard subject and any help is welcome. $\endgroup$ Nov 21, 2021 at 17:40

1 Answer 1


I did not find the solution myself but it was given by a personal communication by the author of this paper on linear optics quantum computing.

Section 4.3 describes a set of distributions that can be generated by a quantum computer, but that cannot be sampled classically, even by providing a polynomially-sized input encoding some information on the quantum state.

This is the requested example with "complexity larger than polynomial".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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