Fetching the paper…
Reading the bibliography…
We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems.
O jistém problému minimálním (About a certain minimal problem)
Otakar Borůvka · 1926
Earlier work this paper cites.
Random walks, universal traversal sequences, and the complexity of maze problems
Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, and Charles Rackoff · 1979
Earlier work this paper cites.
Random Walks and Electric Networks
Peter G. Doyle and J. Laurie Snell · 1984
Earlier work this paper cites.
The electrical resistance of a graph captures its commute and cover times
Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari · 1989
Earlier work this paper cites.
On span programs
Mauricio Karchmer and Avi Wigderson · 1993
Earlier work this paper cites.
Color-coding
Noga Alon, Raphael Yuster, and Uri Zwick · 1995
Earlier work this paper cites.
Quantum measurements and the Abelian stabilizer problem
Alexei Yu. Kitaev · 1995
Earlier work this paper cites.
Graph minors XIII. The disjoint paths problem
Neil Robertson and Paul D. Seymour · 1995
Earlier work this paper cites.
Tight bounds on quantum searching
Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
C ∗ C^{*} algebras of directed graphs and group actions
Alex Kumjian and David Pask · 1999
Earlier work this paper cites.
Complexity measures and decision tree complexity: A survey
Harry Buhrman and Ronald de Wolf · 2002
Earlier work this paper cites.
Quantum query complexity of same graph problems
Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla · 2004
Cited alongside, same era.
Graph minors XX. Wagner’s conjecture
Neil Robertson and Paul D. Seymour · 2004
Cited alongside, same era.
Quantum speed-up of Markov chain based algorithms
Mario Szegedy · 2004
Cited alongside, same era.
Quantum algorithms for element distinctness
Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, and Ronald de Wolf · 2005
Cited alongside, same era.
Quantum algorithms for the triangle problem
Frédéric Magniez, Miklos Santha, and Mario Szegedy · 2005
Cited alongside, same era.
Pairwise independence and derandomization
Michael Luby and Avi Wigderson · 2006
Cited alongside, same era.
Any AND-OR formula of size N N can be evaluated in time N 1 / 2 + o ( 1 ) {N}^{1/2+o(1)} on a quantum computer
Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang · 2010
Later among the works it cites.
Span-program-based quantum algorithm for the rank problem
Aleksandrs Belovs · 2011
Later among the works it cites.
Span programs for functions with constant-sized 1-certificates
Aleksandrs Belovs · 2011
Later among the works it cites.
Quantum algorithm for k k -distinctness with prior knowledge on the input
Aleksandrs Belovs and Troy Lee · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone · 2008
Cited alongside, same era.
Undirected connectivity in log-space
Omer Reingold · 2008
Cited alongside, same era.
Span-program-based quantum algorithm for evaluating formulas
Ben W. Reichardt and Robert Špalek · 2008
Cited alongside, same era.
On the hitting times of quantum versus random walks
Frédéric Magniez, Ashwin Nayak, Peter C. Richter, and Miklos Santha · 2009
Cited alongside, same era.
Daniel Nagaj, Pawel Wocjan, and Yong Zhang · 2009
Cited alongside, same era.
Ben W. Reichardt · 2009
Cited alongside, same era.
Andrew M. Childs and Robin Kothari · 2011
Later among the works it cites.
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy · 2011
Later among the works it cites.
A learning graph based quantum query algorithm for finding constant-size subgraphs
Troy Lee, Frédéric Magniez, and Miklos Santha · 2011
Later among the works it cites.
Reflections for quantum query algorithms
Ben W. Reichardt · 2011
Later among the works it cites.
Faster quantum algorithm for evaluating game trees
Ben W. Reichardt · 2011
Later among the works it cites.
Span-program-based quantum algorithm for evaluating unbalanced formulas
Ben W. Reichardt · 2011
Later among the works it cites.
Quantum query complexity of subgraph containment with constant-sized certificates
Yechao Zhu · 2011
Later among the works it cites.