This question already has an answer here:

There are different theoretical models for quantum computing like the circuit model or the model of adiabatic quantum computers.

Between which of these models exist polynomial-time reductions?

Note that this question does not aim to cover physical implementations of quantum computers which are already discussed here.


marked as duplicate by Niel de Beaudrap, bytebuster, u32i64, Discrete lizard, ItamarG3 Apr 2 '18 at 8:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ There is a nice work about it from 2016, I haven't read all but it is a nice start: Adiabatic Quantum Computing arxiv.org/pdf/1611.04471.pdf $\endgroup$ – Gustavo Banegas Mar 28 '18 at 1:26
  • $\begingroup$ Strongly related: What are the methods of quantum computation? $\endgroup$ – Kiro Mar 28 '18 at 5:51
  • $\begingroup$ If the question were revised to focus on the question of polynomial-time equivalence, I would choose to withdraw my vote to close. $\endgroup$ – Niel de Beaudrap Mar 28 '18 at 11:37
  • $\begingroup$ @NieldeBeaudrap Hmm, I think that at this stage it is better to close this one as dupe and simply ask another question. $\endgroup$ – Discrete lizard Mar 28 '18 at 11:53
  • $\begingroup$ Polynomial time equivalence was one thing I was asking about. Going to revisit my question. $\endgroup$ – datell Mar 28 '18 at 11:54

A non-exhaustive list of theoretical models of quantum computation are provided as answers to another question: "What are the methods of quantum computation?".

As to which models are polynomial-time equivalent — the following is an incomplete list of models which are provably universal for polynomial-time quantum computation, assuming perfect control:

  • The unitary circuit model is polynomial-time equivalent to adiabatic quantum computation [arXiv:quant-ph/0405098];
  • The unitary circuit model is polynomial-time equivalent to quantum circuits with intermediate measurements (by the principle of deferred measurement);
  • The one-way measurement-based model is polynomial-time equivalent to unitary circuits.

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