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

Quantum::Entanglement позволяет моделировать программирование квантового компьютера (Slashdot | Quantum Programming with Perl). Сделаем предположение, что состояние переменной определяется двумя возможными числами 1 и 0(т.н. кубит). Если таких переменных много, то они могут находиться в кластерном("запутанном") состоянии (entangled state), т.е. когда изменение одной из переменных ведет за собой мгновенное изменение всех других. Конечно, обычный компьютер производит вычисления последовательно(и изменение одной переменной не ведет за собой изменения остальных), но данный модуль, тем не менее, прозволяет проводить некоторые эксперименты над такими состояниями.

В модуле Quantum::Entanglement определена функция entangled(), которая на входе имеет значения пар амплитуд и чисел, и на выходе имеет скаляр из суперпозиции этих состояний. Например $die = entangle( 1=>1, 1=>2, 1=>3, 1=>4, 1=>5, 1=>6); создает суперпозицию состояний 1 .. 6. В дальнейшем $die является равновероятным для каждого состояния до тех пор, пока мы не попытаемся определить, какое-же из этих состояний содержит переменная $die.

Теперь нужно определить, что происходит, когда мы наблюдаем нашу переменную и что подразумевается под наблюдением. В широком смысле определение "что-то, что показывает значение переменной" является правильным. Можно довольно многими видами сравнения определить "содержание" переменной, даже операторы типа eq или <= могут сообщить о некоторых свойствах переменной. Каким образом определить, что переменная $die является измеренной? Попадание значения переменной $die в какое-то конкретное число(состояние) из чисел 1 .. 6 определяется возможностью этому числу выпасть при разыгрывании, например, игровой кости. Поскольку игральная кость выпадет в любом случае какой-то своей гранью, то результатом будет число и в идеальном варианте на каждую одну шестую от общего времени всех бросаний кости она будет иметь какой-то номер. Но при этом все остальные состояния уничтожатся. Т.е. в процессе полета кости переменная $die существует($die - равновероятность выпадения одного из 6 номеров), а как только кость на столе успокоилась, то переменной $die, определенной в смысле функции entangle уже не существует, существует только лишь какое-то конкретное е╦ значение. При этом пядь шестых игроков хмуро расплачивается с одним счастливчиком. Это собирающее всех игроков вместе состояние и называется либо запутанным(entangled), либо кластерным, либо странным. Рассмотрим программу: #!/usr/bin/perl -w use strict; use Quantum::Entanglement qw(:DEFAULT); my $foo = entangle(1=>2,1=>3,1=>5,1=>7); # |2> +|3> + |5> +|7> print '$foo is greater than four' if ($foo > 4); данная программа равновероятно(с увеличеним числа е╦ запусков до бесконечности конечно) проводит сравнения либо с |2> + |3> либо с |5> +7>: [root@tv demo]# perl -c rr.pl rr.pl syntax OK [root@tv demo]# chmod 755 rr.pl [root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl [root@tv demo]# ./rr.pl [root@tv demo]# ./rr.pl [root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl [root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl [root@tv demo]# ./rr.pl [root@tv demo]# Если переменная $Quantum::Entanglement::conform имеет значение true: $Quantum::Entanglement::conform = 1; то предпочтительным будет вывод $foo is greater than four, т.е. более положительный ответ: #!/usr/bin/perl -w use strict; use Quantum::Entanglement qw(:DEFAULT); my $foo = entangle(1,2,1,3,1,5,1,7); # |2> +|3> + |5> +|7> $Quantum::Entanglement::conform = 1; print '$foo is greater than four' if ($foo > 4); File rr.pl saved File rr.pl not changed so no update needed. [root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]# ./rr.pl $foo is greater than four[root@tv demo]#

Напишем пример реализации умножения чисел: #!/usr/bin/perl -w use Quantum::Entanglement qw(:DEFAULT); # зададим два массива независимых чисел my @inputsA = (1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,10); my @inputsB = (1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,10); #слинкуем их, т.е. запутаем, сделаем зависимыми my $inputsA = entangle( @inputsA ); my $inputsB = entangle( @inputsB ); # и теперь перемножим эти зависимые состояния чисел my $answer = $inputsA * $inputsB; # запомним основное исходное состояние, чтобы вызвать его снова, если потребуется my $state = save_state($inputsA, $inputsB, $answer); # выставим режим наибольшего благоприятствования, более положительный ответ $Quantum::Entanglement::conform = 1; print "введите два числа между 1 и 10 для перемножения\n"; while (<>) { last unless /(\d+)[^\d]*(\d+)/; 1 if $inputsA == $1; # угу, действительно равно, но в пустом контексте 1 if $inputsB == $2; print "\n$1 * $2 = $answer\n"; ($inputsA, $inputsB, $answer) = $state->restore_state; # восстановим исходное состояние! } на выводе получим: ** Joe's Own Editor v2.9.5 ** Copyright (C) 2001 ** File calc_cache.pl not changed so no update needed. [root@tv demo]# ./calc_cache.pl введите два числа между 1 и 10 для перемножения 1 2 1 * 2 = 2 3 4 3 * 4 = 12 9 9 9 * 9 = 81 q [root@tv demo]#

Что делает этот скрипт, т.к. состояния слинкованы(т.е. изменяя одно изменим все остальные), то их произведение будет связанным произведением комбинации из этих чисел. Т.к. $answer является всевозможными комбинациями из произведений первых двух матриц @inputsA и @inputsB, то фактически получается, что написав строчку my $answer = $inputsA * $inputsB; определили пространство произведений этих комбинаций(т.е. сразу задали всю таблицу умножения).

Далее происходит определение режима наибольшего благоприятствования $Quantum::Entanglement::conform = 1; и само сравнение, уничтожающее сначала неопределенность $inputsA(т.е. при вводе из консоли первого конкретного числа от таблицы умножения остается фактически один столбец с умножением одного числа на все оставшиеся) и, далее воодя второе число, устраняется неопределенность $inputsB(который имеет разброс 1 .. 10). Т.е. изначально заданная система становится конкретизированной, из 100 возможных результатов получается одно.

При распаковке Quantum-Entanglement.*.tar.gz в директории demo/ лежит файл shor.pl, реализующий алгоритм Шора для разложения числа на два множителя. В той-же директории лежит файл root_not.pl, который умеет строить противоположные к начальному entangle(a,c,b,d) состояния.

Всякий раз, когда связанные переменные находятся в таком взаимодействии или при вычислениях, результаты(ведь граней у вышеописанного кубика 6, а значит и 6 возможностей) будут в такой-же степени связаны друг с другом. Если числа могут быть коэффициентами таких состояний(например вероятность выпадения одного номера в 2 раза больше чем другого), то вполне логично предположить, что этими коэффициентами могут быть и комплексные числа. Только вместо обычного значения этого числа нужно использовать квадрат его модуля(например |1+2i|**2 == 5 == |1-2i|**2).

Более подробно умножение комплексных чисел описано тут.

Quantum::Superpositions

(перевод из соответствующего мана)В стандартной интерпретации квантовой механики частицы существуют как функция вероятности. Например, частица, которая могла бы наблюдаться в состоянии A, B, или C, может рассматриваться в таком некотором псевдосостоянии, где она присутствует одновременно во всех трех состояниях. Считается, что такая частица находится в состоянии суперпозиции. Исследования состояния суперпозиции уже довольно давно известны(см. Наука и жизнь - Квантовые компьютеры, Квантовая суперпозиция макроскопических состояний, Квантовый компьютер, для тех кто еще не понял) и их целью является разработка надежных квантовых блоков памяти, в которых единичный бит(1 или 0) может являться свойством квантуемой частицы(qubit). Т.к. частица может быть физически введена в состояние суперпозиции в определенных условиях, то она может сохранять биты, являющиеся одновременно как 0 так и 1. Определенные процессы, основанные на взаимодействиях одного или более кубитов(элементарных носителей информации) используются чтобы создавать квантовые логические затворы. Такие затворы могут, в свою очередь, использоваться для логичеких операциях на кубитах, позволяя проводить параллельные вычисления. Но математика для таких вычислений очень сложна. Описываемый модуль Quantum::Superpositions предлагает другой подход, основанный на суперпозиции полных скалярных произведений.

В модуле Quantum::Superpositions существуют два оператора any и all. Каждый из этих операторов берет спиоск значений(состояний) и помещает их в одну скалярную переменную. any и all опреаторы устанавливают два различных вида суперпозиции, any делает суперпозицию дизъюнктивной, которая(умозрительно конечно) может выводить состояние в любое из возможных согласно требованию алгоритма.

Оператор all создает коньюктивную суперпозицию, которая является всегда в каждом из е╦ состояний одновременно. Суперпозиции - скалярные значения и, следовательно, могут участвовать в арифметических и логических операциях точно так же, как и любой другой тип скаляра. Но, когда операция применяется к суперпозиции, то она применяется параллельно к каждому из состояний, образовывающих ту или иную комбинацию.

Например, если состояния 1, 2, и 3 умножены на 2: $result = any(1,2,3) * 2;

то результатом такого умножения будет соответственно столь же связанные состояния 2, 4, и 6. Если такое состояние проверить на равенство 4-м: if ($result == 4) { print "fore!" }

то тогда сравнение так-же возвращает суперпозицию из двух вариантов "истина" и "ложь", т.к. равенство истинно для одного из состояний и ложно для двух других. Естественно, что значение, которое равновероятно(может быть либо истиной либо ложью) - бесполезно, но оно становится полезным, если добавить некоторый механизм, который определяет приоритет из этих значений. Дизъюнктивная суперпозиция истинна, если любое из е╦ состояний истинно, принимая во внимание при этом, что коньюктивная суперпозиция истинна только в том случае, если все е╦ состояния истинны. То есть предыдущий пример напечатает fore, в котором начиная с if состояние эквивалентно: if (any(2,4,6) == 4)...

т.е. если любой из 2,4 или 6 равен 4, то условие истинно и блок выполняется. С другой стороны, если есть инструкция if (all(2,4,6) == 4)...

то условие неверно, так как не истинно, что все 2, 4, и 6 равны 4. Операции также возможны между двумя суперпозициями: if (all(1,2,3)*any(5,6) < 21) { print "no alcohol"; } if (all(1,2,3)*any(5,6) < 18) { print "no entry"; } if (any(1,2,3)*all(5,6) < 18) { print "under-age" }

В этом примере строка "no alcohol" выведется потому, что суперпозиция, произведеная умножением - декартово следствие соответствующих состояний двух операндов all(5,6,10,12,15,18). Так как все эти результирующие состояния меньше чем 21, то состояние является истинным. Напротив, строка "no entry" не выведется потому, что не все состояния, получаемые в результате операции all(1,2,3)*any(5,6) меньше чем 18. Можно заметить, что тип первого операнда определяет тип результата операции, следовательно третья строка "under-age" напечатана потому, что умножение дизъюнктивой суперпозиции на коньюнктивную суперпозицию дает результат, который является дизъюнктивым: any(5,6,10,12,15,18). Условие if спрашивает, является ли любое из этих значений меньше чем 18, что и является истиной.

Составные суперпозиции могут быть любым видом скалярного значения - числом, строкой или ссылкой: $wanted = any("Mr","Ms").any(@names); if ($name eq $wanted) { print "Reward!"; } $okay = all(\&check1,\&check2); die unless $okay->(); my $large = all( BigNum->new($centillion), BigNum->new($googol), BigNum->new($SkewesNum) ); @huge = grep {$_ > $large} @nums;

Более интересно, когда индивидуальные состояния - скалярные значения и суперпозиция так-же является скалярным значением, т.е. суперпозиция может состоять из состояний, являющихся такими-же суперпозициями. $ideal = any( all("tall", "rich", "handsome"), all("rich", "old"), all("smart","Australian","rich") );

Операции, вовлекающие такую составную суперпозицию работают рекурсивно и в параллельном из каждых ее уникальных состояний и тогда реконструируют результат. Например: while (@features = get_description) { if (any(@features) eq $ideal) { print "True love"; } }

Условие any(@features) eq $ideal истинно, если входные характеристики соответствуют любой из трех добавленных коньюктивных суперпозиций. Т.е. если характеристики все вместе приравниваются к кажомой из "tall", "rich" и "handsome", или ко всем из "smart", "Australian" и "rich".

Иногда необходимо определить список состояний, из которых состоит данная суперпозиция. Фактически, сами по себе это не состояния, но значения к которым могут свертываться состояния - eigenstates, являющиеся полезными. В смысле программирования это набор значений @ev для данной суперпозиции $s такой как `any(@ev) == $s' or `any(@ev) eq $s'

Этот список обеспечивается оператором `eigenstates', который может обратится к любой суперпозиции print "The factor was: ", eigenstates($factor); print "Don't use any of:", eigenstates($badpasswds);

Примеры, показанные выше имеют ту-же самую мета-семантику для обеих арифметических и булевых операций, а именно, что бинарный оператор применяется к декартовым состояниям из двух операций, независимо от того, является ли операция арифметической или логической. Таким образом сравнение двух супрпозиций дает суперпозицию 1's и 0's, давая возможность сравнить любые состояния между собой из двух суперпозиций. Недостаток применения метасемантической арифметики к логическим операциям состоит в том, что может быть потеряна полезная информация. Действительно, есть состояния, которые ответственны за успешное сравнение. Например, возможно определить, является ли любой номер в массиве @newnums меньшим, чем все номера в массиве @oldnums if (any(@newnums) < @all(oldnums)) { print "New minimum detected"; }

Но это не очень хорошо в том смысле, что нельзя увидеть, какой элемент(-ы) @newnum сделал условие истинным. Но, однако, возможно определить различную мета-сематнику для логических операций между суперпозициями; один также сохраняет интуитивную логику сравнений и ограничивает доступ к состоянию, которое вызвало истинность сравнения. Ключ должен отклоняться от арифметического представления суперпозиционного сравнения(а именно, что сравненная суперпозиция уступает суперпозиции сравниваемых комбинаций состояний) Вместо этого, различные операторы сравнения переопределены так, чтобы они формировали суперпозицию тех eigenstates левого операнда, которые заставляют операцию быть истинными. Другими словами старая мета-сематника накладывает результат каждого парралельного сравнения, в то время как новая мета-семантика левого операнда каждого параллельного сравнения выпонляется. Например под первоначальной семантикой сравнения all(7,8,9) <= any(5,6,7) #A all(5,6,7) <= any(7,8,9) #B any(6,7,8) <= all(7,8,9) #C уступили бы: all(0,0,1,0,0,0,0,0,0) #A (false) all(1,1,1,1,1,1,1,1,1) #B (true) any(1,1,1,1,1,1,0,1,1) #C (true) под новой семантикой они уступили бы: all(7) #A (false) all(5,6,7) #B (true) any(6,7) #C (true)

Успешность сравнения(результата) больше не определена значениями конечных состояний, но определена числом состояний конечной суперпозиции. Модуль Quantum::Superpositions обрабатывает логические операции и булевы преобразования именно этим способом. Под этой мета-семантикой возможно проверять сравнение и также определять, какой eigenstates левого операнда был ответственнен за успешное сравнение: $newmins = any(@newnums) < all(@oldnums); if ($newmins) { print "New minima found:", eigenstates($newmins); }

Таким образом, эта семантика обеспечивает механизм проведения параллельного исследования минимумов и максимумов: sub min { eigenstates( any(@_) <= all(@_) ) } sub max { eigenstates( any(@_) >= all(@_) )

Эти определения также весьма интуитивны, почти декларативны: минимум - любое значение, которое является "меньше или равным" чем все другие значения; максимум - любое значение, которое является "большим чем или равным" ко всем из них.

Строковая оценка суперпозиций

Преобразование суперпозиции в строковое представление производит строку, которая кодируется самым простым набором eigenstates эквивалентов первоначальной суперпозиции. Если есть только один eigenstate строчность этого состояния может быть представлено в строковом представлении. Это устраняет явное применение оператора eigenstates, когда возможно только единственное состояние. Например print "lexicographically first: ", any(@words) le all(@words);

Во всех других случаях суперпозиции - преобразуются в формате: "all(eigenstates)" или "any(eigenstates)".

Числовая оценка суперпозиций

Обеспечение неявного преобразования в числа(для ситуаций, где суперпозиции используются как операнды в арифметике или как индексы массива) бывает более лучшим, чем строковое представление, до тех пор, пока нет никакого механизма для фиксирования полного состояния суперпозиции в единственном не добавленном номере. Снова, если суперпозиция имеет единственный eigenstate, то преобразование него выполняется стандартным образом. Например, чтобы вывести значение в элементе массива с самым маленьким индексом в наборе индексов @i: print "The smallest element is: ", $array[any(@i)<=all(@i)];

Суперпозиции как аргументы подпрограмм

Когда суперпозиция применяется, как аргумент подпрограммы, эта подпрограмма применяет свое действие параллельно к каждому состоянию суперпозиции и переизмененные резльтаты так-же формируют аналогичный тип суперпозиции. Например, учитывая: $n1 = any(1,4,9); $r1 = sqrt($n1); $n2 = all(1,4,9); $r2 = pow($n2,3); $r3 = pow($n1,$r1);

тут $r1 содержит дизъюнктивную суперпозицию any(1,2,3), $r2 содержит конюнктивную суперпозицию all(1,64,729) и $r3 содержит конъюнктивную суперпозицию `any(1,4,9,16,64,81,729)'. поскольку встроенные функции sqrt и pow не знают о суперпозициях, моудль обеспечивает им механизм для информирования их относительно того, какие аргументы должны быть переделаны, чтобы образовать суперпозицию. Если вызывать use Quantum::Superpositions со списком аргументов, то список определяет, какие параметры должны быть добавлены, чтобы сохранилось состояние суперпозиции. Унарные функции и подпрограммы могут быть квантованы как-то так: sub incr { $_[0]+1 } sub numeric { $_[0]+0 eq $_[0] } use Quantum::Superpositions UNARY => ["CORE::int", "main::incr"], UNARY_LOGICAL => ["main::numeric"];

Для двойных функций и использования подпрограмм: sub max { $_[0] < $_[1] ? $_[1] : $_[0] } sub same { my $failed; $IG{__WARN__}=sub{$failed=1}; return $_[0] eq $_[1] || $_[0]==$_[1] && !$failed; } use Quantum::Superpositions BINARY => ['main::max', 'CORE::index'], BINARY_LOGICAL => ['main::same'];

Примеры, исследование простых чисел:

Программирования со скалярными суперпозициями возможно является лучшей заменой, которая привлечет к себе противников квантового исчисления: оно может оперировать с простыми числами. Здесь, например, 0(1) - проверка на простоту чиле, основанная на обычном делении: sub is_prime { my ($n) = @_; return $n % all(2..sqrt($n)+1) != 0 }

Подпрограмма берет аргумент $n и считает(парралельно) его модуль относительно каждого целого числа между 2 и sqrt($n). Происходит коньюнктивная суперпозиция модуля который в тот момент сравнивается с нулем. Такое сравнение будет истинно только в том случае, если весь модуль - не нулевой, что является критерием числа, чтобы быть простым. Так как is_prime берет скалярный параметр, то он так-же может являться суперпозицией. В качестве примера можно привести не меняющийся со временем фильтр, определяющий, является ли число частью пары из двух простых чисел: sub has_twin { my ($n) = @_; return is_prime($n) && is_prime($n+any(+2,-2); }

Множества и их пересечения:

Операции со множествами особенно просты для исполнения, если применять superimposable(нет в словаре такого слова) скаляры. Например, учитывая список значений @elems, представив его элементы как элементы множетсва, переменная $v является элементом этого множества, если: $v == any(@elems)

обратите внимение, что такой тип определений эквивалентен определению eigenstate. Та эквивалентность может использоваться, чтобы вычислять пересечения множества. Учитывая две дизъюнктивные суперпозиции $s1=any (@elems1) и $s2=any (@elems2) представляя два множества, переменные, составляющие пересечения этих двух наборов должны быть eigenstates <$s1> и $s2. Следовательно: @intersection = eigenstates(all($s1, $s2));

Этот результат может быть апроксимирован для параллельного применения к обычным элементам произвольного числа массивов: @common = eigenstates( all( any(@list1), any(@list2), any(@list3), any(@list4), ) );

Факторизация

Разложение на числе на множители так-же очень просто, если использовать суперпозиции. Коэффициенты целого числа N - все частные q от N/n(для всех положительных целых чисел n < N), которые так-же являются итегралом. Положительный номер q - floor(q)==q. Следовательно факторизовать число можно можно как-то так: sub factors { my ($n) = @_; my $q = $n / any(2..$n-1); return eigenstates(floor($q)==$q); }

Обработка запросов

Суперпозиции могут так-же применяться для поиска строки в массиве строк. Например, чтобы определить, появляется ли данная строка $target в массиве строк @db: use Quantum::Superpositions BINARY => ["CORE::index"]; $found = index(any(@db), $target) >= 0;

Определить, какая из строк базы данных содержат $target: sub contains_str { if (index($dbstr, $target) >= 0) { return $dbstr; } } $found = contains_str(any(@db), $target); @matches = eigenstates $found;

Сравнение происходит гораздо быстрее, чем это умеет делать база данных, чтобы найти единственную строчку в любой из набора в базе. sub contains_targ { if (index($dbstr, $target) >= 0) { return $target; } } $found = contains_targ($string, any(@targets)); @matches = eigenstates $found;

Или в каждой одновременно $found = contains_targ($string, all(@targets)); @matches = eigenstates $found;

Принимаются корректровки к переводу и примеры.