Span Programs for Functions with Constant-Sized 1-certificates

Details Span Programs for Functions with Constant-Sized 1-certificates Span Programs for Functions with Constant-Sized 1-certificates

2011-05-20

arxiv.org/abs/1105.4024v1

Physics

Quantum Physics

15 pages, 1 figure

Scientific paper

Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph. We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit. We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity $O(n^{35/27})$ that is better than $O(n^{13/10})$ of the best previously known algorithm by Magniez et al.

Affiliated with

Also associated with

No associations

Rating

Span Programs for Functions with Constant-Sized 1-certificates 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 Span Programs for Functions with Constant-Sized 1-certificates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Span Programs for Functions with Constant-Sized 1-certificates will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-648954