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$ ...


18

A Quantum Annealer, such as a D-Wave machine is a physical representation of the Ising model and as such has a 'problem' Hamiltonian of the form $$H_P = \sum_{J=1}^nh_j\sigma_j^z + \sum_{i, j}J_{ij}\sigma_i^z\sigma_j^z.$$ Essentially, the problem to be solved is mapped to the above Hamiltonian. The system starts with the Hamiltonian $H_I = \sum_{J=1}^nh'_j\...


16

Annealing's more of an analog tactic. The gist is that you have some weird function that you want to optimize. So, you bounce around it. At first, the "temperature" is very high, such that the selected point can bounce around a lot. Then as the algorithm "cools", the temperature goes down, and the bouncing becomes less aggressive. Ultimately, it settles ...


15

First, let me note that quantum annealing, or more precisely the adiabatic quantum computation model is polynomially equivalent to the conventional gate-based quantum computation model. Second, the general traveling salesman problem is NP complete. Third, it is generally believed that the with gate-based quantum computation one cannot solve in polinomial ...


14

The time to solution (tts) is highly dependent on the Hamiltonian of the problem one would like to solve. The D-Wave uses a spin-glass-like Hamiltonian which can be in the NP-Complete complexity class. Due to having to run the annealing process multiple times, tts measures are typically quantified by how long it takes to find the ground state some percent ...


13

In adiabatic QC, you encode your problem in a Hamiltonian such that your result can be extracted from the ground state. Preparing that ground state is hard to do directly, so you instead prepare the ground state of an 'easy' Hamiltonian, and then slowly interpolate between the two. If you go slow enough, the state of your system will stay in the ground state....


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 ...


7

I'll do my best to address your three points. My previous answer to an earlier question about the difference between quantum annealing and adiabatic quantum computation can be found here. I'm in agreement with Lidar that quantum annealing can't be defined without considerations of algorithms and hardware. That being said, the canonical framework for ...


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

Yes. This has been done by Morita and Nishimori in their 2008 publication, "Mathematical Foundations of Quantum Annealing." https://arxiv.org/abs/0806.1859 In Section 5 they derive the convergence conditions from path integral Monte Carlo and Green function Monte Carlo methods. To quote; In Sec. 5 we have derived the convergence condition of QA ...


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 ...


5

Vinci and Lidar have a nice explanation in their introduction of non-stoquastic Hamiltonians in quantum annealing (which is necessary to a quantum annealing device to simulate gate model computation). https://arxiv.org/abs/1701.07494 It is well known that the solution of computational problems can be encoded into the ground state of a time-dependent ...


5

The earliest non-internal reference I can find is in NIPS 2009 from a Google/D-Wave effort1. You'll notice that the two Choi papers, in addition to not using the term "Chimera", do not describe a Chimera graph (and note that the name comes from D-Wave, not from graph theory). For a good early reference on Chimera, I recommend Bunyk et al., 20141 , which ...


4

If two matrices (in this case, Hamiltonians) commute, they have the same eigenvectors. So, if you prepare a ground state of the first Hamiltonian, then that will (roughly speaking) remain an eigenstate throughout the whole adiabatic evolution, and so you get out just what you put in. There's no value to it. If you want to be a little more strict, then it ...


4

Until recently, D-Wave's quantum annealing devices always started from a uniform superposition over all $N$ qubits:                                         &...


3

One of the advantages, as stated in the paper you linked, is that with QAOA you can increase the precision arbitrarily, whereas QA will only find the solution with probability 1 as $T \to \infty$ which is impractical. In addition if $T$ is too long you're likely to not find the solution as the probability is not monotonic. I believe an example of this can be ...


3

Quantum annealing as defined by Chakrabarti 1981 and later implemented by Kadowaki and Nishimori 1998 uses a varying transverse magnetic field to facilitate tunneling through the energy landscape of an optimization problem. The system is prepared in the ground state of a Hamiltonian and then the transverse field is applied and slowly reduced (adiabatically) ...


3

In the context of Ising optimizers having an initial Hamiltonian that commutes with the problem Hamiltonian means it is essentially products of $\sigma^Z$ operators, which means that its eigenstates are classical bitstrings. Hence the groundstate at the beginning ($t$=0) will be classical as well, not a superposition of all possible bitstrings. Moreover, ...


3

There are multiple factors that affect an embedding's performance, including what Davide mentions. Depending on your background, the following interpretation of Davide's answer might be easier for you to understand: Early in the anneal, the Ising (classical/user-input/final) Hamiltonian has no effect, which means that two spins in a chain are not compelled ...


3

On parameter setting, check our work: https://journals.aps.org/prx/abstract/10.1103/PhysRevX.5.031040 (Basically you want to make sure that the chains representing the logical qubit have a phase transition synchronized with the minimum gap). But in general this is a hard problem, and precision issues connected to the embedding characteristics are probably ...


2

I will assume you are asking about D-Wave's quantum annealer. If there is a part of the learning process that can fit the QUBO (Quadratic Unconstrained Binary Optimization) formulation, then yes. The problem however is what to consider as binary variables of your problem. In CNN, we have in general real-valued parameters that we tweak for training (using ...


2

A couple papers are out there on algorithms which can be constructed using reverse annealing, http://iopscience.iop.org/article/10.1088/1367-2630/aa59c4/meta and https://arxiv.org/abs/1609.05875 (it is worth pointing out previous somewhat related closed system work: https://link.springer.com/article/10.1007/s11128-010-0168-z). As far as experimental results, ...


2

Well first you will have to specify the MST in a QUBO/Ising formulation. In this article showing formulations for different types of problems, section 8.1 is about the MST with a maximal degree constraint. This paper contains results of Spanning Tree calculations. When you have the formulation, you map it on the Chimera Graph if the hardware size is not ...


1

The errors from quantum annealing apart from having crappy qubits will come from the imperfect instantiation of the qubit coupling. The first problem i.e having bad qubits can ultimately be mitigated by a kind of error correction look at Error-corrected quantum annealing with hundreds of qubits (Pudenz et al., 2014). But as it turns out the second problem ...


1

You can use a technique of reduction by substitution. Here we represent using ancilla representing a Boolean constraint $ z\Leftrightarrow x_1\wedge x_2 $ as a quadratic penalty function : $$P(x_1,x_2;z) = x_1 x_2 - 2(x_1+x_2)z + 3z$$ For a triplet interaction, you use it to reduce to pairwise : $$ x_1 x_2 x_3 = \min_z \bigl\{ z x_3 + M P(x_1,x_2;z) \bigr\},...


1

You need to introduce ancillary variables and minimize over them; which would enable you to have a QUBO form with only pairing terms. For example, if your binary variables are called $ x,y,z $ and you have a $ a*xyz $ term with the coefficient $ a$, you can use a technique of reduction by minimum selection where you introduce another variable $w$ such that ...


1

This answer reflects my understanding of what D-wave have to say about this, in the 2013 whitepaper they link to: Programming With D-Wave: Map Coloring Problem To back up the question, we find once again the claim: "superposition" states [...] give a quantum computer the ability to quickly solve certain classes of complex problems such as optimization, ...


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