A Limit on the Speed of Quantum Computation in Determining Parity

Simple item page
dc.creatorFarhi, E.
dc.creatorGoldstone, J.
dc.creatorGutmann, S.
dc.creatorSipser, M.
dc.date1998-02-16
dc.date1998-10-08
dc.date.accessioned2026-07-07T12:33:25Z
dc.date.available2026-07-07T12:33:25Z
dc.descriptionConsider 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.
dc.description9 pages, latex
dc.identifierhttps://arxiv.org/abs/quant-ph/9802045
dc.identifierhttp://arxiv.org/abs/quant-ph/9802045
dc.identifierPhys.Rev.Lett.81:5442-5444,1998
dc.identifierdoi:10.1103/PhysRevLett.81.5442
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/217116
dc.subjectQuantum Physics
dc.titleA Limit on the Speed of Quantum Computation in Determining Parity
dc.typetext

Files

Collections

arXiv