Fetching the paper…
Reading the bibliography…
We show that quantum query complexity satisfies a strong direct product theorem.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 1998
Earlier work this paper cites.
A parallel repetition theorem
R. Raz · 1998
Earlier work this paper cites.
Quantum Lower Bounds by Quantum Arguments
Andris Ambainis · 2002
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.
Towards proving strong direct product theorems
Ronen Shaltiel · 2003
Earlier work this paper cites.
Polynomial degree vs. quantum query complexity
Andris Ambainis · 2005
Earlier work this paper cites.
A new quantum lower bound method with applications to direct product theorems and time-space tradeoffs
Andris Ambainis, Robert Špalek, and Ronald de Wolf · 2006
Earlier work this paper cites.
Negative weights make adversaries stronger
Peter Høyer, Troy Lee, and Robert Špalek · 2007
Earlier work this paper cites.
Quantum and classical strong direct product theorems and optimal Time-Space tradeoffs
Hartmut Klauck, Robert Špalek, and Ronald de Wolf · 2007
Cited alongside, same era.
A Quantum Algorithm for the Hamiltonian NAND Tree
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2008
Cited alongside, same era.
Span-program-based quantum algorithm for evaluating formulas
Ben W. Reichardt and Robert Špalek · 2008
Cited alongside, same era.
The multiplicative quantum adversary
Robert Špalek · 2008
Cited alongside, same era.
Discrete-query quantum algorithm for NAND trees
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yeung · 2009
Cited alongside, same era.
Ben W. Reichardt · 2009
Rahul Jain · 2010
Later among the works it cites.
Troy Lee, Rajat Mittal, Ben W. Reichardt, and Robert Špalek · 2010
Later among the works it cites.
Reflections for quantum query algorithms
Ben W. Reichardt · 2010
Later among the works it cites.
Symmetry-assisted adversaries for quantum state generation
Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jérémie Roland · 2011
Closest in time.
Personal communication, 2011
Aleksandrs Belovs · 2011
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems
Falk Unger · 2009
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
Cited alongside, same era.
Improved Direct Product Theorems for Randomized Query Complexity
Andrew Drucker · 2011
Closest in time.
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy · 2011
Closest in time.
Strong direct product theorems for quantum communication and query complexity
Alexander A. Sherstov · 2011
Closest in time.