# 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).