NDLI: Quantum oracle interrogation: getting all information for almost half the price

Content Provider	IEEE Xplore Digital Library
Author	van Dam, W.
Copyright Year	1998
Description	Author affiliation: Clarendon Lab., Oxford Univ., UK (van Dam, W.)
Abstract	Consider a quantum computer in combination with a binary oracle of domain size N. It is shown how N/2+/spl radic/N calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 95%. This contrasts the power of classical computers which would require N calls to achieve the same task. From this result it follows that any function with the N bits of the oracle as input can be calculated using N/2+/spl radic/N queries if we allow a small probability of error. It is also shown that this error probability can be made arbitrary small by using N/2+O(/spl radic/N) oracle queries. In the second part of the article 'approximate interrogation' is considered. This is when only a certain fraction of the N oracle bits are requested. Also for this scenario does the quantum algorithm outperform the classical protocols. An example is given where a quantum procedure with N/10 queries returns a string of which 80% of the bits are correct. Any classical protocol would need 6N/10 queries to establish such a correctness ratio.
Starting Page	362
Ending Page	367
File Size	95981
Page Count	6
File Format	PDF
ISBN	0818691727
ISSN	02725428
DOI	10.1109/SFCS.1998.743486
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1998-11-08
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Quantum computing Laboratories Upper bound High performance computing Computer errors
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Quantum oracle interrogation: getting all information for almost half the price (1998)

Quantum Oracle Interrogation: Getting All Information for Almost Half the Price (1999)

Quantum Oracle Interrogation: Getting all information for almost half the price

Quantum oracle interrogation: getting all information for almost half the price (1998)

All pairs almost shortest paths

An information-theoretic analysis of Grover's algorithm

Bounds for small-error and zero-error quantum algorithms

Computing With Almost Optimal Size Threshold Circuits

Quantum computation techniques for gauging reliability of interval and fuzzy data

Quantum oracle interrogation: getting all information for almost half the price

Similar Documents

Quantum oracle interrogation: getting all information for almost half the price (1998)

Quantum Oracle Interrogation: Getting All Information for Almost Half the Price (1999)

Quantum Oracle Interrogation: Getting all information for almost half the price

Quantum oracle interrogation: getting all information for almost half the price (1998)

All pairs almost shortest paths

An information-theoretic analysis of Grover's algorithm

Bounds for small-error and zero-error quantum algorithms

Computing With Almost Optimal Size Threshold Circuits

Quantum computation techniques for gauging reliability of interval and fuzzy data

Quantum oracle interrogation: getting all information for almost half the price