I’m guessing that you mean, can they solve them in polynomial time. It’s not known, but probably they can’t.
The class of decision problems that can be solved in polynomial time by a quantum computer is known as QP. The precise definition requires saying something about the reliability of the algorithm. A quantum computer can do the equivalent of flipping a coin, and it could solve lots of problems if it were lucky, but this is not what is meant by its being able to solve it in polynomial time.
Because a quantum computer can behave just like a classical computer, QP contains P, the class of problems that can be solved in polynomial time on a Turing machine (or typical other abstract classical computer). On the other hand, QP is contained in PSPACE because it is possible to simulate a quantum computer running a polynomial-bounded time with a classical computer using polynomial-bounded space by enumerating all possible computation paths and adding up close approximations to the amplitudes.
Nobody has a proof of where QP lies in between P and PSPACE. Being able to factor integers in polynomial time (polynomial in the number of digits) is equivalent to being able to solve a certain decision problem in polynomial time. That problem is in QP, is in NP, and is not known to be in P. The fact that people have tried for so long to find a fast algorithm suggests maybe it isn’t in P, but we don’t really know. It leads to the suspicion that QP is more than just P. On the other hand, for QP to be PSPACE seems fairly improbable. But it hasn’t yet been proven not to be. It’s likely to be a super difficult problem, like many in computing complexity!
The way that media articles describe quantum computing often makes it sound akin to a mechanism for getting “nondeterminism” like in “nondeterministic polynomial time” (NP). But there is no apparent reason to expect that a quantum computer can solve problems like SAT in polynomial time by exploring all possibilities or whatever.
There is a way that a quantum computer can proceed as if a bit was 0 and as if it were 1, with a 1/2 chance at the end of the calculation of getting both answers. If you are trying to solve an NP-complete problem, however, this is very much like guessing the possible solution by flipping a coin.
If solving an NP-complete problem in polynomial time on a quantum computer was known to be possible, the people in quantum computing could save themselves a lot of mucking around developing special algorithms. A quantum computer is able to excel at some tasks because they are ones where it can get appropriate phase cancellation or phase reinforcement for relevant possibilities. Shor’s algorithm for factoring integers in a quantum computer is celebrated because it uses a clever way of getting the correct answer to be reinforced while the incorrect possible answers cancel out. If it were already able to solve an NP-complete problem like SAT it would be straightforward to use that to factor numbers too and a specialized algorithm like Shor’s algorithm would just be maybe a more efficient way to do it.
Grover’s algorithm for searching allows a lot of searching to be done unusually fast. It takes time proportional to the square root of the number of cases, which is somewhat bizarre, and would be welcome for a lot of things. The square root of an exponential however is just a slower-growing exponential.
It is conceivable that someone will find a quantum algorithm for an NP-complete problem or even a PSPACE-complete problem, but neither one is expected to happen.
