Reversiibeli laskenta on laskentamalli , jossa laskentaprosessi on jossain määrin palautuva . Esimerkiksi laskentamallissa, joka käyttää tilajoukkoja ja niiden välisiä siirtymiä, laskelmien palautuvuuden välttämätön ehto on mahdollisuus rakentaa yksiselitteinen (injektiivinen) kuvaus jokaisesta tilasta seuraavaan. 1900-luvulla ja 2000-luvun alussa käännettävää laskentaa kutsutaan yleensä ei-perinteisiksi laskentamalleiksi.
Laskennallista palautuvuutta on kahta päätyyppiä: fyysisesti palautuva ja loogisesti palautuva . [yksi]
Prosessi on fyysisesti reversiibeli, jos systeemi ei ole sen päätyttyä lisännyt fyysistä entropiaansa eli prosessi on isentrooppinen . Fyysisesti käännettävät piirit: varauksen palautuslogiikka (varausta säilyttävä logiikka), adiabaattiset piirit , adiabaattiset laskelmat. Käytännössä ei-stationaarinen fysikaalinen prosessi ei voi olla täysin fyysisesti reversiibeli (isentrooppinen), mutta hyvin eristetyissä järjestelmissä approksimaatio täydelliseen palautuvuuteen on mahdollista.
Ehkä suurin kannustin tutkia käännettävän laskennan toteuttamiseen tarkoitettuja teknologioita on se, että ne näyttävät olevan ainoa tapa parantaa laskennan energiatehokkuutta yli Neumann-Landauer-periaatteen [2] [3] ennustamat perusrajat , jonka mukaan ainakin kT ln(2) lämpöä vapautuu (n. 3×10 −21 J , kun T=300K) jokaisesta bitin peruuttamattomasta operaatiosta (jos informaatiota poistetaan). 2000-luvun alussa tietokoneet haihduttivat lämpöä noin miljoona kertaa enemmän, 2010-luvun alkuun mennessä ero oli pudonnut useisiin tuhansiin [4] .
Kuten IBM:n Rolf Landauer osoitti vuonna 1961 [3] , jotta laskelma olisi fyysisesti palautuva, sen on oltava myös loogisesti palautuva . Landauerin periaatteessa hän muotoili ensimmäisenä säännön, jonka mukaan tuntemattoman informaation N bitin poistaminen liittyy aina termodynaamisen entropian kasvuun vähintään Nk ln(2). Diskreettiä determinististä laskentaprosessia kutsutaan loogisesti reversiibeliksi, jos siirtymäfunktio, joka kuvaa järjestelmän vanhan tilan uuteen, on injektiivinen (jokainen uusi tila vastaa yksiselitteisesti yhtä vanhaa tilaa), eli on mahdollista määrittää syöte looginen piirin tila tiedoista piirin lopullisesta loogisesta tilasta.
Ei-deterministisille (todennäköisyyspohjaisille tai satunnaisille) prosesseille fyysinen palautuvuus voidaan saavuttaa vähemmän tiukoilla rajoituksilla, nimittäin sillä ehdolla, että kaikkien mahdollisten alkutilojen joukko (keskimäärin) ei pienene laskennan aikana.
Yksi ensimmäisistä käänteisten laskelmien toteutuksen muunnelmista [5] ehdotettiin Charles Bennettin teoksissa., [6] [7] (IBM Research, 1973). Tällä hetkellä monet tutkijat ovat ehdottaneet kymmeniä reversiibelin laskennan käsitteitä, mukaan lukien reversiibelit logiikkaportit, elektroniset piirit, prosessoriarkkitehtuurit, ohjelmointikielet, algoritmit [8] [9] .
Käännettävien laskentakaavioiden toteuttamiseen ja niiden monimutkaisuuden ja rajoitusten arvioimiseen käytetään formalisointia käännettävien porttien - logiikkaporttien analogien - kautta. Esimerkiksi invertteriportti EI (EI) on käännettävä, koska se tallentaa tietoja. Samaan aikaan yksinomainen OR -logiikkaportti (XOR) on peruuttamaton - sen tulojen arvoja ei voida palauttaa yhdestä lähtöarvosta. XOR:n käännettävä analogi voi olla ohjattu negaatioportti ( CNOT - ohjattu EI).