اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدConvergence properties of fixed-point search with general but equal phase shifts for any iterations
296
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Grover presented the fixed-point search by replacing the selective
قيم البحث
اقرأ أيضاً
We estimate convergence rates for fixed-point iterations of a class of nonlinear operators which are partially motivated from solving convex optimization problems. We introduce the notion of the generalized averaged nonexpansive (GAN) operator with a
positive exponent, and provide a convergence rate analysis of the fixed-point iteration of the GAN operator. The proposed generalized averaged nonexpansiveness is weaker than the averaged nonexpansiveness while stronger than nonexpansiveness. We show that the fixed-point iteration of a GAN operator with a positive exponent converges to its fixed-point and estimate the local convergence rate (the convergence rate in terms of the distance between consecutive iterates) according to the range of the exponent. We prove that the fixed-point iteration of a GAN operator with a positive exponent strictly smaller than 1 can achieve an exponential global convergence rate (the convergence rate in terms of the distance between an iterate and the solution). Furthermore, we establish the global convergence rate of the fixed-point iteration of a GAN operator, depending on both the exponent of generalized averaged nonexpansiveness and the exponent of the H$ddot{text{o}}$lder regularity, if the GAN operator is also H$ddot{text{o}}$lder regular. We then apply the established theory to three types of convex optimization problems that appear often in data science to design fixed-point iterative algorithms for solving these optimization problems and to analyze their convergence properties.
We present a self-contained analysis of a particular family of metrics over the set of non-negative integers. We show that these metrics, which are defined through a nested sequence of optimal transport problems, provide tight estimates for general K
rasnoselskii-Mann fixed point iterations for non-expansive maps. We also describe some of their very special properties, including their monotonicity and the so-called convex quadrangle inequality that yields a greedy algorithm to compute them efficiently.
This paper investigates optimal error bounds and convergence rates for general Mann iterations for computing fixed-points of non-expansive maps in normed spaces. We look for iterations that achieve the smallest fixed-point residual after $n$ steps, b
y minimizing a worst-case bound $|x^n-Tx^n|le R_n$ derived from a nested family of optimal transport problems. We prove that this bound is tight so that minimizing $R_n$ yields optimal iterations. Inspired from numerical results we identify iterations that attain the rate $R_n=O(1/n)$, which we also show to be the best possible. In particular, we prove that the classical Halpern iteration achieves this optimal rate for several alternative stepsizes, and we determine analytically the optimal stepsizes that attain the smallest worst-case residuals at every step $n$, with a tight bound $R_napproxfrac{4}{n+4}$. We also determine the optimal Halpern stepsizes for affine nonexpansive maps, for which we get exactly $R_n=frac{1}{n+1}$. Finally, we show that the best rate for the classical Krasnoselskiu{i}-Mann iteration is $Omega(1/sqrt{n})$, and we present numerical evidence suggesting that even after introducing inertial terms one cannot reach the faster rate $O(1/n)$.
For the unsorted database quantum search with the unknown fraction $lambda$ of target items, there are mainly two kinds of methods, i.e., fixed-point or trail-and-error. (i) In terms of the fixed-point method, Yoder et al. [Phys. Rev. Lett. 113, 2105
01 (2014)] claimed that the quadratic speedup over classical algorithms has been achieved. However, in this paper, we point out that this is not the case, because the query complexity of Yoders algorithm is actually in $O(1/sqrt{lambda_0})$ rather than $O(1/sqrt{lambda})$, where $lambda_0$ is a known lower bound of $lambda$. (ii) In terms of the trail-and-error method, currently the algorithm without randomness has to take more than 1 times queries or iterations than the algorithm with randomly selected parameters. For the above problems, we provide the first hybrid quantum search algorithm based on the fixed-point and trail-and-error methods, where the matched multiphase Grover operations are trialed multiple times and the number of iterations increases exponentially along with the number of trials. The upper bound of expected queries as well as the optimal parameters are derived. Compared with Yoders algorithm, the query complexity of our algorithm indeed achieves the optimal scaling in $lambda$ for quantum search, which reconfirms the practicality of the fixed-point method. In addition, our algorithm also does not contain randomness, and compared with the existing deterministic algorithm, the query complexity can be reduced by about 1/3. Our work provides an new idea for the research on fixed-point and trial-and-error quantum search.
Within the framework of generalized noncontextuality, we introduce a general technique for systematically deriving noncontextuality inequalities for any experiment involving finitely many preparations and finitely many measurements, each of which has
a finite number of outcomes. Given any fixed sets of operational equivalences among the preparations and among the measurements as input, the algorithm returns a set of noncontextuality inequalities whose satisfaction is necessary and sufficient for a set of operational data to admit of a noncontextual model. Additionally, we show that the space of noncontextual data tables always defines a polytope. Finally, we provide a computationally efficient means for testing whether any set of numerical data admits of a noncontextual model, with respect to any fixed operational equivalences. Together, these techniques provide complete methods for characterizing arbitrary noncontextuality scenarios, both in theory and in practice. Because a quantum prepare-and-measure experiment admits of a noncontextual model if and only if it admits of a positive quasiprobability representation, our techniques also determine the necessary and sufficient conditions for the existence of such a representation.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
