Scott Aaronson

Quantum Approximate Counting, Simplified

2019 · arXiv (Cornell University)

In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a quantum algorithm for approximate counting. Given a list of $N$ items, $K$ of them marked, their algorithm estimates $K$ to within relative error $\varepsilon$ by …

Doubly infinite separation of quantum information and communication

2016 · Physical Review A

We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call ``doubly infinite,'' between their quantum information and communication complexities. We do so by studying the exclusion game …