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:
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?
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.