Multi-query quantum sums

Publication date 20 November 2015

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 i n 0, 1, ..., n - 1

with the

x^{m t h}

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

l c e i l n / 2 c e i l

quantum queries suffice to determine the parity with probability 1. We consider a generalization to strings

f

of

n

elements of

and the problem of determining

s u m f (x)

. By constructing an explicit algorithm, we show that

n - r

(

n g e r i n N

) entangled quantum queries suffice to compute the sum correctly with worst case probability

m i n l f l o o r n / r f l o o r / 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.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Multi-query quantum sums