3 ms·

I understand why the actual quantum effect is hard to observe, but I'm not sure I understand why the output is so hard to verify as being better or worse than a

by awongh 12y ago

I understand why the actual quantum effect is hard to observe, but I'm not sure I understand why the output is so hard to verify as being better or worse than a classical computer.... Can someone name the physical effect that this processor employs outside of any quantum effects that accounts for it possibly being faster than a room temperature "normal" computer? What algorithms are they running to try to verify that the computer is quantum?

chriswarbo 12y ago
D-Wave's machine is running an approximate optimisation algorithm. It's like trying to solve a large Sudoku by filling in all of the squares randomly then adjusting them to make the solution better and better (ie. get fewer invalid squares). They're using an 'annealing' algorithm to do this, which means that the squares are all adjusted concurrently, in a random way which is biased by how well each square's value fits with its neighbour's. D-Wave claimed that their machine is quantum, without much evidence. They've since shown reasonable evidence that their machine does indeed use quantum effects, so that it's running a 'quantum annealing' algorithm; that basically means there's some probability for non-neighbouring squares to interact, which may find better solutions faster. However, 'quantum annealing' isn't difficult to calculate. Despite the name, it's easy for classical computers to implement it and they can do it faster than D-Wave's machine (thanks to decades of Moore's Law). So at this point D-Wave have a single-purpose ASIC which is more expensive and slower than regular computers. They're doing something quantum, but there doesn't seem to be much point. Compare this to a "real" quantum computer, which would be general-purpose (rather than being restricted to one algorithm like D-Wave's machine) and would be able to efficiently run things like Shor's algorithm, which are known to be unscalable on classical computers.
- gizmo686 12y ago
  Even a general purpose quantom computer would be hard/impossible to verify without studying the internals. For example, we have used a general quantom computer to preform shors algorithm and factor 21. I am not aware of how long the computer took to do so, but it would not suprise me if my cellphone would be faster using naive trial division.
- acqq 12y ago
  http://www.scottaaronson.com/blog/?p=1679 http://www.scottaaronson.com/blog/?p=1679 "In other words, even if you could implement adiabatic optimization perfectly—at zero temperature, with zero decoherence -- we still don't know whether there's any quantum speedup to be had that way, for any of the nifty applications that the article mentions: 'software design, tumor treatments, logistical planning, the stock market, airlines schedules, the search for Earth-like planets in other solar systems, and in particular machine learning'"

by awongh 12y ago

chriswarbo 12y ago

D-Wave's machine is running an approximate optimisation algorithm. It's like trying to solve a large Sudoku by filling in all of the squares randomly then adjusting them to make the solution better and better (ie. get fewer invalid squares). They're using an 'annealing' algorithm to do this, which means that the squares are all adjusted concurrently, in a random way which is biased by how well each square's value fits with its neighbour's. D-Wave claimed that their machine is quantum, without much evidence. They've since shown reasonable evidence that their machine does indeed use quantum effects, so that it's running a 'quantum annealing' algorithm; that basically means there's some probability for non-neighbouring squares to interact, which may find better solutions faster. However, 'quantum annealing' isn't difficult to calculate. Despite the name, it's easy for classical computers to implement it and they can do it faster than D-Wave's machine (thanks to decades of Moore's Law). So at this point D-Wave have a single-purpose ASIC which is more expensive and slower than regular computers. They're doing something quantum, but there doesn't seem to be much point. Compare this to a "real" quantum computer, which would be general-purpose (rather than being restricted to one algorithm like D-Wave's machine) and would be able to efficiently run things like Shor's algorithm, which are known to be unscalable on classical computers.

gizmo686 12y ago
Even a general purpose quantom computer would be hard/impossible to verify without studying the internals. For example, we have used a general quantom computer to preform shors algorithm and factor 21. I am not aware of how long the computer took to do so, but it would not suprise me if my cellphone would be faster using naive trial division.
acqq 12y ago
http://www.scottaaronson.com/blog/?p=1679 http://www.scottaaronson.com/blog/?p=1679 "In other words, even if you could implement adiabatic optimization perfectly—at zero temperature, with zero decoherence -- we still don't know whether there's any quantum speedup to be had that way, for any of the nifty applications that the article mentions: 'software design, tumor treatments, logistical planning, the stock market, airlines schedules, the search for Earth-like planets in other solar systems, and in particular machine learning'"