5
$\begingroup$

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.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
4
$\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.
Improve this answer
$\endgroup$

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