# Tag Info

## Hot answers tagged annealing

28

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 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.... 14 Background Computational problems come in a variety of types, for example: decision problem: given input$x$, output "YES" if$x$belongs to a fixed set$L$and output "NO" otherwise, function problem: given input$x$, output a$y$such that$(x, y)$belongs to a fixed relation$R$, optimization problem: given objective$f$and ... 13 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 ... 11 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 quantum ... 10 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 quantum ... 10 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 ... 8 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 ... 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 I'm very happy my answer from 3 years ago to that question is still helping people! The answer to your new question is found here: Notice that there is another term here which is "Quantum Adiabatic Algorithm" or QAA. In fact those QAA papers from 2000 and 2001 papers call it "Quantum Adiabatic Evolution Algorithm" or QAEA, and "Quantum Computation by ... 6 This is a very particular application of Adiabatic Quantum Computing so I think it's worth briefly mentioning some context. Roughly speaking, one wants to show that given a quantum circuit defined as a sequence of unitary gates$U_1,U_2,\ldots,U_L$it is possible to define a version of the quantum adiabatic algorithm that reproduces (a state with a large ... 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 ... 5 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 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 ... 4 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 ... 4 In Practice: Quantum annealing almost always gives excited states in practice. To get the exact ground state at the end, you need the adiabatic passage to be perfect. The closest thing to a perfect adiabatic passage is probably this recent paper where they get the ground state with 0.975 fidelity, but this is for 3 qubits with a very simple Hamiltonian (... 4 Until recently, D-Wave's quantum annealing devices always started from a uniform superposition over all$N$qubits: &... 4 Currently, it is not preciselly known whether quantum annealers bring any significant speed up. Lets take some task having exponential complexity on classical computer. If you run it on quantum annealer it will probably run faster. However the reason is not reduced complexity (it is still exponential) but smaller constants in function decribing the task ... 3 Let's start with a simple example where$H_i$and$H_f$commute because they are both diagonal:$H_i= \begin{pmatrix}1 & 0\\ 0 & -1 \end{pmatrix} H_p= \begin{pmatrix}-1 & 0\\ 0 & -0.1 \end{pmatrix} $The eigenvector with lowest eigenvalue (i.e. the ground state) of$H_i$is$|1\rangle $so we start in this state. The ground state of$...

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

Below you'll find a brief and simple example. I also recommend that you read A Tutorial on Formulating and Using QUBO Models as it covers the topic in more detail. Example using switches So your idiot sibling fancies themselves an electrician, and rewired your house's climate control system while you were out. Lucky for you, there are only two switches and ...

3

If you use infinite depth then QAOA can be consider as quantum annealer on gate-based. The authors of QAOA original paper probably deduce it from quantum annealing. What I mean by infinite depth is you take $p \to \infty$ in the operator $$U(\beta, \gamma) = \Pi_{i=1}^p U_B(\beta_i)U_C(\gamma_i)$$ Your are right about the commutation problem. However, ...

3

For a problem of size $N$, computational complexity of quantum annealing is $\mathcal{O}(e^{\sqrt{N}})$. This is better than simulated annealing, which has a complexity of $\mathcal{O}(e^{N})$. Both these complexities are mentioned in this paper. More analysis needs to be done to answer this question quantitatively. But, qualitatively, we can expect to have ...

3

Adam gave an excellent answer explaining that the "decision version" of the Ising model could be considered NP-complete, but the term doesn't make sense without that extra context. I'll answer some of the other parts which I think were not yet addressed: "But I don't know an obvious algorithm to check if a given solution is the true ground ...

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