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)|
|Through your library||Only published papers are available at libraries|
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, 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 downloads6 ( #162,892 of 1,089,047 )
Recent downloads (6 months)1 ( #69,722 of 1,089,047 )
How can I increase my downloads?