The number of elements in a subset: A Grover-kronecker quantum algorithm
David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
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||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library||
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Renling 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):87-93.
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 (2010). Can Machines Think? An Old Question Reformulated. Minds and Machines 20 (2):203-212.
Amit Hagar & Michael Cuffaro, 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.
Added to index2009-01-28
Total downloads20 ( #142,353 of 1,726,249 )
Recent downloads (6 months)2 ( #289,836 of 1,726,249 )
How can I increase my downloads?