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 2 Pith papers
-
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...
-
The Physical and Contextual Limits of Quantum Speedup
Quantum speedups come from reversible embeddings and engineered interference that identify solution classes rather than from branchwise classical parallelism, subject to limits like impossible unitary garbage erasure ...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.