Quantum Lower Bound for Recursive Fourier Sampling

Details Quantum Lower Bound for Recursive Fourier Sampling Quantum Lower Bound for Recursive Fourier Sampling

2002-09-09

arxiv.org/abs/quant-ph/0209060v2

Quantum Information and Computation 3(2):165-174, 2003

Physics

Quantum Physics

8 pages. Revised since appearing in QIC, both to correct an error in the definition of the nonparity coefficient and to emphas

Scientific paper

One of the earliest quantum algorithms was discovered by Bernstein and Vazirani, for a problem called Recursive Fourier Sampling. This paper shows that the Bernstein-Vazirani algorithm is not far from optimal. The moral is that the need to "uncompute" garbage can impose a fundamental limit on efficient quantum computation. The proof introduces a new parameter of Boolean functions called the "nonparity coefficient," which might be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Quantum Lower Bound for Recursive Fourier Sampling 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 Quantum Lower Bound for Recursive Fourier Sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Lower Bound for Recursive Fourier Sampling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-500613