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

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?

• Two nitpicks: (1) You don't need $2^n$ complex numbers to describe the quantum state of $n$ qubits. You only need $2^n-1$; the overall scaling of the state vector has no physical significance. (2) The set of state vectors that are reachable by $kn$ 1- and 2-qubit unitaries is neither topologically closed nor algebraically closed under addition, so it doesn't form a Hilbert subspace, or indeed any subspace. – tparker Apr 18 '20 at 1:07
• Thank you for correcting my language. I was not formulating my question carefully. Indeed, the use of the word "subspace" is not appropriate. I should have said "subset". – QC-Novice Apr 18 '20 at 13:32
• As Danylo pointed out, I don't understand what you mean by "The fact that the sequence of gates is a fixed one is important in this argument to avoid branching." A state space is always exponentially large in the of pieces you need to supply in order to specify an element. If the gates are fixed to specified values, there the state space is a single element and there's nothing to compute. If not, then you need to specify $kn$ values and the state space "branches" through a number of possibilities that is exponentially large in $kn$. Which situation are you considering? – tparker Apr 18 '20 at 17:53

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.

• Thank you. To be frank I did not understand your answer. However, in trying to think about it made me realize that one does not begin the calculation from the same initial state in every case. That would given you the same answers (probabilistically). Some part of the initial state may be the same for every computation, but another part of the state needs to be dependent on the details of the problem specification. In the Shor algorithm that would be the number we are trying to factor. That is what I was stupidly missing. Quite probably that is what you meant. Thanks again. – QC-Novice Apr 17 '20 at 19:37
• Yeah, essentially we have only one parameter - a number that we want to factor. Also we can reduce the problem for a particular number - then there will be no parameters at all and a very precise and fixed quantum scheme with a unique output in a large Hilbert space (before final measurement). – Danylo Y Apr 17 '20 at 20:00

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.)

• Thank you, but I actually feel that you have restated the confusion that I think exists in the literature. There is a tendency in the literature to claim that the need to specify coefficients of every computational basis vector in a quantum computer is what makes classical simulation that reaches this state computationally complex. In a way, I am simply pointing out that computational complexity of a quantum state can be much lower than its specification complexity. My question is in essence this: Why should that be different for a classical simulation? – QC-Novice Apr 18 '20 at 14:00
• @QC-Novice I don't know what you mean by "restated a confusion" - confusion is a state of mind, not a statement. Are you claiming that any of the claims in my answer are incorrect? I also don't know what you mean by "specification complexity" - do you mean Kolmogorov complexity? If so, then your claim is wrong: the computational complexity of a quantum state (or more precisely, the problem of producing a quantum state from the all-0 state) must be greater than or equal to its Kolmogorov complexity. – tparker Apr 18 '20 at 17:45

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.

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.

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.