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
13 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 ...
user avatar
  • 21.8k
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,669
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,669
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 ...
user avatar
  • 2,057
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 ...
user avatar
  • 549
8 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 ...
user avatar
  • 11.9k
7 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 &...
user avatar
  • 46.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
  • 46.1k
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
  • 11.9k
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 ...
user avatar
  • 46.1k
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
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)$ ...
user avatar
  • 11.9k
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. ...
user avatar
  • 46.1k
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-...
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
  • 11.9k
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 ...
user avatar
  • 18.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
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 ...
user avatar
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 ...
user avatar
  • 46.1k
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
4 votes

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

For adiabatic Grover you want the ground state of the final Hamiltonian to be the marked item. The key idea with Grover is that the item is hard to find but easy to verify. So the idea is you embed ...
user avatar
4 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$ $$ \...
user avatar
3 votes

Proof on approximating adiabatic evolution by quantum circuit

The Baker-Campbell-Hausdorff formula says that you can expand $$ \log(e^Ae^B)=A+B+[A,B]/2+\ldots=M $$ where higher order terms have 3 or more uses of $A$ and $B$. Now, let's say that $A$ and $B$ are ...
user avatar
  • 46.1k
3 votes

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

Have we fallen into the same 'everything digital' bandwagon trap that keeps recurring? What I have noticed is more the 'everything binary' bandwagon trap; which reminds me of the Grandma's cooking ...
user avatar
  • 3,194
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
  • 11.9k
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

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,057
3 votes

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

Adiabatic quantum computation cannot do anything faster than circuit-based quantum computation from a computational complexity perspective. This is because there is a mathematical proof that circuit-...
user avatar
  • 11.9k

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