بخشی از مقاله
اتومات سلولي کوانتومي و کاربرد هاي آن
چکيده - از آن هنگام که ريچارد فينمن در سال ١٩٨٢ مفهوم محاسبات کوانتومي را ابداع نمود، مدل هاي مختلفي از " کامپيوتر هاي کوانتومي " پيشنهاد شده است . اين مدل ها شامل ماشين هاي تورينگ کوانتومي و مدارات کوانتومي مي شد. اين ايده که شايد قوانين معين مکانيک کوانتومي ابزارهاي محاسباتي قدرتمندي باشند، منجر به مطالعه ي مدل هاي گوناگوني از کامپيوترهاي کوانتومي شده است .
يک نوع ديگر از انواع مدل هاي محاسباتي موجود، يعني اتومات سلولي کوانتومي ( QCA) را که در واقع توسعه ي طبيعي اتومات سلولي کلاسيک (CA) است ، مطالعه مي نماييم .
کليد واژه - اتومات، کلاسيک، کوانتوم، مدارات کوانتومي ، محاسبات،
١- مقدمه
١-١-آتاماتاي سلولي کوانتمي نقطه اي اتوماتاي سلولي
آلن تورينگ در ١٩٣٦ در قضيه تاريخي اش محدوديت هاي توان محاسباتي را اثبات کرد. وي ثابت کرد که هيچ راه ميان
ُبروسريع براي پيش گويي خروجي يک برنامه دلخواه وجود ندارد.
اين قضيه مثالي از تقليل ناپذيري محاسباتي است . ولفرام حدود پنج دهه بعد چنين عنوان کرد که تقليل ناپذيري محاسباتي براي بسياري از سيستم هاي فيزيکي حقيقي برقرار است .
درسال ١٩٤٨ جان فون نويمان هنگام يافتن مدل رياضي براي رشد و نمو سلولها، اتوماتاي سلولي را ابداع کرد.
وي به پيشنهاد استن اولام از ديناميک گسسته به جاي پيوسته استفاده کرده و يک مدل دوبعدي با قابليت توليد مثل راايجاد کرد. اين مدل اولين محاسبه گر موازي است که تقليل ناپذيري محاسباتي آن ثابت شده است . بيست سال بعد جان کانوي با ارايه يک اتوماتاي سلولي دوبعدي به نام بازي زندگي اولين و ساده ترين مدل محاسبات جهاني را به وجود آورد.
اتوماتاي سلولي کاربردهاي فراواني در شاخه هاي مختلف ازعلوم مانند رياضي ، علوم کامپيوتر، شيمي ،زيست شناسي ، فيزيک و اخترشناسي دارد.درواقع اوتوماتاي سلولي لبزلري مناسب براي مدل سازي پديده هاي طبيعي با استفاده از قوانين موضعي است .
به صورت مخفف QCA نوعي فناوري محاسباتي است که جهت ساخت مدارهايي در ابعاد نانو به کار برده مي شود. اين فناوري بر پايه سلول QCA شکل گرفته است ، سلولي متشکل از چهار حفره که به صورت مربعي در کنار يکديگر قرار گرفته اند.
سلول QCA داراي دو الکترون اضافي است ، که مي توانند آزادانه بين حفره ها حرکت کنند. به طور کلي ٦ حالت مختلف براي قرار گرفتن ٢ الکترون در ٤ حفره، امکان پذير است . تمامي اين حالت پايدار نيستند زيرا بدليل وجود نيروي دافعه ي کولمبي بين الکترون ها، آن ها همواره در وضعيتي قرار مي گيرند که بيشترين فاصله را از يکديگر داشته باشند. بنا بر اين حالت هاي پايدار وقتي برقرارند که حفره ها به صورت قطري اشغال شده باشند. محل قرارگيري اين دو الکترون در حفره ها با توجه به قانون دافعه کولومب در گوشه هاي مخالف اريب خواهد بود که دو ساختار را ايجاد مي کند. اين دو ساختار دو قطب +١ و -١ را نمايش مي دهند که در محاسبات، مقدارهاي منطقي ١ و ٠ را به ترتيب به آنها نسبت مي دهيم . الکترون ها هنگام جايجايي در داخل سلول با يک حرکت غير خطي بين حفره ها تونل مي رنند.
فاصله حفره ها معمولا حدود ٢٠ نانومتر است .نيروي دافعه ي کولمبي فقط بين الکترون هاي داخل يک سلول برقرار نيست ، بلکه هر سلول نيز بر سلول هاي مجاور تاثير مي گذارد. در صورتي که دو سلول در کنار يکديگر قرار داشته باشند، همواره در وضعيتي قرار مي گيرند که نيروي دافعه ي کولمبي به حداقل برسد. از يک آرايه سلول هاي کنارهم مي توان مانند يک سيم براي انتشار اطلاعات استفاده کرد. همچنين مي توان سلول ها را به حالت ٤٥ درجه قرار داد. در هر مدار مبتني بر QCA، يک يا چند ورودي وجود دارد که مقدار آنها ثابت است . همچنين يک يا چند خروجي وجود دارد که با توجه به نوع چينش سلول ها و مقدار ورودي ها و نيرويي که الکترون هاي مجاور به هم وارد مي کنند مقدار منطقي ١ يا ٠ مي گيرند.
٢-١-مزيت استفاده از تکنولوژي QCA در مدارهاي منطقي به جاي تکنولوژي هاي سنتي :
مدارهايي که تحت تکنولوژي CMOS ساخته مي شوند تفاوت بسيار چشمگيري در مساحت و ميزان توان مصرفي نسبت به مدارهاي تحت تکنولوژي QCA دارند. بدين معني که نسبت به مدارهاي QCA مساحت بسيار زيادي اشغال مي کنند و توان مصرفيشان بسيار بسيار بيشتر است . اين گونه است که QCA با اين خصوصيات منحصر به فرد تحول بزرگي در حوزه الکترون هاي مجاور به هم وارد مي کنند مقدار منطقي ١ يا ٠ مي گيرند.علم کامپيوتر و مدارهاي منطقي به حساب مي آيد.
٣-١-مفهوم Clock در QCA :
در مدارهاي QCA،Clock در مقايسه با مدارهاي سنتي مانند عاملي الکترونيکي است که حرکت اکترون¬ها در داخل سلول را کنترل مي کند. در واقع نحوه کنترل آن به اين صورت است که اگر اطلاعاتي به قسمتي از مدار برسد که بايد با چند ورودي ديگر ترکيب شده و خروجي مطلوب را توليد کند، در صورتي که ورودي هاي ديگر ديرتر به آن قسمت مدار برسند، از انتشار اطلاعات در آن قسمت تا رسيدن ورودي هاي ديگر جلوگيري مي -کند. بدين ترتيب در واقع وجود Clock باعث ايجاد همزماني در بخش هاي مختلف مدار مي شود. هر Clock چهار فاز دارد : Switch : اين فاز نيروهاي مانع حرکت الکترون ها در داخل هر سلول شروع به افزايش مي کند و حرکت الکترون¬ها آرام آرام رو به سختي مي گرايد. Hold : در اين فاز نيروهاي مانع حرکت الکترون ها در داخل سلول به حد بيشينه خود رسيده و مکان الکترون¬ها ثابت ماقي مي ماند.
Release :در اين فاز مقدار نيروي مانع شونده رو به کاهش مي گذارد و آرام آرام الکترون ها آزاد مي شوند. Relax : در اين فاز سلول هيچ قطبيتي ندارد و الکترون ها کاملا آزادانه در داخل سلول حرکت مي کنند.
يک کامپيوتر کوانتومي کامپيوتري است که مي تواند پردازش هاي مربوط به فيزيک کوانتومي را شبيه سازي نمايد و مطابق فيزيک کوانتومي عمل مي نمايد. فينمن به اين نکته توجه کرد که انجام يک مسئله ي شبيه سازي در فيزيک کوانتومي توسط کامپيوترهايي که بر اساس فيزيک کلاسيک بنا شده اند، به گونه اي رام نشدني ظاهر مي گردد. از آنجا بود که فينمن پيشنهاد داد: شايد کامپيوترهاي کوانتومي به طور ذاتي از کاميوترهاي کلاسيک قوي تر باشند. در اين مقاله يک نوع ديگر از مدل هاي محاسباتي اتومات سلولي يعني اتومات سلولي کوانتومي (QCA) را که در واقع توسعه ي طبيعي اتومات سلولي کلاسيک (CA) است . مطالعه مي نماييم . QCA بر شبکه اي از q- ديت ها بنا شده است و قانون به روز کردن شامل عملکردهاي يکاني موضعي مي باشد که با ساير عملکردهاي نظير خود در شبکه تعويض پذير هستند. يکي از اهداف اين مدل اين است که مشابه مدل مدارات کوانتومي به عنوان مدل تئوري براي انجام محاسبات کوانتومي عمل نمايد. مزيت اصلي QCA بر مدارات کوانتومي اين است که QCA به طور قابل ملاحظه اي بسيار کمتر به سخت افزار کوانتومي وابسته است . به طور ويژه بر خلاف پياده سازي هاي مستقيم مدارات کوانتومي ، تحول سراسري شبکه در مدل QCA با فرض کنترل مستقل برq-ديت ها با هم و به طور موازي آدرس دهي مي کردند. همچنين همگن در فضا مانند شبکه هاي گازي کوانتومي ، spin chain و غيره مناسب مي باشد. برخي نتايجي که نشان دهنده ي مزيت هاي بنا کردن
مدل بر عملکرد هاي يکاني موضعي است ، نشان داده است : جهاني بودن از ديدگاه محاسباتي ، ارتباط قوي با مدل مدارات کوانتومي و پياده سازي آسان روي سخت افزار کوانتومي .
668
هر اتومات سلولي عملياتي را روي يک مجموعه متنهاي و گسسته از مقادير انجام مي دهد. اتومات سلولي ٢ در سال ١٩٤٨ توسط جان فون نويمن ٣ به عنوان يک مدل زيستي خود باز توليد ابداع شد . او مي خواست بفهمد آيا ممکن است يک ماشين انتزاعي ٤ خود باز توليد باشد؟ به عبارت ديگر آيا ماشيني هست که بتواند به طور خودکار يک کپي از خودش از خودش را بسازد؟ يک ماشين انتزاعي همچنين يک کامپيوتر انتزاعي ٥ ناميده مي شود که در نظريه ماشين ها استفاده مي گردد. در تئوري محاسبات از ماشين انتزاعي اغلب در تمامي آزمايشاتي که به محاسبه پذيري يا به تحليل پيچيدگي الگوريتم ها وابسته است استفاده مي گردد. يکي از بهترين مثال هاي اين نوع ماشين ها تورينگ است . فون نويمن به پيشنهاد اولام ٦ به جاي استفاده از ديناميک پيوسته از يک ديناميک گسسته استفاده کرد و اتوماتوني ٢- بعدي ساخت که قابليت خود باز توليد داشت . اين اتومات سلولي (CA ) ديناميک پيچيده و فضاي حالت بزرگي داشت و اولين مدل محاسباتي موازي گسسته بود که اثبات شده است يک کامپيوتر جهاني ٧ مي باشد. هر سلول اين CA در هر لحظه از زمان در يکي از ٢٩ حالت ممکن قرار داشت اما به دليل پيچيدگي زياد قواعد فون نويمن هرگز روي يک کامپيوتر اجرا نشد. ماشين هايي که بر اساس مدل CA بنا مي شدند، CAM8 ناميده مي شدند. ساختار چنين ماشين هايي از درجه ي توازي بسيار بالايي برخوردار است لذا به طور وسيعي براي شبيه سازي سيستم هايي با رفتار پيچيده مورد استفاده قرار مي گيرند.
بعد از مطالعات فون نويمن روي ساختارهاي خود باز توليد کننده مطالعات راجع به امکان استفاده ماشين هايي براي انجام محاسبات افزايش يافت که ساختارهاي خود باز توليد کننده به طور چشمگيري براي حل مسائل NP-complete مورد استفاده قرار گيرند. بيست سال بعد جان کانوي٩ مدل خود را که اکنون به بازي ١٠ مشهور است ابداع کرد. و بعد از آن در سال ١٩٨٤ در انيستيتوي Santa Fa ( که يکي از مراکز تحقيقاتي بسيار مهم در ارتباط با تئوري سيستم هاي پيچيده است ) تحقيقاتي در مورد کاربرد CA در مدل کردن سيستم هاي پيچيده انجام گرفت . در همين سال اولين کنفرانس بين المللي که منحصرًا به اتومات سلولي اختصاص داده شده بود، توسط تافلي ١١ و ولفرام١٢ در MTT سازماندهي شد. بعد از آن در سال ١٩٨٧ اولين کنفرانس بين المللي زندگي مصنوعي در لابراتوار بين المللي Los Alamosتوسط کريس لانگتن ١٣ برپا شد.
١-٤- ساختار CA بر چهار بخش اساسي مبتني است :
شبکه سلولي Lattice of cells
حالت سلول ها State of cells
همسايگي سلول ها Neighborhood of cells
