<p>Two quick clarifications:</p>

<ol>
<li><p>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.)</p></li>
<li><p>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 <i>adiabatic optimization algorithm</i> (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.</p></li>
</ol>

CC BY-SA 3.0
2013-03-23T03:29:09.400Z
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.
Joe Fitzsimons
CC BY-SA 3.0
2013-03-23T12:42:10.973Z
However, the Bacon & Flammia scheme does not have a unique ground state and thus significantly differs from conventional AQC.
Norbert Schuch
CC BY-SA 3.0
2013-03-23T13:46:28.720Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2013-03-23T02:43:26.673Z
2013-03-23T02:43:26.673Z
Scott Aaronson
<p><a href="http://arxiv.org/abs/quant-ph/0405098">Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation -
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev</a></p>

CC BY-SA 3.0
2013-03-22T17:25:42.950Z
2013-03-22T17:25:42.950Z
Mateus de Oliveira Oliveira
<p>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.</p>

<ol>
<li>Is adiabatic quantum computing as powerful as the circuit model, or is it inherently less powerful?</li>
<li>Are there complexity classes specifically related to adiabatic computing as opposed to the circuit model?</li>
<li>How does one quantitatively measure the power of adiabatic computing versus the power of the circuit model?</li>
</ol>

CC BY-SA 3.0
2013-03-23T15:35:06.520Z
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](http://chat.stackexchange.com/transcript/message/8628605#8628605), 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*
vzn
CC BY-SA 3.0
2013-03-23T15:36:12.790Z
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*.
Niel de Beaudrap
CC BY-SA 3.0
2013-03-23T15:42:41.700Z
afaik/iiuc not all adiabatic models use qubits. could be wrong about that. if you have/know something/ref that explains that, it will be helpful.
vzn
CC BY-SA 3.0
2013-03-23T15:49:20.110Z
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.
Niel de Beaudrap
CC BY-SA 3.0
2013-03-23T15:56:31.240Z
yes! have investigated. for example wikipedia states qm adiabatic computing is based on the [adiabatic thm](http://en.wikipedia.org/wiki/Adiabatic_theorem). an example on that page is a _pendulum_. from long experience, know that presumably no question Ive ever asked or will ask will be acceptable to you or some others on here & dont take it personally... your downvote is sufficient to communicate your negative opinion(s)... will respond to _meta_ discussion which is _more appropriate_ for such complaint(s)...
vzn
CC BY-SA 3.0
2013-03-23T16:43:26.140Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2013-03-24T01:13:32.110Z
@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.
Niel de Beaudrap
<cc.complexity-theory><reference-request><complexity-classes><quantum-computing><quantum-information>
Is adiabatic quantum computing as powerful as the circuit model?
vzn
# Is adiabatic quantum computing as powerful as the circuit model?

(Asked by: username_0 on 2013-03-22)

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?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, quantum-computing, quantum-information
> **Comments:**
> **username_0**: 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](http://chat.stackexchange.com/transcript/message/8628605#8628605), 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*  
> **username_1**: 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*.  
> **username_0**: afaik/iiuc not all adiabatic models use qubits. could be wrong about that. if you have/know something/ref that explains that, it will be helpful.  
> **username_1**: 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.  
> **username_0**: yes! have investigated. for example wikipedia states qm adiabatic computing is based on the [adiabatic thm](http://en.wikipedia.org/wiki/Adiabatic_theorem). an example on that page is a _pendulum_. from long experience, know that presumably no question Ive ever asked or will ask will be acceptable to you or some others on here & dont take it personally... your downvote is sufficient to communicate your negative opinion(s)... will respond to _meta_ discussion which is _more appropriate_ for such complaint(s)...  
> **username_2**: @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.  
> **username_1**: @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.  

---

## 2 answers

### Answer by username_5 on 2013-03-22. Score: 18 | Accepted answer

[Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation -
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev](http://arxiv.org/abs/quant-ph/0405098)


---

### Answer by username_3 on 2013-03-23. Score: 19

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.

> **Comments:**
> **username_2**: 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.  
> **username_4**: However, the Bacon & Flammia scheme does not have a unique ground state and thus significantly differs from conventional AQC.  
> **username_2**: @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.  

---

