Results 1 to 4 of 4

Thread: Data compression on quantum computers?

  1. #1
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    237
    Thanks
    39
    Thanked 92 Times in 48 Posts

    Data compression on quantum computers?

    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 01:12.

  2. #2
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    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.

  3. #3
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    237
    Thanks
    39
    Thanked 92 Times in 48 Posts
    Quote Originally Posted by Matt Mahoney View Post
    Another problem with quantum computing is that the output is probabilistic.
    ...
    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 08:14.

  4. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,333
    Thanks
    209
    Thanked 1,007 Times in 532 Posts
    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.

Similar Threads

  1. Any money in data compression?
    By bitewing in forum The Off-Topic Lounge
    Replies: 18
    Last Post: 19th March 2019, 11:34
  2. Data compression explained
    By Matt Mahoney in forum Data Compression
    Replies: 92
    Last Post: 7th May 2012, 19:26
  3. Advice in data compression
    By Chuckie in forum Data Compression
    Replies: 29
    Last Post: 26th March 2010, 16:09
  4. Data Compression Crisis
    By encode in forum The Off-Topic Lounge
    Replies: 15
    Last Post: 24th May 2009, 20:30
  5. Data Compression Evolution
    By encode in forum Forum Archive
    Replies: 3
    Last Post: 11th February 2007, 15:33

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •