Обратими изчисления
Обратимо изчислениее изчислителен модел, при който изчислителният процес е донякъде обратим. Например, в изчислителен модел, който използва набори от състояния и преходи между тях, необходимо условие за обратимостта на изчисленията е възможността за конструиране на недвусмислено (инжективно) преобразуване на всяко състояние в следващото. За 20-ти век и началото на 21-ви век обратимите изчисления обикновено се наричат нетрадиционни изчислителни модели.
Съдържание
Има два основни типа обратимост на изчисленията:физически обратимаилогически обратима. [1]
Процесът е физически обратим, ако след завършването си системата не е увеличила физическата си ентропия, т.е. процесът е изоентропичен. Физически обратими вериги: логика за възстановяване на заряда (логика за спестяване на заряд), адиабатни вериги, адиабатни изчисления. На практика един нестационарен физически процес не може да бъде напълно физически обратим (изентропичен), но за добре изолирани системи е възможно приближение до пълна обратимост.
Вероятно най-големият стимул за изследване на технологиите за внедряване на обратими изчисления е, че те изглеждат единственият начин за подобряване на енергийната ефективност на изчисленията отвъд фундаменталните граници, предвидени от принципа на Нойман-Ландауер [2] [3], според който се отделя понеkTln(2) топлина (около 3×10 −21 J при T=300K) за всяка необратима операция на бит ( при изтриване на малко информация). В началото на 21 век компютрите отделяха около милион пъти повече топлина, а в началото на 2010-те разликата спадна до няколко хиляди [4] .
Както е показано от Ролф Ландауер ( англ. ) от IBM през 1961 г. [3] , за да може процесът на изчисл.е физически обратимо, също така се изисква да бъде логически обратимо (логически обратимо). В принципа на Ландауер той беше първият, който формулира правилото, според което изтриването наNбита неизвестна информация винаги е свързано с увеличаване на термодинамичната ентропия с най-малкоNkln(2). Дискретният детерминиран изчислителен процес се нарича логически обратим, ако преходната функция, която преобразува старото състояние на системата в новото, е инжективна (всяко ново състояние уникално съответства на едно старо състояние), тоест е възможно да се определи входното логическо състояние на веригата от информация за крайното логическо състояние на веригата.
За недетерминирани (вероятностни или случайни) процеси физическата обратимост може да бъде постигната при по-малко строги ограничения, а именно при условие, че наборът от всички възможни начални състояния (средно) не намалява по време на изчислението.
Един от първите варианти [5] на реализация на обратими изчисления е предложен в трудовете на Чарлз Бенет (англ.) бълг. , [6] [7] (IBM Research, 1973). Понастоящем десетки концепции за обратимо изчисление са предложени от много учени, включително обратими логически портове, електронни схеми, процесорни архитектури, езици за програмиране, алгоритми [8] [9] .
За реализацията на обратими изчислителни схеми и оценки на тяхната сложност и ограничения се използва формализация чрез обратими гейтове - аналози на логическите гейтове. Например инверторният гейт НЕ (НЕ) е обратим, тъй като съхранява информация. В същото време изключителната логическа порта ИЛИ (XOR) е необратима - стойностите на нейните входове не могат да бъдат възстановени от една изходна стойност. Обратим аналог на XOR може да бъдеконтролирана врата за отрицание (CNOT - контролирано НЕ).