D.R. Mitchell presented a clever way of solving the NP-complete 3-SAT
problem by reducing it to determining the geometric (or Berry) phase
acquired by a ground eigenvector transported about a loop in a
specially structured, continuous, parameterized Hermitian matrix
space(See [1].) Unfortunately, as the loop is traversed, the ground
eigenvalue on the loop narrowly avoids collision with excited
eigenvalues. At these points, the ground eigenvector must be
transported "exponentially slowly" to avoid jumping and spoiling
the computation - so only a polynomial speedup results.
So I pose this general question:
Are there matrix spaces where an eigenvalue gap condition
can be enforced throughout the entire loop traversal?
For example, most d-regular graphs are good expanders, i.e., the gap
between the largest eigenvalue 'd' and the second largest eigenvalue
of the the adjacency graph is large.
One continuous analog is the space of symmetric, doubly stochastic
non-negative matrices.
Can we transport the unique maximal/Perron eigenvector(eigenvalue 1)
around loops in this space with the gap remaining large?
Unless I am mistaken, quite general problems can be recast into
this form, so I surmise that near collisions with the maximal/Perron
eigenvalue are unavoidable, but I can't prove it.
I would appreciate any help or suggestions.
Thanks,
Lou Pagnucco
[1]"Geometric Phase Based Quantum Computation Applied to an
NP-Complete Problem"
http://xxx.lanl.gov/PS_cache/quant-ph/pdf/0508/0508177v1.pdf
.
|
