Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAccuracy vs run time in adiabatic quantum search
89
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Adiabatic quantum algorithms are characterized by their run time and accuracy. The relation between the two is essential for quantifying adiabatic algorithmic performance, yet is often poorly understood. We study the dynamics of a continuous time, adiabatic quantum search algorithm, and find rigorous results relating the accuracy and the run time. Proceeding with estimates, we show that under fairly general circumstances the adiabatic algorithmic error exhibits a behavior with two discernible regimes: the error decreases exponentially for short times, then decreases polynomially for longer times. We show that the well known quadratic speedup over classical search is associated only with the exponential error regime. We illustrate the results through examples of evolution paths derived by minimization of the adiabatic error. We also discuss specific strategies for controlling the adiabatic error and run time.
rate research
Read More
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.
In classical computing, analog approaches have sometimes appeared to be more powerful than they really are. This occurs when resources, particularly precision, are not appropriately taken into account. While the same should also hold for analog quantum computing, precision issues are often neglected from the analysis. In this work we present a classical analog algorithm for unstructured search that can be viewed as analogous to the quantum adiabatic unstructured search algorithm devised by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. We show that similarly to its quantum counterpart, the classical construction may also provide a quadratic speedup over standard digital unstructured search. We discuss the meaning and the possible implications of this result in the context of adiabatic quantum computing.
We derive a version of the adiabatic theorem that is especially suited for applications in adiabatic quantum computation, where it is reasonable to assume that the adiabatic interpolation between the initial and final Hamiltonians is controllable. Assuming that the Hamiltonian is analytic in a finite strip around the real time axis, that some number of its time-derivatives vanish at the initial and final times, and that the target adiabatic eigenstate is non-degenerate and separated by a gap from the rest of the spectrum, we show that one can obtain an error between the final adiabatic eigenstate and the actual time-evolved state which is exponentially small in the evolution time, where this time itself scales as the square of the norm of the time-derivative of the Hamiltonian, divided by the cube of the minimal gap.
We study the adiabatic-impulse approximation (AIA) as a tool to approximate the time evolution of quantum states, when driven through a region of small gap. The AIA originates from the Kibble-Zurek theory applied to continuous quantum phase transitions. The Kibble-Zurek mechanism was developed to predict the power-law scaling of the defect density across a continuous quantum phase transition. Instead here, we quantify the accuracy of the AIA via the trace norm distance with respect to the exact evolved state. As expected, we find that for short times/fast protocols, the AIA outperforms the simple adiabatic approximation. However, for large times/slow protocols, the situation is actually reversed and the AIA provides a worse approximation. Nevertheless, we found a variation of the AIA that can perform better than the adiabatic one. This counter-intuitive modification consists in crossing twice the region of small gap. Our findings are illustrated by several examples of driven closed and open quantum systems.
We study the short-time evolution of the bipartite entanglement in quantum lattice systems with local interactions in terms of the purity of the reduced density matrix. A lower bound for the purity is derived in terms of the eigenvalue spread of the interaction Hamiltonian between the partitions. Starting from an initially separable state the purity decreases as $1 - (t/tau)^2$, i.e. quadratically in time, with a characteristic time scale $tau$ that is inversly proportional to the boundary size of the subsystem, i.e., as an area-law. For larger times an exponential lower bound is derived corresponding to the well-known linear-in-time bound of the entanglement entropy. The validity of the derived lower bound is illustrated by comparison to the exact dynamics of a 1D spin lattice system as well as a pair of coupled spin ladders obtained from numerical simulations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
