Reversibel beräkning är en beräkningsmodell där beräkningsprocessen är något reversibel . Till exempel, i en beräkningsmodell som använder uppsättningar av tillstånd och övergångar mellan dem, är en nödvändig förutsättning för reversibiliteten av beräkningar möjligheten att konstruera en entydig (injektiv) mappning av varje tillstånd till nästa. För 1900-talet och början av 2000-talet brukar reversibel datoranvändning kallas icke-traditionella datormodeller.
Det finns två huvudtyper av beräkningsreversibilitet: fysiskt reversibel och logiskt reversibel . [ett]
Processen är fysiskt reversibel om systemet inte har ökat sin fysiska entropi efter dess slutförande, det vill säga processen är isentropisk . Fysiskt reversibla kretsar: laddningsåtervinningslogik (laddningsbevarande logik), adiabatiska kretsar , adiabatiska beräkningar. I praktiken kan en icke-stationär fysisk process inte vara fullständigt fysiskt reversibel (isentropisk), men för välisolerade system är en approximation till fullständig reversibilitet möjlig.
Det kanske största incitamentet för att utforska teknologier för att implementera reversibel datoranvändning är att de verkar vara det enda sättet att förbättra energieffektiviteten för beräkningar bortom de grundläggande gränserna som förutsägs av Neumann-Landauer-principen [2] [3] , enligt vilken åtminstone kT ln(2) värme frigörs (ca 3×10 −21 J vid T=300K) för varje irreversibel operation på en bit (när en bit av information raderas). I början av 2000-talet avledde datorer ungefär en miljon gånger mer värme, i början av 2010-talet hade skillnaden sjunkit till flera tusen [4] .
Som visades av Rolf Landauer från IBM 1961 [3] , för att en beräkning ska vara fysiskt reversibel måste den också vara logiskt reversibel . I Landauers princip var han den förste att formulera regeln enligt vilken radering av N bitar av okänd information alltid är associerad med en ökning av termodynamisk entropi med åtminstone Nk ln(2). En diskret deterministisk beräkningsprocess kallas logiskt reversibel om övergångsfunktionen som mappar systemets gamla tillstånd till det nya är injektiv (varje nytt tillstånd motsvarar unikt ett gammalt tillstånd), det vill säga det är möjligt att bestämma ingångslogiken kretsens tillstånd från information om kretsens slutliga logiska tillstånd.
För icke-deterministiska (probabilistiska eller slumpmässiga) processer kan fysisk reversibilitet uppnås under mindre stränga restriktioner, nämligen under förutsättning att mängden av alla möjliga initiala tillstånd (i genomsnitt) inte minskar under beräkningen.
En av de första varianterna [5] av implementeringen av reversibla beräkningar föreslogs i verk av Charles Bennett, [6] [7] (IBM Research, 1973). För närvarande har dussintals koncept för reversibel beräkning föreslagits av många forskare, inklusive reversibla logiska grindar, elektroniska kretsar, processorarkitekturer, programmeringsspråk, algoritmer [8] [9] .
För implementering av reversibla beräkningsscheman och uppskattningar av deras komplexitet och begränsningar, används formalisering genom reversibla grindar - analoger av logiska grindar. Till exempel är invertergrinden INTE (NOT) reversibel, eftersom den lagrar information. Samtidigt är den exklusiva ELLER- logikgrinden (XOR) irreversibel - värdena på dess ingångar kan inte återställas från ett enda utgångsvärde. En reversibel analog av XOR kan vara en kontrollerad negationsgrind ( CNOT - controlled NOT).