Fetching the paper…
Reading the bibliography…
We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem.
Linear Representations of Finite Groups
Jean-Pierre Serre · 1977
Earlier work this paper cites.
The Graph Isomorphism Problem: Its Structural Complexity
J. Köbler, U. Schöning, and J. Toran · 1993
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997
Earlier work this paper cites.
Quantum algorithm for the collision problem
Gilles Brassard, Peter Høyer, and Alain Tapp · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. Shor · 1997
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.
Permutation Groups
Peter James Cameron · 1999
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
Andris Ambainis · 2000
Earlier work this paper cites.
The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions
Bruce E. Sagan · 2001
Earlier work this paper cites.
Quantum lower bound for the collision problem
Scott Aaronson · 2002
Cited alongside, same era.
Quantum lower bounds for the collision and the element distinctness problems
Yaoyun Shi · 2002
Cited alongside, same era.
Polynomial degree vs. quantum query complexity
Andris Ambainis · 2003
Cited alongside, same era.
Adiabatic quantum state generation and statistical zero knowledge
Dorit Aharonov and Amnon Ta-Shma · 2003
Cited alongside, same era.
Associations Schemes: Designed Experiments, Algebra and Combinatorics
Rosemary Bailey · 2004
Cited alongside, same era.
A lower bound on the quantum query complexity of read-once functions
Howard Barnum and Michael Saks · 2004
Cited alongside, same era.
A new quantum lower bound method with applications to direct product theorems and Time-Space tradeoffs
Andris Ambainis, Robert Špalek, and Ronald de Wolf · 2007
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.
Quantum and classical strong direct product theorems and optimal Time-Space tradeoffs
Hartmut Klauck, Robert Špalek, and Ronald de Wolf · 2007
Later among the works it cites.
Quantum complexities of ordered searching, sorting, and element distinctness
Peter Høyer, Jan Neerbek, and Yaoyun Shi · 2008
Later among the works it cites.
Lower bounds for randomized and quantum query complexity using Kolmogorov arguments
Sophie Laplante and Frédéric Magniez · 2008
Later among the works it cites.
The multiplicative quantum adversary
Robert Špalek · 2008
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A polynomial quantum query lower bound for the set equality problem
Gatis Midrijānis · 2004
Cited alongside, same era.
A new quantum lower bound method with an application to strong direct product theorem for quantum search
Andris Ambainis · 2005
Cited alongside, same era.
Limitations of quantum coset states for graph isomorphism
Sean Hallgren, Cristopher Moore, Martin Roetteler, Alexander Russell, and Pranab Sen · 2006
Cited alongside, same era.
All quantum adversary methods are equivalent
Robert Špalek and Mario Szegedy · 2006
Cited alongside, same era.
Later among the works it cites.
Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function
Ben W. Reichardt · 2009
Later among the works it cites.
Troy Lee, Rajat Mittal, Ben W. Reichardt, and Robert Špalek · 2010
Closest in time.
Strong direct product theorems for quantum communication and query complexity
Alexander A. Sherstov · 2010
Closest in time.