2011/07/11 by David Meyer, David A. Meyer, Meyer, David A. +2
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1107.1940
11 pages, 1 figure; presented at TQC 2011
arxiv created 2011/07/11 · openalex publication_date 2011/07/11 · arxiv updated 2011/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
PARITY is the problem of determining the parity of a string f of n bits given access to an oracle that responds to a query x∈\0,1,...,n-1\ with the x\rm th bit of the string, f(x). Classically, n queries are required to succeed with probability greater than 1/2 (assuming equal prior probabilities for all length n bitstrings), but only \lceil n/2\rceil quantum queries suffice to determine the parity with probability 1. We consider a generalization to strings f of n elements of \Zk and the problem of determining ∑ f(x). By constructing an explicit algorithm, we show that n-r (n≥ r∈\N) entangled quantum queries suffice to compute the sum correctly with worst case probability min\\lfloor n/r\rfloor/k,1\. This quantum algorithm utilizes the n-r queries sequentially and adaptively, like Grover's algorithm, but in a different way that is not amplitude amplification.