1
$\begingroup$

There is something fundamental I don’t understand about quantum computing and hence the following question may be very trivial or stupid for which I apologize in advance.

A boolean function $f:\{0,1\}^n \to \{0,1\}$ has a certain (classical) complexity (say with respect to the basis $\{and, or, not\}$) which is defined as the smallest number of gates (i.e. the size of the circuit) in a classical circuit using only $and$, $or$, and $not$ and which computes $f$.

Say a quantum circuit computes $f$ if applied to the initial state $e_{x0^r}$ with $x\in\{0,1\}^n$ it ends in a quantum state where the probablility of measuring $f(x)$ is $\geq \frac{3}{4}$. Moreover, say the quantum circuit complexity is the smallest number of quantum gates (using only some from a basis, say, and let’s also call this the size as well) needed for computing $f$.

I have two questions:

  1. If I am not mistaken, I have read/heard at somewhere that one can ‘obviously emulate’ a quantum circuit of size $k$ by a classical circuit of size $2^k$. (‘Emulated‘ means here that the same boolean function is computed.) Why is this trivial, if it is true? :) Is quantum circuit complexity as defined above at least bounded by the logarithm of the classical circuit complexity?

  2. This question is about ‘the other direction’ and as a motivation for quantum circuits it is even more interesting to me: Can a classical circuit of size $2^k$ be emulated by a quantum circuit of size $k$?

Thank you.

Comment: Perhaps the thing similar to 1 above which was meant by some people is concerning the inputs. But I even don’t see how one can encode a general state of $k$ qubits (a unit vector in $(\mathbb{C}^2)^k)$ by using $2^k$ classical bits as the latter can be only zero and one each - let alone the gates. Hence I don’t see how one can simulate any quantum circuit using a classical circuit.

$\endgroup$
1
  • $\begingroup$ About (1): I don't think $2^k$ will do it, but $2^{O(k)}$ will. The idea is that you can approximate all gates and unitaries up to some finite precision $\epsilon$, and (for the most part) a classical circuit can simulate arbitrary real numbers with $\epsilon$ precision with $\log(1/\epsilon)$ complexity. Since quantum circuits are generally probabilistic anyway, we can forget the approximation factor. $\endgroup$
    – Sam Jaques
    Apr 12 at 7:19

2 Answers 2

2
$\begingroup$

Before answering let me generalize and formalize your framing a bit, so that I can say things concretely without fussing over details. I believe the heart of your question concerns the power of an exponentially-sized classical circuit vs. a polynomially-sized quantum circuit. But I will also focus on the case where the circuit are exponential only in depth, and preclude the possibility of exponentially many bits. Thus, we are focused on matters of exponential time, not space. My answers below would need to change otherwise.

Computer scientists like to define complexity classes to classify the difficulty of various computational problems. For example, the class EXP denotes the class of problems classically solvable in exponential time (with a polynomial number of bits, however). Your first question concerns whether the simulation of quantum circuits is in EXP. Indeed, it is, because one can simply perform the appropriate matrix multiplication on a (complex) vector space of dimension $2^n$. Given exponential time, a classical computer can emulate a quantum computer.

To address question (2), suppose one could emulate a classical circuit of size $N$ with a quantum circuit of size $O(\log N)$. From the standpoint of complexity theory, this would imply that quantum computers could efficiently solve all problems in EXP. The class of problems that can be efficiently solved on a quantum computer is termed BQP. Thus, we would have EXP $\subset$ BQP. On the other hand, we've already essentially shown above that BQP $\subset$ EXP. We would be forced to conclude that BQP = EXP.

Though we cannot prove (as far as I know) whether this is indeed the case, we should be quite suspicious. Most experts don't believe that BQP contains NP, let alone EXP. This would preclude efficient solutions to the likes of the traveling salesman problem. For a better discussion of this than I can give, see this other post.

To summarize, it would be very, very surprising if quantum computers were as powerful as you describe. I doubt there are many people in the field who believe so.

$\endgroup$
2
  • $\begingroup$ Thank you for the explanation. I cannot really follow your argument for (1). Do you have a (strict) reference for the fact that $BQP\subset EXP$? Thanks. $\endgroup$
    – mrpotato
    Apr 14 at 19:27
  • $\begingroup$ @mrpotato en.wikipedia.org/wiki/BQP $\endgroup$
    – Jacob
    Apr 15 at 13:55
0
$\begingroup$

Actually what you're asking for is provably false! We can prove this with a counting argument: there simply aren't enough quantum circuits of size $k$ to possibly emulate all classical circuits of size $2^k$.

I'll be sketchy with the details, but roughly speaking, there are $2^{O(k\log k)}$ possible quantum circuits of size $k$. For an intuition, imagine laying out a circuit of some depth $D$ with $Q$ qubits. Then (a) we can choose out of the $D\times Q$ possible places to put each gate in the circuit, for $\binom{QD}{k}$ choices; (b) if we have $g$ different gates to choose from, then for each of the $k$ gates we use, we can choose which of $g$ gates it is (so $g^k$ choices). We can approximate (a) as $\binom{QD}{k}\approx \left(\frac{QD}{k}\right)^k=2^{k(\lg(QD)-\lg(k)}$. The (b) term is $g^k=2^{k\lg g}$, so overall we have $2^{O(k\log k)}$.

(This isn't quite right: we have to be careful about multi-qubit gates; we overcounted; $Q$ and $D$ depend on $k$; but the idea holds generally).

Then we can count how many classical circuits there are that use $2^k$ gates. In fact, we can create any function $f:\{0,1\}^k\rightarrow \{0,1\}$ with $O(k2^{k})$ gates, by translating the following algorithm:

Input x:
for i from 0 to 2^k:
     if x == i:
         set output to f(i)

That is, we just check for every possible address and write the result to the output bit if it matches (the "if" can be translated into a circuit based on AND gates). The address-check uses $O(k)$ gates and there are $2^k$ such checks, giving the circuit size. Since there are $2^{2^k}$ distinct functions of this form, then there are at least $2^{2^k}$ distinct classical circuits of size $O(k2^k)$.

(In fact I am fairly sure you can compile the circuit above into one of size $O(2^k)$ by re-using most of the address check between steps.)

Now there are some logarithmic factors on both sides that are annoying to deal with, but you can see that the number of distinct classical circuits of size $2^k$ grows roughly as $2^{2^k}$, while the number of possible quantum circuits of size $k$ grows at most as $2^{O(k\log k)}$. For large enough $k$, there are far more classical circuits.

$\endgroup$

Your Answer

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

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