patternMinor
The physical implementation of quantum annealing algorithm
Viewed 0 times
thealgorithmphysicalimplementationannealingquantum
Problem
From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum computers).
Can anyone explain that algorithm in terms of quantum gates and quantum algorithms, or in physical terms (a part of algorithm that depends on quantum hardware)?
Does anyone have any ideas about that?
Please tell me, if you know some links related this question.
Can anyone explain that algorithm in terms of quantum gates and quantum algorithms, or in physical terms (a part of algorithm that depends on quantum hardware)?
Does anyone have any ideas about that?
Please tell me, if you know some links related this question.
Solution
The approach to quantum computing that you are referring to is something called the adiabatic model. It's actually based on continuous time evolution of quantum systems, rather than on discretized-time models (i.e. no gates). It turns out that it is possible to approximate continuous time evolution with a discrete set of gates, and so the algorithm can be implemented in any universal model of quantum computation.
In order to understand the algorithm and how it works, you need to know some physics. A Hamiltonian, $H$, is an observable which corresponds to the total energy of the system. Any eigenstate, $\psi$, of $H$ corresponds to a configuration of the system for which there is a definite energy, $E$, equal to the corresponding eigenvalue of $H$.
The dynamics of a quantum system are determined by its Hamiltonian, and for a fixed Hamiltonian, the evolution is given by $\psi(t) = e^{-iHt/\hbar}\psi(0)$.
The adiabatic algorithm is based on the adiabatic theorem, which roughly speaking, states that if you start in the ground state (the lowest energy state of the system) of some Hamiltonian $H_0$ and slowly change the Hamiltonian as a function of time, then you will continue to remain in the ground state (or rather very close to it) of the instantaneous Hamiltonian, provided that the speed at which the Hamiltonian changes is sufficiently slow. How slow this must be depends on the minimum gap between the ground state and the next lowest energy level, and varies from one Hamiltonian to the other.
The adiabatic algorithm is simply to start in the ground state of some simple Hamiltonian, $H_0$, for which the ground state is easy to prepare, and slowly interpolate between it and some target Hamiltonian, $H_1$, which encodes in its ground state the solution to the problem you are trying to solve. Thus, the time varying Hamiltonian may look something like $H(t) = (1-t/T)H_0 + (t/T)H_1$, where $T$ is the total time for the adiabatic evolution. As long as $T$ is sufficiently large, the adiabatic theorem guarantees that the resulting state at time $T$ will be very close to the ground state of $H_1$.
It should be noted that the linear interpolation above is certainly not the only possible choice, and indeed looking for better paths between $H_0$ and $H_1$ is an active area of research, since the path determines the minimum value which can be taken by $T$. None the less, the above should give you a taste of how the algorithm works.
In order to understand the algorithm and how it works, you need to know some physics. A Hamiltonian, $H$, is an observable which corresponds to the total energy of the system. Any eigenstate, $\psi$, of $H$ corresponds to a configuration of the system for which there is a definite energy, $E$, equal to the corresponding eigenvalue of $H$.
The dynamics of a quantum system are determined by its Hamiltonian, and for a fixed Hamiltonian, the evolution is given by $\psi(t) = e^{-iHt/\hbar}\psi(0)$.
The adiabatic algorithm is based on the adiabatic theorem, which roughly speaking, states that if you start in the ground state (the lowest energy state of the system) of some Hamiltonian $H_0$ and slowly change the Hamiltonian as a function of time, then you will continue to remain in the ground state (or rather very close to it) of the instantaneous Hamiltonian, provided that the speed at which the Hamiltonian changes is sufficiently slow. How slow this must be depends on the minimum gap between the ground state and the next lowest energy level, and varies from one Hamiltonian to the other.
The adiabatic algorithm is simply to start in the ground state of some simple Hamiltonian, $H_0$, for which the ground state is easy to prepare, and slowly interpolate between it and some target Hamiltonian, $H_1$, which encodes in its ground state the solution to the problem you are trying to solve. Thus, the time varying Hamiltonian may look something like $H(t) = (1-t/T)H_0 + (t/T)H_1$, where $T$ is the total time for the adiabatic evolution. As long as $T$ is sufficiently large, the adiabatic theorem guarantees that the resulting state at time $T$ will be very close to the ground state of $H_1$.
It should be noted that the linear interpolation above is certainly not the only possible choice, and indeed looking for better paths between $H_0$ and $H_1$ is an active area of research, since the path determines the minimum value which can be taken by $T$. None the less, the above should give you a taste of how the algorithm works.
Context
StackExchange Computer Science Q#11218, answer score: 7
Revisions (0)
No revisions yet.