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.

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