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....
7
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 ...
7
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 ...
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 ...
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 ...
5
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 ...
5
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 ...
5
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 ...
4
Until recently, D-Wave's quantum annealing devices always started from a uniform superposition over all $N$ qubits:
&...
4
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 ...
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
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 ...
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
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, ...
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
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
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, ...
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
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 $...
2
Here I found a few resources talking about TRIAD which is a minor embedding technique Vicky Choi introduced :
Optimizing Adiabatic Quantum Program Compilation using a Graph-Theoretic Framework
Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem
Minor-Embedding in Adiabatic Quantum Computation: II. Minor-universal graph ...
1
The first difficulty is to answer whether we can convert all conventional circuit gates into adiabatic ones (or simply geometric), this has been done theoretically and recently experimentally as well (ref: https://arxiv.org/abs/1304.5186). To answer the first question, yes, it is possible.
Since this correspondence is now true, we need to tackle the problems ...
Only top voted, non community-wiki answers of a minimum length are eligible
