Google Finds D-Wave Machine To Be 10^8 Times Faster Than Simulated Annealing (blogspot.ca) 157
An anonymous reader sends this report form the Google Research blog on the effectiveness of D-Wave's 2X quantum computer:
We found that for problem instances involving nearly 1000 binary variables, quantum annealing significantly outperforms its classical counterpart, simulated annealing. It is more than 10^8 times faster than simulated annealing running on a single core. We also compared the quantum hardware to another algorithm called Quantum Monte Carlo. This is a method designed to emulate the behavior of quantum systems, but it runs on conventional processors. While the scaling with size between these two methods is comparable, they are again separated by a large factor sometimes as high as 10^8.
A more detailed paper is available at the arXiv.
Great. Just what Google needs (Score:3, Insightful)
Just what Google needs: more computer power with which to monetize the details of your private life.
Re: (Score:3)
Sounds like something a Luddite would say.
Re: (Score:2)
Re: (Score:2)
The thing is, it doesn't matter if it gets developed for computing bomb trajectories or for computing consumer spending habits. Technology is fucking awesome and can be re-purposed to make our lives better. Even the atomic bomb gave us insight into construction of a nuclear reactor.
Re: (Score:2)
Have you ever worked in industry. There is a huge amount of "you can't do this until you've done that, that, that, the othe
Wow (Score:2)
Help me put the speed of this into perspective. (Score:5, Funny)
I'm having trouble visualizing just how fast one of these computers would be.
If I were to buy one of these computers, would it be fast enough to run Firefox at a reasonable speed?
Re:Help me put the speed of this into perspective. (Score:5, Funny)
I'm having trouble visualizing just how fast one of these computers would be.
If I were to buy one of these computers, would it be fast enough to run Firefox at a reasonable speed?
Given that it's a quantum processor ... yes and no.
Wait, you said Firefox? Then no.
Re: (Score:2)
Firefox might run faster, but you might also get webpages from an alternate reality. Of course, that could be good, too, because you might find a better Firefox.
Re:Help me put the speed of this into perspective. (Score:5, Interesting)
And that would simply be awful.
Re:Help me put the speed of this into perspective. (Score:5, Funny)
But they don't necessarily "solve" problems -- they're likely to find good near-solutions.
So the result would render webpages differently with each browser you visit? Situation normal then!
Re:Help me put the speed of this into perspective. (Score:5, Funny)
Sorry, four or more tabs on Firefox is NP Complete. The quantum speed up is only square root of N- not enough for something like that.
Re: (Score:1)
No. These computers cannot be used for general purpose computing. They can only do simulated annealing. Pretty much useless and not even real quantum computers.
Re:Help me put the speed of this into perspective. (Score:5, Interesting)
Re: (Score:3)
You might want to read the article (or even the summary). Google is saying that their results suggest that these computers are NOT just doing simulated annealing, but rather true quantum annealing.
I can do real annealing with complexity class O(1), with a metal rod, a blow torch, a hammer and a bucket of water.
Re: (Score:2)
If you can do quantum annealing with the same set up I see a Nobel price coming your way :-)
The q word actually means something.
Re: (Score:2)
At this point I don't know of many serious researchers who doubt the accumulated evidence that D-Wave actually manages to implement quantum annealing.
How useful that actually is remains to be seen.
Re: (Score:2)
I can do real annealing with complexity class O(1), with a metal rod, a blow torch, a hammer and a bucket of water.
If you're using the bucket of water, then if you're using iron then you're quenching, not annealing. Not sure why you need the hammer though. Bash the dislocations out of the crystal structure!
Re: (Score:2)
Re: (Score:2)
They can only do simulated annealing. Pretty much useless and not even real
That smells like Windows 10
Proof that D-Wave is actually a Quantum Processor? (Score:1)
So is this finally proof that D-Wave has actually produced a real working quantum processor and isn't just pulling the wool over everyone's eyes? Every other story I've heard of D-Wave is that nobody is allowed to see inside the black box and that nobody can actually get any significant speedup out of using the black box, which of course D-Wave attributed to "poor optimization".
Re: Proof that D-Wave is actually a Quantum Proces (Score:1)
1) D-Wave is a specialized quantum computing device which even in theory isn't as powerful as the devices usually hypothesized. It can only run a subset of quantum algorithms. This is what the post is referring to when discussing the interconnectedness of the qubits. 2) The first D-Wave computers had a much smaller number of qubits, and even the 2X doesn't have that many.
Thus, especially with the first generation even the theoretical performance of the D-Wave wasn't much greater than a modern classical CPU.
Re: (Score:3)
Actually, it is not. For specialized things, analog computers have always been vastly faster than digital ones. This thing may still turn out to not even be a specialized quantum computer.
Re: (Score:2)
They idea that this is a scam is indeed laughable. Let's forget for a moment that in comparison to the chip they are running a classical chip would have a very different heat signature. The company would also have gone to incredible length to produce niobium lithographic processes to produce fake chips like the one on display in their reception area. And then they would have produced several peer reviewed articles on a technology that doesn't exist.
Then again I know people who believe the Boston marathon bo
Re: (Score:2)
Good point :-)
Re:Proof that D-Wave is actually a Quantum Process (Score:5, Informative)
This finally proves that, in some applications, D-Wave's machine offers considerable speedup over alternatives. It also confirms that D-Wave's machine uses quantum effects to speed up computation, but this point was never in dispute.
However, the term "quantum computer" has a very specific meaning (just like "Turing machine" has a specific meaning), and D-Wave's machine isn't a quantum computer. They use that label, pretending that they mean the literal reading but hoping you get confused and think of the technical one.
Re: (Score:2)
They use that label, pretending that they mean the literal reading but hoping you get confused and think of the technical one.
Thought to be fair, anyone that wants a quantum computer will certainly know that D-Wave's machine is not one upon reading its description.
Re: (Score:2)
Wait, are you telling me that nobody is going to put $10M down just to see if they can play their favorite MMOG faster?
Damn, there goes D-Wave's business model ...
Re: (Score:2)
Before we say it's proof, can we at least say that it's faster than traditional processors at solving a particular problem (with the understanding the quantum computers will require different algorithms than linear computers to solve the same problem)?
Re: (Score:2)
We can say that. We can also remember that the same is true for a host of other computing devices, for example graphics cards, signal processors, specialized analog computers, etc.
This thing is not special, despite what many people believe. It does also not demonstrate that quantum computers are possible.
Re: (Score:2)
Shifting goalposts. D-Wave's critics indeed spent years claiming that the machines were hoaxes and offered no quantum effects. Understandable, as extraordinary claims require extraordinary evidence and D-Wave was found wanting for some time. Other critics claimed the entire field of quantum computing was fraudulent--this was a hobby horse of cranks and conspiracy theorists, but unfortunately CS attracts a fair number of those. Google's validation of D-Wave's current technology shuts down both those camps of
Re: (Score:3)
It does not shut anybody down that actually understand the subject matter. (You do not.) This thing is not a quantum computer. It is a special-purpose analog computer that happens to use some quantum effects. And (again) it looks like they have made the comparison as unfair, and hence as meaningless, as possible.
Re:Proof that D-Wave is actually a Quantum Process (Score:4, Interesting)
You didn't read the GP's post properly. He said that the critics claimed it never showed any quantum effects. Whether it's a full Turing complete computer is immaterial to that. It's a special purpose computational element which does, despite the critics' claims to actually use quantum effects for a very substantial speed up.
It's not a full quantum computer by any stretch of the imagination. I don't entirely understand it, but from my understanding it's not even especially useful unless your cost function fits a -very- specific form.
Nonetheless, it appears that if you have a real thing for ising models the D-Wave can now find a good minima somewhat faster than classical systems.
So yay. That's pretty cool if true. An actual problem solved with quantum computing based techniques faster than classical solutions. It's a start and an interesting step forwards, since so far they've not been able to beat a simulation of their system running on a PC and now they can. If it's really 10^8 times faster, it would even be faster than a custom classical annealing ASIC built on the same area of silicon.
That makes the result interesting, because it's the first time classical computation has ever been beaten, and that's with vast resources invested in it.
Re: (Score:2)
I have. There are different critics out there that say different things.
Re:Proof that D-Wave is actually a Quantum Process (Score:4, Informative)
It also confirms that D-Wave's machine uses quantum effects to speed up computation, but this point was never in dispute.
Boy, are you wrong on that count. [wavewatching.net]
As to the term quantum computer. It computes with qubits, it's not universal, but in that it resembles some of the analog computers of yore.
Re: (Score:2)
Google ran the same test on the previous chip, before they committed to buying the machine. [wavewatching.net] This test is for the new ~1K qubit chip.
Other than that, coding for this machine is certainly not straightforward, and it is more an experimental device at this time. Certainly not something that'll give you a price performance advantage over conventional hardware, but as they keep doubling their qubit density every 15 months this may change in the not too distant future.
Re: (Score:2)
If I remember correctly, their test results for the previous chip were later demonstrated to be rather misleading. The previous chip was indeed faster at solving the particular problem class it was hardwired for than a particular general-purpose solver running on a conventional computer, but someone managed to come up with an optimised solver that was faster than D-Wave at solving the exact problem class D-Wave was made to solve, on a normal general-purpose PC. It's not clear if the same applies to the new
Re: (Score:2)
It wasn't so much the test results that were misleading, then the way it was presented. The same applies to this test i.e. this is not comparing to an optimized solver.
Re: (Score:2)
so what you are saying is that it is misleading. How else, other than presentation, would you expect something to be misleading?
Re: (Score:2)
The underlying scientific paper could already be misleading. But in both cases, as far as I can tell, this wasn't the case.
As to the presentation, it's the kind of typical marketing spin that you get anywhere in the IT industry.
If you want the truth and look at the papers, the truth you'll get.
Re: (Score:2)
I think you exactly identified the disconnect between the scientists and the business crowd. Scientifically it would be quite significant to see true quantum speed-up, as it'll confirm what theory predicts, i.e. that quantum resources can be harnessed to perform better than any Turing machine or classical computer could.
For the business crowd any practical speed up will do - quantum be damned.
Re: (Score:3)
No, this proves that in some applications, D-Wave's machine offers considerable speedup over intentionally de-optimized alternatives. From the blog post:
We should note that there are algorithms, such as techniques based on cluster finding, that can exploit the sparse qubit connectivity in the current generation of D-Wave processors and still solve our proof-of-principle problems faster than the current quantum hardware.
In other words, the current D-Wave machine requires that problems have a particular, very restricted structure and they're only 10^8 times faster when competing with poorly-optimised solvers that don't take advantage of that special structure. if you use a properly optimised conventional solver, the D-Wave machine is actually slower. Google are hoping that
Re: (Score:1)
I have a hard time believing a single core process is the next best choice.
On 10 cores its still at worst 10^7 times faster, on 100 cores its still at worst 10^6 times faster.
You do not seem to be very bright.
Re: (Score:3)
Provided by the objective function is parallelization yes. Because SA is not.
D-Wave's problem space is limited, but... (Score:3)
No, "Quantum Computer" isn't a really well-defined term - it's basically "Sufficiently Advanced Technology Using Handwavium". It's usually used to mean "Quantum Computer that can execute Shor's Algorithm", which can solve a few problems like factoring which would make it extremely disruptive to cryptography. D-Wave has been upfront for a long time about how their computer doesn't do that - it does something much more specialized and handwavy, and this is the first article I've seen that indicates that the
Re: (Score:3)
Re: (Score:2)
From what I've read, this computer can't "solve" the traveling salesman problem at all (not faster, not slower, simply not at all). It is not an actual (hypothesized) universal quantum processor and thus your workloads are limited and so are your problem sets. It allows you to do quantum annealing for (128?) qubits and that's pretty much it.
Traveling Salesman vs. Quantum Computers (Score:2)
Traveling Salesman Problem is NP-complete, so not only is this machine not going to solve it exactly, neither is Shor's model, even though that one does solve factoring, trashing most of the public-key crypto systems.
But there are lots of heuristics for approximate solutions to TSP, and many of them are "create some complete tour of the network, then randomly perturb it a bunch of times to see if you can get any better results", i.e., simulated annealing, so a quantum annealing machine might turn out to be
Re: (Score:3)
Balderdash. There is no heating up involved to collapse the superconductivity. Rather the flux is read-out/measured via SQUID [wordpress.com] and as with any measurement it collapses the quantum mechanical superposition - in this case spin up and down magnetic fluxes in the same Josephson junction.
Never took QM 101, did you?
Re: (Score:2)
Re: (Score:2)
Agreed. The wavefunction is what collapses, although I guess you could call the phase transition out of superconductivity a collapse if so inclined. Just an odd way of putting it, what really collapses at that time is the Cooper-pair superpositions of the electrons. At any rate rather unusual verbiage.
Re: (Score:2)
No proof at all. This may well just be highly parallelized classical analog computing, the speed-up factor is a bit on the low side. And even if it uses quantum effects, the D-Wave is not a real quantum computer, it is a 1-trick pony and can only do simulated annealing.
Re:Proof that D-Wave is actually a Quantum Process (Score:5, Informative)
D-Wave has published about chip architecture for quite some time now. You must be frequenting the wrong science sites.
Google for instance is following their overall approach [wavewatching.net] but throw in hardware error correction. The latter has to be implemented via software on the D-Wave chip [wavewatching.net], which in essence is nothing more than a bunch of coupled josephson junctions (I heinously oversimplify of course, but there are now dozens of publication like this [ieee.org] since D-Wave left the stealth mode).
Re: (Score:3)
"the solution would be found effectively instantly ....since the atoms go through all possible quantum states simultaneously."
This is not the way a Quantum Computer works. You invoke the quantum parallel fallacy that that Scott Aaranson devotes an entire book to. [scottaaronson.com]
NP complete problems can be encoded in a quantum hamiltonian, but that does not mean at all that an adiabatic quantum computer could find the minima instantaneously.
Generally quantum computer are not expected to find solutions to NP complete proble [scottaaronson.com]
In other news (Score:3, Funny)
Light bulb found to light up a room over 99% closer to the speed of light as a simulated lightbulb took to run a simulation of the same on our desktop computer.
Two questions (Score:1)
1) Simulated annealing? I guess it's the most direct comparison but that is a terribly inefficient optimizer. I'm not sure what to make of this news in that regard, but it is definitely impressive in any case. Why not run some more advanced particle swarm algorithms in a direct head-to-head on a well-understood problem?
2) How accurate are these results for practical application? I can give you answers REALLY fast, but good luck verifying their accuracy.
Re:Two questions (Score:4, Informative)
Simulated annealing? I guess it's the most direct comparison but that is a terribly inefficient optimizer.
Do you know of any algorithms that are more efficient while still offering the same finite-time guarantee (of finding the optimal solution) that simulated annealing does?
This is one of the key points. More efficient methods are frequently more efficient because they wont search the entire space no matter how long you let them run. While simulated annealing wont search the entire space in practice, the operator has control over how much of the space gets sampled by altering the rate of convergence (the "cooling" rate)
The "more efficient method" that you mentioned, particle swarms, is only more efficient when such a finite-time guarantee is left behind. The finite-time guaranteed version of particle swarms is not more efficient, instead being equally as efficient.
Re: (Score:2)
Do you know of any algorithms that are more efficient while still offering the same finite-time guarantee (of finding the optimal solution) that simulated annealing does?
Simulated annealing requires that 1/T be grown logarithmically. In other words, the finite time guarantees are exponential time, just like direct search (i.e. trying every configuration).
I like simulated annealing, it's simple, easy to implement and easy to apply to a lot of problems. The finite time guarantees are not useful in practice h
Re: (Score:2)
This thing can only do simulated annealing. It is not a quantum computer that can run different algorithms.
Re: (Score:2)
It's called "quantum annealing". Look it up.
Re: (Score:2)
English is a descriptive language. Get over it. Get over yourself, too, while you're getting over stuff.
Re: (Score:2)
I see you looked it up. Well done.
Note careful terminology by Google (Score:5, Informative)
Despite being a computing device that relies on quantum effects, D-Wave's machine is not a "quantum computer [wikipedia.org]" as that term is defined by computer scientists.
Commendably, Google's blog post calls the device a "quantum annealer", rejecting D-Wave's self-label of "quantum computer" which is a misleading marketing ploy. Perhaps if D-Wave's device had come before theoretical CS researcher defined their computational model, the term "quantum computer" would have taken a different meaning, but as things stand the meaning of "quantum computer" was fixed well before D-Wave was founded.
Re: (Score:1)
This D-Wave thing looks pretty far from a general-purpose computer. I don't claim that I know how it works, but from the description at the corporation's website and the paper draft, it indeed looks like a big chunk of magnet (picturing the Ising model) with programmable coupling among dipolar cells, and a programmable background field. Building that thing may yield many engineering insights and should be lauded as such, but speaking of a computer (or a glorified analog calculator), it probably can't run
Re: (Score:2)
Yes, it only can optimizing a potential function, but that gives you a lot of mileage, because a huge amount of real world problems can be mapped onto a graph that can be embedded into the Ising spin model.
Re: (Score:2)
So analog computers then weren't computers either, since they didn't follow Turing's definition?
It computes with qubits. I think it is perfectly reasonable to call it a special purpose quantum computer.
Re: (Score:2)
It would be far more honest to call is a "limited usefulness single-purpose quantum computing device".
Incidentally, the Turing definition definition does not apply for analog computers. But a real quantum computer (not this D-Wave con device) _is_ a non-analog computer that can solve discrete problems like factoring numbers.
Re: (Score:2, Insightful)
Look I am quite aware what the gate model quantum computer is and can do, but it is disingenuous to pretend that it is the only game in town, and the only such machine that is allowed to be called a quantum computer.
Two competing models have been shown to be computationally equivalent, namely quantum cellular automatons and adiabatic quantum computing. The latter you get if the machine can implement an arbitrary Hamiltonian. The D-Wave machine is restricted in that it can only implement spin-glass like Hami
Re: (Score:2)
you've been posting a lot and seem intent on an assertion that the D-Wave is a "quantum computer" rather than an "analog computer utilizing quantum effect". The thing is, you don't really have anything to back your assertion. You admit that it is very limited and narrowly focused, but seem to believe that those facts are irrelevant because it utilizes a quantum effect.
Do you accept a flashlight as being a digital computer? It uses an on-off (digital) switch. Is any circuit board a digital computer by virtue
Re: (Score:2)
I believe in the descriptiveness of language. Does it compute? Yes, in the case of the D-Wave. No, in case of the flash light.
Does it utilize qubits as basic information processing unite? Yes, again in case of the D-Wave.
Hence, it is justified to call it a quantum computer. Albeit, it should be qualified as a restricted adiabatic quantum computer, or quantum annealer.
Until we know what kind of quantum computing architecture will win, it is ludicrous to pretend that there is just one way to do quantum compu
Re: (Score:2)
Sorry, but the flashlight does compute. Its function is an approximation of "battery not empty" AND "lightbulb not broken" AND "switch on" THEN "shine light".
This should amply demonstrate that your definition of "computer" is so broad it is completely meaningless and hence useless.
Re: (Score:2)
Please ask a any first grader if this amounts to the kind of complexity that is meant when people use the word "compute".
Re: (Score:2)
It is not. That is my whole point. But even more so, it is not the amount of universality and flexibility expected.
Re: (Score:2)
The problem is that this gets misunderstood. The "Quantum Computer" is the magic machine that can break encryption, compute everything massively faster, etc. The D-Wave is not that machine.
Re: (Score:2)
I regard this as an opportunity to educate the masses that Quantum Computers are not magical machines, and that the qubits aren't fairy dust. I.e. you can have a machine like D-Wave that utilizes them, yet is still fundamentally limited in what it can do.
Re: (Score:2)
Analog computers are computers, of course -- they just aren't Turing machines. In TCS, "computer" is not the name of any model of computation -- unlike "Turing machine", "register machine", "pushdown automaton" and "quantum computer". So the word "computer" retains its everyday meaning.
On the other hand, you wouldn't call a device with a stack a "pushdown automaton" unless it actually was a pushdown automaton, right? Similarly, I wouldn't call something a "quantum computer" unless it really corresponds t
Re: (Score:2)
There's a world of difference between a classical system like you describe and quantum annealing.
At any rate, entanglement on the chip has been demonstrated [aps.org], and outside experts comparing different models to characterize the chip, also came to the conclusion that it indeed performs quantum annealing. [nature.com]
At this point this question can be regarded as settled.
The only open, remaining question is how useful quantum annealing will be in practice.
As to Feynman, his original proposal of a quantum simulator is much cl [wavewatching.net]
Re: (Score:2)
Don't forget to write a note to the Physical Review X journal, they apparently have abysmal peer review.
Any particular reason why you ignore the other paper I linked?
Re: (Score:2)
You must have missed this clue in the abstract:
"Here, we present results from tests on a 108 qubit D-Wave One device based on superconducting flux qubits."
This paper was instrumental in settling the question if D-Wave performs quantum annealing.
Re: (Score:2)
No, quantum annealing only shares conceptual similarities to this macroscopic physical process.
https://www.youtube.com/watch?... [youtube.com]
Re: (Score:2)
Simulated annealing is an optimization process for a computer, and I've always been a bit dubious of the "annealing". Take your input variables, and your function from those variables that determines how good the result is. Picture your input variables as making an N-dimensional space. Pick a spot in that space randomly. Make a random displacement. Compare the goodness function values there. If the new spot has a better value, go there. Otherwise, go there with a probability determined by a "tempera
Re: (Score:2)
Pretty good picture of the process.
One thing to add though, in addition to quantum tunneling true quantum annealing should also be able to tap into another resource: Entanglement. If qubits are entangled they are described by the same wavefunction, i.e. they are essentially a non-localized smeared out unity, and will experience the valleys in more than one place. Entanglement is very short lived on the D-Wave machine, and very sensitive to temperature increase.
The fact that the chip's performance is extreme [wavewatching.net]
Re: (Score:2)
No that's not the trick. The trick is making the qbits coherent with each other so that one can use the machine for quantum computation, just replicating a number of qbits on a chip is trivial in comparison. Now D-wave says that coherency isn't that important and that the minor quantum effects that they get is good enough (=increases performance somehow). That there are quantum effects in the machine have been shown but AFAIK not that those effects are beneficial.
While running very cold for a "quantum compu
More info (Score:2)
I didn't realize that quantum computers were commercially sold now. I wondered about the price; I wasn't able to find out how much this new computer costs. But per Wikipedia, the first model of this computer sold for about $10 million; and I presume that this new and more powerful version costs more. (The press releases say that this thing computes at extremely low temperatures, so it must include an expensive cooling system.)
Interestingly, the Wikipedia article says that a lot of famous people were dubi
Re: (Score:1)
Only if you observe them being sold.
Re: (Score:2)
They sold the D-Wave One for about $10M to Lockheed. Figure that'll still get you a current model.
Re: (Score:2)
Why didn't they get Maple syrup instead?
And who forced NASA and Google to get their machine?
Set it on fire? (Score:2)
Annealing? I RTFS and am envisioning repeatedly setting the D-Wave on fire and letting it cool slowly.
After reading the summary on the Google Research Blog...I still get that picture. Not really my field. :-(
Re: (Score:2)
Annealing? I RTFS and am envisioning repeatedly setting the D-Wave on fire and letting it cool slowly.
As I recall, the Pentium 4 chip worked along those same lines.
Snake Oil (Score:2)
However a few million dollar is very cheap as insurance for Google.
There is absolutely no firm scientific evidence that anything is actually being computed by so called quantum computers, hence Google hedging its language.
The press is stupid (Score:2)
This is a comparison of the D-Wave with a simulation of the Quantum Algorithm on a classical computer.
This is nonsense! You really have to compare the best known algorithms for each machine in order to get any meaningful results. Turns out that that the classical algorithm still wipes the floor with the D-Wave on a moderately powerful single core PC when the comparison is fair.
This factor is not even a strong proof that the D-Wave is using quantum effects, just that it simulates them very well.
The truly pat
Re: (Score:2)
Update: Here is a really good summary of what is going on:
http://www.scottaaronson.com/b... [scottaaronson.com]
tl;dr: Nice research, no practical speed-ups, unclear whether the D-WAVE can even achieve any real speed-up.
Re: (Score:2)
According to the many-worlds interpretation [wikipedia.org] of quantum mechanics, reality is a Beowulf cluster. Sort of.
Re: (Score:2)
There are some similarities but the story has long moved past that. [wavewatching.net]
Re: (Score:2)
Every quantum computer is a probabilistic machine. It's baked into the cake.
The quantum superposition collapses when you measure. Just one measurement will not necessarily give you the right answer (this also holds for gate based quantum computers e.g. Shor's factorization algorithm).
But just like Probabilistic Turing machines can outperform their deterministic brethren, quantum computers can do more than Turing machines with only a classical random number source, because quantum probabilities follow non-c
Re: (Score:2)
actually, it is now widely conjectured that P=BPP, or that any efficient probabilistic algorithm can be efficiently simulated by a polynomial-time deterministic TM.
Re: (Score:2)
Interesting, wasn't aware of that, especially since in practice randomized algorithm often outperform the next best deterministic ones.
What informs this conjecture?
Re: (Score:2)
i'd imagine that it's because people keep finding ways to replace the randomness in specific algorithms with deterministic chaos that's "good enough". maybe that's not the best basis for believing it, but imho it's better than the reason people think P!=NP. i mean, even in reality, those randomized algorithms (usually) work just fine with a PRNG instead of "truly random" numbers.
otoh, i agree that it is a bit weird. maybe we can think of the randomization as being a shitty oracle? i mean, imagine taking an
Re: (Score:2)
Re: (Score:2)
In this case whoever made the press release and indicated any real-world speedup. Not a direct lie, but gross misdirection.
The paper is actually honest and admits that they are not faster than a classical computer AT ALL: "Based on the results presented here, one cannot claim a quantum speedup for D-Wave 2X, as this would require that the quantum processor in question outperforms the best known classical algorithm."
The thing is, the D-Wave is only faster than a simulation of the Quantum Algorithm on a class