Алгоритм Дойча


Алгоритм Дойча

Алгоритм Дойча — Джоза — это квантовый алгоритм, предложенный Давидом Дойчем и Ричардом Джозой в 1992 году. Он стал одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. Эти алгоритмы благодаря использованию явления квантовой запутанности и принципа суперпозиции обладают значительным приростом скорости выполнения по сравнению с соответствующими классическими алгоритмами.

Задача Дойча — Джоза заключается в определении, является ли функция двоичной переменной f(n) постоянной (принимает либо значение 0, либо 1 при любых аргументах) или сбалансированной (для половины области определения принимает значение 0, для другой половины 1).

Для решения этой задачи классическому детерминированному алгоритму необходимо произвести 2^{n-1}+1 вычислений функции f в худшем случае. Классическому вероятностному алгоритму потребуется меньше времени, чтобы дать верный ответ с высокой вероятностью. Но в любом случае для получения верного ответа с единичной вероятностью потребуется 2^{n-1}+1 вычислений. Алгоритм Дойча — Джоза всегда дает верный ответ, совершив лишь одно вычисление значения функции f.

Алгоритм Дойча — Джоза основан на разработанном Давидом Дойчем в 1985 году схожем алгоритме, являющемся частным случаем первого. В этом алгоритме функция f(x1) являлась функцией одной переменной, в отличие от функции многих переменных f(x1, x2, …, xn), используемой в более позднем алгоритме.

См. также

Литература



Wikimedia Foundation. 2010.

Смотреть что такое "Алгоритм Дойча" в других словарях:

  • Алгоритм Дойча — Джоза — это квантовый алгоритм, предложенный Давидом Дойчем и Ричардом Джозой в 1992 году. Он стал одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. Эти алгоритмы благодаря использованию явления квантовой… …   Википедия

  • Алгоритм Дойча-Джозса — …   Википедия

  • Алгоритм Дойча-Йозца — …   Википедия

  • Алгоритм Дойча-Йозса — …   Википедия

  • Алгоритм Дойча-Джоса — …   Википедия

  • Алгоритм Дойча-Джоза — …   Википедия

  • Алгоритм Дойча-Йоша — …   Википедия

  • Алгоритм дойча-джоза — …   Википедия

  • Алгоритм Гровера — Алгоритм Гровера (англ. Grover search algorithm, GSA)  квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения где есть булева функция от n переменных.[1] Предполагается, что функция задана в виде чёрного… …   Википедия

  • Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время , используя O(log N) логических кубитов. Значимость алгоритма заключается в том, что при использовании квантового компьютера с… …   Википедия