## Archive for **August 2012**

## Lines through four lines

(Reposting this from an earlier blog which I gave up on, but liked the post so I added some pictures – all images produced using the amazing free alternative to Maple/Mathematica, Sage).

I was reading Fulton-Pandharipande (“Notes on stable maps and quantum cohomology”) the other day and came across the classical result that there are exactly two lines passing through a generic quadruple of lines in . I encourage people to whom this fact is unfamiliar to convince themselves of it. It was unfamiliar to me and I found it hard to visualise, so I sat down and drew some pictures until I understood it.

## Quantum computers: Grover’s algorithm

I’ve been meaning to get my head around the idea of a quantum computer for a while now and, since my mathematical energy is currently reduced to clearing out my ETH office, I thought I’d do some reading and find out more. I leafed through my dusty copy of Wikipedia [Wik], picked up Kitaev et al [KSV] from the library and turned to chapter two…

I think the easiest way to illustrate how a quantum computer differs (functionally) from a classical computer is by explaining an algorithm which only makes sense for quantum computers and which really outperforms a classical algorithm for the same task (that is the point of quantum computers, after all). The first algorithm they explain in [KSV] is called Grover’s algorithm and it performs the task of searching a database. Wikipedia [Wik] has a really nice exposition too, but I was initially confused by what they both call a “quantum oracle” (sounds like something from Star Trek TNG). I tried to explicitly avoid that in what I said below.

**TLDR:** Classically you have to look through all N elements of a database until you find the right one (so runtime increases linearly in N); Grover’s algorithm has a surprising runtime of order to do the same thing, using clever ideas from quantum mechanics.