Quantum Adiabatic Algorithm and Large Spin Tunnelling

Abstract

We provide a theoretical study of the quantum adiabatic evolution algorithm with different evolution paths proposed in [E. Farhi, et al., arXiv:quant-ph/0208135]. The algorithm is applied to a random binary optimization problem (a version of the 3-Satisfiability problem) where the n-bit cost function is symmetric with respect to the permutation of individual bits. The evolution paths are produced, using the generic control Hamiltonians H(τ) that preserve the bit symmetry of the underlying optimization problem. In the case where the ground state of H(0) coincides with the totally-symmetric state of an n-qubit system the algorithm dynamics is completely described in terms of the motion of a spin-n/2. We show that different control Hamiltonians can be parameterized by a set of independent parameters that are expansion coefficients of H(τ) in a certain universal set of operators. Only one of these operators can be responsible for avoiding the tunnelling in the spin-n/2 system during the quantum adiabatic algorithm. We show that it is possible to select a coefficient for this operator that guarantees a polynomial complexity of the algorithm for all problem instances. 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.

27 pages, 3 figures

References in corpus (11)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Strengths and Weaknesses of Quantum Computing
• Quantum Computation by Adiabatic Evolution
• Statistical mechanics of the random K-SAT model
• The Entropy of the K-Satisfiability Problem
• First- and Second-Order Transitions between Quantum and Classical Regimes for the Escape Rate of a Spin System
• Tunable Quantum Tunneling of Magnetic Domain Walls
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• The Semiclassical Propagator for Spin Coherent States
• Quantum Adiabatic Evolution Algorithms with Different Paths
• A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability

Cited by in corpus (12)

• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Adiabatic Quantum Computation in Open Systems
• Cavity method for quantum spin glasses on the Bethe lattice
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Mean Field Analysis of Quantum Annealing Correction
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
• Quantum adiabatic optimization and combinatorial landscapes
• Probing nonlinear adiabatic paths with a universal integrator
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Quantum Adiabatic Computation and the Travelling Salesman Problem