Student World

***opět přinášíme jeden článek, který se zde objevil před cca 5 lety

Na rozdíl od kvantových počítačů, které jsou mediálně poměrně vděčným tématem, toho o spinových sklech dosud – alespoň v češtině – mnoho napsáno nebylo. Česky na toto téma vyšla snad pouze krátká zmínka v knize „Mezi chaosem a řádem“ a jeden článek v časopise Vesmír. Proto ani česká terminologie není dosud ustálená a v některých případech ponecháváme v závorkách anglická označení.

Nejsou skleněná

Spinová skla nejsou „skleněná“, nejde o žádné křemičitany, ale o kovové slitiny – např. železa s manganem. Struktura látky je celkově pravidelná, neexistuje ale pravidelnost v rozmístění jednotlivých typů atomů.
Tím, co nás na spinovém skle zajímá především, jsou jeho magnetické vlastnosti.

Odbočka k magnetům

Nejprve malá odbočka k magnetickým vlastnostem obecně. V případě kovů ze skupiny železa se magnetické dipóly souhlasně uspořádají a vytvoří poměrně velké oblasti tzv. domén. Pokud navíc látku v tomto stavu vystavíme vnějšímu magnetickému poli, dojde k úplnému uspořádání domén, látka se sama stane magnetem a zůstane jím i po odstranění vnějšího magnetického pole.
Toto všemu samozřejmě platí jen do určité teplotní meze. Magnetické materiály charakterizujeme tzv. Curierovou teplotou, při jejímž překročení způsobí tepelné vibrace chaos, magnetické momenty budou uspořádány náhodně a navzájem se vyruší. Mimochodem – popsaná teplotní závislost neplatí jen pro magnety kovové; vlastnosti magnetů vykazuje i řada organických látek, většina z nich ovšem tuto vlastnost ztrácí při teplotách nižších než pokojových. Výzkumné týmy se přitom snaží tuto mez zvýšit (článek o snaze připravit nekovový magnet pracující za vysokých teplot, jehož základem by byly uhlíkové fullereny http://www.scienceworld.cz/sw.nsf/ID/7E27F83748508B3EC1256E9700489D21?OpenDocument&cast=1).
Kromě feromagnetů existují také materiály antiferomagnetické, např. mangan, u nichž mají atomy naopak tendenci se uspořádat antiparalelně (sousední magnetické momenty míří opačným směrem, což vede k nulové magnetizaci nejen celkově, ale i v malém lokálním měřítku). Takové látky jsou nemagnetické za jakýchkoliv teplot.

Frustrovaná skla

Ačkoliv se zřejmě žádný psychiatr nepokusil prozkoumat duševní stav spinového skla, fyzikové si z medicíny vypůjčili termín frustrace, aby tím vyjádřili jakousi „nespokojenost této látky se sebou samou“.
Ve spinovém skle totiž neexistuje žádné jednoduché uspořádání, které by vyhovovalo všem atomům, respektive mělo nejnižší možnou energii. Třeba u slitiny železa s manganem se vedle sebe ocitnou atomy, z nichž část se chce točit „souhlasně“ a část „nesouhlasně“. Ať již dopadne natočení spinů jakkoliv, vždy bude v látce existovat relativně mnoho částic, které nemohou vhodným natočením spinu splnit svoje feromagnetické a antiferomagnetické „závazky“ se svými sousedy. Právě tuto neschopnost spinového skla dosáhnout jednoznačného rovnovážného stavu označili fyzikové jako frustraci.
Frustrovaná látka tedy zdaleka nemusí mít pouze jeden způsob natočení spinů, který zaručuje nejnižší energii, těchto stavů může být velmi mnoho – a vzhledem k počtu částic v reálném množství látky, výpočetním schopnostem současných počítačů a v neposlední řadě i úrovni poznání spinových skel pak není pro vědce vůbec snadné předpovídat chování těchto materiálů. Hovoří o neexistenci uspořádané fáze, nebo naopak o možnosti existence nové dosud neznámé fáze {equilibrium condensed disordered phase}, chaotickém chování při změně teploty (samozřejmě až do určité meze – při vyšších teplotách vše překryje šum, jakékoliv feromagnetické vlastni zmizí a problém ztrácí na zajímavosti). Samostatnou kapitolu tvoří rovněž chování spinových skel působením vnějšího magnetického pole.
Nakonec je možné, že právě obtíže spojené s vědeckým popisem spinových skel vedly k použití termínu frustrace…

Vztah k informatice

Jak ale tohle všechno souvisí s počítači zmíněnými v titulku našeho článku? První spojitost se ukázala už v polovině 70. let. D. Sherrington a S. Kirkpatrick, kteří tehdy působili jako vědci ve společnosti IBM, se rozhodli modelovat magnetické vlastnosti spinových skel na základě předpokladu, že každý jednotlivý „atomový magnet“ ve spinovém skle interaguje se všemi ostatními. Tento idealizovaný model umožnil aplikovat metody statistické mechaniky.
Následně byly na problém aplikovány optimalizační a evoluční algoritmy včetně metody simulovaného žíhání (podrobněji např. v článku „Optimalizačné algoritmy“ http://www.scienceworld.cz/sw.nsf/ID/36E02F629C5BD4D3C1256E970048C6ED?OpenDocument&cast=1), které měly odhalit, jaký stav uspořádání atomových magnetů je stabilnější než jiný, tedy rozpoznat globální a lokální extrémy.
Zkoumání spinových skel pak vedlo k modelům, které se mohou uplatnit i při návrzích některých dalších komplexních systémů – včetně neuronových sítí. I v případě spinových skel totiž platí, že drobný zásah na jednom místě může vést k přeuspořádání systému jako celku.
To ale není na spinových sklech z hlediska informatiky a kybernetiky tím nejzajímavějším. Vraťme se ještě jednou do historie…

Isingův model

Jedním ze základních modelů, které fyzika používá pro popis chování pevných látek, je tzv. Isingův model. Německý fyzik Ernst Ising tento jednoduchý matematický model vytvořil již roku 1925, aby pokud možno obecně popsal fázové přechody látek.
Model je skutečně prostý – částice látky jsou uspořádány v geometricky pravidelné struktuře, typicky v čtvercové mřížce, a interagují se svými sousedy (podle specifik konkrétních aplikací se uvažuje interakce bud jen s nejbližšími sousedy, nebo i s širším okolím). Ising s použitím jednorozměrného modelu ve své disertační práci teoreticky zkoumal chování feromagnetické látky. Jednorozměrná geometrická mřížka mu ale nestačila ani pro hrubý popis fázových přechodů v reálných feromagnetech. Uspokojivý popis feromagnetika podal až roku 1944 norský chemik Lars Onsager, pozdější laureát Nobelovy ceny, s použitím dvojdimenzionálního Isingova modelu. Jeho výsledky byly v průběhu dalších 20 let ještě zobecněny.

Orákulum pro NP problémy

V roce 1984 však bylo dokázáno, že třídimenzionální Isingův model spinových skel, případně dvojdimenzionalní model zahrnující vnější magnetické pole, představuje z hlediska propočtu možných stavů NP úplný problém (tedy zhruba řečeno problém, jehož výpočetní náročnost roste v závislosti na objemu vstupních dat – v tomto případě počtu interagujících atomů – exponenciálně).
Pro odborníky zabývající se spinovými skly bylo příslušné zjištění velmi nepříjemné, protože reálné NP úplné problémy na počítačích se současnou architekturou nikdy nebude možné uspokojivě řešit. A nyní přichází klíčová myšlenka poněkud připomínající Feynmanovu ideu kvantových počítačů.
Spinová skla přece reálně existují a vykazují konkrétní vlastnosti bez ohledu na Isingův model či výpočetní možnosti současných počítačů. Kdyby se tedy někdy podařilo „namíchat“ spinové sklo (tedy nastavit jeho lokální fero a antiferomagnetické vlastnosti) do stavu, který odpovídá konkrétní NP úplné úloze, „výpočet“ úlohy by vlastně proběhl tím, že by jednotlivé spiny zaujaly stav korespondující s řešením původní úlohy. Podobně jako u kvantových počítačů by se původní obtížná vlastnost (výpočetní náročnost) rázem změnila v obrovskou výhodu – hmota by „počítala“ za nás, my bychom pak pouze přečetli uspořádání skla a výsledek převedli do jazyka původní úlohy.
K tomu všemu zbývá dodat, že veškeré NP úplné úlohy jsou na sebe převoditelné. Pokud dokážeme efektivně řešit jednu z nich, padnou všechny – od problému obchodního cestujícího po problém splnitelnosti a řadu dalších úloh.
Na cestě k těmto aplikacím spinových skel samozřejmě stále zůstává velké množství „kdyby“. Výhodou celé technologie by snad mohl být fakt, že na rozdíl od kvantového počítání se ovšem spinová skla popisují prostřednictvím klasické fyziky, takže nemusíme vymýšlet složité postupy, jak udržet dostatečně dlouho při životě propletené stavy atd.

Co číst dál

Odborné články
http://www.physics.arizona.edu/~dls/dice02.ps – D. L. Stein: Spin Glasses: Still Complex After All These Years?
http://www.siam.org/siamnews/07-00/ising.pdf – Barry A. Cipra: The Ising Model Is NP-Complete

Další on-line zdroje
http://pespmc1.vub.ac.be/SPINGL.html, http://www.informatik.uni-koeln.de/ls_juenger/research/sgs/spinglass.html, http://www.iop.org/EJ/abstract/0305-4470/20/10/036

V češtině
http://www.vesmir.cz/clanek.php3?CID=1725 – František Slanina: Spinová skla, Vesmír 1998/9
Peter Covenesy, Roger Highfield: Mezi chaosem a řádem, Mladá fronta, Praha, 2003

Představte si, že např. červené atomy feromagnetické látky v naší mřížce by se „chtěly“ natočit magnetickými momenty souhlasně se svými sousedy, zatímco zelené antiforemagnetické by se naopak rády natočily naopak. Je jasné, že určení nejstabilnějšího stavu systému („jak vyhovět maximu požadavků“) představuje výpočetně extrémně náročnou úlohu.
(podle http://www.informatik.uni-koeln.de/old-ls_juenger/projects/spinglass.html)

autor Jan Poslušný