652 citations · 1.1k across the 25 of their papers we have counts for
4 papers · 1 filter
On the Quantum Complexity of Closest Pair and Related Problems
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin +2
The closest pair problem is a fundamental problem of computational geometry: given a set of points in a -dimensional space, find a pair with the smallest distance. A classic…
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
Scott Aaronson, Sam Gunn
Recently, Google announced the first demonstration of quantum computational supremacy with a programmable superconducting processor. Their demonstration is based on collecting samp…
Gentle Measurement of Quantum States and Differential Privacy
Scott Aaronson, Guy N. Rothblum
In differential privacy (DP), we want to query a database about n users, in a way that "leaks at most eps about any individual user," even conditioned on any outcome of the query.…
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
Scott Aaronson, Robin Kothari, William Kretschmer +1
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Lauren…