Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
23 votes
Accepted

Did D-Wave show quantum advantage in 2023?

A clear case of quantum advantage Google's quantum group demonstrated quantum advantage with a much earlier version of D-Wave hardware in the following figure from a 2016 paper, in which the D-Wave ...
user1271772 No more free time's user avatar
15 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 ...
James Wootton's user avatar
14 votes

Are quantum computers just a variant on Analog computers of the 50's & 60's that many have never seen nor used?

Here is a quick list of notable differences between analog and quantum computers: Analog computers can't pass Bell tests. The state space of an analog computer with N sliders is N dimensional. The ...
Craig Gidney's user avatar
  • 37.5k
13 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). ...
Andrew O's user avatar
  • 1,749
12 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 ...
Andrew O's user avatar
  • 1,749
9 votes

Are quantum computers just a variant on Analog computers of the 50's & 60's that many have never seen nor used?

What work has been done on the mapping of quantum phenomena to analog computing, and learning from that analogy? A starting place (with a lot of good references) to learn about analog quantum ...
user1271772 No more free time's user avatar
9 votes
Accepted

Can adiabatic quantum computing be faster than Grover's algorithm?

Good question. For unstructured search, adiabatic quantum computation indeed gives the exact same $\sqrt{N}$ speedup that the standard gate-based Grover's algorithm does, as proven in this important ...
tparker's user avatar
  • 2,791
9 votes
Accepted

Is there a general method of expressing optimization problem as a Hamiltonian?

As requested in the comments, here is a worked example. The main body deals with minimizing $f(x)$ for a specific problem. At the bottom follows a brief discussion of constraints then a brief ...
bRost03's user avatar
  • 579
8 votes

What are XX, YY, YZ etc. couplings?

In the mentioned context, what is meant is that, between a pair of qubits that are coupled, an XX coupling means something of the form $$ X\otimes X\equiv\left(\begin{array}{cccc} 0 & 0 & 0 &...
DaftWullie's user avatar
  • 58.6k
8 votes
Accepted

Why is the time ordering omitted in the trotterised version of the time-dependent evolution operator?

Ok, here's my attempt: take a time-dependent Hamiltonian $H(t)$ and consider its evolution in the time interval $[0,t]$. Discretize this interval in $k$ steps of length $\Delta \tau \equiv t/k$ $$ \...
Gianni Mossi's user avatar
7 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 ...
DaftWullie's user avatar
  • 58.6k
7 votes

Does the D-Wave hardware show any advantage for academic use-cases, for example in condensed matter physics?

Interest in academia In the past, only a small number of academic institutions, with a small number of professors, existed. Now there's about 30,000 universities and who knows how many colleges, ...
user1271772 No more free time's 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 ...
user1271772 No more free time's user avatar
6 votes

How to recognize if a paper is talking about quantum annealing or gate logic?

I've not looked at those papers specifically, but there are several different models for quantum computation (see here), including the gate model and the adiabatic model, which are polynomial time ...
DaftWullie's user avatar
  • 58.6k
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 ...
Gianni Mossi's user avatar
6 votes

In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed?

Grover's algorithm We are given a function $f(a)$ such that $f(a)=0$ for all of the $N$ possible values of $a$, except when $a=\omega$ in which case we have $f(\omega)=1$. Assuming that this $f(a)$ ...
user1271772 No more free time's user avatar
6 votes
Accepted

Under what conditions the minimum eigengap is non-zero?

I think this is formally undecidable. In detail, Cubitt, Perez-Garcia, and Wolf (arxiv, Nature) reduced the problem of determining the gap of a translationally-invariant Hamiltonian to the problem of ...
Mark Spinelli's user avatar
6 votes

Can Shor's algorithm be done with the same efficiency on an adiabatic quantum computer as on a circuit-based one?

Initially, Aharanov et al. showed that adiabatic computation is polynomially equivalent to gate-based quantum computation. There could be a significant, but still only polynomial overhead in ...
Mark Spinelli's user avatar
5 votes

Can we do adiabatic quantum computing with a quantum circuit model and how?

Adiabatic Quantum Computation is simply the time-evolution of a Hamiltonian where the system is prepared in a particular initial state (the ground state) and the Hamiltonian varies slowly in time. ...
DaftWullie's user avatar
  • 58.6k
5 votes
Accepted

What is the correspondence between adiabatic phase and a topological phase?

When a quantum system, parametrized by a manifold of classical parameters, evolves along a closed path in the parameter space, its state experiences a unitary transformation, which is called a ...
David Bar Moshe's user avatar
5 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:               ...
Mark Fingerhuth's user avatar
5 votes
Accepted

How to tell if the ground states of two Hamiltonians are solutions of the same optimization problem?

Short Answer: It is potentially hard (as bRost03 indicates in the comments). To be precise, coNP-hard. Longer Answer: In adiabatic quantum computation, the ground-...
Niel de Beaudrap's 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 ...
user1271772 No more free time's user avatar
4 votes

Are quantum computers just a variant on Analog computers of the 50's & 60's that many have never seen nor used?

Are quantum computers just a variant on Analog computers of the 50's & 60's that many have never seen nor used? No, they are not. The digital vs analog factor is not the point here, the ...
glS's user avatar
  • 25.2k
4 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 ...
tparker's user avatar
  • 2,791
4 votes

What is the correspondence between adiabatic phase and a topological phase?

From Wikipedia: In physics, topological order is a kind of order in the zero-temperature phase of matter (also known as quantum matter). Macroscopically, topological order is defined and ...
DaftWullie's user avatar
  • 58.6k
4 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 ...
Fax's user avatar
  • 141
4 votes

Why QAOA with $p \rightarrow \infty $ gives the optimal solution?

The Quantum Approximate Optimization Algorithm is closely related to the Quantum Adiabatic Algorithm. Let's say we have a simple Hamiltonian (in our case $H_B$) with a known ground state and another ...
GiannisKol's 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 ...
Martin Vesely's user avatar

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