Does a classical computer really require $2^n$ complex numbers to represent the state of $n$ qubit quantum computer?

Question

One often reads that the key reason why classical computers (probabilistic or deterministic) are unable to simulate quantum algorithms such as Simon's or Shor's efficiently is that a classical computer needs $2^n$ complex numbers to represent an $n$ qubit state of a quantum computer. While it is true that the dimensionality of the Hilbert space spanned by an $n$ qubit computational basis is $2^n$, it seems to me that the subspaces reachable by many quantum algorithms that employ fixed sequence of unitary gates are substantially smaller.

Let $n$ be the number of qubits in a quantum computer. Consider an algorithm that starts from some simple initial state (say the 0 for all qubits) and employs a sequence of $kn$ unitary gates ($k$ being some factor), each involving no more than 1 or 2 qubits. One may ask: What is the size of the Hilbert subspace reachable by this algorithm from the initial state? A 2 qubit gate should not need more than 16 complex numbers for its representation and $kn$ such gates in a fixed sequence will not need more than $16kn$ such numbers (in reality the factor will be smaller). The fact that the sequence of gates is a fixed one is important in this argument to avoid branching. Many algorithms including Shor's, Grover's, Simon's are based on fixed gate sequences like this. If the number of gates scales as a polynomial of $n$, the "size" of the Hilbert subspace reachable from the initial state should scale as polynomial of $n$ as well. Therefore, I do not see why we would need $2^n$ complex numbers as would be needed to describe the entire Hilbert space. Can someone help explain why? If my thinking is correct, wouldn't this logic be a generalization of Gottesman-Knill theorem and wouldn't it also imply that there exists "classical", possibly probabilistic computing, algorithms capable of equalling Simon's and Shor's in efficiency? What am I missing?

Answer 1

If you treat the gate sequence as fixed then by the same logic you can treat the actual gates as fixed. No parameters is better than polynomial number of them :)

But the problem is not with this. Let's say we want to implement Shor's period finding routine. The output of the unitary gate sequence will be some state in $2^n$-dimensional Hilbert space. We do not need to know all those $2^n$ complex parameters of the output. We just need to find some indexes where corresponding complex numbers have highest amplitudes (this is essentially what the final measurement part does). But how can we know what complex numbers have the highest amplitudes without computing all of them? No one knows, although it isn't proved that there is no tricky algorithm to find this efficiently on a classical computer.

Answer 2

The issue is that you are confusing the notions of Komogorov complexity and computational complexity. Kolmogorov complexity (roughly) means the smallest amount of data that you need to provide in order to completely specify an object. Computational complexity (roughly) refers to the minimum number of time steps that it takes any Turing machine to convert an input tape with the problem instance to an output tape with the solution to that instance.

You are correct that any quantum state that can be reached from the all-0 initial state with a fixed-depth circuit by definition has a Kolmogorov complexity that is at most linear in the number of qubits: one can specify the state by simply giving the circuit. So in that sense, only very "simple" states can be practically reached by a quantum circuit.

But that's not the sense that really matters for most purposes. Not all states that are "simple" in that sense can be efficiently simulated by a classical computer. Put another way, not all states that are difficult to calculate require a complicated description to specify. As a concrete example, consider the smallest natural number $n$ such that prime-counting function $\pi(n)$ exceeds the logarithmic integral $\mathrm{li}(n)$. Such a number has extremely low Kolmogorov complexity; I just uniquely specified it with one very short sentence. But it has extremely high computational complexity: all the computers in the world could not calculate its value. Some quantum states reachable by shallow circuits are similar.

(Strictly speaking, what I said above isn't right, because a single number doesn't have a computational complexity; only a problem does. But it conveys the general idea.)

Answer 3

As Danylo Y have answered, the key is you don't need to read out the entire quantum state at the end of the quantum algorithm to get your answer. There is another algorithm, called HHL algorithm, which is design to solve linear system of equations $Ax = b$. It provides an exponential speed up, and uses $O(\log(N))$. If you think about it, it already takes $O(N)$ to write down the entire solution... so writing down all the entries of $x$ would make you lose out all the advantage... the idea is you can translate the problem to about preparing the state $x$ for which we can sample.

Answer 4

I believe the issue you are missing is entanglement, which is an essential resource in quantum computing algorithms. Since we generate entanglement between these qubits, we can no longer think of independent subspaces of the Hilbert space where the final state can be represented as a tensor product of these subspaces. This is because an entangled state can't be represented as a tensor product of pure states. Therefore, once you have entanglement the idea of keeping track of only given subspaces and therefore a smaller number of complex numbers is not meaningful, you have to keep track of the entire entangled state.

You really can not do a lot of meaningful stuff without generating massive amounts of entanglement.

Answer 5

Consider an $n$ qubit system. For each qubit you need to store 2 complex numbers, making $2n$ numbers in total. But if these qubits are entangled, then you can no longer store those numbers separetely. The overall system of $n$ qubits is represented by a vector of dimension $2^n$ and can not be written as the tensor product of individual vectors.