Physics – Quantum Physics
Scientific paper
2010-10-06
Physics
Quantum Physics
This is part of the article arXiv:quant-ph/1004.2226
Scientific paper
In Amin and Choi \cite{AC09}, we show that an adiabatic quantum algorithm for the NP-hard maximum independent set (MIS) problem on a set of special family of graphs in which there are exponentially many local maxima would have the exponentially small minimum spectral gap and thus would require the exponential time, due to the first order quantum phase transition (FQPT). The problem Hamiltonian of the adiabatic quantum algorithm for MIS is based on the reduction to the Ising problem and has flexible parameters. In this paper, we show numerically on the 15-vertex graph that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS, we can prevent the FQPT and drastically increase the minimum spectral gap. The result is further supported by visualization from the Decomposed State Evolution Visualization (\desev) --- a visualization tool we introduced. Furthermore, our result also serves to concretely clarify that it is not sufficient to consider one specific problem Hamiltonian for proving the failure of adiabatic quantum optimization for a problem. We also raise the basic question about what the appropriate formulation of adiabatic running time should be.
No associations
LandOfFree
Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians 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 Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-428407