4
$\begingroup$

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.

$\endgroup$

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
3
$\begingroup$

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.
$\endgroup$

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