The Aaronson-Ambainis Conjecture (2008-2019)
Shtetl-Optimized 2019-11-17
Summary:
Around 1999, one of the first things I ever did in quantum computing theory was to work on a problem that Lance Fortnow suggested in one of his papers: is it possible to separate P from BQP relative to a random oracle? (That is, without first needing to separate P from PSPACE or whatever in […]