The problem Hamiltonian of the adiabatic quantum algorithm for the maximum-weight independent set problem (MIS) that is based on the reduction to the Ising problem (as described in [Choi08]) has flexible parameters. We show that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS on CK graphs, we can prevent the first order quantum phase transition and significantly change the minimum spectral gap. We raise the basic question about what the appropriate formulation of adiabatic running time should be. We also describe adiabatic quantum algorithms for Exact Cover and 3SAT in which the problem Hamiltonians are based on the reduction to MIS. We point out that the argument in Altshuler et al.(arXiv:0908.2782 [quant-ph]) that their adiabatic quantum algorithm failed with high probability for randomly generated instances of Exact Cover does not carry over to this new algorithm.
The problem Hamiltonian of the adiabatic quantum algorithm for the maximum-weight independent set problem (MIS) that is based on the reduction to the Ising problem (as described in [Choi08]) has flexible parameters. We show that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS on CK graphs, we can prevent the first order quantum phase transition and significantly change the minimum spectral gap. We raise the basic question about what the appropriate formulation of adiabatic running time should be. We also describe adiabatic quantum algorithms for Exact Cover and 3SAT in which the problem Hamiltonians are based on the reduction to MIS. We point out that the argument in Altshuler et al.(arXiv:0908.2782 [quant-ph]) that their adiabatic quantum algorithm failed with high probability for randomly generated instances of Exact Cover does not carry over to this new algorithm.
The problem Hamiltonian of the adiabatic quantum algorithm for the maximum-weight independent set problem (MIS) that is based on the reduction to the Ising problem (as described in [Choi08]) has flexible parameters. We show that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS on CK graphs, we can prevent the first order quantum phase transition and significantly change the minimum spectral gap. We raise the basic question about what the appropriate formulation of adiabatic running time should be. We also describe adiabatic quantum algorithms for Exact Cover and 3SAT in which the problem Hamiltonians are based on the reduction to MIS. We point out that the argument in Altshuler et al.(arXiv:0908.2782 [quant-ph]) that their adiabatic quantum algorithm failed with high probability for randomly generated instances of Exact Cover does not carry over to this new algorithm.
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.
One of the most important questions in studying quantum computation is: whether a quantum computer can solve NP-complete problems more efficiently than a classical computer? In 2000, Farhi, et al. (Science, 292(5516):472--476, 2001) proposed the adiabatic quantum optimization (AQO), a paradigm that directly attacks NP-hard optimization problems. How powerful is AQO? Early on, van Dam and Vazirani claimed that AQO failed (i.e. would take exponential time) for a family of 3SAT instances they constructed. More recently, Altshuler, et al. (Proc Natl Acad Sci USA, 107(28): 12446--12450, 2010) claimed that AQO failed also for random instances of the NP-complete Exact Cover problem. In this paper, we make clear that all these negative results are only for a specific AQO algorithm. We do so by demonstrating different AQO algorithms for the same problem for which their arguments no longer hold. Whether AQO fails or succeeds for solving the NP-complete problems (either the worst case or the average case) requires further investigation. Our AQO algorithms for Exact Cover and 3SAT are based on the polynomial reductions to the NP-complete Maximum-weight Independent Set (MIS) problem.
One of the most important questions in studying quantum computation is: whether a quantum computer can solve NP-complete problems more efficiently than a classical computer? In 2000, Farhi, et al. (Science, 292(5516):472--476, 2001) proposed the adiabatic quantum optimization (AQO), a paradigm that directly attacks NP-hard optimization problems. How powerful is AQO? Early on, van-Dam and Vazirani claimed that AQO failed (i.e. would take exponential time) for a family of 3SAT instances they constructed. More recently, Altshuler, et al. (Proc Natl Acad Sci USA, 107(28): 12446--12450, 2010) claimed that AQO failed also for random instances of the NP-complete Exact Cover problem. In this paper, we make clear that all these negative results are only for a specific AQO algorithm. We do so by demonstrating different AQO algorithms for the same problem for which their arguments no longer hold. Whether AQO fails or succeeds for solving the NP-complete problems (either the worst case or the average case) requires further investigation. Our AQO algorithms for Exact Cover and 3SAT are based on the polynomial reductions to the NP-complete Maximum-weight Independent Set (MIS) problem.
We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all consistent with two disparate planted solutions and then penalizing one of them with a single additional clause. We argue that by randomly modifying the beginning Hamiltonian, one obtains (with substantial probability) an adiabatic path that removes this difficulty. This suggests that the quantum adiabatic algorithm should in general be run on each instance with many different random paths leading to the problem Hamiltonian. We do not know whether this trick will help for a random instance of 3SAT (as opposed to an instance from the particular set we consider), especially if the instance has an exponential number of disparate assignments that violate few clauses. We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way to numerically investigate the ground state as well as the first excited state of our system. Our arguments are supplemented by Quantum Monte Carlo data from simulations with up to 150 spins.
We present a quantum adiabatic algorithm for solving MIS with Rydberg atoms, which uses graph degrees to engineer the Hamiltonian for adiabatic evolution. Our approach extends the algorithm of Pichler et al. for MIS state preparation, which uses time-dependent global controls to excite atoms while the Rydberg blockade mechanism suppresses adjacent excitations. To accelerate adiabatic evolution, we introduce local light shifts that favor excitation of low-degree nodes and constrain the final Hamiltonian so that energy scales inversely with the number of Rydberg excitations, preventing convergence to non-MIS states. Benchmarking our degree-dependent MIS algorithm with the traditional adiabatic algorithm on a set of 1000 MIS instances, we demonstrate numerically that our algorithm inflates the minimal spectral gap and, consequently, accelerates the convergence. By fitting power-law relations for both the time-to-solution and success probability metrics as a function of the hardness parameter, we demonstrate a superior scaling exponent for our algorithm over the traditional global protocol. Furthermore, the classical Hamiltonian engineering step required to construct degree-dependent controls introduces only polynomial overhead. These results indicate that our algorithm can be used to extend the size of graphs for which MIS can be found on physical hardware. Moreover, our approach extends beyond MIS to additional graph problems such as MAX-CUT.