(by R.R. Tucci, June 2007)
Okay, suppose you didn't do so hot on the previous puzzler, and now Joe Pesci is looking for you. You decide to lie low and stay put, until Joe cools off on Sunday, when he goes to visit his mama. Suppose there are 8 possible hideouts called {0,1,2,3,4,5,6,7} that you can occupy. ak is your pulse rate in hideout k. The more scared you are in hideout k, the higher ak is. (If your hideout is a physics colloquium, your pulse rate is normal, even relaxed, because you know Joe thinks physics is for queers, so he would never be found there. If the hideout is a restaurant that likes playing the Tarantella as background music, then your pulse rate is through the roof.) Your Hamiltonian H looks like this:
| H = |
|
The red numbers in the matrix H are not matrix entries; they just label the rows and columns with the hideout names. Empty cells in the matrix H represent 0 entries. 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?