Recognition: unknown
A Limit on the Speed of Quantum Computation in Determining Parity
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
The Physical and Contextual Limits of Quantum Speedup
Quantum speedups arise from engineered interference in high-dimensional Hilbert spaces rather than classical branchwise parallelism, constrained by no unitary garbage erasure, contextuality, and absence of absorbing h...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.