Reverzibilní počítání je výpočetní model, ve kterém je proces výpočtu poněkud reverzibilní . Například ve výpočtovém modelu, který využívá množiny stavů a přechodů mezi nimi, je nutnou podmínkou reverzibility výpočtů možnost sestrojit jednoznačné (injektivní) zobrazení každého stavu do dalšího. Pro 20. století a počátek 21. století jsou reverzibilní výpočty obvykle označovány jako netradiční výpočetní modely.
Existují dva hlavní typy výpočetní vratnosti: fyzicky reverzibilní a logicky reverzibilní . [jeden]
Proces je fyzicky reverzibilní, pokud po jeho dokončení systém nezvýšil svou fyzickou entropii , to znamená, že proces je izoentropický . Fyzikálně reverzibilní obvody: logika obnovy náboje (logika zachování náboje), adiabatické obvody , adiabatické výpočty. Nestacionární fyzikální proces v praxi nemůže být zcela fyzikálně reverzibilní (izentropický), nicméně u dobře izolovaných systémů je přiblížení k úplné reverzibilitě možné.
Snad největší pobídkou k prozkoumání technologií pro implementaci reverzibilních výpočtů je to, že se zdají být jediným způsobem, jak zlepšit energetickou účinnost výpočtů nad základní limity předpokládané Neumannovým-Landauerovým principem [2] [3] , podle kterého alespoň Při každé nevratné operaci na bitu (při vymazání části informace) se uvolňuje kT ln(2) tepla (asi 3×10 −21 J při T=300K). Na začátku 21. století odváděly počítače asi milionkrát více tepla, na začátku roku 2010 se rozdíl snížil na několik tisíc [4] .
Jak ukázal Rolf Landauer z IBM v roce 1961 [3] , aby byl výpočet fyzicky vratný, musí být také logicky reverzibilní . V Landauerově principu jako první formuloval pravidlo, podle kterého je vymazání N bitů neznámé informace vždy spojeno se zvýšením termodynamické entropie alespoň o Nk ln(2). Diskrétní deterministický výpočetní proces se nazývá logicky reverzibilní, pokud je přechodová funkce, která mapuje starý stav systému na nový, injektivní (každý nový stav jednoznačně odpovídá jednomu starému stavu), to znamená, že je možné určit vstupní logický stav. stavu obvodu z informace o konečném logickém stavu obvodu.
Pro nedeterministické (pravděpodobnostní nebo náhodné) procesy lze fyzikální reverzibilitu dosáhnout za méně přísných omezení, a to za podmínky, že množina všech možných počátečních stavů (v průměru) se během výpočtu nesníží.
Jedna z prvních variant [5] implementace reverzibilních výpočtů byla navržena v dílech Charlese Bennetta, [6] [7] (IBM Research, 1973). V současné době byly mnoha vědci navrženy desítky konceptů reverzibilního počítání, včetně reverzibilních logických hradel, elektronických obvodů, architektur procesorů, programovacích jazyků, algoritmů [8] [9] .
Pro implementaci reverzibilních výpočtových schémat a odhadů jejich složitosti a omezení se využívá formalizace prostřednictvím reverzibilních hradel - analogů logických hradel. Například invertorová brána NOT (NOT) je reverzibilní, protože ukládá informace. Exkluzivní logická brána OR (XOR) je zároveň nevratná - hodnoty jejích vstupů nelze obnovit z jedné výstupní hodnoty. Reverzibilním analogem XOR může být řízená negační brána ( CNOT - řízené NOT).