Not a lot to go on here, from a numerical point of view. But fitting (1/sqrt2)^(n+2) x (poly in n) seems to give reasonably consistent results, something like poly = 1.000 + 0.094 n - 0.0052 n^2 - 0.0007 n^3 + 0.00013 n^4 ... Apart from the first coefficient, it's hard to say whether these might actually be simple rationals. WFL On 2/9/07, Mike Stay <mike@math.ucr.edu> wrote:

0.38490017945975 0.29101243968677 0.21666469449485 0.15928582101343 0.11593604442994 0.08373599185262 0.06012913678590 0.04299237598573

This is the magnitude of the nonzero entries in log(G_n)/(i pi), where G_n is the unitary matrix implementing Grover's algorithm for an n-qubit quantum computer. More specifically,

T_1 = |1 1| / sqrt(2) |1 -1|

T_n = T_1 tensor T_{n-1}

S_{n,k} = the 2^n x 2^n identity matrix except entry (k,k)=-1

Grover's algorithm is then G_n = T_n S_{n,1} T_n S_{n,m} where m is the marked state.

They decrease roughly like sqrt(2) at each step, but not exactly. Does anyone know how I could figure out a closed form for the terms, or a reference if someone else already has? -- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun