
Open Problems Related to Quantum Query Complexity
I offer a case that quantum query complexity still has loads of enticing...
read it

An Automated Approach to the Collatz Conjecture
We explore the Collatz conjecture and its variants through the lens of t...
read it

Efficient Learning of NonInteracting Fermion Distributions
We give an efficient classical algorithm that recovers the distribution ...
read it

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...
read it

Quantum Implications of Huang's Sensitivity Theorem
Based on the recent breakthrough of Huang (2019), we show that for any t...
read it

Quantum CopyProtection from Hidden Subspaces
Quantum copyprotection is an innovative idea that uses the nocloning p...
read it

On the Quantum Complexity of Closest Pair and Related Problems
The closest pair problem is a fundamental problem of computational geome...
read it

On the Classical Hardness of Spoofing Linear CrossEntropy Benchmarking
Recently, Google announced the first demonstration of quantum computatio...
read it

Quantum Approximate Counting, Simplified
In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a quantum algorith...
read it

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
This paper proves new limitations on the power of quantum computers to s...
read it

A Quantum Query Complexity Trichotomy for Regular Languages
We present a trichotomy theorem for the quantum query complexity of regu...
read it

Quantum Lower Bound for Approximate Counting Via Laurent Polynomials
We consider the following problem: estimate the size of a nonempty set S...
read it

PDQP/qpoly = ALL
We show that combining two different hypothetical enhancements to quantu...
read it

Online Learning of Quantum States
Suppose we have many copies of an unknown nqubit state ρ. We measure so...
read it

Shadow Tomography of Quantum States
We introduce the problem of *shadow tomography*: given an unknown Ddime...
read it

Quantum POMDPs
We present quantum observable Markov decision processes (QOMDPs), the qu...
read it

The Ghost in the Quantum Turing Machine
In honor of Alan Turing's hundredth birthday, I unwisely set out some th...
read it
Scott Aaronson
is this you? claim profile