The number of elements in a subset: A Grover-kronecker quantum algorithm
| Abstract | In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can …nd a single marked object in a database of size N by using only O(pN ) queries of the oracle that identi…es the object. His result was generalized to the case of …nding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either M or K, M < K, our task is to determine which is the case. We show how to solve this problem with a high probability of success using only iterations of Grover’s basic step (and no other algorithm). Let m be the required number of iterations; we prove that under certain restrictions on the sizes of M and K the estimation.. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,631 |
| External links |
  Try with proxy. |
| Through your library | Only published papers are available at libraries |
Similar books and articlesRenling Jin (2007). Inverse Problem for Cuts. Logic and Analysis 1 (1):61-89.
J. C. E. Dekker (1986). The Inclusion-Exclusion Principle for Finitely Many Isolated Sets. Journal of Symbolic Logic 51 (2):435-447.
Amit Hagar & Alexandre Korolev (2006). Quantum Hypercomputability? Minds and Machines 16 (1).
Jeffrey Bub (2008). Quantum Computation and Pseudotelepathic Games. Philosophy of Science 75 (4):458-472.
Tien D. Kieu (2002). Quantum Hypercomputation. Minds and Machines 12 (4):541-561.
Achim Hoffmann (forthcoming). Can Machines Think? An Old Question Reformulated. Minds and Machines.
Amit Hagar, Quantum Computing. Stanford Encyclopedia of Philosophy.
David Ellerman (2009). Counting Distinctions: On the Conceptual Foundations of Shannon's Information Theory. Synthese 168 (1):119 - 149.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads6 ( #145,407 of 548,972 )Recent downloads (6 months)1 ( #63,511 of 548,972 )How can I increase my downloads? |
My notes
Discussion
