26

There is still a search for problems where the D-Wave shows improvement over classical algorithms. One might recall media splashes where the D-Wave solved some instances $10^8$ times faster than a classical algorithms but forgot to mention that the problem can be solved in polynomial time using minimum weight perfect matching. Denchev showing $10^8$ ...


12

As Troyer and Lidar saw no speed increase with the D-Wave 1 compared to classical computers, the D-Wave 2 benchmark figure reported in 2013 of 3600 times as fast as CPLEX (the best algorithm on a conventional machine) suggests the D-Wave 2 is 3600 times as fast as the D-Wave 1. However: the results are in a pretty restricted set of parameters, so this may ...


11

There are two points I'd make here. D-Wave's computer and Google's computer are fundamentally different. D-Wave's computer is a quantum annealer. Imagine a landscape with some grassy hills. If you put a ball at the top of the hill, it will roll to a local minima, or even the minimum - in this case, a valley. Similarly, a quantum annealer has the qubits as ...


11

Short explanation: D-Wave implements quantum annealing, while Google has digitized adiabatic quantum computation. Lengthy Explanation: D-Wave advertises their line of quantum computers as having thousands of qubits, though these systems are designed specifically for quadratic unconstrained binary optimization. More information about D-Wave's manufacturing ...


10

The common Computer Science usage of 'ignoring constants' is only useful where the differences in performance of various kinds of hardware architecture or software can be ignored with a little bit of massaging. But even in classical computation, it is important to be aware of the impact of architecture (caching behaviour, hard disk usage) if you want to ...


7

In the classical case, there is a pretty big difference between digital computers and analogue ones. The methodology and hardware is very much distinct (in all cases I know of, at least). The divide is still there in the quantum case, but it doesn't run quite as deep. The hardware can be similar, but requirements on how it behaves and how to manipulate it ...


7

As usual, it is too soon to make comparisons like this. The power consumption of a device will depend strongly on the architecture it uses, for one. However, in principle, there is no reason to suspect that quantum computers would consume more energy than classical devices performing the same operations. Indeed, one would expect the opposite, the ...


7

As far as I know the closest answer to your question for applications is given in the recent (still unpublished) work presented at the March meeting by Bibek Pokharel, where he compares graph 3-coloring instances on D-Wave Two, D-Wave 2X and D-Wave 2000Q, all other things staying reasonably equal. The short answer is that all the performance increase is ...


6

Is there proof that the D-wave (one) is a quantum computer and is effective? D-Wave Video - Offers an explanation of: "How do we know ...": https://youtu.be/kq9VqR0ZGNc One analogy you might make with the D-Wave One, an adiabatic ('analog') computer, is to the "south-pointing chariot" or the "Antikythera mechanism". A lengthy explanation is offered in ...


6

The first part of your question seems like a duplicate of an existing QC SE post: Are there emulators for quantum computers?. I'm not completely sure what you mean by building a quantum computer from scratch inside simulations. However, yes, you can make software simulations of a quantum computer using your average laptop/desktop. The exact "limit" will ...


5

Well, I'm working on a simulator of a quantum computer currently. The basic idea of quantum computing, of course, is gates represented by matrices applied to qubits represented by vectors. Using Python's numpy package, this isn't that hard to program in the most basic sense. From there, one might expand upon, of course, the interface. One might also ...


5

Some near-term quantum algorithms rely on getting lucky with the measurements, and in fact these algorithms will not scale efficiently to large sizes. But most quantum algorithms don't have this problem; it is required that the amount luck needed [i.e. retries] scales only polynomially with the problem size. For example, Shor's algorithm fails if the ...


4

You may be confusing two uses of the word "base". One definition of "base" has to do with how many digits are used to represent a number. For example, base two uses the digits 0 and 1, and the number five is written as 101 in base two. But in quantum mechanics there is another use of the word "base" which has to do with basis vectors for a vector space. This ...


4

The answer to the first question (why is energy efficiency in quantum vs classical not discussed as often as speed?) is: in part because the problem is less univocal and in part because the answer is less flattering. The answer to the second question (are quantum computers more or less energetically efficient?) will change with time, since it depends on ...


3

I feel like this answer mostly rests on an underlying misunderstanding of what it means to "simulate" something. Generally speaking, to "simulate" a complex system means to reproduce certain features of such system with a platform that is easier to control (often, but not always, a classical computer). Therefore, the question of whether "one can simulate a ...


3

I will attempt to address the following question only. I'm asking whether the method of 'running' quantum algorithms on a 'quantum computer' 'simulated' on a classical computer would be able to outperform normal classical algorithms (preferably for problems that not obviously involve quantum simulation) The closest thing to this that I am aware of are ...


3

Let me first answer the general question how to get a reasonably tight Lieb-Robinson (LR) speed when you are facing a generic locally interacting lattice model, and then I'll come back to the 1D XY model in your question, which is very special to be exactly solvable. General Method The method to obtain the tightest bound to date (for a generic short-range ...


2

The preferred basis problem is essentially something from the many worlds interpretation: If we are to interpret a superposition as representing many universes, what basis should we choose? Since this comes from the foundations of QM, this aspect of your question is perhaps better suited to the physics stack exchange. Is there a preferred basis for a ...


2

You can't ignore the constant factors when comparing quantum computation to classical computation. They're too large. For example, here is an image from some slides I presented last year: The things along the bottom are magic state factories. They have a footprint of 150K physical qubits. Since the AND gate uses 150K qubits for 0.6 milliseconds, we surmise ...


1

While other answers provide good points, I feel that I still disagree a bit. So, I will share my own thoughts on this point. In short, I think featuring the constant 'as is' is a wasted opportunity at best. Perhaps it is the best we are able to get for now, but it is far from ideal. But first, I think a brief excursion is nessecary. When do we have an ...


1

The question here seems to be: "can a classical computer be more efficient by simulating a quantum computer?" and "what research has been done on this?" I think it's important, first, to point out that no one is 100% sure that a quantum computer is even actually better than a classical computer, whether or not we have the fastest possible algorithms for a ...


1

Easiest thing talk about the algorithms for each architecture and the difference between physical and logical qubits. As far as I know we do not know yet how to perform quantum error correction efficiently on an adiabatic machine. Most computations on these devices are just repeated lots and lots of times without much error correction. For the gate model ...


Only top voted, non community-wiki answers of a minimum length are eligible