Zaostřeno na spinová skla

Fyzikální hříčka, nebo princip nové generace počítačů? Jeden z pokusů o realizaci počítání způsobem fyzikálně...


Fyzikální hříčka, nebo princip nové generace počítačů?
Jeden z pokusů o realizaci počítání způsobem fyzikálně odlišným od současných
algoritmů představují kvantové počítače. Trochu v jejich stínu přitom zůstává
technologie do určité míry analogická spinová skla. V obou případech jde o
snahu přimět hmotu, aby "počítala za nás".
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.

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še 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 (poznámka redakce: v CW č. 38/2001 jsme např.
informovali o snaze připravit nekovový magnet pracující za vysokých teplot,
jehož základem by byly uhlíkové fullereny).
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,
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é vlastnosti 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? 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í (poznámka redakce: podrobněji viz CW č. 3/2003 v
článku "Optimalizačné algoritmy"), 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. 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
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í feroa
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
D. L. Stein: Spin Glasses: Still Complex After All These Years?
(www.physics.arizona.edu/~dls/
dice02.ps)
Barry A. Cipra: The Ising Model Is NP-Complete (www.siam.org/
siamnews/07-00/ising.pdf)
Další on-line texty
pespmc1.vub.ac.be/SPINGL.html
www.informatik.uni-koeln.de/
ls_juenger/research/sgs/
spinglass.html
www.iop.org/EJ/abstract/
0305-4470/20/10/036
V češtině
František Slanina: Spinová skla, Vesmír 9/1998 www.vesmir.cz/
clanek.php3?CID=1725
Peter Covenesy, Roger Highfield: Mezi chaosem a řádem, Mladá fronta, Praha,
2003









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.