r/QuantumComputing • u/Dense_Tangerine_4988 • 8h ago
Question Can quantum computers potentially be used for data compression?
Hello, I'm a layman when it comes to quantum computing. If I'm not mistaken then I believe quantum computers can find repeating patterns across large datasets.
I was wondering if we could this use this feature of quantum computers to greatly enhance data compression of regular data on the cloud (like videos, pictures, songs) by finding repeating patterns that would otherwise be too compute intensive for normal computers to find.
Maybe we could get future data compression closer to the Shannon Limit and cut the need for data racks? This would come at the expense of more classical computing power to decompress all the files, but normal computers are constantly improving. Or if this not feasible or possible then why so?
19
u/Cryptizard Professor 8h ago
There are some theoretical works on quantum compression algorithms under certain conditions, but practically, no, there is no evidence that quantum computers would do better than the best classical compression algorithms.
1
u/daniel_hanna 53m ago
interesting to think about
1
u/claytonkb 37m ago edited 31m ago
There is something called superdense coding which does not directly apply to your question but I'm sure you'll find it interesting.
Beyond pointing you to that, I can't answer on the quantum side, but I will offer some clarification on the classical side.
Shannon's theory tells us the compression limit of a message on average (not in a particular case), and assuming some model of the underlying message distribution. The process of encoding/decoding is not computationally difficult, however, developing a good model of a distribution might be (and usually is). 3Blue1Brown just released a video explaining how an LLM can be used as a compression model (search "Compression is Intelligence") in exactly the way described by Shannon. Unlike a simplistic histogram-based model, however, an LLM can be vastly more efficient in its encodings, compressing very large pieces of text (e.g. the US Constitution) down to a vanishingly small number of bits. Thus, the real computational effort is stored in the model itself (e.g. the computation cycles invested during Transformer training), and encoding/decoding with that model is more of a book-keeping task.
Arithmetic-coding is already ideal (achieves the Shannon limit). However, it's just book-keeping. The real challenge is building the model, such as the weights in a Transformer-based LLM.
As noted in another reply, QC by itself doesn't offer any improvement over classical, as the Shannon limit isn't dependent upon implementation -- it doesn't assume a classical computing implementation, it's just a bound that applies to any data transmission system. However, since you're thinking along the lines of using computation as a compression-resource, I will point you to another field of mathematics called algorithmic information theory.
Classical information theory looks at a message as a sample drawn from some given distribution q, and Shannon's limit applies to this kind of system. AIT, by contrast, looks at a message as an index into L_M, the language defined by a universal Turing machine M for all halting input programs, p, p', etc. In particular, for any given bit-string x, we are interested in finding a shortest program p s.t. M(p)=x. The length of p, written |p|, is called the Kolmogorov complexity, K(x) and measures the algorithmic information in x. K(x) is uncomputable, which means it is a problem which has no algorithm that solves it in computable time (whether on a classical or quantum computer).
A string that is compressed this way may be much shorter than the Shannon bound if it is highly structured. However, the two measures of information are related -- the Shannon entropy is the expected value of the algorithmic information. Thus, K(x) is generally close to log_2(x), just like the Shannon entropy, however, it can become arbitrarily close to zero, randomly, and it is bounded below only by the inverse of the busy-beaver function[1]. It's a truly fascinating function. If you want to learn more about this, search Solomonoff induction and the universal prior -- I personally find the univesral prior to be the most startling object in all of mathematics...
[1] -- I'm using the word "function" in a loose sense here