Fetching the paper…
Reading the bibliography…
We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether an $n$-vertex graph is planar, is a forest, or does not contain a path of a given length.
On a problem of K. Zarankiewicz
Thomason Kövari, Vera T. Sós, and Pál Turán · 1954
Earlier work this paper cites.
Homomorphieeigenschaften und mittlere Kantendichte von Graphen
Wolfgang Mader · 1967
Earlier work this paper cites.
On the time required to recognize properties of graphs: a problem
Arnold L. Rosenberg · 1973
Earlier work this paper cites.
Cycles of even length in graphs
J. Adrian Bondy and Miklós Simonovits · 1974
Earlier work this paper cites.
A generalization and proof of the Aanderaa-Rosenberg conjecture
Ronald L. Rivest and Jean Vuillemin · 1975
Earlier work this paper cites.
A topological approach to evasiveness
Jeff Kahn, Michael Saks, and Dean Sturtevant · 1983
Earlier work this paper cites.
Graph minors. VIII. A Kuratowski theorem for general surfaces
Neil Robertson and Paul D. Seymour · 1990
Earlier work this paper cites.
Color-coding
Noga Alon, Raphael Yuster, and Uri Zwick · 1994
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Peter W. Shor · 1994
Earlier work this paper cites.
Quantum mechanics helps in searching for a needle in a haystack
Lov K. Grover · 1996
Earlier work this paper cites.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 1998
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
Andris Ambainis · 2000
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 · 2000
Cited alongside, same era.
Improved lower bounds on the randomized complexity of graph properties
Amit Chakrabarti and Subhash Khot · 2001
Cited alongside, same era.
Quantum amplitude amplification and estimation
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp · 2002
Cited alongside, same era.
Lower bounds for local search by quantum arguments
Scott Aaronson · 2004
Cited alongside, same era.
Quantum walk algorithm for element distinctness
Andris Ambainis · 2004
Cited alongside, same era.
On the power of Ambainis lower bounds
Shengyu Zhang · 2004
Later among the works it cites.
Graph theory
Reinhard Diestel · 2005
Later among the works it cites.
Quantum algorithms for the triangle problem
Frédéric Magniez, Miklos Santha, and Mario Szegedy · 2005
Later among the works it cites.
All quantum adversary methods are equivalent
Robert Špalek and Mario Szegedy · 2005
Later among the works it cites.
Quantum query complexity of some graph problems
Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla · 2006
Later among the works it cites.
Negative weights make adversaries stronger
Peter Høyer, Troy Lee, and Robert Špalek · 2007
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quantum query complexity for some graph problems
Aija Berzina, Andrej Dubrovsky, Rusins Freivalds, Lelde Lace, and Oksana Scegulnaja · 2004
Cited alongside, same era.
Graph minors. XX. Wagner’s conjecture
Neil Robertson and Paul D. Seymour · 2004
Cited alongside, same era.
Graph properties and circular functions: How low can quantum query complexity go?
Xiaoming Sun, Andrew C. Yao, and Shengyu Zhang · 2004
Cited alongside, same era.
Quantum speed-up of Markov chain based algorithms
Mario Szegedy · 2004
Cited alongside, same era.
Search via quantum walk
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha · 2007
Later among the works it cites.
Quantum query complexity of boolean functions with small on-sets
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, and Shigeru Yamashita · 2008
Later among the works it cites.
A new quantum lower bound method, with an application to strong direct product theorem for quantum search
Andris Ambainis · 2010
Closest in time.
Quantum query complexity of minor-closed graph properties
Andrew M. Childs and Robin Kothari · 2011
Closest in time.