Fetching the paper…
Reading the bibliography…
We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite.
On the time required to recognize properties of graphs: A problem
A. L. Rosenberg · 1973
Earlier work this paper cites.
Random walks, universal traversal sequences, and the complexity of maze problems
R. Aleliunas, R. Karp, R. Lipton, L. Lovasz, and C. Rackoff · 1979
Earlier work this paper cites.
On Span Programs
M. Karchmer and A. Wigderson · 1993
Earlier work this paper cites.
Quantum measurements and the Abelian Stabilizer Problem
A. Y. Kitaev · 1995
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
Tight bounds on quantum searching
M. Boyer, G. Brassard, P. Høyer, and A. Tapp · 1998
Earlier work this paper cites.
Quantum algorithms revisited
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca · 1998
Earlier work this paper cites.
Quantum simulations of classical random walks and undirected graph connectivity
J. Watrous · 1999
Earlier work this paper cites.
Space-bounded quantum complexity
J. Watrous · 1999
Earlier work this paper cites.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2000
Earlier work this paper cites.
Quantum search on bounded-error inputs
P. Høyer, M. Mosca, and R. de Wolf · 2003
Earlier work this paper cites.
Quantum query complexity of some graph problems
C. Dürr, M. Heiligman, P. Høyer, and M. Mhalla · 2004
Earlier work this paper cites.
Graph minors. XX. Wagner’s conjecture
N. Robertson and P. D. Seymour · 2004
Earlier work this paper cites.
Graph properties and circular functions: How low can quantum query complexity go?
X. Sun, A. C. Yao, and S. Zhang · 2004
Cited alongside, same era.
Quantum speed-up of Markov chain based algorithms
M. Szegedy · 2004
Cited alongside, same era.
Probability and computing: Randomized algorithms and probabilistic analysis
M. Mitzenmacher and E. Upfal · 2005
Cited alongside, same era.
On the power of Ambainis lower bounds
S. Zhang · 2005
Cited alongside, same era.
Quantum query complexity of boolean functions with small on-sets
A. Ambainis, K. Iwama, M. Nakanishi, H. Nishimura, R. Raymond, S. Tani, and S. Yamashita · 2008
Cited alongside, same era.
V. Giovannetti, S. Lloyd, and L. Maccone · 2008
Reflections for quantum query algorithms
B. Reichardt · 2011
Later among the works it cites.
Span-Program-based quantum algorithm for evaluating unbalanced formulas
B. Reichardt · 2011
Later among the works it cites.
Span Programs for functions with constant-sized 1-certificates
A. Belovs · 2012
Later among the works it cites.
Span Programs and quantum algorithms for st-connectivity and claw detection
A. Belovs and B. Reichardt · 2012
Later among the works it cites.
Quantum query complexity of minor-closed graph properties
A. Childs and R. Kothari · 2012
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Span-Program-based quantum algorithm for evaluating formulas
B. Reichardt and R. Špalek · 2008
Cited alongside, same era.
B. Reichardt · 2009
Cited alongside, same era.
Span-program-based quantum algorithm for the rank problem
A. Belovs · 2011
Cited alongside, same era.
Quantum query complexity of state conversion
T. Lee, R. Mittal, B. Reichardt, R. Špalek, and M. Szegedy · 2011
Cited alongside, same era.
Search via quantum walk
F. Magniez, A. Nayak, J. Roland, and M. Santha · 2011
Cited alongside, same era.
Faster quantum algorithm for evaluating game trees
B. Reichardt · 2011
Cited alongside, same era.
Later among the works it cites.
Quantum query complexity of constant-sized subgraph containment
Y. Zhu · 2012
Later among the works it cites.
Quantum walks and electric networks
A. Belovs · 2013
Later among the works it cites.
Time-efficient quantum walks for 3-distinctness
A. Belovs, A. M. Childs, S. Jeffery, R. Kothari, and F. Magniez · 2013
Later among the works it cites.
Span-program-based quantum algorithm for tree detection
G. Wang · 2013
Later among the works it cites.
Improved quantum algorithm for triangle finding via combinatorial arguments
F. Le Gall · 2014
Later among the works it cites.
Span-program-based quantum algorithms for graph bipartiteness and connectivity
A. Āriņš · 2015
Later among the works it cites.
Nand-trees, average choice complexity, and effective resistance
S. Jeffery and S. Kimmel · 2015
Later among the works it cites.