6533b7dcfe1ef96bd1271cb4

RESEARCH PRODUCT

Span programs for functions with constant-sized 1-certificates

Aleksandrs Belovs

subject

CombinatoricsDiscrete mathematicsGrover's algorithmQuantum phase estimation algorithmSimon's problemQuantum walkQuantum algorithmQuantum algorithm for linear systems of equationsMathematicsQuantum complexity theoryQuantum computer

description

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 element 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(n35/27) that is better than O(n13/10) of the best previously known algorithm by Magniez et al.

yearjournalcountryeditionlanguage
2012-05-19Proceedings of the forty-fourth annual ACM symposium on Theory of computing
https://doi.org/10.1145/2213977.2213985