# Quantum and classical scaling of memory

In the literature of Quantum Computation (QC), when discussing the simulation of quantum systems, one usually comes across comparisons with the classical digital analog such as: "Classically the size of the simulating computer grows exponentially with system size (e.g. system size being the number of variables $N$)." More precisely, let's take an example:

## Classical simulation of a system with $k$ quantum variables:

Taking for simplicity the usual 2-state system of e.g. photon polarisation (state up and down): The system composed of $k$ particles each with a 2-dimensional Hilbert space of states $\mathcal{H_2},$ has a corresponding total Hilbert space of $\mathcal{H}=\mathcal{H_2}\otimes \mathcal{H_2}\otimes ...=\mathcal{H_{2^k}},$ with dimension $2^k.$ So each state of this system is described by vector of $2^k$ components. So to store one such state in memory, one needs to store at least $2^k$ numbers. Furthermore, to implement any unitary operator for this system, we'd need to store a matrix of size $(2^k)^2=2^{2k},$ corresponding to its number of elements. Now let's see the quantum version of these requirements:

## Quantum simulation of the same system:

The dimensionality of the total Hilbert space does not change, but having access to a Quantum computer, the $k$ quantum variables correspond only to $k$ quantum bits, so in contrast instead of $2^{2k}$ storage, we only need $k$ bit (qubits to be correct) storage here, and the unitary matrix is still of same size as before, i.e. having $2^{2k}$ elements, meaning to apply a unitary transformation, $2^{2k}$ logical operations have to be performed, even in the Quantum Computer.

• First question: Does this mean that accessing bits in a quantum memory takes always constant time? (dependent on $k$)
• Would the above scenario regarding the storage change for either the classical or quantum simulation, if the $k$ particles are entangled?
• Is the main reason that quantum computers overtake their classical analogs in efficiency, the fact that logical gates can be applied to qubits being in superposition states, without destroying the superposition, hence being equivalent to applying many operations simultaneously (i.e. as many as there are terms in the superposition)? whereas classically each term in the superposition would be an additional degree of freedom, i.e. separate bits of information to store? I tried to maintain a level of generality in the questions, in order to grasp the conceptual core of these matters, but if you see a specific example as fit for an answer, feel free to use one.
• First question: That depends on the design of the quantum computer, just like in the classical case, doesn't it? I don't see any physical reason why one can't make the assumption that constant access time is physically possible in a real design. – CuriousOne Sep 11 '15 at 15:49
• It is neither correct that in order to apply a linear operator to a vector, you have to store its matrix representation, nor that you have to perform $2^{2k}$ logical operations to implement a unitary transformation in a quantum computer. – Norbert Schuch Sep 12 '15 at 21:17
• @NorbertSchuch If you find time, would you be so kind as to write an answer explaining these concepts? I'd be most interested. One reference where I have read such a description, is e.g. in Seth Lloyd's 1996 paper, Universal Quantum Simulators, section "Simulation Efficiency". I'm sure you've read this paper before. – user098876 Sep 13 '15 at 13:55
• Which concepts? What I mentioned in my comment is not an answer to your question. But if you look at e.g. the classical Fourier transform, it can be implemented much more efficiently, and similarly for e.g. the Quantum Fourier Transform. (Not to mention "silly" examples such as the identity gate, flipping each bit, etc.) – Norbert Schuch Sep 13 '15 at 16:00
• We apply unitary operations not to all $k$ qubits at once, but just to two of them at a time. This only requires 16 complex numbers (although in a physical quantum computer, while these 16 numbers describe the unitary, we probably wouldn't actually implement a gate by feeding in 16 numbers to it). – Peter Shor Sep 22 '15 at 17:18

## 1 Answer

After a while I realized that at the heart of the poster's questions are very relevant, and difficult questions, not all of which have answers. Here I have rephrased/reorganized the questions to make for easier answering.

1) Does accessing quantum memory always take constant time?

In both quantum and classical computers one could make a physical system that could access many bits at once (or apply unitary transformations all at once). But for either computer it is safe to assume that storage access takes linear time in bits, which is typically not a hindrance when distinguishing hard computations (intractable = exponential resources in systems size) from tractable ones.

2) Does one need an exponential number of bits to simulate a quantum system? An operator? What about qubits? Is entanglement a factor?

As pointed out by the original poster, the size of Hilbert space increases exponentially with the number of sites in a finite system [see PRL 106, 170501 (2011)]. In particular, if one thinks of simulating a quantum computer of $N$ bits, the dimension of the Hilbert space of states is $2^N$. As for the representation in qubits, it is often in the latter case that the $N$ qubits suffice, but the question is whether every quantum system can represent the state of every other in an amount of space that is polynomial in the system size. The answer is yes, because Hilbert spaces of equal dimension are fungible [Caves 04].

As for operators, it is known that time evolution can be simulated within a fixed error with polynomial resources for a local Hamiltonian by creating an approximate operator by expanding operator exponentials [Lloyd, S. (1996). "Universal quantum simulators"]. These can also be created classically assuming one can simulate a few basis operators classically.

The deep question that remains is whether all quantum systems can be simulated "efficiently" (in polynomial resources) by a classical computer. This is the complexity question BQP ?$\ne$ PP. This problem has not been solved, but its solution would be extremely important both for computation and for physics. Note that even though the Hilbert space is large, quantum simulation can still be done without storing the exact states, but at the cost of exponential time [MP Frank 09].

From the physics perspective some progress has been made on identifying systems that can be simulated efficiently classically. This is where entanglement becomes extremely relevant. The use of tensor networks has allowed the simulation of many classes of Hamiltonians based on entanglement [Orus 14]. This is done by approximating states by states created by glueing together product states with quantum correlations, or entanglement. In addition, there is a recent version of DMRG that provably solves the ground state problem for 1D gapped Hamiltonians [Landau 15]. In particular one might hope to parametrize approximate states with a polynomial set of parameters that is dense enough in the exponentially large Hilbert space to make it approximately tractable [Verstraete 15]. While this is not thought to be possibly by many, as it would greatly soften the power of quantum computation over classical, results in either direction are very useful!

3) Why are quantum computers better (at simulating quantum physics)?

This is a very hard question, and many would say the complexity problem just mentioned needs to be solved for us to make the claim that quantum computers are better. However, we can wonder why we have found quantum algorithms that are better than our best ideas for classical computers. I think the best answer to this question on stackexchange is in this post.

• Thanks a lot for this extensive answer, and specially for citing so many useful and relevant references. Two general sub-questions if I may: Is there any real difference between the time evolution operator compared to any other unitary operator? (either from a conceptual or computational point of view). I ask because if as you say in 2) time evolution can be simulated with polynomial resources, does this also hold for other unitary operators? – user929304 Nov 16 '15 at 12:28
• And the second question: Analogous to how a quantum computer stores the $(N)$ states using qubits thus avoiding to explicitly store $2^N$ components, how are the operators implemented to avoid storing $2^{2N}$ components? In other words is the expansion of operator exponentials to reduce the exponential resources to polynomial, the only way known so far? By the way, from the Feynman famous paper on simulating quantum systems, where he shows that in order to simulate a QM system classically we need exponential resources in time and space, do we today have reason to believe that it is not so? – user929304 Nov 16 '15 at 12:35
• The operator statement above can be rephrased: "any operator generated by a local Hermitian operator (Hamiltonian) can be approximately created/applied with a number of operations that is polynomial is accuracy and system size. The idea is to create it approximately with a finite fixed set of operators available. There are, however, believed to be states that are outside of this reach, which must be related to the initial state by an impossible operator, although this seems not to be proven - see the comments in Scott Aaranson's post: scottaaronson.com/blog/?p=1697 – Brent Nov 16 '15 at 18:35
• I think Feynman's intuition is that it is very difficult to simulate quantum physics without using QM. He points out that some simple tries don't work. However, this is different from asking the question: if we teach the computer to do QM as a physicist does it (correctly) how difficult is the simulation on a classical computer? In particular, are there quantum systems that require exponential classical resources (space or time) to simulate no matter how smart the programmer? I think most people believe that there are such systems, but to prove this would again require solving BQP ?= PP. – Brent Nov 16 '15 at 18:53