Portal de Periódicos da CAPES

Limit on the Speed of Quantum Computation in Determining Parity

1998; American Physical Society; Volume: 81; Issue: 24 Linguagem: Inglês

10.1103/physrevlett.81.5442

1092-0145

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser,

Computability, Logic, AI Algorithms

Consider a function $f$ which is defined on the integers from 1 to $N$ and takes the values $\ensuremath{-}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.