اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHow Quantum is the Speedup in Adiabatic Unstructured Search?
124
0
0.0
(
0
)
تأليف
Itay Hen
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 propose a method to speed up the quantum adiabatic algorithm using catalysis by many-body delocalization. This is applied to random-field antiferromagnetic Ising spin models. The algorithm is catalyzed in such a way that the evolution approximates
a Heisenberg model in the middle of its course, and the model is in a delocalized phase. We show numerically that we can speed up the standard algorithm for finding the ground state of the random-field Ising model using this idea. We also demonstrate that the speedup is due to gap amplification, even though the underlying model is not frustration-free. The crossover to speedup occurs at roughly the value of the interaction which is known to be the critical one for the delocalization transition. We also calculate the participation ratio and entanglement entropy as a function of time: their time dependencies indicate that the system is exploring more states and that they are more entangled than when there is no catalyst. Together, all these pieces of evidence demonstrate that the speedup is related to delocalization. Even though only relatively small systems can be investigated, the evidence suggests that the scaling of the method with system size is favorable. Our method is illustrated by experimental results from a small online IBM quantum computer, showing how to verify the method in future as such machines improve. The cost of the catalytic method compared to the standard algorithm is only a constant factor.
The quantum adiabatic theorem states that if a quantum system starts in an eigenstate of the Hamiltonian, and this Hamiltonian varies sufficiently slowly, the system stays in this eigenstate. We investigate experimentally the conditions that must be
fulfilled for this theorem to hold. We show that the traditional adiabatic condition as well as some conditions that were recently suggested are either not sufficient or not necessary. Experimental evidence is presented by a simple experiment using nuclear spins.
The quantum complexity of a unitary operator measures the difficulty of its construction from a set of elementary quantum gates. While the notion of quantum complexity was first introduced as a quantum generalization of the classical computational co
mplexity, it has since been argued to hold a fundamental significance in its own right, as a physical quantity analogous to the thermodynamic entropy. In this paper, we present a unified perspective on various notions of quantum complexity, viewed as functions on the space of unitary operators. One striking feature of these functions is that they can exhibit non-smooth and even fractal behaviour. We use ideas from Diophantine approximation theory and sub-Riemannian geometry to rigorously quantify this lack of smoothness. Implications for the physical meaning of quantum complexity are discussed.
Nonlinear variants of quantum mechanics can solve tasks that are impossible in standard quantum theory, such as perfectly distinguishing nonorthogonal states. Here we derive the optimal protocol for distinguishing two states of a qubit using the Gros
s-Pitaevskii equation, a model of nonlinear quantum mechanics that arises as an effective description of Bose-Einstein condensates. Using this protocol, we present an algorithm for unstructured search in the Gross-Pitaevskii model, obtaining an exponential improvement over a previous algorithm of Meyer and Wong. This result establishes a limitation on the effectiveness of the Gross-Pitaevskii approximation. More generally, we demonstrate similar behavior under a family of related nonlinearities, giving evidence that the ability to quickly discriminate nonorthogonal states and thereby solve unstructured search is a generic feature of nonlinear quantum mechanics.
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 an
d numerical simulation. The results show it provides a better speedup than the previous adiabatic search algorithm.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
