Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userElimination of Perturbative Crossings in Adiabatic Quantum Optimization
113
0
0.0
(
0
)
Authors
Neil G. Dickson
Ask ChatGPT about the research
No Arabic abstract
It was recently shown that, for solving NP-complete problems, adiabatic paths always exist without finite-order perturbative crossings between local and global minima, which could lead to anticrossings with exponentially small energy gaps if present. However, it was not shown whether such a path could be found easily. Here, we give a simple construction that deterministically eliminates all such anticrossings in polynomial time, space, and energy, for any Ising models with polynomial final gap. Thus, in order for adiabatic quantum optimization to require exponential time to solve any NP-complete problem, some quality other than this type of anticrossing must be unavoidable and necessitate exponentially long runtimes.
rate research
Read More
We consider a physical system with a coupling to bosonic reservoirs via a quantum stochastic differential equation. We study the limit of this model as the coupling strength tends to infinity. We show that in this limit the solution to the quantum stochastic differential equation converges strongly to the solution of a limit quantum stochastic differential equation. In the limiting dynamics the excited states are removed and the ground states couple directly to the reservoirs.
We consider a composite open quantum system consisting of a fast subsystem coupled to a slow one. Using the time-scale separation, we develop an adiabatic elimination technique to derive at any order the reduced model describing the slow subsystem. The method, based on an asymptotic expansion and geometric singular perturbation theory, ensures the physical interpretation of the reduced second-order model by giving the reduced dynamics in a Lindblad form and the state reduction in Kraus map form. We give explicit second-order formulas for Hamiltonian or cascade coupling between the two subsystems. These formulas can be used to engineer, via a careful choice of the fast subsystem, the Hamiltonian and Lindbald operators governing the dissipative dynamics of the slow subsystem.
We propose a protocol for quantum adiabatic optimization, whereby an intermediary Hamiltonian that is diagonal in the computational basis is turned on and off during the interpolation. This `diagonal catalyst serves to bias the energy landscape towards a given spin configuration, and we show how this can remove the first-order phase transition present in the standard protocol for the ferromagnetic $p$-spin and the Weak-Strong Cluster problems. The success of the protocol also makes clear how it can fail: biasing the energy landscape towards a state only helps in finding the ground state if the Hamming distance from the ground state and the energy of the biased state are correlated. We present examples where biasing towards low energy states that are nonetheless very far in Hamming distance from the ground state can severely worsen the efficiency of the algorithm compared to the standard protocol. Our results for the diagonal catalyst protocol are analogous to results exhibited by adiabatic reverse annealing, so our conclusions should apply to that protocol as well.
We restate the adiabatic elimination approximation as the first term in a singular perturbation expansion. We use the invariant manifold formalism for singular perturbations in dynamical systems to identify systematic improvements on adiabatic elimination, connecting with well established quantum mechanical perturbation methods. We prove convergence of the expansions when energy scales are well separated. We state and solve the problem of hermiticity of improved effective hamiltonians.
We consider an open quantum system described by a Lindblad-type master equation with two times-scales. The fast time-scale is strongly dissipative and drives the system towards a low-dimensional decoherence-free space. To perform the adiabatic elimination of this fast relaxation, we propose a geometric asymptotic expansion based on the small positive parameter describing the time-scale separation. This expansion exploits geometric singular perturbation theory and center-manifold techniques. We conjecture that, at any order, it provides an effective slow Lindblad master equation and a completely positive parameterization of the slow invariant sub-manifold associated to the low-dimensional decoherence-free space. By preserving complete positivity and trace, two important structural properties attached to open quantum dynamics, we obtain a reduced-order model that directly conveys a physical interpretation since it relies on effective Lindbladian descriptions of the slow evolution. At the first order, we derive simple formulae for the effective Lindblad master equation. For a specific type of fast dissipation, we show how any Hamiltonian perturbation yields Lindbladian second-order corrections to the first-order slow evolution governed by the Zeno-Hamiltonian. These results are illustrated on a composite system made of a strongly dissipative harmonic oscillator, the ancilla, weakly coupled to another quantum system.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
