Kitaev Wins MacArthur!

I just saw the news that Alexei Kitaev, a pioneer in quantum computing and an incredible physicst/computer scientist, has won a MacArthur “genius” award. Awesome!

Kitaev was my next door neighbor while I was a postdoc at Caltech, and among the many highlights of my short life I count listening to Kitaev’s amazing, confounding, brilliant and way over my head ideas. One event in particular I will always remember involved Alexei talking to theoretical computer scientists and, halfway through the talk, pointing out how Majorana fermions were essential to understanding what was going on in that particular computer science problem. Sure in retrospect I understood what he was saying, but how the hell did he make that connection?!?! Truly a genius and completely deserving of the MacArthur award. Congrats Alexei!

Update 8pm PST: Seems that news article has been taken down. Hmm.
Update 12:30am PST List of fellows now posted here. In a local note, David Montgomery who studies geomorphology has also been named a MacArthur fellow.

1. #1 jeff watson
September 23, 2008

Dave,

It’s always wonder to celebrate the success of a friend. It makes one realize that the brass ring is attainable to those who seriously try for it. Tell your friend that Masteroftheuniverse offers his most heartfelt congrats.

Jeff

2. #2 Aaron
September 23, 2008

Dave, now you need to tell us the CS problem.

3. #3 anon
September 23, 2008

Alexei is without doubt the smartest person I’ve ever met.

-posted anonymously so as not to offend all the extremely-smart-but-not-quite-as-unbelievably-amazing-as-Alexei people I’ve met.

4. #4 Patrick
September 23, 2008

Aaron:

Having witnessed the event and been similarly amazed, here’s a no-frills summary.

The problem: Prove an asymptotically tight lower bound on the quantum communication complexity of the disjointness problem. [See Razborov 2002.]

The subproblem: You are given a matrix whose rows and columns are indexed by binary strings of length n and Hamming weight k. The entries of the matrix depend only on the number of sites at which the row and column strings both contain a 1. Find the eigenvalues and eigenvectors.

The solution to the subproblem is well known in certain circles, but it isn’t particularly easy. [See Knuth’s online unpublication about “Combinatorial matrices.”] Alexei was intrigued when the question came up during the talk and diagonalized the matrices on the spot by mapping the problem onto a question about spin chains. Wild.

Congratulations to Alexei on very well-deserved recognition!

5. #5 K.B.
September 23, 2008

“Alexei is without doubt the smartest person I’ve ever met.”

And, oddly enough (in light of this), one of the best instructors I’ve ever had.

6. #6 Jonathan Vos Post
September 24, 2008

Caltech professor wins MacArthur “genius” award
Article Launched: 09/23/2008 01:37:36 PM PDT

PASADENA – Alexei Kitaev, a Russian-born Caltech faculty member, has been awarded one of this year’s \$500,000 MacArthur “genius awards” for his work in quantum physics.

With a joint appointment at Caltech as professor of theoretical physics and computer science in the Divisions of Physics, Mathematics and Astronomy and of Engineering and Applied Science, Kitaev explores the mysterious behavior of quantum systems and their implications for developing practical applications, such as quantum computers, Caltech officials said.

Kitaev has explored the use of quantum physics for performing computation and although his work is focused mainly at the conceptual level, Caltech officials said he also participates in hands-on efforts to develop working quantum computers.

In a statement, Kitaev said he was “very surprised” when he received the call from Daniel Socolow, director of the MacArthur Fellows Program, telling him of his selection for the award.

“I didn’t know what the award was at first,” said Kitaev, who was born and educated in Russia. “But then I looked up the names of people who have previously received a MacArthur award, and saw that they are very good scientists. I am excited and honored to be in the same group with them.”

Kitaev received a diploma from the Moscow Institute of Physics and Technology in 1986, and his Ph.D from Russia’s Landau Institute for Theoretical Physics in 1989. He served as a researcher at Microsoft Research from 1999 until 2001. He first came to Caltech as a visiting associate and a lecturer in 1998 and was named professor of theoretical physics and computer science in 2002.

Kitaev is one of 25 newly named 2008 Fellows, who include UCLA astronomer Andrea Ghez, who received her M.S. in 1989 and her Ph.D in 1993 from Caltech, and Harvard Medical School neurobiologist Rachel Wilson, who was a postdoctoral fellow at Caltech from 2001 to 2004.

Kitaev also joins the ranks of previous Caltech MacArthur Fellows, including its two 2007 awardees, Michael Elowitz and Paul W. Rothemund.

7. #7 Dave Bacon
September 24, 2008

Today is the first day of classes but hopefully I’ll get a chance to write about some of Kitaevs work this week.

8. #8 Ian Durham
September 24, 2008

Too bad The Quantum Times just came out. I’ll add it in for the next issue, though. Congrats to Alexei!

As a note, there’s a fascinating history to Majorana spinors (the algebraic construction of Majorana particles). While Majorana gets the credit for their discovery, they were independently discovered by Eddington who used some interesting algebraic sleights-of-hand in his Fundamental Theory.

As for Majorana, Fermi called him a genius on par with Newton. Unfortunately he disappeared under mysterious circumstances on a ferry in 1937(9?).