The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
arXiv:1910.02985 · doi:10.1007/s11128-020-2582-1
Abstract
We study the relation between the Ising problem Hamiltonian parameters and the minimum spectral gap (min-gap) of the system Hamiltonian in the Ising-based quantum annealer. The main argument we use in this paper to assess the performance of a QA algorithm is the presence or absence of an anti-crossing during quantum evolution. For this purpose, we introduce a new parametrization definition of the anti-crossing. Using the Maximum-weighted Independent Set (MIS) problem in which there are flexible parameters (energy penalties J between pairs of edges) in an Ising formulation as the model problem, we construct examples to show that by changing the value of J, we can change the quantum evolution from one that has an anti-crossing (that results in an exponential small min-gap) to one that does not have, or the other way around, and thus drastically change (increase or decrease) the min-gap. However, we also show that by changing the value of alone, one can not avoid the anti-crossing. We recall a polynomial reduction from an Ising problem to an MIS problem to show that the flexibility of changing parameters without changing the problem to be solved can be applied to any Ising problem. As an example, we show that by such a reduction alone, it is possible to remove the anti-crossing and thus increase the min-gap. Our anti-crossing definition is necessarily scaling invariant as scaling the problem Hamiltonian does not change the nature (i.e. presence or absence) of an anti-crossing. As a side note, we show exactly how the min-gap is scaled if we scale the problem Hamiltonian by a constant factor.
arXiv comment25 pages, 15 figures
References in corpus (12)
- Adiabatic Quantum Computing
- Anderson localization casts clouds over adiabatic quantum optimization
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
- Adiabatic optimization versus diffusion Monte Carlo
- Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems
- Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
- Pechukas-Yukawa formalism for Landau-Zener transitions in the presence of external noise
Cited by in corpus (11)
- Improved Boltzmann machines with error corrected quantum annealing
- Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
- Ferromagnetically shifting the power of pausing
- Advantage of pausing: parameter setting for quantum annealers
- Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
- Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
- Anti-crossings and spectral gap during quantum adiabatic evolution
- Quantum computing and the stable set problem
- Path Matters: Industrial Data Meet Quantum Optimization
- Fighting Exponentially Small Gaps by Counterdiabatic Driving
- Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing