All Questions
Tagged with speedup resource-request
2 questions
5
votes
1
answer
122
views
Review on quantum resources required in mixed-state quantum computing
I am trying to see which features we know are necessary for mixed-state quantum computing to avoid the algorithms being efficiently simulated on classical computers.
In the case of pure-state quantum ...
- 1,962
4
votes
0
answers
72
views
Bound on quantum speedups under various models of complexity
What are the bounds on quantum speedups under the various models of complexity? How big or small can they be?
Under the query model, my understanding is that the lower bound is $\Omega(\sqrt{N})$ as ...
- 1,086