How to quantify noncommutativity? If I have two operators or finite-dimensional matrices $A$ and $B$, how can I quantify the amount to which they commute or don't commute? (I would consider it a big plus if it is computable easily for finite complex-valued matrices $A, B \in \mathbb C^{n\times n}$.) 
Let me try the obvious thing here: by definition if $A$ and $B$ commute, then the commutator $[A, B] = AB-BA = 0$. Naively would use some sort of functional like an operator norm to reduce this to a number that could potentially behave like a metric. The first thing I thought of was the trace, but clearly that doesn't work since $\mathrm{tr } [A, B] =\mathrm{tr } (AB-BA) = \mathrm{tr }AB - \mathrm{tr }AB = 0$ always. One could then turn to, say, the Frobenius norm of $[A, B]$. What is known about the maximal (or supremal) value of such norms?
Are there quantifiers of noncommutativity that can also account for higher-order effects, e.g.  cases where $[A, B] \ne 0$ but $[A, [A,B]] = 0$? This should be "less" non-commuting than if $[A, B] \ne 0$ and $[A, [A,B]] \ne 0$ and $[B, [A,B]] \ne 0$ but, say, $[A, [B, [A, B]]] = 0$.
For those who prefer a free algebraic setting, the question can be framed as: how free is a non-free algebra? Is there a sensible way to measure proximity to a free algebra? What if I had an algebra where $AB=BA$ is the only one relation that makes it not a free algebra; is there a sense it is "less free" or "more free" than an algebra where $ABABAB=BAA$ is the only such relation, or example.
Motivation: it is sometimes said that free probability is the study of "maximally" non-commuting objects. I would like to know if this statement can be made precise in the sense of how one can define "maximally non-commuting" in a sensible fashion.
 A: Have a look at this paper:
http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=8&ved=0CHEQFjAH&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.54.7075%26rep%3Drep1%26type%3Dpdf&ei=_1mtT8vHDI-1hAf3kJifDA&usg=AFQjCNG4ku3ERsScCZe9qdfYhT5mYGcaZA
One way to measure commutativity defect,as discussed in the paper is by the rank of $[A,B]$. If $rank([A,B])=1$, $A,B$ are called a Laffey pair.
This approach is based on the fact that commuting matrices have a simultaneous triangularization. See also Commuting Matrices and the Weak Nullstellensatz.
A: I don't imagine what I will write below has anything to do with free probability, but it outlines an algebraic approach along the lines of your third and fourth paragraph.  Namely, I'd suggest looking at work of Kapranov, and Feigin and Shoikhet:
Noncommutative geometry based on commutator expansions, http://arxiv.org/abs/math/9802041
On $[A,A]/[A,[A,A]]$ and on a $W_n$-action on the consecutive commutators of free associative algebra http://arxiv.org/abs/math/0610410
and several follow-up papers featuring the term "lower central series" in either the title or the abstract.  The idea is that there are a variety of natural filtrations on any algebra which capture precisely this idea that operators may not commute but may have identities involving higher commutators which are a sort of weakened commutativity.
A neat example of this is due to Feigin-Shoikhet and says that the algebra of even degree differential forms on $\mathbb{C}^n$ (equipped with a certain quantized form) is the universal quotient of the free algebra $A_n$ on $n$ generators such that $[a,[b,c]]=0$ for all $a,b,c \in A_n$ (but $[a,b]\neq 0$ in general).  That such a general quotient of the free algebra gives you something so directly related to commutative algebra (and in particular exhibiting polynomial growth in degree) is rather interesting.  In particular, the case you asked about is when $n=2$, and you get just the algebra of functions and two forms, with product $f\ast g = fg + df\wedge dg$.
One answer to 4 is that one can define a locally free algebra to be an algebra $A$, such that the completion of $A$ at the lift from $A_{ab}$ of any maximal ideal is free.  For instance, the algebra $A_3 / <x^2+y^2+z^2-1>$ is locally free of rank two, even though it is not free, because one can easily show that its completions at
$<(x-x_0),(y-y_0),(z-z_0)>$
is a (completed) free algebra in two generators for any $(x_0,y_0,z_0)$ satisfying the defining equation.  These (not just this example, but this class of locally free algebras) behave similarly to free algebras, and it was showed by Etingof that their universal quotient by triple commutators as in the above paragraph is again (a quantization of) even-degree differential forms (but now on the corresponding variety).
A: I've always wanted to explore some quantities of the following sort, but have not had the time to do so. Particularly, I'd like to see if there is any connection with free entropy dimension (because with matrices we can consider actual volumes of sets). The following by no means conclusively answers the question, but may provide some food for thought. For the sake of simplicity, suppose we are trying to measure "how free" a finitely generated group $G$ is. Suppose we are working with a countable group generated by a finite set $F$ (to get the overall measurement we'd have to take a supremum over all finite generating sets). Define a metric on $G$ as $d(g,h)=$length of $g^{-1}h$ with respect to F.
The idea is to think of the group as analogous to a manifold and consider something roughly analogous to "volume entropy"  around a given point (element of the group). For example, around $g_{0}\in G$ and $\eta \geq 0$ one might consider the quantity $$V(g_{0},F,\eta):=lim_{R\rightarrow \infty}\frac{| \lbrace h\in G:d([g_{0},h],e)\leq \eta,\ d(g_{0},h)\leq R\rbrace|}{|B_{d}(g_{0},R)| \} $$
Here, $B_{d}(g_{0},R)$ denotes, of course, the ball of radius $R$ around $g_0$ and the absolute value bars denote cardinality. One then would take the supremum over all $g_{0} \in G$ to obtain something global. 
Note that if one lets $\eta=0$, one is measuring the asymptotic growth of the fraction of elements that commute with $g_0$. 
Roughly, this measures the asymptotic growth of the fraction of words with controlled commutator with a given word. It's clear that the above quantity may not do a very good job at measuring the distance from the free group (it looks like it may fail for a one-relator group...since it only considers asymptotic growth) but maybe it can be usefully modified. Thanks for a very nice question! 
A: A good way to quantify the non-commutativity of $A,B$ is to compare their flows, e.g. to compare the solutions of
$
\dot u=Au,\quad\dot v=Bv
$
with same initial datum. A complete answer is given by the Campbell-Hausdorff formula
$$
\exp{tA}\  \exp{tB}=\exp{\bigl(t(A+B)+\frac{t^2}{2}[A,B]+\frac{t^3}{12}([A,[A,B]]+[B,[B,A]])+\dots\bigr)}.
$$
In the exponent are appearing successively the first bracket and the iterated brackets. 
A: One very algebraic way to approach it (alas not that easily approached computationally) - somewhat related to David Jordan's answer - would be to look at the Lie subalgebra generated by $A$ and $B$ in the algebra of matrices (that is, the linear span of all commutator words in $A$ and $B$) and impose one or another condition relaxing commutativity, e.g. say that it is nilpotent of degree $k$ or solvable of degree $k$. In that case, $k$ will of course somewhat quantify the magnitude of noncommutativity $A$ and $B$ share. 
A: One common way to quantify non-commutativity which is especially popular in operator algebra theory and non-commutative geometry is to use the Schatten norms.  Given a bounded operator $T$ on a separable Hilbert space $H$ one defines the Schatten $p$-norm $||T||_p$ (for $p \geq 1$) of $T$ to be the trace of the operator $|T|^p$ defined using the functional calculus.  More explicitly, if the operator $\sqrt{T^*T}$ has countable spectrum (a necessary condition for $||T||_p$ to be finite) then
$$||T||_p^p = \sum_n \lambda_n^p$$
where the sum is taken over the spectrum of $\sqrt{T^*T}$.  In particular the case $p = 1$ corresponds to the trace norm and $p = 2$ corresponds to the Hilbert-Schmidt norm.  
In the finite dimensional case the Schatten norms are of course all finite, but in the infinite dimensional case it is useful to measure the non-commutativity of two operators $A$ and $B$ by calculating the minimum value of $p$ such that $||[A,B]||_p < \infty$.  For example one can measure the regularity of a function on a manifold by asking which Schatten classes its commutators with appropriately chosen (pseudo)differential operators belong to.  This is the basis of Connes' notion of a non-commutative manifold.
Also note that every Schatten class operator is compact, and for many purposes it is useful to replace the condition that two operators commute with the condition that their commutator is compact.  Of course this particular notion has no finite dimensional analogue.
A: EDIT (see updated part (d) below).
Below are some answers to subparts of the whole question.
a). "...What is known about the maximal (or supremal) value of such norms?"
It is known that for the Frobenius norm $\| [A,B] \|_F \le \sqrt{2}\| A \|_F\|B\|_F$, and this bound is tight. More generally, Wenzel and Audenaert (Impressions of convexity --- An illustration for commutator bounds, math.FA-1004.2700v1) prove commutator bounds for Schatten norms. These bounds assume the form
$$
  \| AB-BA\|_p \le C_{p,q,r} \|A\|_q\|B\|_r,
$$
where $\|X\|_p$ denotes the Schatten-p norm. Moreover, Wenzel and Audenaert establish the tightest possible values for the constant $C_{p,q,r}$. 
For lower-bounds, much less is known. See this popular MO question for pointers.
b). "Are there quantifiers of noncommutativity that can also account for higher-order effects?"
Here, you could again repeatedly invoke the above norm based commutator bounds. More interestingly, one could check to see how many "large" terms there are in the corresponding Baker-Campbell-Hausdorrf series (though this sounds like overdo to me)
c). "Maximally noncommutative": Here, one way to characterize maximally noncommutative matrices would be to find examples that make the commutator norm inequality above into an equality. For explicit constructions, please see the cited paper of Wenzel and Audenaert.
d). "other ways of quantifying noncommutativity?" --- this is open ended, but one other way to quantify nc could be to see how many "bits of information" are required to encode the difference $AB-BA$. Such an "information complexity" measure might not be that easy to make precise though.

EDIT: If one restricts the class of operators / matrices of interest, then more interesting measures of noncommutativity are possible, including those with a physical interpretation.
  The most notable examples come from quantum information theory, where measures of noncommutativity have been of interest for quite long. Here, instead of arbitary complex matrices, a measure called skew entropy has been used to quantify noncommutativity of a positive operator $A$ with respect to a fixed Hermitian operator $K$ (see [1] for details). This is defined as,
  \begin{equation*}
  S(A,K) := \frac{1}{2}\mbox{trace}[A^{1/2},K]^2.
\end{equation*}
  The above quantity was introduced by Wigner and Yanase, and was generalized later by Dyson to 
  \begin{equation*}
  S_t(A,K) := \frac{1}{2}\mbox{trace}[A^t,K][A^{1-t},K],\quad 0 < t < 1.
\end{equation*}
  (The second measure is also interesting for the fact that it's concavity (in $A$ was conjectured by Dyson, and proved as a consequence of the famous Lieb concavity theorem).

References
[1]: Positive definite matrices. R. Bhatia. Princeton University Press. 2007.
A: "(I would consider it a big plus if it is computable easily for finite complex-valued matrices $A,B \in \mathbb{C^{n×n}}$.)"
If you want to measure non-commutativity of two matrices in an easy fashion, I would suggest using the Frobenius norm.  This is because for any square matrix, $T = (t_{i,j})$, 
$||T||_F =(\sum_{i,j}|t_{i,j}|^2)^{1/2}$, which is not hard to compute.
