Is the extended Euclidean algorithm optimal for computing modular inverses? Is there an algorithm that can compute modular inverses in less than $O(n^{2})$? If not, is the Euclidean algorithm provably optimal?
 A: Firstly, you use $O(n^2)$ in a way that I'm not accustomed. If we are using it on two numbers with the larger of size $n$, then the extended Euclidean algorithm runs in time $O( (\log n)^2)$. In fact, Lamé showed that the number of steps is less than $10$ times the number of digits of the smaller of the two numbers in the algorithm$^{[1]}$. This proof is short and uses the Fibonacci numbers (which happen to be the exact cases when there is worst-case running time).
But that is besides the point. In practice, there is a faster algorithm that is still often used, although it has roughly the same asymptotic growth of $O( \log^2 n)$. It's called the Binary GCD algorithm (also called Stein's algorithm), since it takes advantage of how computers store data.
For very large numbers, you might use the asymptotically faster methods of Schönhage$^{[2]}$ or Stehlé$^{[3]}$.
I don't describe them, but instead point you towards a survey article by Möller, which describes 4 different sub-$O( \log^2 n )$ algorithms and their implementations.

References
[1]: Lamé, 1844. "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus Acad. Sci. 19: 867–870.
[2]: Cesari G (1998). "Parallel implementation of Schönhage's integer GCD algorithm". In G. Buhler. Algorithmic Number Theory: Proc. ANTS-III, Portland, OR. New York: Springer-Verlag. pp. 64–76. Volume 1423 in Lecture notes in Computer Science.
[3]:Stehlé D, Zimmermann P (2005). "Gal's accurate tables method revisited". Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17). Los Alamitos, CA: IEEE Computer Society Press.
