Saturday, February 9, 2008

Ubiquitous Eigenvectors and Quantum Computing

Recently I have been studying Quantum Computation (QC). If you want to get anywhere with QC you need to master Linear Algebra and Vector Spaces since QC is baically an exercise in applied vector space theory.

Being a bit rusty in the topic myself, I decided to pick up the book Finite-Dimensional Vector Spaces by Paul Richard Halmos. Although Halmos is one of my favorite math authors, I picked this book primarily because it has a Kindle edition. It turns out that another one of Halmos's books, Linear Algebra Problem Book, is a far better choice for the non-mathematcian. The later book walks you step by step through bite sized problems and provides hints (and also all the answers if you get stuck). A free resource with answers can also be found here.

One of the central mathematical techniques at the heart of Linear Algebra is the concept of Eigenvectors and Eigenvalues. The term Eigen is derived from German and means "characteristic". An Eigen Decomposition is a method of reducing a square matrix to into a constant (eigenvalue) and a vector (eigenvector). This decompostion is central to many problems in physics.

It turns out that the study of Eigen decompostion can yield deep insight into problems that are in the realm of computer science. Consider, for instance, this paper about Google's page rank algorithm and the Eigenface technique for facial recognition.

Coming to grips with the mathematics behind Vector Spaces is one of the single most rewarding experiences for anyone interested in advanced problems in computer science. It is a must if you ever want to graduate from the comprehension of clasical algorithms to the comprehension of quantum algorithms. However, if are curious about QC but the thought of learning advanced linear algebra sounds like too big of a comitment, then you might want to check out Quantum Computation explained to my Mother. This is the most approachable paper I have ever read on the topic that is also mathematically accurate.