10.5. „Megfordítható” számítások

Ebben az alfejezetben a számításokat, mint fizikai folyamatokat vizsgáljuk, összekapcsoljuk a számítástechnikát a fizikával, ugyanis a számítások a hardver szintjén fizikai folyamatokkal valósulnak meg. A számítógépeink elektromos árammal működnek. Energiára szükség van, mert az információ feldolgozása munka. Mérnöki szempontból a számítás, illetve annak alapjai, a tranzisztorok kapcsolása, a töltés tárolása és a buszos kommunikációs technológiák. Ezekből a téglákból épült fel az első digitális számítógép és napjaink számítógépei is.

Egy áramkör lehet analóg vagy digitális. Az analóg áramkörök nagyon gyorsak és hatékonyak, de nehéz őket megtervezni, szabályozni és általában nem programozhatók. Ezzel szemben a digitális áramkörök könnyen tervezhetőek, programozhatóak. Rengeteg olyan eszközt lehet kapni, ami ebben hatékony segítséget nyújt. A digitális technika elterjedése miatt sokszor úgy gondoljuk, hogy az információ diszkrét egységben, bitben, mérhető; ezzel szemben az analóg műszerek, illetve a világ körülöttünk gyakran emlékeztethet minket, hogy ez nem teljesen így van. Az információ sokszor folytonos és rengeteg hőt (energiát) emészt fel az analóg-digitális konvertálás. Az információ diszkretizálása egy konvenció, nem pedig fizikai törvény. A számításokról való elképzeléseinket is annyira befolyásolja a digitális elektronika, hogy hajlamosak vagyunk megfeledkezni az analóg számításokról, és analóg jelfeldolgozásról, pedig ezek mindegyike jelentősen gyorsabb, illetve energiatakarékosabb, mint digitális megfelelője. A kvantumszámítások valamiképpen visszahozzák ezeket az analóg eszközöket, és tulajdonképpen ez eredményezi a kvantumszámítógépek hatalmas erejét.

Mérnöki szemszögből vizsgálva, sem a Turing-gép, sem az elterjedt magas-szintű programozási nyelvek nem teljeskörű leírásai annak, amit számításnak hívunk. Ezek mindegyike szekvenciális algoritmusleíró eszköz , így mondanak ugyan valamit általánosan a számítógépekről, mint gépekről és talán egy nagyon keveset a párhuzamos számításokról és a kommunikációról is, de semmit sem a számítások termodinamikájáról.

Egy művelet (logikailag) megfordítható, ha az eredményéből egyértelműen kikövetkeztethető a bemenete. A legtöbb logikai kapu irreverzibilis, vagyis nem megfordítható. Az információelméletben a Shannon-féle entrópiát használják az információ mennyiségének mérésére. Ennek megfelelően egy irreverzibilis logikai kapuval elvégzett művelet során változik a rendszer entrópiája. Az információelméletbeli entrópiaforgalom szorosan összefügg a termodinamikai entrópia fogalmával. Ily módon az információelmélet és a fizika is szoros kapcsolatban állnak. Példaképpen egy bit információ törlésénél legkevesebb Joule hő keletkezik, ahol a környezet hőmérséklete (Kelvinben mérve), ahol a számítás végbemegy, pedig a Boltzmann állandó (ami a mikro- és makrovilág mértékegységeinek egyik összekapcsolója). Ez az eredmény, ami Landauernek köszönhető, nagyon fontos a mérnököknek és fizikusoknak; viszont sem a Turing-gépet, sem az elterjedt programozási nyelveket nem lehet arra használni, hogy ilyen, fizikai szinten fontos megállapításokat felhasználhassunk a számításokról/algoritmusokról melyeket leírunk általuk.

Vegyük észre, hogy bármely nem egybemenetű (de egykimenetű) logikai kapu számítása elvesztett információt eredményez. Például a klasszikus számítások univerzális kapuja a NAND kapu információt veszít: A kaput a következő formulával írhatjuk le: . Ha a jobb oldali érték 1, akkor . Ez azt jelenti, hogy vagy vagy mindkettő 0, de nem tudjuk, hogy melyik. Ez az információ elvész, tehát hőnek kell keletkeznie.

Ezt az észrevételt felhasználhatjuk, mint feltételt a számítások során ellenőrzésre is. Miután különböző számításokat elvégeztünk, egyszerűen vizsgáljuk meg, hogy mennyi hőt generáltunk a lépéseinknek megfelelően. Amennyiben nem generáltunk hőt, abban az esetben valószínűleg semmivel sem kerültünk közelebb a megoldáshoz. Ebben az elgondolásban a számítást, mint fizikai folyamatot vizsgáltuk.

A hő és a munkavégzés a fizikában közeli kapcsolatban vannak. Ahhoz, hogy egy hőerőgépet munkára bírjunk, egy bizonyos mennyiségű hőt el kell pazarolnunk. Ez az eredmény Carnot nevéhez fűződik (Carnot-körfolyamat).

Ezzel szemben, meglepő módon, legalább az elméletben lehetséges, hogy úgy végzünk számításokat, hogy nem veszítünk információt. Létezik egy 3-bemenetű kapu, a Toffoli kapu , ami univerzális és ugyanakkor megfordítható, tehát nem veszít információt, és ebből kifolyólag nem keletkezik hő a használata során.

A Toffoli kapu a következőképpen van definiálva:

Néha szokták nevezni vezérelt-vezérelt-negáció kapunak is. Az első két paramétert nevezhetjük vezérlő ágaknak a harmadikat pedig cél ágnak. A cél ág csak akkor változik, ha mindkét vezérlő ág értéke igaz (1) ahol a bináris összeadás operátora, vagy más néven a kizáró-vagy (XOR) operátor. (Vegyük észre, hogy és .) A jelölés megengedi a vezérlő ágak ( indexűek) és a cél ág ( indexű) szerepének permutálását, tehát ki tudjuk számolni pl. a értékét.

10.3. ábra - A Toffoli kapu diagramja.

A Toffoli kapu diagramja.

A Toffoli kapu diagramja a 10.3. ábrán látható. (Balról az input bitek, jobbra pedig az eredménybitek; annak megfelelően, ahogy egy számítást is az írási/olvasási irányunknak megfelelően balról-jobbra tekintünk. A kvantumkapukat a 12. fejezetben részletesen fogjuk ismertetni.)

Ha a helyére 1-et írunk akkor a következőt kapjuk: aminek utolsó tagja nem más, mint NAND . Tehát ahogy NAND, úgy a Toffoli kapu is univerzális, segítségével bármilyen logikai kapu szimulálható.

Ugyancsak könnyű észrevenni, hogy a kapu nem veszít információt. A felső két szálon nem vész el információ, ezért az alsón mindig újra tudjuk konstruálni az inputot segítségükkel, ha tudjuk, hogy mi az output. Valahogy az lehet az érzése egyeseknek, hogy csaltunk: A szimbólum a legalsó szálon felfogható egy egyszerű kapuként 3 bemenettel , és és egy kimenettel . Ahogy ez információt veszít, abból kifolyólag hőt is termel. A tény, hogy az input információt eltároljuk a felső két szálon, még nem változtatja meg azt, hogy maga a kapu információt veszít, és ezáltal nem visszafordítható. Ha a fenti módszer alapján próbálnánk implementálni a Toffoli kaput, nem jutnánk semmivel előrébb, ugyanúgy veszne az energia a hőtermeléssel. Ahhoz, hogy tényleg hő termelése nélkül működjön, teljesen másképpen, egy alap -as kapuként kell implementálni egyben az egész kaput.

Fredkin 3 bites kapuja a következőképpen működik

Könnyen belátható, hogy az első bemenet(ek)től függően a negáció, illetve a konjunkció művelet valósítható meg a kapu segítségével, vagyis és . Mivel pedig a negációval és a konjunkcióval minden logikai művelet megvalósítható, a Fredkin kapu is univerzális számítási értelemben. Másrészt ez a kapu is megfordítható, sőt annyival „többet tud”, mint a Toffoli kapu, hogy itt a bemeneti és a kimeneti 1-esek száma azonos bármilyen bemenet esetén. Ennek következtében ez a kapu optikai (foton alapú) megvalósításokban is jól használható, hiszen foton nem vész el és nem keletkezik (sem előre, sem visszafele követve a számítást). Látható, hogy a reverzibilis kapuk esetén a kimeneti bitek száma több, mint a hagyományos logikai kapuk esetén, ezek a felesleges bitek természetes velejárói a megfordítható kapuknak.

1982-ben javasolta Fredkin és Toffoli a biliárdgolyó számítási modell t, amely e kapuk egy valóban visszafordítható megvalósítását demonstrálja. Akárcsak a biliárdgolyók a játékban, a golyók Fredkin és Toffoli számítógépében is egymásnak és a falnak ütköznek, miközben végrehajtják a számítást. Ha az ütközések rugalmasak, és az asztalon keletkező súrlódást kiküszöbölhető, akkor ezek a számítások hő termelése nélkül zajlanának le. Persze ez a két feltétel gyakorlatilag teljesíthetetlen, így a biliárdgolyó-számítógép csak egy idealizált modell.

Ezeknek a megfordítható kapuknak fontos jelentősége van a kvantumszámításokban, mivel az általuk ihletett kvantumos kapu, a Deutsch kapu, a kvantumszámításokhoz univerzális. Ezenfelül a kvantumszámítások reverzibilisek, vagyis elvileg hőtermelés nélkül végezhetőek.

Másrészt Bennett bizonyította 1973-ban, hogy minden számítást meg lehet csinálni csupán reverzibilis (megfordítható) kapuk segítségével, vagyis nem kell megsemmisíteni a számítás közben a feleslegessé vált biteket.

Ennyi „fizikai” bevezető után, már készen állunk arra, hogy lássuk a kvantummechanikán alapuló számítási folyamatok alapjait.