There are different models of quantum computing like quantum circuits, adiabatic or annealing. Another thing to mention is the complexity class BQP. It is pretty much a given that the different models are equivalent as computational models and in turn they are equivalent to deterministic turing machines. However, like in the case with DTM's, my question is are they equivalent in terms of efficient classes? That is, could it be the case that for the different models we would have different BQP classes such that they are not necessarily equivalent?

  • $\begingroup$ A quantum circuit algorithm can be transformed into a quantum adiabatic algorithm with the exact same time complexity. Is that what you wish to know? $\endgroup$ Jan 13, 2022 at 16:34
  • $\begingroup$ Yes, I was curious if there are models for which this may not be the case $\endgroup$
    – H.C Manu
    Jan 13, 2022 at 17:25

1 Answer 1


Quantum Turing machines, quantum circuits, and quantum adiabatic algorithms are polynomially equivalent, in complexity class BQP [1,2]. Concerning quantum annealers, it is unknown whether they offer any speedup relative to classical annealers.

To find a computational model that is in a different complexity class, one has to look for non-universal quantum computers. For example, adiabatic quantum computation of "stoquastic" Hamiltonians [3] (with real nonpositive off-diagonal matrix in the computational basis) is in BStoqP $\subset$ BQP.

Another example, Instantaneous Quantum Polynomial-time (IQP) computation is a model of quantum computation consisting only of commuting two-qubit gates. It is believed that no classical algorithm can simulate IQP efficiently [4].

  1. A survey of quantum complexity theory, U. Vazirani.

  2. Simple proof of equivalence between adiabatic quantum computation and the circuit model, A. Mizel, D.A. Lidar, M. Mitchell.

  3. Adiabatic Quantum Computing, T. Albash, D.A. Lidar.

  4. Quantum Commuting Circuits and Complexity of Ising Partition Functions, K. Fujii, T. Morimae.


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.

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