An Exact Quantum Polynomial-Time Algorithm for Simon's Problem

Details An Exact Quantum Polynomial-Time Algorithm for Simon's Problem An Exact Quantum Polynomial-Time Algorithm for Simon's Problem

1997-04-14

arxiv.org/abs/quant-ph/9704027v1

Physics

Quantum Physics

12 pages, LaTeX2e, no figures. To appear in Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems (IST

Scientific paper

We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.

Affiliated with

Also associated with

No associations

Rating

An Exact Quantum Polynomial-Time Algorithm for Simon's Problem 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 An Exact Quantum Polynomial-Time Algorithm for Simon's Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Exact Quantum Polynomial-Time Algorithm for Simon's Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-489934