Алгоритмическое охлаждение: различия между версиями

Имея на входе битовую строку длины n, распределение вероятностей которой известно и достаточно далеко от равномерного, можно использовать сжатие данных для генерации более короткой строки, скажем, из m бит, в которой энтропия каждого бита будет гораздо ближе к единице. В качестве простого примера рассмотрим строку из четырех бит со следующим распределением: <math>p_{0001} = p_{0010} = p_{0100} = p_{1000} = 1/4</math>, где <math>p_i</math> – вероятность строки i. Вероятность любого другого значения строки равна нулю, так что в сумме вероятности равны единице. Затем битовая строка может быть сжата с помощью алгоритма сжатия без потерь в 2-битовую строку, содержащую двоичное описание местоположения «1» в четырех вышеупомянутых строках. Поскольку вероятности всех этих строк равны нулю, можно также представить себе аналогичный процесс, который генерирует выходную строку той же длины n, что и входная, но при этом такую, что с помощью алгоритма сжатия на месте без потерь энтропия преобразуется в последние два бита. Например, логические вентили, оперирующие битами, могут выполнять перестановку <math>0001 \to 0000, 0010 \to 0001, 0100 \to 0010</math> и <math>1000 \to 0011</math>, тогда как другие входные строки преобразуются в выходные строки, в которых два старших значащих бита не равны нулю; например, <math>1100 \to 1010</math>. Легко заметить, что энтропия теперь полностью сосредоточена на двух наименьших значащих битах, что полезно при сжатии данных, в то время как два наибольших значащих бита имеют нулевую энтропию.

Чтобы получить некоторое представление о конструкции логических вентилей, выполняющих манипуляции с энтропией, можно ознакомиться с близким к этому процессу сценарием, который впервые был рассмотрен фон Нейманом. Он показал метод извлечения честных подбрасываний монеты, если эта монета подделана; он предложил взять пару подбрасываний подделанной монеты с результатами <math>a</math> и <math>b</math> и использовать значение <math>a</math>, обусловленное <math>a \ne b</math>. Простой расчет показывает, что <math>a = 0</math> и <math>a = 1</math> теперь получаются с равными вероятностями, и поэтому энтропия монеты <math>a</math> увеличивается в этом случае до 1. Противоположный случай, распределение вероятности <math>a</math> при <math>a = b</math>, приводит к сильно детерминированному подбрасыванию монеты, а именно к подбрасыванию (обусловленному) с большей погрешностью или меньшей энтропией. Вентили, которые меняют на противоположное значение <math>b</math>, если (и только если) <math>a = 1</math>, называются вентилями с контролируемым отрицанием. Если после применения такого вентиля получается <math>b = 1</math>, это означает, что до операции с вентилем имело место соотношение <math>a \ne b</math>, и теперь энтропия <math>a</math> равна 1. Если же после применения вентиля получается <math>b = 0</math>, это означает, что до операции с вентилем имело место <math>a = b</math>, и теперь энтропия <math>a</math> меньше своего первоначального значения.