Mathematical Field Notes

Archive for August 2012

Lines through four lines

with 8 comments

(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 \mathbb{CP}^3. 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.

Read the rest of this entry »

Written by Jonny Evans

August 14, 2012 at 12:36 pm

Quantum computers: Grover’s algorithm

leave a comment »

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 \sqrt{N} to do the same thing, using clever ideas from quantum mechanics.

Read the rest of this entry »

Written by Jonny Evans

August 13, 2012 at 10:13 pm