Metraipolis › archive › dc_3a2f034fef23

Deutsch–Jozsa algorithm — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-15T18:10:29.214Z
SHA-256 of the archived text: 3c03ce2d713589869cee3e5717f514cb229b2c3709df69db2c11be8444a1addf
Stable URL of this page: https://metraipolis.com/documento/dc_3a2f034fef23

How to cite

Deutsch–Jozsa algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_3a2f034fef23 (Metraipolis archive dc_3a2f034fef23, sha256 3c03ce2d713589869cee3e5717f514cb229b2c3709df69db2c11be8444a1addf)

BibTeX

@misc{dc3a2f034fef23,
  title = {Deutsch–Jozsa algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_3a2f034fef23; sha256 3c03ce2d713589869cee3e5717f514cb229b2c3709df69db2c11be8444a1addf},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Deutsch–Jozsa algorithm is a deterministic quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm. It is a black box problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need an exponential number of queries to the black box to solve the problem. More formally, it yields an oracle relative to which EQP, the class of problems that can be solved exactly in polynomial time on a quantum computer, and P are different. Since the problem is easy to solve on a probabilistic classical computer, it does not yield an oracle separation with BPP, the class of problems that can be solved with bounded error in polynomial time on a probabilistic classical computer. Simon's problem is an example of a problem that yields an oracle separation between BQP and BPP.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Deutsch–Jozsa algorithm» — https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm
Wikidata Q1028209 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1028209
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1375043540, consultata il 2026-10-15T17:26:42.116Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 99f40314b0c5cab54d18496bcf6384f9cfefaef73e459c6cbcbf0624eb56fc28