Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Limit on the Speed of Quantum Computation in Determining Parity

Limit on the Speed of Quantum Computation in Determining Parity 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Physical Review Letters American Physical Society (APS)

Limit on the Speed of Quantum Computation in Determining Parity

Physical Review Letters , Volume 81 (24) – Dec 14, 1998
3 pages

Loading next page...
 
/lp/american-physical-society-aps/limit-on-the-speed-of-quantum-computation-in-determining-parity-gwIulSDkTw

References (9)

Publisher
American Physical Society (APS)
Copyright
Copyright © 1998 The American Physical Society
ISSN
1079-7114
DOI
10.1103/PhysRevLett.81.5442
Publisher site
See Article on Publisher Site

Abstract

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.

Journal

Physical Review LettersAmerican Physical Society (APS)

Published: Dec 14, 1998

There are no references for this article.