Can exponentially long bitstrings be stored in (and retrieved from) qubits reliably?


The background:

I recently read that quantum compression can be used to turn N qubits into lgN qubits (http://www.scientificamerican.com/article/quantum-bits-compressed-for-the-first-time/, inferred from the line "1 million qubits squeezed into 20"), and that piqued my curiosity about whether or not classical information could be:

1) converted from a bitstring to qubits,
2) compressed to lg(N) of its original size,
3) sent over a quantum network,
4) decompressed, and
5) converted from qubits to a bitstring

(this seems way too good to be true.)

The questions:

Can bitstrings be stored in (and retrieved from) qubits reliably?

Could transmission of any size N file be improved from Θ(N) to an average (not worst case) below Θ(N) when either qubits or bits can be sent over the network?

Additional comments:

Even if sending classical information through a quantum network is possible, I realize it might not be reliable since quantum computers have some probability of returning any answer.

Additionally, several checksums would have to be sent through a classical network to examine the validity of the decompressed information.



Quantum compression only works on permutation-invariant sets of qubits, which is a very strict condition that prevents it from being useful for much of anything.

In general you can't squash n bits of entropy into fewer than n qubits. This was proven all the way back in 1973 and is known as Holevo's theorem:

given n qubits, although they can "carry" a larger amount of (classical) information (thanks to quantum superposition), the amount of classical information that can be retrieved, i.e. accessed, can be only up to n classical (non-quantum encoded) bits.

Some interesting related facts:

  • If you have pre-shared entanglement, you can double the capacity. With n pre-shared bell pairs between a sender and receiver, you can use superdense coding to pack 2n bits into n transmitted qubits (the already-transmitted bell pair parts play the role of the other n qubits).
  • What if you only want to get n bits out, but different bits in different situations? Can we make an exponentially huge dictionary with linearly sized entries? Nope: quantum advice is not more space-efficient than classical advice.
  • What if you used quantum compression to send 2^n identical copies of a|0> + b|1>, and then the receiver statistically inferred a based on how many 0s they measured? Is this roundabout way of sending real numbers more efficient? Nope: the standard deviation of the statistic (~1/sqrt(2^n)) is worse than the precision you get from sending n bits of binary (1/2^n).