Why does non-commutativity in quantum mechanics require us to use Hilbert spaces? I am reading Why we do quantum mechanics on Hilbert spaces by Armin Scrinzi. He says on page 13: 

What is new in quantum mechanics is non-commutativity. For handling this, the Hilbert space representation turned out to be a convenient — by many considered the best — mathmatical environment. For classical mechanics, working in the Hilbert space would be an overkill: we just need functions on the phase space.

I understand the definition of a Hilbert space, but I do not understand why non-commutativity compels us to use Hilbert spaces.
Can someone explain? 
 A: 
I understand the definition of a Hilbert space. But I do not understand why non-commutativity compels us to use Hilbert spaces.

It doesn't, but that's not what Scrinzi is saying.
The reason is doesn't is because we could work, for example, in Wigner quasiprobability representation:
$$\rho\mapsto W(x,p) = \frac{1}{\pi\hbar}\int_{-\infty}^\infty\langle x+x'|\rho|x-x'\rangle e^{-2ipx'/\hbar}\,\mathrm{d}x'\text{,}$$
where for pure states $\rho = |\psi\rangle\langle \psi|$ as usual, and Hermitian operators correspond to functions through the inverse Weyl transformation.
Note that $W(x,p)$ is a real function that's just like a joint probability distribution over the phase space, except that it's allowed to be negative. The uncertainty principle requires us to give up something, but it doesn't actually force Hilbert spaces on us.
However, what Scrinzi is saying is two things: (a) Hilbert spaces are very convenient to us in quantum mechanics, and (b) Hilbert spaces could be used in classical mechanics, but because non-commutativity doesn't exist in classical mechanics, it's "overkill" there, whereas it's "just the right amount of kill" in quantum mechanics. Both claims are correct.
The reason we can have used Hilbert spaces in classical mechanics is because they can represent very general algebras of observables, while the classical algebra of observables, being commutative, is actually simpler. (Cf. the Gel'fand–Naimark theorem for $C^*$-algebras in particular.)
The Hilbert space formulation of classical mechanics was done by Koopman and von Neumann in 1931-1932. But what their formulation actually does is generalize classical mechanics unless one imposes an artificial restriction that you're only ever allowed to measure observables in some mutually commutative set; only then is the classical (in the 19th century sense) mechanics is recovered exactly.
It is that artificial restriction that quantum mechanics lifts. Physically, non-commutativity observables corresponds to an uncertainty principle between them.
A: For a general and brief overview of the mathematical framework of Quantum Mechanics, see this answer. In a nutshell, Hilbert spaces arise from the representation theory of C*-algebras, which are postulated to be the relevant mathematical object that describes a quantum theory (because it contains observables in its self-adjoint part, and states as special elements from its topological dual).
To further motivate non-commutativity, consider the following facts. The first is that any commutative (unital) C*-algebra, by a theorem of Gelfand and Naimark, is isomorphic to $C(X)$, i.e. the C*-algebra of continuous functions over the compact Hausdorff space $X$, with uniform norm. Such a topological space can then be interpreted as the usual phase space of classical Hamiltonian mechanics.
A deeper motivation stems from Heisenberg's uncertainty principle. It is known that, if you have two incompatible observables (i.e. measurements that mutually influence their outcomes), then they cannot be measured simultaneously with arbitrary precision, and a way to reproduce this is to postulate that such observables, say $A$ and $B$, satisfy the relation
$$AB - BA = \frac {i\hbar}2C,$$
for some other (possibly generalised) observable $C$.
Another purely quantum phenomenon is that of interference, like the one experienced in the double-slit experiment, and this never occurs if the C*-algebra of observables is commutative. Hence there must be a superselection sector which is at least 2-dimensional, and hence an irreducible representation of the C*-algebra of the quantum mechanical system which is not 1-dimensional. For if this isn't the case then one can take the direct sum of all the GNS representations from pure states, which are irreducible and hence 1-dimensional by hypothesis. The image of such a representation is faithful and clearly commutative, and this forces the C*-algebra itself to be commutative as well (recall that a C*-algebra is commutative if and only if all its irreducible representations are 1-dimensional). So the relevant Hilbert space for classical mechanics is merely $\mathbb C$, while for quantum mechanics one needs at least $\mathbb C^2$ and an irreducible closed subalgebra of the $2\times2$ matrices $M_2(\mathbb C)$.
A: One of the reasons might be that if the position ($x$) and momentum ($p$) were operators in a finite dimensional space their commutator $[x,p]$ would always have trace zero. So, in order to have Heisenberg relation we need (unbounded) operators in infinite dimensional space. :)
