| dbo:abstract
|
- 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 current 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 a 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. (en)
- Der Algorithmus von Deutsch ist ein Quantenalgorithmus für Quantencomputer, mit dem man bestimmen kann, ob eine auf einem Bit operierende Funktion konstant oder balanciert ist. Diese Aufgabenstellung ist unter dem Namen Problem von Deutsch bekannt. Der Algorithmus von Deutsch ist zwar kaum von praktischem Nutzen, er war jedoch historisch der erste Quantenalgorithmus, der eine Aufgabenstellung nachweisbar schneller löst als ein klassischer Algorithmus und damit die theoretischen Möglichkeiten von Quantencomputern aufzeigt. Eine Verallgemeinerung ist der Deutsch-Jozsa-Algorithmus. Dabei wird das Problem von Deutsch auf mehrere Bits übertragen. Die Algorithmen wurden nach ihren Urhebern David Deutsch und Richard Jozsa benannt. (de)
- En computación cuántica, el algoritmo de Deutsch-Jozsa es un algoritmo cuántico, propuesto por David Deutsch y en 1992. Fue uno de los primeros algoritmos diseñados para ejecutar sobre un computador cuántico y que tiene el potencial de ser más eficiente que los algoritmos clásicos al aprovechar el paralelismo inherente de los estados de superposición cuánticos. En el problema de Deutsch-Jozsa, se tiene una función (que puede considerarse como un oráculo o caja negra) f(x1, x2,..., xn) que toma n bits de entrada x1, x2,..., xn y devuelve un valor binario f(x1, x2,..., xn)= 0 ó 1. El objetivo es determinar si la función es constante (0 en todas las entradas o 1 en todas las entradas) o balanceada (devuelve 1 para la mitad de las entradas y 0 para la otra mitad). El problema es determinar cómo es la función (constante o balanceada) aplicando entradas a la caja negra y observando su salida. A modo de ejemplo, considérese la función , es decir, la función que devuelve el resto de dividir la entrada entre dos. Esta función devuelve 1 si el argumento es impar y 0 si el argumento es par, por lo que se trata de una función balanceada. La función del algoritmo sería la de llegar a esta misma conclusión con el menor número posible de iteraciones, algo que en el caso clásico requeriría la evaluación repetida de la función hasta alcanzar dos resultados diferentes, y por tanto el número de iteraciones dependería del orden en el que se escogieran las variables de entrada. (es)
- L'algorithme de Deutsch-Jozsa est un algorithme quantique, proposé par David Deutsch et Richard Jozsa en 1992 avec des améliorations de R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca en 1998. Bien qu'il ne soit pas d'un grand intérêt pratique, il s'agit d'un des premiers algorithmes quantiques qui est plus efficace qu'un algorithme classique. (fr)
- ドイッチュ・ジョサのアルゴリズムは、量子アルゴリズムであり、1992年にとによって提案され、 Richard Cleve, Artur Ekert, Chiara Macchiavello, そして Michele Mosca によって 1998 年に改良された。実用性は限られるが、既存のどの決定論的古典アルゴリズムよりも指数関数的に早い量子アルゴリズムのうち最も早期に発見されたものの一つである。また、これは決定的アルゴリズムであり、常に解を得ることができ、またその解は常に正しい。 (ja)
- L'algoritmo di Deutsch-Jozsa è un algoritmo quantistico deterministico proposto da David Deutsch e Richard Jozsa nel 1992 e successivamente migliorato da Richard Cleve, Artur Ekert, Chiara Macchiavello, e Michele Mosca nel 1998. Sebbene sia di scarso interesse pratico, è uno dei primi esempi di algoritmi quantistici ad essere esponenzialmente più veloce di un qualsiasi algoritmo deterministico classico. (it)
- Algorytm Deutscha-Jozsy – algorytm kwantowy utworzony przez Dawida Deutscha i w 1992 poprawiany później przez , Artura Ekerta, Chiarę Macchiavello i Michele Mosca w 1998. Sam algorytm nie ma dużej wartości praktycznej – jest to jeden z pierwszych przykładów algorytmu kwantowego, który jest wykładniczo szybszy od każdego możliwego deterministycznego, klasycznego algorytmu. Algorytm Deutscha-Jozsy jest również deterministyczny, to znaczy zawsze zwraca poprawną odpowiedź. (pl)
- Алгоритм Дойча — Йожи (упоминается также как алгоритм Дойча — Джозы) — квантовый алгоритм, предложенный Дэвидом Дойчем и в 1992 году, и ставший одним из первых квантовых алгоритмов. Алгоритм основывается на явлении квантовой запутанности и принципе суперпозиции, благодаря чему демонстрирует квантовое превосходство — значительно более эффективную работу в сравнении с известными классическими алгоритмами. Алгоритм Дойча — первый вариант алгоритма, разработанный Дойчем в 1985 году; в нём рассматривается функция от одной переменной. (ru)
- O algoritmo de Deutsch-Jozsa é um algoritmo quântico, proposto por David Deutsch e em 1992, e melhorado por , Artur Ekert, Chiara Macchiavello e en 1998.Apesar de possuir uma aplicação prática limitada, trata-se de um dos primeiros exemplos de um algoritmo quântico que é exponencialmente mais rápido que qualquer algoritmo determinístico clássico. (pt)
- Алгоритм Дойча — Йожи (іноді алгоритм Дойча — Джози, англ. Deutsch–Jozsa algorithm) — квантовий алгоритм, запропонований Девідом Дойчем і Річардом Йожею в 1992 році й вдосконалений Річардом Клівом, Артуром Екертом, К'ярою Маккіавелло й в 1998 році. Цей алгоритм став одним із перших прикладів алгоритму для квантового комп'ютера. Завдяки використанню квантової переплутаності й принципу суперпозиції такий алгоритм має значний приріст швидкості виконання в порівнянні з відповідним класичним аналогом. Задача Дойча — Йожи полягає у визначенні, чи є функція двійкової змінної константою (тобто, набуває або значення 0, або значення 1 за будь-яких аргументів) або збалансованою (для половини області визначення набуває значення 1, для іншої половини — значення 0). При цьому вважається, що функція a priori є або константою, або збалансованою. Для розв'язання цієї задачі класичний детермінований алгоритм має виконати в найгіршому випадку обчислень функції . Класичний детермінований алгоритм потребує меншого часу, щоб дати правильну відповідь із високою ймовірністю. Але в будь-якому разі для отримання правильної відповіді з одиничною ймовірністю потрібно виконати обчислень. Алгоритм Дойча — Йожи завжди дає правильну відповідь, виконуючи лише одне обчислення функції . Якщо функція незбалансована, то алгоритм може дати відповідь «константа» з деякою ймовірністю, причому при збільшенні різниці між кількістю «0» і «1» збільшується й ця ймовірність. Алгоритм Дойча — Йожи оснований на схожому алгоритмі (алгоритм Дойча, розроблений Девідом Дойчем у 1985 році), який є частковим випадком першого. В цьому алгоритмі функція є функцією однієї змінної, на відміну від функції багатьох змінних , яка використовується в алгоритмі Дойча — Йожи. (uk)
- 多伊奇-乔萨算法（英語：Deutsch–Jozsa algorithm）是戴维·多伊奇和于1992年提出的一种确定性量子算法。1998年，、、基娅拉·马基亚韦洛（Chiara Macchiavello）与对其进行了改进。尽管该算法目前在现实中基本没有用途，但可以证明它比任何可能的确定性经典算法都快指数级，是最早提出的有此特性的量子算法之一。 (zh)
|
| rdfs:comment
|
- L'algorithme de Deutsch-Jozsa est un algorithme quantique, proposé par David Deutsch et Richard Jozsa en 1992 avec des améliorations de R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca en 1998. Bien qu'il ne soit pas d'un grand intérêt pratique, il s'agit d'un des premiers algorithmes quantiques qui est plus efficace qu'un algorithme classique. (fr)
- ドイッチュ・ジョサのアルゴリズムは、量子アルゴリズムであり、1992年にとによって提案され、 Richard Cleve, Artur Ekert, Chiara Macchiavello, そして Michele Mosca によって 1998 年に改良された。実用性は限られるが、既存のどの決定論的古典アルゴリズムよりも指数関数的に早い量子アルゴリズムのうち最も早期に発見されたものの一つである。また、これは決定的アルゴリズムであり、常に解を得ることができ、またその解は常に正しい。 (ja)
- L'algoritmo di Deutsch-Jozsa è un algoritmo quantistico deterministico proposto da David Deutsch e Richard Jozsa nel 1992 e successivamente migliorato da Richard Cleve, Artur Ekert, Chiara Macchiavello, e Michele Mosca nel 1998. Sebbene sia di scarso interesse pratico, è uno dei primi esempi di algoritmi quantistici ad essere esponenzialmente più veloce di un qualsiasi algoritmo deterministico classico. (it)
- Algorytm Deutscha-Jozsy – algorytm kwantowy utworzony przez Dawida Deutscha i w 1992 poprawiany później przez , Artura Ekerta, Chiarę Macchiavello i Michele Mosca w 1998. Sam algorytm nie ma dużej wartości praktycznej – jest to jeden z pierwszych przykładów algorytmu kwantowego, który jest wykładniczo szybszy od każdego możliwego deterministycznego, klasycznego algorytmu. Algorytm Deutscha-Jozsy jest również deterministyczny, to znaczy zawsze zwraca poprawną odpowiedź. (pl)
- Алгоритм Дойча — Йожи (упоминается также как алгоритм Дойча — Джозы) — квантовый алгоритм, предложенный Дэвидом Дойчем и в 1992 году, и ставший одним из первых квантовых алгоритмов. Алгоритм основывается на явлении квантовой запутанности и принципе суперпозиции, благодаря чему демонстрирует квантовое превосходство — значительно более эффективную работу в сравнении с известными классическими алгоритмами. Алгоритм Дойча — первый вариант алгоритма, разработанный Дойчем в 1985 году; в нём рассматривается функция от одной переменной. (ru)
- O algoritmo de Deutsch-Jozsa é um algoritmo quântico, proposto por David Deutsch e em 1992, e melhorado por , Artur Ekert, Chiara Macchiavello e en 1998.Apesar de possuir uma aplicação prática limitada, trata-se de um dos primeiros exemplos de um algoritmo quântico que é exponencialmente mais rápido que qualquer algoritmo determinístico clássico. (pt)
- 多伊奇-乔萨算法（英語：Deutsch–Jozsa algorithm）是戴维·多伊奇和于1992年提出的一种确定性量子算法。1998年，、、基娅拉·马基亚韦洛（Chiara Macchiavello）与对其进行了改进。尽管该算法目前在现实中基本没有用途，但可以证明它比任何可能的确定性经典算法都快指数级，是最早提出的有此特性的量子算法之一。 (zh)
- Der Algorithmus von Deutsch ist ein Quantenalgorithmus für Quantencomputer, mit dem man bestimmen kann, ob eine auf einem Bit operierende Funktion konstant oder balanciert ist. Diese Aufgabenstellung ist unter dem Namen Problem von Deutsch bekannt. Der Algorithmus von Deutsch ist zwar kaum von praktischem Nutzen, er war jedoch historisch der erste Quantenalgorithmus, der eine Aufgabenstellung nachweisbar schneller löst als ein klassischer Algorithmus und damit die theoretischen Möglichkeiten von Quantencomputern aufzeigt. (de)
- 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 current practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. (en)
- En computación cuántica, el algoritmo de Deutsch-Jozsa es un algoritmo cuántico, propuesto por David Deutsch y en 1992. Fue uno de los primeros algoritmos diseñados para ejecutar sobre un computador cuántico y que tiene el potencial de ser más eficiente que los algoritmos clásicos al aprovechar el paralelismo inherente de los estados de superposición cuánticos. (es)
- Алгоритм Дойча — Йожи (іноді алгоритм Дойча — Джози, англ. Deutsch–Jozsa algorithm) — квантовий алгоритм, запропонований Девідом Дойчем і Річардом Йожею в 1992 році й вдосконалений Річардом Клівом, Артуром Екертом, К'ярою Маккіавелло й в 1998 році. Цей алгоритм став одним із перших прикладів алгоритму для квантового комп'ютера. Завдяки використанню квантової переплутаності й принципу суперпозиції такий алгоритм має значний приріст швидкості виконання в порівнянні з відповідним класичним аналогом. (uk)
|
