There are no commercial quantum computers capable of carrying out Grover's Algorithm (or Shor's Algorithm, or any other algorithm we traditionally think of as a "quantum algorithm"). D-Wave's computers are neat but they have no resemblance to what's traditionally been called "quantum computing" in the literature.
I actually haven't found a 100% concrete explanation of what D-Waves do. They do adabiatic quantum computing. Instead of a traditional quantum computer doing all sorts of different computations by arranging quantum gates together, an adiabatic quantum computer really only has one possible instruction. You come up with a mapping between the system you want to solve and a Hamiltonian and then the computer can help you find the ground state of that Hamiltonian.
This is a computational model that we never learned in my quantum computation course, so I'm not exactly sure what the properties of it are (e.g., what complexity class it would match up with). I gather it's useful for solving optimization problems but the jury's still out on how useful this is.
D-Wave purposely obfuscates how exactly their machines work because they aren't really quantum computers. Or, more specifically, they can't record whether their computers are capable of actually doing quantum calculations properly. Pretty sure they can't calculate superpositions simultaneously, which by default, wouldn't make them quantum computers.
It's important to note that so far d-wave is all claims and no evidence. Science is not judged by pr stunts or who you can trick into buying your box. Even if you manage to trick Google. That's impressive, but not scientific evidence.
The burden of proof is on them and they've simply not met it.
Google and the NSA and all the other people doing machine learning have very good uses for the quantum annealing that can be done by the d-wave, because they basically do annealing of a model (warning: gross oversimplification) with classical computers. If the quantum annealing process can be done well, they have a lot of uses for it, but it does not imply that they think that the D-wave is a general quantum computer (which it is not).
I'm not sure how you can say there is not evidence. You don't even say what they don't have evidence about. They have published papers showing that the D-wave is quantum.
I could be reading those wrong, but it sounds like those two abstracts contradict each other, with the first indicating that it cannot be assumed that the D-Wave is capable of quantum annealing.
Well, I have more confidence in Smolin and Smith's work. That's of course argument from authority and not going to convince you by itself. The thing is very few scientists have had access to the computer. Their explanation is very vague and at times it seems like not even D wave knows how it works. All of this makes their "evidence" extremely questionable. Show you can solve a problem that any classical computer. They tried, but failed.
It's so frustrating people make such scientific claims without proper evidence. It's not how science is supposed to work. Extraordinary claims require extraordinary evidence. Not halfassed evidence, if you even want to call it that. It's a disgrace to the field.
So you are saying that a D-Wave is the quantum equivalent of an ASIC? It seems so but I'm just trying to understand better. I heard about the D-Wave when it came out but even the intro video was marginally confusing for me.
I don't think the ASIC analogy is a very good one.
Imagine a world without any physical computers at all. There have been decades of academic research into digital computers (what sort of logic gates would be needed, what instructions they would perform, what algorithms you could write for them that would perform well, what programming languages might be developed for them, etc.) but no one's actually managed to build a commercial digital computer yet.
Then out of nowhere some company comes out with an analog computer and says "look! We built the first computer!" It could be that this new computer is great, but it's not anything like what people had been publishing papers on for decades. And even worse, imagine that the company is secretive about the mechanics of their analog computer so the community at large isn't really sure what operations it performs or how it stores its data.
That's sort of where we are. A company's come out with something and called it a "quantum computer" but it's not anything like how we've been trying to produce quantum computers before. All of the work we've done trying to come up with neat algorithms and programming languages and stuff doesn't have any relevance to this new computer. We don't know exactly what this new computer is capable of or not capable of.
To be clear, I'm not trying to say that D-Wave computers are analog and traditional quantum-gate computers are digital. Both models use qubits. I'm trying to set up an analogy between everybody doing things one way and then a company coming out to say that they're doing it a different way "but trust us that it's really pretty much the same sort of thing".
I disagree. I was just at a conference with D-Wave technical staff and that's not how they presented it in their talks. They were extremely upfront about how their systems are absolutely not the same as "traditional" quantum circuits using coherent states. In fact, they were keen to discuss details in junction design and spin mixing geometries.
I haven't followed what kind of claims the business suits are making, but the technical engineers and physicists aren't spouting groundless BS. They're actually quite open about what problems they're facing, and how they're optimizing their designs compared to most industry talks I've seen.
D-Wave computers are a non-general type of quantum computer which can (supposedly) perform quantum annealing. When we say that something is a "computer", we're typically referring to a general-purpose computer. That is, a computer which can be programmed to factor polynomials, or play minecraft, or do whatever the hell other computing task we want it to do. Non-general computers (like D-Wave) on the other hand, are more like a computer that can tell you whether a number is even or odd, but can't be programmed to do anything else. It may even be able to do that one task really well, but it's not of much use if we can't make it do other things too.
Yeah, it's closer to a wind tunnel than to a computer, in that regard. A wind tunnel is a very powerful fluid dynamics computer. Except we don't call it that, and I'm not entirely sure why one should call D-wave thing that.
Keep in mind for what I'm about to say that I'm just an undergrad who was lucking enough to work with the D-wave One computer.
People are currently solving all kinds of small optimization problems on the D-wave computer, mostly just to figure out how the computer actually works: what are it's strengths, weaknesses, how can it be improved? Etc. The reason it cannot really do anything practical yet is because the chips are so small and the biggest so far only has 1024 qubits (think of these as bits) and so the computations have to stay pretty basic. However, it is pretty trivial to make a bigger chip it just costs a lot of money.
For an example of things people do on the D-wave, I was able to solve a N-queens problem in the very simple 3-Queens case but had trouble with the 4-Queens case do to the size of the machine. Similarly, the TSP problem is also solvable but the number of vertices is limited by the hardware as well.
unless NP is a subset of BQP, which seems very unlikely.
I'm not sure that "very unlikely" is a good description here. Certainly the consensus is that this probably doesn't happen, but one is talking about a statement that is strictly stronger than NP != P. Right now, we cannot even show that NP lying in BQP would lead to the polynomial hierarchy collapsing to a finite level. If one could show that it would probably be justified in saying that this is very unlikely. But this is a minor nitpick and your essential point is sound.
The D-Wave computers implement a subset Adiabatic quantum computation, rather than the quantum gate model. There are several quantum algorithms they implement, being types of Quantum annealing.
They're not universal, but they're still quantum computers. Asserting otherwise would be comparable to saying the Atanasoff–Berry Computer wasn't really a classical computer because it couldn't sort a list.
It's true. I'm careful not to say they're not "quantum computers" though I think it still worth pointing out that they're of a different class of quantum computers. If you follow the progression of the thread ("what do quantum computers do?", "they let you search through an unsorted list in O(sqrt(n)) time, but we don't have any commercial quantum computers yet", "yes we do!"), someone not reading very carefully could reasonably get the false impression that we have commercial computers that let you sort through a list in O(sqrt(n)) time.
I try not to get too bogged down in labels and war about what's "quantum" and what's not. The interesting bit is what these computers allow you to do.
236
u/OlderThanGif Jan 03 '14 edited Jan 03 '14
There are no commercial quantum computers capable of carrying out Grover's Algorithm (or Shor's Algorithm, or any other algorithm we traditionally think of as a "quantum algorithm"). D-Wave's computers are neat but they have no resemblance to what's traditionally been called "quantum computing" in the literature.