Proving the power of postselection

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

26 pages. This is a heavily improved version of arXiv:1102.0666

Scientific paper

It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time computers. It is also unknown whether polynomial-time quantum machines with postselection are more powerful than their probabilistic counterparts with the same resource restrictions. We approach these problems by imposing additional constraints on the resources to be used by the computer, and are able to prove for the first time that postselection does augment the computational power of both classical and quantum computers, and that quantum does outperform probabilistic in this context, under simultaneous time and space bounds in a certain range. We also look at postselected versions of space-bounded classes, as well as those corresponding to error-free and one-sided error recognition, and provide classical characterizations. It is shown that $\mathsf{NL}$ would equal $\mathsf{RL}$ if the randomized machines had the postselection capability.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Proving the power of postselection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Proving the power of postselection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Proving the power of postselection will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-217495

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.