Stack Exchange Network
Stack Exchange network consists of 181 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Visit Stack Exchange
Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Anybody can ask a question
The best answers are voted up and rise to the top
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.
2,4821313 silver badges3636 bronze badges
asked Mar 27, 2018 at 21:49
51233 silver badges1212 bronze badges
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.
answered Mar 28, 2018 at 11:36
Niel de BeaudrapNiel de Beaudrap
11.6k11 gold badge2424 silver badges6666 bronze badges