اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدQuantum Partial Search of a Database with Several Target Items
45
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 present 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%.
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.
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.
Partial search has been proposed recently for finding the target block containing a target element with fewer queries than the full Grover search algorithm which can locate the target precisely. Since such partial searches will likely be used as subr
outines for larger algorithms their success rate is important. We propose a partial search algorithm which achieves success with unit probability.
Item-based collaborative filtering (ICF) has been widely used in industrial applications such as recommender system and online advertising. It models users preference on target items by the items they have interacted with. Recent models use methods s
uch as attention mechanism and deep neural network to learn the user representation and scoring function more accurately. However, despite their effectiveness, such models still overlook a problem that performance of ICF methods heavily depends on the quality of item representation especially the target item representation. In fact, due to the long-tail distribution in the recommendation, most item embeddings can not represent the semantics of items accurately and thus degrade the performance of current ICF methods. In this paper, we propose an enhanced representation of the target item which distills relevant information from the co-occurrence items. We design sampling strategies to sample fix number of co-occurrence items for the sake of noise reduction and computational cost. Considering the different importance of sampled items to the target item, we apply attention mechanism to selectively adopt the semantic information of the sampled items. Our proposed Co-occurrence based Enhanced Representation model (CER) learns the scoring function by a deep neural network with the attentive user representation and fusion of raw representation and enhanced representation of target item as input. With the enhanced representation, CER has stronger representation power for the tail items compared to the state-of-the-art ICF methods. Extensive experiments on two public benchmarks demonstrate the effectiveness of CER.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
