Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDoes Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
234
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.
rate research
Read More
Quantum fluctuations driven by non-stoquastic Hamiltonians have been conjectured to be an important and perhaps essential missing ingredient for achieving a quantum advantage with adiabatic optimization. We introduce a transformation that maps every non-stoquastic adiabatic path ending in a classical Hamiltonian to a corresponding stoquastic adiabatic path by appropriately adjusting the phase of each matrix entry in the computational basis. We compare the spectral gaps of these adiabatic paths and find both theoretically and numerically that the paths based on non-stoquastic Hamiltonians have generically smaller spectral gaps between the ground and first excited states, suggesting they are less useful than stoquastic Hamiltonians for quantum adiabatic optimization. These results apply to any adiabatic algorithm which interpolates to a final Hamiltonian that is diagonal in the computational basis.
Using the probability theory-based approach, this paper reveals the equivalence of an arbitrary NP-complete problem to a problem of checking whether a level set of a specifically constructed harmonic cost function (with all diagonal entries of its Hessian matrix equal to zero) intersects with a unit hypercube in many-dimensional Euclidean space. This connection suggests the possibility that methods of continuous mathematics can provide crucial insights into the most intriguing open questions in modern complexity theory.
We propose a new adiabatic algorithm for the unsorted database search problem. This algorithm saves two thirds of qubits than Grovers algorithm in realizations. Meanwhile, we analyze the time complexity of the algorithm by both perturbative method and numerical simulation. The results show it provides a better speedup than the previous adiabatic search algorithm.
This paper presents a logic language for expressing NP search and optimization problems. Specifically, first a language obtained by extending (positive) Datalog with intuitive and efficient constructs (namely, stratified negation, constraints and exclusive disjunction) is introduced. Next, a further restricted language only using a restricted form of disjunction to define (non-deterministically) subsets (or partitions) of relations is investigated. This language, called NP Datalog, captures the power of Datalog with unstratified negation in expressing search and optimization problems. A system prototype implementing NP Datalog is presented. The system translates NP Datalog queries into OPL programs which are executed by the ILOG OPL Development Studio. Our proposal combines easy formulation of problems, expressed by means of a declarative logic language, with the efficiency of the ILOG System. Several experiments show the effectiveness of this approach.
Adiabatic quantum computing and optimization have garnered much attention recently as possible models for achieving a quantum advantage over classical approaches to optimization and other special purpose computations. Both techniques are probabilistic in nature and the minimum gap between the ground state and first excited state of the system during evolution is a major factor in determining the success probability. In this work we investigate a strategy for increasing the minimum gap and success probability by introducing intermediate Hamiltonians that modify the evolution path between initial and final Hamiltonians. We focus on an optimization problem relevant to recent hardware implementations and present numerical evidence for the existence of a purely local intermediate Hamiltonian that achieve the optimum performance in terms of pushing the minimum gap to one of the end points of the evolution. As a part of this study we develop a convex optimization formulation of the search for optimal adiabatic schedules that makes this computation more tractable, and which may be of independent interest. We further study the effectiveness of random intermediate Hamiltonians on the minimum gap and success probability, and empirically find that random Hamiltonians have a significant probability of increasing the success probability, but only by a modest amount.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
