research
∙
02/27/2023
Query-optimal estimation of unitary channels in diamond distance
We consider process tomography for unitary quantum channels. Given acces...
share
research
∙
10/12/2022
Quantum divide and conquer
The divide-and-conquer framework, used extensively in classical algorith...
research
∙
08/16/2022
Mean estimation when you have the source code; or, quantum Monte Carlo methods
Suppose y is a real random variable, and one is given access to “the cod...
research
∙
12/02/2021
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
We study the complexity of optimizing highly smooth convex functions. Fo...
research
∙
08/10/2021
Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
We study the problem of learning a Hamiltonian H to precision ε, supposi...
research
∙
02/16/2021
Unambiguous DNFs and Alon-Saks-Seymour
We exhibit an unambiguous k-DNF formula that requires CNF width Ω̃(k^2),...
research
∙
10/23/2020
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
Based on the recent breakthrough of Huang (2019), we show that for any t...
research
∙
10/05/2020
No quantum speedup over gradient descent for non-smooth convex optimization
We study the first-order convex optimization problem, where we have blac...
research
∙
06/19/2020
When Is Amplification Necessary for Composition in Randomized Query Complexity?
Suppose we have randomized decision trees for an outer function f and an...
research
∙
04/28/2020
Quantum Implications of Huang's Sensitivity Theorem
Based on the recent breakthrough of Huang (2019), we show that for any t...
research
∙
06/20/2019
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search p...
research
∙
04/18/2019
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
This paper proves new limitations on the power of quantum computers to s...
research
∙
02/10/2019
Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
We define a new query measure we call quantum distinguishing complexity,...
research
∙
09/06/2018
Quantum algorithms and approximating polynomials for composed functions with shared inputs
We give new quantum algorithms for evaluating composed functions whose i...
research
∙
07/17/2018
Classical lower bounds from quantum upper bounds
We prove lower bounds on complexity measures, such as the approximate de...
research
∙
10/25/2017