CoChat

Oracle Quantum Computing

Berthiaume, A., Brassard, G. · 2005 · Workshop on Physics and Computation
Cited by 20

The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.

Abstract

Building on work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer. The results given in this paper have been presented at the 7th Annual IEEE Symposium on Structure in Complexity Theory, Boston, June 1992, and at the Workshop on Physics and Computation, PhysComp '92, Dallas, October 1992; they have appeared in preliminary form in those Proceedings [7, 8]. y Supported in part by an Nserc postgraduate fellowship. z Supported in part by Canada's Nserc E. W. R. Steacie Memorial Fellowship an...

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/phycmp.1992.615538

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 3 references

Cited by

See all 20

Metadata

Authors
Berthiaume, A., & Brassard, G.
Venue
Workshop on Physics and Computation
Publisher
IEEE
Published
2005-08-24
Pages
195-199
OpenAlex
W1906651570
Cited by
20
References
3
FWCI
0.24
Type
conference paper
Language
en
Open access
closed

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Oracle Quantum Computing. https://app.cochat.ai/papers/10.1109/phycmp.1992.615538
The paper
Berthiaume, A., & Brassard, G. (2005). Oracle Quantum Computing. Workshop on Physics and Computation. https://doi.org/10.1109/phycmp.1992.615538

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.