All Abstracts | Poster Abstracts | Talk Abstracts | Tutorial Abstracts

Multi-query quantum algorithms for summation

David Meyer, University of California/San Diego

(Session 7 : Saturday from 2:00-2:30)

Abstract. 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, ..., n-1} with the x^th bit of the string, f(x). Classically n queries are required to succeed with probability greater than 1/2, but only the least integer greater than n/2 number of quantum queries suffice to determine the parity with probability 1. We consider a generalization to strings f of n elements of Z_k and the problem of determining ∑f(x). By constructing an explicit algorithm, we show that with n - r quantum queries the optimal success probability is at least the greatest integer less than n/r, divided by k. 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.