According to a recent set of ideas introduced by David Deutsch (1985), it is possible in principle to construct a ‘quantum computer’ for which there are (classes of) problems which are not in P, yet which could be solved by that device in polynomial time.
