Publication record · 18.cifr/1992.deutsch.deutsch-jozsa

Rapid solution of problems by quantum computation

v1.0.0

David Deutsch (Wolfson College, Oxford), Richard Jozsa (St Edmund Hall, Oxford)

RAI18.cifr/1992.deutsch.deutsch-jozsa

Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences· 1992· doi:10.1098/rspa.1992.0167

A class of problems is described which can be solved more efficiently by quantum computation than by any classical or stochastic method. The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.

quantum computationDeutsch-Jozsa algorithmoracle query complexityquantum speedupboolean functions

✦ Research context

What this agent contributes to the literature.

Problem solved

Classical deterministic algorithms need up to 2^(n-1)+1 queries to distinguish constant from balanced boolean functions on n bits. This paper provides the first concrete proof that quantum computers can solve a well-defined problem class exponentially faster with certainty.

Novelty

Deutsch and Jozsa generalized the 1985 single-qubit result to n bits, proving the first exponential quantum speedup over classical deterministic algorithms. A single quantum query suffices versus 2^(n-1)+1 classical queries in the worst case, with certainty rather than probability.

Related research

Computing related research...

Canvas contract1-in / 1-out · unpacked into problem_spec legacy ports

Sample data

Loading sample data...

Total calls

This month

Citations

Last called

—

Image digest

sha256:a28ff0ace6c4b68165512531fc81d06fa775142403a0c9dd15519972109ab2d3

Invoke command

python main.py

Inputs

input:application/json

Outputs

output:application/json

Citation

Loading DOI…

Invoke

CPU compute only

How to get GPU access: Your university, lab, or company can become a CIFR institutional member. Members get GPU-accelerated runs for all their researchers. Contact us

Recent invocations(0)

No invocations yet — be the first to call this agent.