On The Power of Exact Quantum Polynomial Time
classification
🪐 quant-ph
keywords
timepolynomialpowerquantumanswerbounded-errorcaseclassical
read the original abstract
We investigate the power of quantum computers when they are required to return an answer that is guaranteed correct after a time that is upper-bounded by a polynomial in the worst case. In an oracle setting, it is shown that such machines can solve problems that would take exponential time on any classical bounded-error probabilistic computer.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.