Physics – Quantum Physics
Scientific paper
2002-08-29
Physics
Quantum Physics
17 pages, 5 figures
Scientific paper
We apply a quantum adiabatic evolution algorithm to a combinatorial optimization problem where the cost function depends entirely on the of the number of unit bits in a n-bit string (Hamming weight). The solution of the optimization problem is encoded as a ground state of the problem Hamiltonian H_p for the z-projection of a total spin-n/2. We show that tunneling barriers for the total spin can be completely suppressed during the algorithm if the initial Hamiltonian has its ground state extended in the space of the z-projections of the spin. This suppression takes place even if the cost function has deep and well separated local minima. We provide an intuitive picture for this effect and show that it guarantees the polynomial complexity of the algorithm in a very broad class of cost functions. We suggest a simple example of the Hamiltonian for the adiabatic evolution: H(tau) = (1-tau) hat S_{x}^{2} + tau H_p, with parameter tau slowly varying in time between 0 and 1. We use WKB analysis for the large spin to estimate the minimum energy gap between the two lowest adiabatic eigenvalues of H(tau).
Bulatov Alex
Smelyanskiy Vadim
No associations
LandOfFree
Total suppression of a large spin tunneling barrier in quantum adiabatic computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Total suppression of a large spin tunneling barrier in quantum adiabatic computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Total suppression of a large spin tunneling barrier in quantum adiabatic computation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-252773