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 […]