9
$\begingroup$

Much of the quantum computing literature focuses on the circuit model. Adiabatic quantum computing is not based on applying a sequence of unitary operators, but on changing a time-dependent Hamiltonian. I am looking for insight into any of the following.

  1. Is adiabatic quantum computing as powerful as the circuit model, or is it inherently less powerful?
  2. Are there complexity classes specifically related to adiabatic computing as opposed to the circuit model?
  3. How does one quantitatively measure the power of adiabatic computing versus the power of the circuit model?
Improve this question
$\endgroup$
7
  • $\begingroup$ ok NdB yes it wasnt formulated in the perfect way, thx to respondents for clarification, exactly what was sought. arose in reaction to another persons question on chat, can further discussion there by anyone interested. am sure others with higher rep could figure out better questions but there seems a strong inverse correlation there. as for bkg all the refs backing it up got sliced off by the 1st edit. also, asked another question long ago that led to this one but that other question got vaporized. poof $\endgroup$
    – vzn
    Mar 23, 2013 at 15:35
  • 2
    $\begingroup$ I saw the previous edit. News releases are not research articles. More to the point, essentially any research article would have indicated to you that adiabatic quantum computing is essentially qubit based. It doesn't matter what prompted it: your question doesn't show much effort — and activity for activity's sake is what StackExchange fora try to avoid. $\endgroup$
    – Niel de Beaudrap
    Mar 23, 2013 at 15:36
  • 3
    $\begingroup$ Vzn: the whole point is this: why don't you investigate that yourself? And if after actually investigating you cannot find any references, why not ask that question? That would be constructive, and you could ask (and investigate) that question about quantum computing in general, not just adiabatic computing. $\endgroup$
    – Niel de Beaudrap
    Mar 23, 2013 at 15:49
  • 4
    $\begingroup$ @NieldeBeaudrap: To me it looked like he simply used "qubit model" as a substitute for circuit model, which is of course not an accurate substitution, but I took that to be the meaning of the question. $\endgroup$
    – Joe Fitzsimons
    Mar 23, 2013 at 16:43
  • 1
    $\begingroup$ @JoeFitzsimons: fair enough — that is probably the most practical approach, as it implies that the question has a sensible answer, i.e. those below. Though vzn should edit the question to actually ask that question, if so, for posterity. $\endgroup$
    – Niel de Beaudrap
    Mar 24, 2013 at 1:13

2 Answers 2

Reset to default
18
$\begingroup$

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation - Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev

Improve this answer
$\endgroup$
19
$\begingroup$

Two quick clarifications:

  1. Adiabatic QC is typically "based on qubits" just as much as circuit-based QC is -- I don't know where you got the idea that it isn't! (Though one could also use qutrits or other building blocks, in either the circuit or the adiabatic models.)

  2. As Mateus pointed out, the justly-famous result of Aharonov et al. says that "adiabatic QC is equivalent to standard QC." But that result needs to be interpreted with a bit of care. It holds if the final state of the adiabatic computation can be arbitrary -- so that, in particular, the final state can encode the entire history of a circuit-based quantum computation. However, if the final state needs to be a classical computational basis state---as it typically is in the adiabatic optimization algorithm (the "original" example of adiabatic QC)---then adiabatic QC can certainly be simulated in the circuit model, but the reverse is not known and is far from clear. So with the latter assumption, it's possible that adiabatic optimization really does give rise to a new complexity class intermediate between BPP and BQP.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Bacon and Flammia's paper on adiabatic cluster state computation would seem to give an alternate route which, as far as I can see, somewhat circumvents the need for a history, though you still have lots of additional qubits. $\endgroup$
    – Joe Fitzsimons
    Mar 23, 2013 at 3:29
  • 2
    $\begingroup$ However, the Bacon & Flammia scheme does not have a unique ground state and thus significantly differs from conventional AQC. $\endgroup$
    – Norbert Schuch
    Mar 23, 2013 at 12:42
  • 3
    $\begingroup$ @NorbertSchuch: But if you add the extra stabilizer terms to the initial Hamiltonian corresponding to fixing the initial state, then the ground state is non-degenerate. $\endgroup$
    – Joe Fitzsimons
    Mar 23, 2013 at 13:46

Your Answer

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