We study the quantum adiabatic evolution algorithm with different evolution paths that correspond to different control Hamiltonians $H(\ensuremath{\tau})$ sampled from a random ensemble. The algorithm is applied to a random binary optimization problem where the cost function is symmetric with respect to the permutation of individual bits. We investigate the method proposed by Farhi et al. when different evolution paths preserve the bit symmetry of the control Hamiltonians $H(\ensuremath{\tau})$ and are generated by an ensemble of random $8\ifmmode\times\else\texttimes\fi{}8$ matrices. In this case, the algorithm dynamics is completely described in terms of the motion of a spin-n/2 system. We show that different evolution paths can be parametrized by a small number of independent parameters that are expansion coefficients of $H(\ensuremath{\tau})$ in a certain universal set of operators. One of these operators is responsible for avoiding the tunnelling for the spin-n/2 system and the corresponding coefficient determines the algorithm complexity for a given problem instance. We show that any problem instance can be solved in polynomial time by applying one of the two universal path modifications (due to the possible reflection symmetry of the problem). We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin $n/2$ and provide a complete characterization of such paths.We study the quantum adiabatic evolution algorithm with different evolution paths that correspond to different control Hamiltonians $H(\ensuremath{\tau})$ sampled from a random ensemble. The algorithm is applied to a random binary optimization problem where the cost function is symmetric with respect to the permutation of individual bits. We investigate the method proposed by Farhi et al. when different evolution paths preserve the bit symmetry of the control Hamiltonians $H(\ensuremath{\tau})$ and are generated by an ensemble of random $8\ifmmode\times\else\texttimes\fi{}8$ matrices. In this case, the algorithm dynamics is completely described in terms of the motion of a spin-n/2 system. We show that different evolution paths can be parametrized by a small number of independent parameters that are expansion coefficients of $H(\ensuremath{\tau})$ in a certain universal set of operators. One of these operators is responsible for avoiding the tunnelling for the spin-n/2 system and the corresponding coefficient determines the algorithm complexity for a given problem instance. We show that any problem instance can be solved in polynomial time by applying one of the two universal path modifications (due to the possible reflection symmetry of the problem). We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin $n/2$ and provide a complete characterization of such paths.

arXiv:quant-ph/0309150Physical Review ADec 24, 200315 citations

Progress in the quantum Adiabatic algorithm

Edward Farhi

APSMar 1, 20151 citation

Total suppression of a large spin tunneling barrier in quantum adiabatic computation

Alex Bulatov, Vadim Smelyanskiy

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).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).

arXiv:quant-ph/0208189Aug 29, 20022 citations

n/2

and provide a complete characterization of such paths.