![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
Кроме этого исследователи запускали на квантовом процессоре алгоритм Дойче-Джоза. Это теоретический алгоритм, который по данной последовательности нулей и единиц четной длины отвечает на вопрос: верно ли, что все значения в наборе нули, единицы или нулей и единиц одинаковое количество. При этом заранее известным полагается, что последовательность имеет один из трех данных видов. Этот алгоритм выдает ответ всего за один шаг, в то время как классический алгоритм требует 2n - 1 + 1 шагов, где n - длина последовательности
Я возьмусь утверждать, что для этого алгоритма необходимо O(n) операций. Берем массив произвольной длинны, заполняем его в случайном порядке нулями и единицами. Заводим 2 доп. ячейки памяти, в которые будем записывать кол-во нулей и единиц. Далее:
long a = 0, b = 0, i = 0;
for(i = 0, i < n; i++)
{
if (matrix[i] == 0)
a++;
else
b++;
}
Теперь остается только сравнить a и b. И где здесь 2n - 1 + 1 шагов?
Хотя, если верить написанному - становится ясно, почему современный софт на современном железе так работает :)
2009-06-29 07:34 pm (UTC)
В википедии написано, что есть функция f, которая в качестве входного параметра принимает последовательность из нулей и единиц длиной n, а возвращает одно из чисел: 0 или 1. И задача в том, чтобы определить, какого она типа - константа или сбалансированная (т.е. 0 и 1 поровну).
То есть для данного n число вариантов 2^n. Надо проверить в худшем случае половину все вариантов и ещё один из-за чётности n.
(Anonymous)
2009-06-30 02:37 am (UTC)
Пробегаешь по всему массиву и смотришь, отличается ли итый элемент от иплюспервого. Если хоть раз отличается - то считаем что поровну. Если ни один элемент не отличается - то сравниваешь нулевой элемент с нулем. Если равны - значит последовательность нулевая, если не равны - значит из единиц.
2009-06-30 02:56 am (UTC)
The problem statement
In the Deutsch-Jozsa problem, we are given a black box quantum computer known as an oracle that implements the function f{0,1}^n->(0,1). We are promised that the function is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input domain and 0 for the other half); the task then is to determine if f is constant or balanced by using the oracle.
Другими словами, есть функция, которая жрет последовательность нулей и единиц, а на выход выдает либо ноль, либо единицу. А алгоритм проверяет не последовательность, а саму функцию: либо она выдает только нули, либо она выдает только единицы, либо и того и другого поровну, в зависимости от входного значения.
P.S. Предыдущий ответ тоже я писал
2009-06-30 05:50 am (UTC)
2009-06-30 06:33 am (UTC)