James Pommersheim

PARITY is the oracle (or black-box) problem of determining the parity of an n-bit string by querying positions in the string. We construct an n-r quantum query algorithm that computes the sum correctly with probability min{floor(n/r)/k,1}, for each 1 <= r <= n. This quantum algorithm utilizes the n-r queries sequentially and adaptively, like quantum search algorithms, but in a different way that is not amplitude amplification. We motivate the development of our algorithm by considering the simplest new instances of SUM and conclude by recalling the result of van Dam.