4
$\begingroup$

We can strongly simulate a quantum circuit if we can estimate the probability of measuring $|0^n\rangle$, say, at the end to within some fixed relative error.

Now, by measurement, a quantum computer can certainly weakly simulate itself, i.e. sample from its own output distribution. Naively, I had also thought quantum computers to be able to strongly simulate itself.

However, I watched this talk recently by David Gosset: Classical simulation of quantum circuits via stabilizer rank where he claims this is not true (see 1 minute onwards). In particular, he seems to be saying strong simulation is $P^{\#}$-hard which implies quantum computers can't do it. Could someone please provide me with some reference to what he is saying?

$\endgroup$
9
$\begingroup$

Apart from the formal result about #P-hardness, there's something worth touching on, about the nature of strong simulation itself. I'll comment first on strong simulation, and then specifically on the quantum case.

1. Strong simulation even of classical randomised computation is hard

Strong simulation is a very powerful concept — not only in the fact that it is a useful concept to consider, but in the more practical sense that it would allow you to do very powerful computations, even if you could do it in a purely classical setting.

At issue here is that a process with random outcomes — whether or not it is quantum — does not automatically come equipped with a way to compute the probabilities of its events; not even for the probabilities of the events which you actually see realised. The power of randomised computation, so to speak, is that you don't have to worry much about what the precise probability of an event is: it suffices to sample and attempt to realise that event sufficiently often to be confident of roughly what that probability is (or, for instance, just that the probability is non-zero).

Asking for actual probabilities is a very, well, strong requirement to ask of a simulation, in the following sense:

Proposition. Strongly simulating a polynomial-time randomized computation with zero error is #P-hard.

  • Proof: For any non-deterministic Turing machine N, consider the question of how many branches it accepts on for an input $x \in \{0,1\}^m$. It is enough for us to consider the case where N makes a non-deterministic choice at every transition, and runs for time $m \in \mathrm{poly}(n)$ in every branch, so that the branches of the computation can be indexed by the strings $z \in \{0,1\}^m$. The computation performed by N can be represented similarly as a deterministic computation (a function $f$) depending on the input $x$ and a given branch string $z$. If we represent the status of 'accept' vs. 'reject' by a bit $a \in \{0,1\}$ which is computed as $a = f(x,z)$.

    Determining the number of branches $z \in \{0,1\}^m$, for which $f(x,z) = a$ for a given $x \in \{0,1\}^n$, is essentially the canonical #P-complete problem, using this connection to non-deterministic Turing machines.

    Consider a polynomial-time randomised computation. We can describe this computation as a deterministic classical computation, performed with the help of a uniformly random bit-string of length $m$. Suppose that we are interested in whether a particular bit yields the outcome '1'. For an input $x \in \{0,1\}^n$ and random bit-string $z \in \{0,1\}^m$, let $f(x,z) \in \{0,1\}$ be the value that this bit takes: then $f(x,z)$ can be computed in polynomial time. The probability $P(a)$ that this computation gives the result $a \in \{0,1\}$ is then $$ P(a) = \frac{\# \bigl\{ z \in \{0,1\}^m \;\big|\; f(x,z) = a \bigr\}}{2^m}\,. $$ Because we could choose $f$ to be the function determining the acceptance condition of a non-deterministic Turing machine on input $x$ in branch $z$, then it is #P-complete to compute $P(a)$ exactly.

Proposition. Strongly simulating a polynomial-time randomized computation, with any relative error, is NP-hard.

  • Proof. An important corner-case of the problem of approximating a probability with relative error, is the case where the exact probability is equal to zero. In this case, any process which gives the correct probability up to any multiplicative factor must correctly produce the exact probability, if that probability happens to be 0. Similarly, any process which approximates an event with positive probability up to a positive scalar factor, must yield a probability estimate which is greater than zero. That process can then be used to determine whether the number of accepting branches of a non-deterministic Turing machine is zero or non-zero.

From these two observations, you should take away the idea that strong simulation is a strong requirement — in many cases, unfairly strong — to make of a simulation method: it allows you to do much more powerful things than the computational model itself might be capable of.

2. Strong simulation of quantum computation is very hard

One difference between classical and quantum computation is on how difficult we think it is (in a complexity-theoretic sense) to strongly simulate them.

We know that it is NP-hard to strongly simulate a polynomial-time classical randomised process to relative error less than 1. Simulating a quantum process isn't going to be any easier. However, there is reason to believe that even with unreasonably powerful computational resources which would allow us to strongly simulate classical processes with bounded relative error, it will still be difficult to strongly simulate quantum processes.

Theorem (Stockmeyer [1]). For any counting problem in #P, and any constant $d \geqslant 0$ constant, the problem of computing the counting problem within to a $(1 + O(n^{-d}))$ factor is in $\mathbf{FP^{\:\!NP^{\:\!NP}}}$.

The difficulty in the q quantum case is that while classical probabilities correspond to counting the number of accepting branches of a non-deterministic Turing machine, quantum computation corresponds more closely to counting the difference between the number of accepting and rejecting branches of a non-deterministic Turing machine. That is, where a classical probability corresponds to a #P function, a quantum amplitude corresponds to a GapP function, which is the set of functions which may be expressed as a difference between two #P functions. The connection between quantum computation and GapP may be made formal, but on a high level, it is essentially because quantum computation can involve destructive interference between amplitudes associated with different events. More formally:

Proposition (Liberal paraphrase of Theorem 3.2 of [2]). For any $f \in \mathbf{GapP}$, there is a polynomial-time quantum algorithm $Q$, with an accepting configuration $c$, and a polynomial $p$ such that, for all $x \in \{0,1\}^n$, $\langle c | Q | x \rangle = -f(x) \cdot 2^{-p(n)/2}$.

Approximating GapP functions even to constant factors is difficult, because computing a GapP function to within even a constant factor determines whether it is positive or negative. If you can do this, you can immediately solve the PP-complete problem of determining whether or not the number of accepting paths is greater than the number of rejecting paths; and if you do it repeatedly, with a number of related quantum computations in which you artificially inflate the number of accepting or rejecting paths by doing your quantum computation conditionally, you can compute the exact GapP function essentially by binary search (the same way you can find a satisfying solution to a boolean formula, if one exists, given an oracle which simply tells you whether a solution exists).

References

In addition to the references mentioned above, Maarten Van den Nest's article [3] mentioned by Martin Schwarz is noteworthy for presenting the first definition of 'strong simulation' of quantum systems (to distinguish it from the more reasonable standard of weak simulation), and also for presenting a number of ideas of the links between classical and quantum computation in the context of simulation.

  1. Stockmeyer.
    The complexity of approximate counting.
    Proceedings of STOC '83 (pp.&thinsp.118-126), 1983.
    [PDF available at acm.org]

  2. Fenner, Green, Homer, and Pruim.
    Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy.
    Proceedings of the Royal Society London A vol. 455 (pp. 3953–3966), 1999.
    [arXiv:quant-ph/9812056]

  3. Van den Nest.
    Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond.
    Quantum Information and Computation, vol. 10 (pp. 258-271), 2010.
    [arXiv:0811.0898].

$\endgroup$
  • $\begingroup$ Thanks for such a detailed answer, I understand BQP is contained in P#, is the containment proven to be strict? $\endgroup$ – dcw Apr 2 at 3:23
  • $\begingroup$ Great, that cleared things up! $\endgroup$ – dcw Apr 2 at 13:07
  • 2
    $\begingroup$ So, technically, $\mathbf{BQP}$ is a decision class and $\mathbf{\#P}$ is a function class, so that the more correct statement is just that $\mathbf{BQP \subseteq P^{\#P}}$. But as usual in complexity theory, we cannot prove whether the containment is strict. $\endgroup$ – Niel de Beaudrap Apr 2 at 16:09
3
$\begingroup$

Could someone please provide me with some reference to what he is saying?

Here is a reference to a discussion of this and related questions:

Quant. Inf. Comp. 10, 3-4 pp. pp0258-0271 (2010), or https://arxiv.org/abs/0811.0898

$\endgroup$

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.