Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Дойча Джоза

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

Задача Дойча — Джоза заключается в определении, является ли функция двоичной переменной f постоянной или сбалансированной.

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

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