A Limit on the Speed of Quantum Computation in Determining Parity

Details A Limit on the Speed of Quantum Computation in Determining Parity A Limit on the Speed of Quantum Computation in Determining Parity

1998-02-16

arxiv.org/abs/quant-ph/9802045v2

Phys.Rev.Lett.81:5442-5444,1998

Physics

Quantum Physics

9 pages, latex

Scientific paper

10.1103/PhysRevLett.81.5442

Consider a function f which is defined on the integers from 1 to N and takes the values -1 and +1. The parity of f is the product over all x from 1 to N of f(x). With no further information about f, to classically determine the parity of f requires N calls of the function f. We show that any quantum algorithm capable of determining the parity of f contains at least N/2 applications of the unitary operator which evaluates f. Thus for this problem, quantum computers cannot outperform classical computers.

Affiliated with

Also associated with

No associations

Rating

A Limit on the Speed of Quantum Computation in Determining Parity 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 A Limit on the Speed of Quantum Computation in Determining Parity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Limit on the Speed of Quantum Computation in Determining Parity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-602937