Multi-query quantum sums

Details Multi-query quantum sums Multi-query quantum sums

2011-07-11

arxiv.org/abs/1107.1940v1

Physics

Quantum Physics

11 pages, 1 figure; presented at TQC 2011

Scientific paper

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\in\{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 $\Z_k$ and the problem of determining $\sum f(x)$. By constructing an explicit algorithm, we show that $n-r$ ($n\ge r\in\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.

Affiliated with

Also associated with

No associations

Rating

Multi-query quantum sums does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multi-query quantum sums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-query quantum sums will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137345