28 votes
Accepted

Is there proof that the D-wave (one) is a quantum computer and is effective?

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 ...
user avatar
  • 1,679
19 votes
Accepted

Why can't quantum annealing be described by a gate model?

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}\...
user avatar
  • 3,487
17 votes

Why can't quantum annealing be described by a gate model?

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 ...
user avatar
  • 1,457
15 votes

Level of advantage provided by annealing for traveling salesman

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 ...
user avatar
14 votes
Accepted

Why is it crucial that the initial Hamiltonian does not commute with the final Hamiltonian in adiabatic quantum computation?

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 ...
user avatar
14 votes
Accepted

Are spin-glass problems NP (-complete)?

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" ...
user avatar
  • 14.4k
13 votes
Accepted

How long does quantum annealing take to find the solution to a given problem?

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....
user avatar
  • 1,679
12 votes
Accepted

What is the difference between quantum annealing and adiabatic quantum computation models?

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). ...
user avatar
  • 1,679
11 votes
Accepted

What precisely is quantum annealing?

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 ...
user avatar
  • 1,679
10 votes
Accepted

How much faster is “D-Wave Two” compared to its predecessor?

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 ...
user avatar
8 votes

Is there proof that the D-wave (one) is a quantum computer and is effective?

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 ...
user avatar
  • 2,229
7 votes

How much faster is “D-Wave Two” compared to its predecessor?

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-...
user avatar
6 votes
Accepted

Adiabatic Quantum Computing vs Adiabatic Quantum Optimization vs Quantum Annealing

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 ...
user avatar
  • 12.1k
6 votes

Why is it crucial that the initial Hamiltonian does not commute with the final Hamiltonian in adiabatic quantum computation?

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 ...
user avatar
  • 47.6k
6 votes
Accepted

Assessing speed-up via Quantum-Stochastic correspondence

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 ...
user avatar
  • 1,679
6 votes
Accepted

Adiabatic Quantum Computer e intermediate Hamiltonian evolves the state within the manifold

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 ...
user avatar
5 votes
Accepted

What is the difference between QAOA and Quantum Annealing?

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$ ...
user avatar
  • 1,679
5 votes
Accepted

When and where was the first use of the term Chimera?

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 ...
user avatar
4 votes
Accepted

Are there established best practices for designing Dwave embeddings?

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 ...
user avatar
4 votes

Are there established best practices for designing Dwave embeddings?

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 ...
user avatar
4 votes
Accepted

Can quantum annealing find excited states?

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 ...
user avatar
  • 12.1k
4 votes
Accepted

What precisely is Reverse Annealing?

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

What is the computational complexity of quantum annealing?

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 ...
user avatar
3 votes
Accepted

Hardware wise, how does D-Wave achieve quantum annealing?

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 ...
user avatar
  • 1,679
3 votes

What is the difference between quantum annealing and adiabatic quantum computation models?

All three of the bulleted or numbered claims in your OP are correct. But the flaw in your logic in combining them together is that D-Wave is not a "universal" quantum annealer, in the sense ...
user avatar
  • 2,107
3 votes

Why is it crucial that the initial Hamiltonian does not commute with the final Hamiltonian in adiabatic quantum computation?

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 ...
user avatar
3 votes

Why is it crucial that the initial Hamiltonian does not commute with the final Hamiltonian in adiabatic quantum computation?

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 & -...
user avatar
  • 12.1k
3 votes

What is an example of a simple QUBO problem?

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 ...
user avatar
  • 131
3 votes
Accepted

Can QAOA be considered as simulation of a quantum annealer on a gate-based quantum computer?

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 ...
user avatar
  • 12.7k
3 votes
Accepted

What is the computational complexity of quantum annealing?

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

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