اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDeleting a marked item from an unsorted database with a single query
42
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this Letter we present a quantum deletion algorithm that deletes a marked state from an unsorted database of $N$ items with only a single query. This algorithm achieves exponential speedup compared with classical algorithm where O(N) number of query is required. General property of this deleting algorithm is also studied.
قيم البحث
اقرأ أيضاً
It is known that if we can clone an arbitrary state we can send signal faster than light. Here, we show that deletion of unknown quantum state against a copy can lead to superluminal signalling. But erasure of unknown quantum state does not imply faster than light signalling.
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.
The negative weight adversary method, $mathrm{ADV}^pm(g)$, is known to characterize the bounded-error quantum query complexity of any Boolean function $g$, and also obeys a perfect composition theorem $mathrm{ADV}^pm(f circ g^n) = mathrm{ADV}^pm(f) m
athrm{ADV}^pm(g)$. Belovs gave a modified version of the negative weight adversary method, $mathrm{ADV}_{rel}^pm(f)$, that characterizes the bounded-error quantum query complexity of a relation $f subseteq {0,1}^n times [K]$, provided the relation is efficiently verifiable. A relation is efficiently verifiable if $mathrm{ADV}^pm(f_a) = o(mathrm{ADV}_{rel}^pm(f))$ for every $a in [K]$, where $f_a$ is the Boolean function defined as $f_a(x) = 1$ if and only if $(x,a) in f$. In this note we show a perfect composition theorem for the composition of a relation $f$ with a Boolean function $g$ [ mathrm{ADV}_{rel}^pm(f circ g^n) = mathrm{ADV}_{rel}^pm(f) mathrm{ADV}^pm(g) enspace . ] For an efficiently verifiable relation $f$ this means $Q(f circ g^n) = Theta( mathrm{ADV}_{rel}^pm(f) mathrm{ADV}^pm(g) )$.
Solving eigenvalue problems is crucially important for both classical and quantum applications. Many well-known numerical eigensolvers have been developed, including the QR and the power methods for classical computers, as well as the quantum phase e
stimation(QPE) method and the variational quantum eigensolver for quantum computers. In this work, we present an alternative type of quantum method that uses fixed-point quantum search to solve Type II eigenvalue problems. It serves as an important complement to the QPE method, which is a Type I eigensolver. We find that the effectiveness of our method depends crucially on the appropriate choice of the initial state to guarantee a sufficiently large overlap with the unknown target eigenstate. We also show that the quantum oracle of our query-based method can be efficiently constructed for efficiently-simulated Hamiltonians, which is crucial for analyzing the total gate complexity. In addition, compared with the QPE method, our query-based method achieves a quadratic speedup in solving Type II problems.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
