اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدQuantum search for unknown number of target items hybridizing the fixed-point method with the trail-and-error method
50
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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, 210501 (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.
قيم البحث
اقرأ أيضاً
We consider a database separated into blocks. Blocks containing target items are called target blocks. Blocks without target items are called non-target blocks. We consider a case, when each target block has the same number of target items. We presen
t a fast quantum algorithm, which finds one of the target blocks. Our algorithm is based on Grover-Radhakrishnan algorithm of partial search. We minimize the number of queries to the oracle.
Grovers algorithm achieves a quadratic speedup over classical algorithms, but it is considered necessary to know the value of $lambda$ exactly [Phys. Rev. Lett. 95, 150501 (2005); Phys. Rev. Lett. 113, 210501 (2014)], where $lambda$ is the fraction o
f target items in the database. In this paper, we find out that the Grover algorithm can actually apply to the case where one can identify the range that $lambda$ belongs to from a given series of disjoint ranges. However, Grovers algorithm still cannot maintain high success probability when there exist multiple target items. For this problem, we proposed a complementary-multiphase quantum search algorithm, %with general iterations, in which multiple phases complement each other so that the overall high success probability can be maintained. Compared to the existing algorithms, in the case defined above, for the first time our algorithm achieves the following three goals simultaneously: (1) the success probability can be no less than any given value between 0 and 1, (2) the algorithm is applicable to the entire range of $lambda$, and (3) the number of iterations is almost the same as that of Grovers algorithm. Especially compared to the optimal fixed-point algorithm [Phys. Rev. Lett. 113, 210501 (2014)], our algorithm uses fewer iterations to achieve success probability greater than 82.71%, e.g., when the minimum success probability is required to be 99.25%, the number of iterations can be reduced by 50%.
In [Phys. Rev. Lett. 113, 210501 (2014)], to achieve the optimal fixed-point quantum search in the case of unknown fraction (denoted by $lambda$) of target items, the analytical multiphase matching (AMPM) condition has been proposed. In this paper, w
e find out that the AMPM condition can also be used to design the exact quantum search algorithm in the case of known $lambda$, and the minimum number of iterations reaches the optimal level of existing exact algorithms. Experiments are performed to demonstrate the proposed algorithm on IBMs quantum computer. In addition, we theoretically find two coincidental phases with equal absolute value in our algorithm based on the AMPM condition and that algorithm based on single-phase matching. Our work confirms the practicability of the AMPM condition in the case of known $lambda$, and is helpful to understand the mechanism of this condition.
The existing decoy-state quantum key distribution (QKD) beating photon-number-splitting (PNS) attack provides a more accurate method to estimate secure key rate, while it still considers that only single-photon pulses can generate secure keys in any
case. However, multiphoton pulses can also generate secure keys if we can confirm that there is no attack. In this paper, under the null hypothesis of no PNS attack, we first determine whether there is an attack or not by retrieving the missing information of the existing decoy-state protocols, extract a Cauchy distribution statistic, and further provide a detection method and the Type I error probability. If the result is judged to be an attack, we can use the existing decoy-state method and the GLLP formula to estimate secure key rate. Otherwise, all pulses received including both single-photon pulses and multiphoton pulses, can be used to generate the keys and we give the secure key rate in this case. Finally, the associated experiments we performed (i.e., the significance level is $5%$) show the correctness of our method.
In the treatment plan optimization for intensity modulated radiation therapy (IMRT), dose-deposition coefficient (DDC) matrix is often pre-computed to parameterize the dose contribution to each voxel in the volume of interest from each beamlet of uni
t intensity. However, due to the limitation of computer memory and the requirement on computational efficiency, in practice matrix elements of small values are usually truncated, which inevitably compromises the quality of the resulting plan. A fixed-point iteration scheme has been applied in IMRT optimization to solve this problem, which has been reported to be effective and efficient based on the observations of the numerical experiments. In this paper, we aim to point out the mathematics behind this scheme and to answer the following three questions: 1) whether the fixed-point iteration algorithm converges or not? 2) when it converges, whether the fixed point solution is same as the original solution obtained with the complete DDC matrix? 3) if not the same, whether the fixed point solution is more accurate than the naive solution of the truncated problem obtained without the fixed-point iteration? To answer these questions, we first performed mathematical analysis and deductions using a simplified fluence map optimization (FMO) model. Then we conducted numerical experiments on a head-and-neck patient case using both the simplified and the original FMO model. Both our mathematical analysis and numerical experiments demonstrate that with proper DDC matrix truncation, the fixed-point iteration can converge. Even though the converged solution is not the one that we obtain with the complete DDC matrix, the fixed-point iteration scheme could significantly improve the plan accuracy compared with the solution to the truncated problem obtained without the fixed-point iteration.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
