Question

Let f(n) be a space-constructible superpolynomial function. Then BQP $\subseteq$ PSPACE $\subset$ SPACE(f(n)), so in particular, SPACE(f(n)) $\not\subseteq$ BQP. Let L be a problem such that every problem in SPACE(f(n)) is BQP-reducible to L. Then L $\notin$ BQP.

Are there any problems that have been proven to not be in BQP for which that is not known to be provable by the above method?

Answer 1

There are few complexity class separations known which do not follow from some type of diagonalization (a complexity hierarchy theorem of some kind). I know of none for $\mathbf{BQP}$. One canonical example of a separation that doesn't seem to follow from a diagonalization argument is $\mathbf{AC}^0 \subsetneq \mathbf{NC}^1$, which instead follows from the Ajtai-Furst-Saxe-Sipser theorem that the parity of $n$ bits does not have polynomial size circuits of unbounded fan-in and constant depth.

Now, if by "the above method" you meant something more specific than just diagonalization, then there is just a little something else you can say about $\mathbf{BQP}$. Adleman, DeMarrais, and Huang proved that $\mathbf{BQP} \subseteq \mathbf{PP}$:

Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang: Quantum Computability. SIAM J. Comput. 26(5): 1524-1540 (1997)

(Recall that $\mathbf{PP}$ consists of languages recognized by randomized polynomial time algorithms with "exponential precision". Without loss of generality, we may say that an input is "accepted" by such an algorithm if and only if the probability of outputting $1$ is strictly greater than $1/2$. Note this probability could be $1/2+1/2^{n^{\Omega(1)}}$. It is known that $\mathbf{PP} \subseteq \mathbf{PSPACE}$, but the other direction is unknown.)

Just like $\mathbf{PSPACE}$ has a superpolynomial analogue $\mathbf{SPACE}(f(n))$, $\mathbf{PP}$ has a superpolynomial analogue $\mathbf{PTIME}(f(n))$, so in your above argument you can replace $\mathbf{SPACE}(f(n))$ with $\mathbf{PTIME}(f(n))$. Note the latter is contained in the former.