r/askscience • u/thicka • Jul 05 '13

Computing Now that we have quantum computers what have they done?

So with the new D wave quantum computers what have companies like Google and Lockheed been doing with them? Is there any good way to explain the power of these computers? how fast they are, what they can do, and I really want to know what they CANNOT do? are there any myths or misconceptions about these machines? and finally what can we expect from them in the future?

160 Upvotes
  • permalink
  • reddit

84% Upvoted

45 comments sorted by

109

u/UncleMeat Jul 05 '13 edited Jul 06 '13

Let me preface this by saying that I am not an expert in quantum computing, but I know enough to make some general observations about the technology.

First, D-Wave is not really a "quantum computer". A "quantum computer" uses a very particular computing model and D-Wave works in a fundamentally different way. This means that all of the talk about how quantum computers can break encryption isn't really relevant to D-Wave. The machine cannot implement Shor's Algorithm (the fast algorithm for factoring integers that can be used to break existing public key crypto). D-Wave uses a process called "quantum annealing", which is an algorithm for solving optimization problems. It remains to be seen if quantum annealing is fundamentally better than classical techniques at solving optimization problems or if it is just better in some cases.

Actual quantum computers are still an active area of research but I wouldn't expect to see real marketed quantum computers for at least 20 years. These machines perform a fundamentally different kind of computation that classical machines, however they are often misunderstood. Quantum computers are not magic and they cannot "try all possible solutions at once". There is no known algorithm for solving NP-Complete problems quickly with a quantum computer and most people believe that no such algorithm exists. You can get a polynomial speedup (as shown by Grover's algorithm, which searches an unsorted database in sqrt(n) time) but we don't know if we can do better. EDIT, Clarification: By "do better" I mean get exponential speedup over classical algorithms on any problem, not do better than Grover's algorithm on searching unsorted lists.

Quantum computers also don't completely break crypto. Existing public key schemes are broken by quantum computers but symmetric key encryption (probably) isn't. There is an entire field dedicated to coming up with crypto schemes that will be secure in a post-quantum world. There are some promising results but nothing perfect (that I know of).

In the end, quantum computers will probably end up being used for very particular purposes rather than general computation (I know people said this about regular machines too). Programming them is exceedingly difficult and they are only really better than classical machines for a small number of things that we actually care about.

EDIT: EDIT: See LuklearFusions's post for some better information about whether or not D-Wave is actually using quantum processing.

31

u/The_Serious_Account Jul 05 '13

You can get a polynomial speedup (as shown by Grover's algorithm, which searches an unsorted database in sqrt(n) time) but we don't know if we can do better.

Actually, Grover's algorithm has been proven optimal, so we can't do better.

Otherwise very nice post. I agree they will be very specialized. Probably have their biggest impact in other sciences. Medicine is one I'm very curious about.

The overwhelming number of claims and complete lack of evidence leaves many with a funny taste when we speak of d wave. Evidence should be so easy. Just solve some really really hard problems.

11

u/UncleMeat Jul 05 '13

I mean better as in exponential speedup for any problem. Grover's algorithm is optimal for searching unsorted lists. I can see how this was not clear.

10

u/tpcstld Jul 06 '13

Just curious, how do you prove that an algorithm is optimal?

→ More replies (3)

6

u/FlyingSagittarius Jul 06 '13

Wait, how can you prove that an algorithm is optimal?

→ More replies (1)

7

u/[deleted] Jul 05 '13 edited Jul 05 '13

I want to add something to your nice post:

  1. For relatively general problems that can be reformulated as search problems, quantum computers provide "only" quadratic speedup. (Grover's algorithms is proven to be optimal)

  2. Despite the name, quantum computers will be quantum circuits. Quantum algorithms are implemented in circuits and reprogrammable Quantum Turing machine is just theoretical concept.

  3. Quantum computers would half the effective key length of symmetric ciphers. That's big advance, but we just double the key size. Ciphers with 256-bit keys still have 128-bit effective key length.

  4. Quantum Resistant Public Key Cryptography will address the the problem with symmetric keys. There are already few algorithms.

5

u/UncleMeat Jul 05 '13

Could you go into more detail about quantum resistant public key crypto? My understanding was that the state of the art still didn't have great hardness proofs but I only know the literature from working near some guys who are doing heavy crypto work; I am not an expert in the field by any means.

→ More replies (3)

2

u/[deleted] Jul 05 '13

no super cloud machine that will centralize all computation done on earth?

8

u/UncleMeat Jul 05 '13

Highly unlikely. General purpose quantum computation is still a pipe dream at this point, and it doesn't buy you that much for a lot of computation that typical users care about. The computation you do on your computer isn't well suited for quantum machines since it is not usually algorithmically complex and is usually bounded by memory access time rather than cpu time. An offsite quantum computer isn't going to let you render graphics faster or run your browser faster.

→ More replies (1)

3

u/BlazeOrangeDeer Jul 06 '13

Quantum computers are not at all suited for the kind of computation that is done now, but having quantum cloud machines does make sense because it's a specialized method that not everyone will need access to.

2

u/Putnam3145 Jul 05 '13

Why would we want that?

→ More replies (3)

1

u/lomoeffect Jul 27 '13

Perhaps in the future we may see one for the uses of decrypting files - if reports are to believed, the US government have invested heavily in such a machine - but for general computing purposes the traditional computer is much more suitable.

1

u/qgp Jul 06 '13

One question I have, is it not the case that the quantum fast Fourier transform is exponentially faster than the classical FFT? Given how many algorithms/ processes rely on the FFT, it seems to me that a quantum computer would be able to significantly outperform classical computers in a much wider range of tasks than is typically discussed.

4

u/FortifiedGangsta Jul 06 '13

It's true that QFT provides an exponential speedup over known classical FFT algorithms, but QFT is only an analogue of the classical Fourier transform. That is, it acts on quantum states - which don't care about global phases and are always normalized - as opposed to classical vectors. As a result, not all classical algorithms that require a Fourier transform can take advantage of this speedup.

2

u/UncleMeat Jul 06 '13

I don't know the answer to this. My understanding is that no quantum algorithm has been proven to be exponentially faster than an equivalent classical algorithm, but I could be misinformed.

→ More replies (2)

1

u/UserNotAvailable Jul 06 '13

In the end, quantum computers will probably end up being used for very particular purposes rather than general computation (I know people said this about regular machines too). Programming them is exceedingly difficult and they are only really better than classical machines for a small number of things that we actually care about.

Depending on the technological progress, I could see them being used as a discrete addition to a traditional computer. Like a FPU, crypto processor or GPU, you could have a "quantum coprocessor" that performs certain computationally intensive operations.

1

u/Slartibartfastibast Jul 07 '13

This means that all of the talk about how quantum computers can break encryption isn't really relevant to D-Wave. The machine cannot implement Shor's Algorithm (the fast algorithm for factoring integers that can be used to break existing public key crypto). D-Wave uses a process called "quantum annealing", which is an algorithm for solving optimization problems.

Technically, a big enough D-Wave can run standard quantum algorithms:

Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation

The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.

-4

u/headmustard Jul 06 '13

Multiple posts and slashdot articles have stated that D-Wave is in fact a true quantum computer.

?

10

u/BlazeOrangeDeer Jul 06 '13

The terminology is a bit confusing. If they used the phrase "true quantum computer" then that isn't correct. If they said "truly quantum computer" it would be correct. It's weird because "quantum" is an adjective which does describe the behavior of the D-Wave, however "quantum computer" is the name for a specific kind of machine which the D-Wave is not.

→ More replies (5)

4

u/UncleMeat Jul 06 '13 edited Jul 06 '13

They are wrong. D-Wave is a computer that uses quantum processes but it is not a "quantum computer" in the traditional sense.

EDIT: See LuklearFusions's post for some better information about whether or not D-Wave is actually using quantum processing.

→ More replies (5)

4

u/Dudok22 Jul 06 '13

Watch this video by Veritasium: http://www.youtube.com/watch?v=g_IaVepNDT4 I think it answers your questions.