Would a quantum computer solve the Riemann hypothesis?

Question

I heard that a quantum computer can give many results as one computation step. Does it mean that it would be just a brute force search for a quantum computer to solve for example the Riemann's hypothesis or Goldbach's conjecture?

Answer 1

It's already possible in principle to prove theorems via brute force, because it's relatively easy to check whether some random string of digits is a proof of the Riemann hypothesis. The problem is that this is too slow to finish in the next $10^{100}$ years or so. The problems that quantum computation can speed up are thus far few and very special, so there's no reason whatsoever to expect that a quantum computer would help with this, although it's not impossible.

Answer 2

Since automated theorem proving is in NP, this question can be rephrased as follows:

Does the complexity class BQP contain NP?

The answer is currently unknown, but it is suspected not to be true. Here is a discussion on MO: https://mathoverflow.net/questions/35151/what-impact-would-p-np-have-on-the-characterization-of-bqp

See also, related discussion on TCS: https://cstheory.stackexchange.com/questions/2800/if-p-np-could-we-obtain-proofs-of-goldbachs-conjecture-etc