Fetching the paper…

Reading the bibliography…

2011

Span Programs for Functions with Constant-Sized 1-certificates

Belovs, Aleksandrs

Original
PDF
Post on X

Understand

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.

Span Programs for Functions with Constant-Sized 1-certificates · Around

Built on

Grover, L.: A fast quantum mechanical algorithm for database search
1996
Earlier work this paper cites.
Brassard, G., Høyer, P., Tapp, A.: Quantum algorithm for the collision problem
1998
Earlier work this paper cites.
Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching
1998
Earlier work this paper cites.
Nielsen, M., Chuang, I.: Quantum computation and quantum information
2000
Earlier work this paper cites.
Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey
2002
Earlier work this paper cites.

Similar

Shi., Y.: Quantum lower bounds for the collision and the element distinctness problems
Original
2002
Cited alongside, same era.
Magniez, F., Santha, M., Szegedy, M.: Quantum Algorithms for the Triangle Problem
2003
Cited alongside, same era.
Ambainis, A.: Quantum walk algorithm for element distinctness
2004
Cited alongside, same era.
Buhrman, H., Durr, C., Heiligman, M., Hoyer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness
2005
Cited alongside, same era.

Then

Reichardt, B., Špalek, R.: Span-program-based quantum algorithm for evaluating formulas
Original
2008
Later among the works it cites.
Reichardt, B.: Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
Original
2009
Later among the works it cites.
Reichardt, B.: Reflections for quantum query algorithms
Original
2010
Later among the works it cites.
Belovs, A.: Span-program-based quantum algorithm for the rank problem
Original
2011
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…