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.