It’s known that BQP (the stuff that a quantum computer can compute in probabilistic polynomial time) is a subset (maybe not a proper one) of PSPACE. I’m pretty sure the same thing applies to QR (the stuff computable on a quantum turing machine) vs R (same for a classical Turing machine). So anything that a quantum computer can do, a classical computer can also do, though the classical computer might take exponentially longer.

Usually though, this type of “proof” is supposed to be “concise” (its size is bounded by a polynomial over the size of the problem instance). The classical complexity classs is called NP, non-deterministic polynomial time, with P=?NP being the best known open problem in complexity.

For quantum computers, the analog of NP is called QMA (Quantum Merlin Arthur). QMA is at least as large as BQP, and it’s unknown whether BQP is contained in NP, so the answer to your question is “nobody knows for sure”, in the sense of having a mathematical proof. I think it’s generally believed though that BQP is larger than P (that’s why there’s so much hype about quantum computers), that NP is larger than P, and so on.

en.wikipedia.org/wiki/QMA en.wikipedia.org/wiki/BQP