1.5k citations · 3.7k across the 74 of their papers we have counts for
8 papers · 1 filter
The space "just above" BQP
Scott Aaronson, Adam Bouland, Joseph Fitzsimons +1
We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to a…
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Scott Aaronson, Andris Ambainis
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one nee…
Bounding the seed length of Miller and Shi's unbounded randomness expansion protocol
Renan Gross, Scott Aaronson
Recent randomness expansion protocols have been proposed which are able to generate an unbounded amount of randomness from a finite amount of truly random initial seed. One such pr…
Near invariance of the hypercube
Scott Aaronson, Hoi Nguyen
We give an almost-complete description of orthogonal matrices of order that "rotate a non-negligible fraction of the Boolean hypercube onto itself," in the…
Quantum lower bound for inverting a permutation with advice
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs +1
Given a random permutation as a black box and , we want to output . Supplementary to our input, we are given classical advice in the form…
Quantum POMDPs
Jennifer Barry, Daniel T. Barry, Scott Aaronson
We present quantum observable Markov decision processes (QOMDPs), the quantum analogues of partially observable Markov decision processes (POMDPs). In a QOMDP, an agent's state is…