Different quantum computation models equivalence

Question

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?

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.