Can exponentially long bitstrings be stored in (and retrieved from) qubits reliably?
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.)
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?
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
npre-shared bell pairs between a sender and receiver, you can use superdense coding to pack
ntransmitted qubits (the already-transmitted bell pair parts play the role of the other
- What if you only want to get
nbits 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^nidentical copies of
a|0> + b|1>, and then the receiver statistically inferred
abased 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
nbits of binary (1/2^n).