(by R.R. Tucci, June 2007)
For most of the guys, killings got to be accepted. Murder was the only way everybody stayed in line. You got out of line, you got whacked. Everybody knew the rules. --Joe Pesci, playing the role of Tommy, in the movie GoodFellas
Suppose you are a quantum system (i.e., a wiseguy), and Joe Pesci tells you to walk a straight line, or else. The rules, which everybody knows, are that you must take exactly one step, either to the right or to the left, with every tick of Joe's watch. Also, you must stand at one of the following eight places of a number line: {0,1,2,3,4,5,6,7}. Thus, your Hamiltonian H looks like this:
| H = g |
|
The red numbers in the matrix H are not matrix entries; they just label the rows and columns with the names of the places you can stand on. Empty cells in the matrix H represent 0 entries. The blue 1 entries are needed iff you can walk back and forth between states 0 and 7. g is a real number. Your evolution operator is exp(-itH), where i2= -1 and t is the time according to Joe's watch.
Your job, intrepid QC programmer, is to express exp(-itH) as a sequence of elementary operations (such as CNOTs and single-qubit rotations). You may do this approximately (using Trotter's trick) or exactly (or both, if you are a demigod programmer). How does the number of elementary operations scale with the dimension of H?