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....
11
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 state space of a quantum computer with N qubits is $2^N$ dimensional.
Error correct an analog computer and what you've got is a digital computer (i.e. not ...
10
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 ...
9
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 ...
9
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 paper by Roland and Cerf. This agrees with the equivalence between adiabatic and gate-based quantum computation that you mentioned.
(One minor correction to ...
8
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 discussion about the general case.
Let's solve the Weighted Maximum Cut problem since this
Is a relatively straight-forward example
Is hard classically
Is a ...
7
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 computing (also known as "quantum analogue computing" and "continuous variable quantum computing") is here. Note that analog classical computing is not as powerful as ...
7
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 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{array}\right),
$$
tensored with identity between all other ...
6
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 equivalent. That means if one has an exponential speedup, so does the other. The discussion should be interchangeable.
The title, if not the question body, also ...
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 ...
6
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)$ can be calculated using a classical reversible code or hardware, we can find $\omega$ with $\mathcal{O}(\sqrt{N})$ steps using a quantum circuit as opposed to a ...
5
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.
Simulating a Hamiltonian on a quantum computer is a standard problem. Making that Hamiltonian time varying doesn’t really make it any worse since you break it ...
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 ...
5
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 ...
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
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 difference between quantum and classical devices lies at a more fundamental level.
A quantum device cannot, in general, be simulated efficiently by a classical device, ...
4
Until recently, D-Wave's quantum annealing devices always started from a uniform superposition over all $N$ qubits:
&...
4
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 geometric phase.
In most applications of quantum computing, this parameter space is usually a set of control parameters used to drive the system. More precisely, the ...
4
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 described by robust
ground state degeneracy and quantized non-Abelian geometric phases
of degenerate ground states
(emphasis is mine). Clearly, it is a special ...
4
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-space of the final Hamiltonian is typically determined by the optimum solution to some constraint satisfaction problem (CSP). If the CSP is perfectly solvable, the ground-space is spanned by (...
4
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 the 'easy to verify' into the Hamiltonian, which is the similar as marking the item via the phase oracle in the gate model.
For example consider a simple case ...
4
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$
$$
\tau_{n} \equiv n \Delta \tau, \qquad n = 0,1,\ldots,k-1.
$$
Now consider the piecewise-constant product of the propagators $\exp(-i H(\tau_n)\Delta \tau)$ taken ...
3
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 anti-Hermitian so that $e^A$, and similar terms, are unitary. We have
$$
\|\exp(A+B)-\exp(A)\exp(B)\|=\|e^{A+B}\left(\mathbb{I}-e^Me^{-(A+B)}\right)\|.
$$
The ...
3
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 secret:
Once upon a time, a mother was teaching her daughter the family recipe for making a whole baked ham. It was the very best ham anybody had ever had so ...
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
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
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-based quantum computation can efficiently simulate adiabatic quantum computation [see section 5 of this paper].
can it really be faster than $\mathcal{O}(\...
3
In this particular one (by quickly overlooking), they refer mostly to the logic gate approach. But nothing prevent them from talking about both. It depends on the algorithm and on which original model it was thought/designed on. Generally, if it is linear algebra based, it will be the logic gate approach. If they refer to optimization of a QUBO, they will ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible