Did anyone think which data compression methods will become more popular when quantum computers become as available as traditional computers nowadays?
Did anyone think which data compression methods will become more popular when quantum computers become as available as traditional computers nowadays?
Last edited by Alexander Rhatushnyak; 15th June 2010 at 00:12.
If practical quantum computing is possible (we don't know if it will be), then one possibility is to speed up Levin search (Kolmogorov compression with exponential time limits) from O(2^n) to O(2^(n/2)) using Grover's algorithm. You want to find the shortest program P that outputs x, so you try all programs up to length |x| and run each one for 2^|P| steps until you find a match. Grover's algorithm lets you do this in 2^(|x|/2) steps which is an exponential speedup but still requires exponential time. But it would let you check |x| up to twice as long.
The disadvantage is that P has to be quantum computable. That means that all operations in P have to be time reversible. For example, P could not have assignment statements because you couldn't run them backwards to get back the value overwritten. I don't know that this is a severe drawback because you can always make an algorithm time reversible by saving the overwritten values. For example, you replace assignments with swaps.
Another problem with quantum computing is that the output is probabilistic. You are computing a probability distribution over 2^n complex numbers for n qubits. When you read the output, you just get n bits selected by this distribution. But I think you could overcome that easily by testing decompression on a classical computer.
I guess almost all quantum computers will use deterministic co-processors to run deterministic algorithms.
Last edited by Alexander Rhatushnyak; 23rd June 2010 at 07:14.
I may be wrong, but I think that quantum computing is more about logic design for digital systems with high probability of errors,
than quantum magic or anything.
In that sense, already the modern chips have that to an extent - like circuits with ECC etc.
So I think anything can be implemented directly on the quantum computer, we'd only have to add measures to put the overall error probability
under a reasonable threshold (modern chips have documented non-zero error rates anyway).
But programming for unstable memory (aka qubits) certainly seems really interesting and similar to CM in many ways.