13
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....
10
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 ...
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
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 ...
8
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 ...
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
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 ...
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 ...
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
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
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 (...
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
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
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, ...
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 ...
2
A couple papers are out there on algorithms which can be constructed using reverse annealing, http://iopscience.iop.org/article/10.1088/1367-2630/aa59c4/meta and https://arxiv.org/abs/1609.05875 (it is worth pointing out previous somewhat related closed system work: https://link.springer.com/article/10.1007/s11128-010-0168-z). As far as experimental results, ...
2
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 $...
2
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 ...
2
How can I calculate the ground state of $H(0)$?
The ground state means the eigenvector with lowest eigenvalue. Take your given example,
$$
H(1)=\left(\begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array}\right).
$$
You solve $\text{det}(H(1)-\lambda\mathbb{I})=0$ to find the eigenvalues. In this case, $\lambda=0,2$. So you're interested in the smallest ...
2
No, as point 4 is not satisfied.
The D-Wave machines are quantum annealers and thus not universal.
See this question on how to make from the D-Wave machine a universal quantum computer.
2
D-Wave works more like a quantum simulator. It has a grid of two-level quantum system 'qubits'. However any single qubit cannot be arbitrarily rotated like in a universal QC.
All qubits form a collective state that is the ground state of some Hamiltonian. The Hamiltonian is parametrized by a set of coefficients. Initially the coefficients are set so that ...
2
I'm not sure if you're wanting to implement $H_p=f(z)|z\rangle\langle z|$ for a specific $z$, or
$$
H_p=\sum_zf(z)|z\rangle\langle z|.
$$
I'm going to assume the latter because you can easily redefine the function to convert it into the former. Now, assume that $g(z)$ is a function that we can compute efficiently on a classical computer that gives the best $...
Only top voted, non community-wiki answers of a minimum length are eligible
