8
$\begingroup$

Background: In any adiabatic quantum computer (AQC) algorithm, we solve problems in the following manner: We have an initial Hamiltonian, $H_{0}$, whose ground state is easy to find, and a problem Hamiltonian $H_{P}$, whose ground state encodes the solution to our problem. If we then evolve our AQC for a time $T$ so that its energy is described by the Hamiltonian $$H(t) = (1-t/T)H_{0} + (t/T)H_{P}$$ then provided a couple of conditions apply, the system will be in the ground state of $H_{P}$ at time $T$ (and voila, we would have a solution to our problem)

Question: If we just set up the AQC so its energy is initially described by the Hamiltonian $H_{P}$, why wouldn't the system just 'fall' into its ground state (encoding a solution to our problem immediately)? Why do we need to evolve the AQC from the initial Hamiltonian $H_{0}$ into $H_{P}$?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

Most NP-complete problems can be formulated as finding the ground state of some Hamiltonian. If you create a physical system that has such a Hamiltonian, it will be a "frustrated system". It will settle into a state that is a local minimum of the energy, and while quantum mechanics says that it will eventually decay into the ground state (assuming that it's not isolated; that is, there is some mechanism for it to lose energy), the time this takes may easily be many orders of magnitude larger than the lifetime of the universe.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If you wanted to calculate the ground-state of an arbitrary problem Hamiltonian, you have to search through 1/2^N states. For N=100 that is practically impossible even with massive parallelization, and even that is still orders of magnitude below problem sizes that have industrial application. Of course, the best classical algorithms use heuristics and problem structure, to increase tractability, but the hope is that AQC will provide at least polynomial speed-up on some algorithms, and blow the best classical algorithms on the biggest supercomputers out of the water (yet to be demonstrated). $\endgroup$
    – Paradox
    Commented Feb 8, 2017 at 13:18
5
$\begingroup$

I once asked the exact same question during a course on quantum computation. Systems only "fall into" their ground states when they are in thermal equilibrium at zero temperature. Both of these pieces are problematic: (a) many systems that have been proposed for quantum computation have energy scales low enough that getting them down to sufficiently low temperatures is extremely challenging, and (b) as Peter Shor pointed out, you have no idea how long it will take for the system to actually reach thermal equilibrium - you could have a physical equivalent of a Monte-Carlo sign problem, where it takes exponentially long in system size for local perturbations to get you into thermal equilibrium.

But if you can control the initial Hamiltonian $H_0$, you can "force" the system into its ground state much more quickly - in principle by measurement filtration, but more realistically by making $H_0$ unfrustrated and with a very large characteristic energy scale. For example, if you have a system of quantum spins and you apply a huge uniform field to the whole system ("huge" meaning much larger than the temperature and the relevant spin interaction scale), then the whole system will align with the field very quickly and you can be confident that you're in the ground state.

Improve this answer
$\endgroup$
7
  • $\begingroup$ It's actually fairly easy (at least in theory) to construct systems so that (a) isn't a problem. The big problem is (b). $\endgroup$
    – Peter Shor
    Commented Jan 4, 2017 at 14:08
  • 1
    $\begingroup$ @PeterShor True, but I think there are also systems where (a) is hard. D-Wave works ("works") at 15 mK, which isn't too hard to achieve, but aren't there also proposals for AQC in cold atom systems (e.g. arxiv.org/abs/quant-ph/0406144)? That would need to be performed at the nanokelvin scale, which is much, much harder than millikelvin. $\endgroup$
    – tparker
    Commented Jan 4, 2017 at 14:22
  • $\begingroup$ @tparker Thanks, great answer. Is this uniform field (that one applies to the system to hasten it reaching the ground state) what is used in quantum annealing algorithms (such as on the D-Wave machines)? And is this what enables the 'tunneling' between barriers separating local minima in quantum annealing algorithms? $\endgroup$
    – Alex Michael
    Commented Jan 4, 2017 at 22:28
  • 1
    $\begingroup$ @AlexMichael I don't know the answer to your first question. I'm not sure if I understand your second question, but the adiabatic theorem guarantees that the ground state of the initial Hamiltonian will evolve to the ground state of the final Hamiltonian as long as the Hamiltonian is varied much more slowly then the time scale set by the energy gap to the first excited state, because the system can quantum-tunnel through energy barriers as long as it has enough time to do so. In principle, the details of the initial Hamiltonian are unimportant, just the size of its energy gap. $\endgroup$
    – tparker
    Commented Jan 5, 2017 at 6:03
  • $\begingroup$ why i can force initial Hamiltonian H0 to be at ground state but not force final hamiltonian to be at ground state? $\endgroup$
    – Ka Wa Yip
    Commented Jan 29, 2017 at 21:05
0
$\begingroup$

You start in some state which is a complicated mess of eigenstates then. And you haven't given a mechanism to decay. Just evolution with a single Hp. You only know how to start in ground state of H0 and move from there.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.