Fetching the paper…
Reading the bibliography…
Aaronson and Ambainis (SICOMP `18) showed that any partial function on $N$ bits that can be computed with an advantage $\delta$ over a random guess by making $q$ quantum queries, can also be computed classically with an advantage $\delta/2$ by a randomized decision tree making ${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$ queries.
Tables for computing bivariate normal probabilities
Donald B. Owen · 1956
Earlier work this paper cites.
An inequality for hermite polynomials
Jack Indritz · 1961
Earlier work this paper cites.
Rapid solution of problems by quantum computation
David Deutsch and Richard Jozsa · 1992
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Quantum complexity theory
Ethan Bernstein and Umesh Vazirani · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Peter W. Shor · 1997
Earlier work this paper cites.
On the power of quantum computation
Daniel R. Simon · 1997
Earlier work this paper cites.
Sharp Quantum versus Classical Query Complexity Separations
J. Niel de Beaudrap, Richard Cleve, and John Watrous · 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.
Exponential algorithmic speedup by a quantum walk
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman · 2003
Earlier work this paper cites.
Quantum property testing
Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig · 2008
Cited alongside, same era.
BQP and the Polynomial Hierarchy
Scott Aaronson · 2010
Cited alongside, same era.
Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal · 2010
Cited alongside, same era.
Quantum one-way communication can be exponentially stronger than classical communication
Bo’az Klartag and Oded Regev · 2011
Cited alongside, same era.
Mean Field Models for Spin Glasses, Volume I: Basic Examples
Michel Talagrand · 2011
Cited alongside, same era.
Analysis of Boolean Functions
Ryan O’Donnell · 2014
Cited alongside, same era.
Krivine diffusions attain the Goemans-Williamson approximation ratio
Ronen Eldan and Assaf Naor · 2019
Later among the works it cites.
Oracle separation of BQP and PH
Ran Raz and Avishay Tal · 2019
Later among the works it cites.
Towards optimal separations between quantum and randomized query complexities
Avishay Tal · 2019
Later among the works it cites.
k k -Forrelation Optimally Separates Quantum and Classical Query Complexity
Nikhil Bansal and Makrand Sinha · 2020
Closest in time.
Concentration on the Boolean hypercube via pathwise stochastic analysis
Ronen Eldan and Renan Gross · 2020
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Separations in query complexity using cheat sheets
Scott Aaronson, Shalev Ben-David, and Robin Kothari · 2016
Cited alongside, same era.
Separations in query complexity based on pointer functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs · 2017
Cited alongside, same era.
Forrelation: A problem that optimally separates quantum from classical computing
Scott Aaronson and Andris Ambainis · 2018
Cited alongside, same era.
Query-To-Communication Lifting for BPP Using Inner Product
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi · 2019
Cited alongside, same era.
Entangled simultaneity versus classical interactivity in communication complexity
Dmitry Gavinsky · 2020
Closest in time.
Lower Bounds for XOR of Forrelations
Uma Girish, Ran Raz, and Wei Zhan · 2020
Closest in time.
An Optimal Separation of Randomized and Quantum Query Complexity
Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu · 2020
Closest in time.
A stochastic calculus approach to the oracle separation of BQP and PH
Xinyu Wu · 2020
Closest in time.