Turing produced the Turing machine in an effort to answer the question ``Is there a mechanical procedure by which the truth or falsity of any mathematical conjecture can be decided?'' Turing reasoned that if there was such a method, and if it were truly mechanical in nature and requiring no creative effort, then it could be performed by a Turing machine. The proof offered by Turing that there is no such procedure is the same as the proof of Turing's Halting problem, which states that no Turing machine H can in general be given any arbitrary Turing machine X and its input (Ix) as its own (H's) input, and determine whether X will run to completion on Ix. The demonstration by Turing of a problem which can not be solved by a Turing machine suggests the division of functions into two groups: those that can be computed by a Turing machine and those that can not.
By the Church-Turing thesis we can generally say that functions that are not Turing computable are simply ``not computable.'' It should be stressed at this point that this classification of a function that is not Turing computable as not computable in a general sense is due to the definitional aspect of the Church-Turing thesis. It is a logical possibility that some future computing machine will indeed be able to compute some function that a Turing machine can not - however no such machine is known, and the development of such a machine would be a large breakthrough. Arguments can be made that no such machine would be physically possible - however this is not a settled question.
Determining if a function is computable at all is interesting, but this distinction is not fine enough to determine if a function can realistically be solved by a physical computer in a reasonable amount of time. If a computation will take billions of years to compute, it may as well be uncomputable from the perspective of the pragmatist. A algorithm can be characterized by the number of operations and amount of memory it requires to compute an answer given an input of size n. These characterizations of the algorithm determine what is called the algorithm's running time or time complexity. Specifically, the time complexity of an algorithm to compute a function is determined by looking at how the number of operations of the algorithm scale with the size of the input of the function it computes. We'll take the size of the input to be the number of bits needed to represent that number in binary.
An algorithm which computes its output for an input of size n using resources (computational steps, memory, etc.) that is bounded above by a polynomial function of n are said to be of polynomial time. For example if an algorithm with an input size of 10 bits took 104 +7*102 + 1001 operations to compute its answer it would be considered a polynomial time algorithm.
Problems which can be solved in polynomial time or less are generally deemed to be tractable. An algorithm which solves a problem in polynomial time may be referred to as efficient. Problems which require more than polynomial time are usually considered to be intractable, for example an algorithm which would require 2n operations for an input size of n would be considered intractable, as the number of operations grows exponentially with the input size, not polynomially. Generally tractable problems are considered to be those which may practically be solved in the real world. (Shor)
In complexity theory, problems are often restated in terms of a decision problem - this means that the function of interest takes in its input and produces a yes or no answer.
Computer Scientists have grouped problems into a variety of complexity classes, below are some of the more well known.
Given these distinctions, to determine if an function may be efficiently computed by a classical computer there are two questions that must be answered. First, can a Turing machine compute the function, if so then the function is called computable. Second the time complexity of the algorithm to be used must by considered. In general if an algorithm requires polynomial time or less to compute it is considered to be tractable, and if not it is considered to be intractable.
Accordingly, interest in quantum computing is twofold. First it is of interest if a quantum computer can compute functions which are uncomputable on a classical computer, and second it is of interest whether an algorithm which is intractable on a Turing machine may be tractable on a quantum computer.