محاسبات برگشت پذیر

محاسبات برگشت پذیر به هر نوع از محاسبات گفته می شود که به‌طور کلی فرایند محاسبات از لحاظ زمانی برگشت پذیر باشد.

در نوعی از محاسبات که که از انتقال های خطی برای رفتن از یک حالت به حالتی دیگر در ماشین استفاده می کند ، یک شرط ضرروی برای برگشت پذیری آن است که رابطه بین نگاشت بین یک وضعیت به وضعیت بعدی آن باید به‌صورت یک به یک باشد. محسبات برگشت پذیر نوعی از محسابات غیر متعارف است.

با توجه به یکپارچگی ماشین های کوانتومی ، مدار های کوانتومی برگشت پذیر هستند تا وقتی که در وضعیت های کوانتومی که در حال انجام عملیات هستند دچار فروپاشی نشوند.^[۱]

دو نوع اصلی و درواقع نزدیک به یکدیگر در برگشت پذیری وجود دارد : 1. برگشت پذیری فیزیکی 2. برگشت پذیری منطقی^[۲]

یک فرایند در صورتی که منجر به افزایش آنتروپی فیزیکی نشود ، از نظر فیزیکی برگشت پذیر می باشد(ایزنتروپیک است). سبکی از طراحی مدار وجود دارد که به طور خاص این ویژگی را نشان میدهد که درواقع از آن به عنوان منطق بازیابی شارژ ، مدار های آدیاباتیک یا محاسبات آدیاباتیک یاد می شود.( برای مطالعه بیشتر به آدیاباتیک مراجعه کنید). اگرچه در عمل هیچ فرآیند فیزیکی غیرایستایی نمی‌تواند دقیقاً برگشت‌پذیر یا هم‌آنتروپی (ایزنتروپیک) باشد، هیچ محدودیت شناخته‌شده‌ای برای نزدیکی به برگشت‌پذیری کامل وجود ندارد، به‌شرطی که سیستم به اندازه کافی از تعامل با محیط‌های خارجی ناشناخته ایزوله شده باشد و قوانین فیزیکی توصیف‌کننده تکامل سیستم به‌طور دقیق شناخته شده باشند.

یکی از انگیزه‌های مطالعه فناوری‌هایی که به دنبال پیاده‌سازی محاسبات برگشت‌پذیر هستند، این است که پیش‌بینی می‌شود این فناوری‌ها تنها راه بالقوه برای بهبود بهره‌وری انرژی محاسباتی (یعنی تعداد عملیات مفید انجام‌شده به ازای واحد انرژی اتلاف‌شده) فراتر از حد بنیادی فون نویمان-لاندائر ^[۳][۴] باشند، که برابر با (kT ln(2)) انرژی اتلاف‌شده به ازای هر عملیات غیرقابل‌برگشت روی یک بیت است.

اگرچه حد لاندائر در دهه ۲۰۰۰ میلیون‌ها بار کمتر از مصرف انرژی کامپیوترها و در دهه ۲۰۱۰ هزاران بار کمتر بود^[۵]، طرفداران محاسبات برگشت‌پذیر استدلال می‌کنند که این تفاوت عمدتاً به سربارهای معماری نسبت داده می‌شود که به‌طور مؤثری تأثیر حد لاندائر را در طراحی‌های مدار عملی تقویت می‌کنند. ازاین‌رو، ممکن است بدون استفاده از اصول محاسبات برگشت‌پذیر، پیشرفت فناوری عملی به‌طور قابل‌توجهی فراتر از سطوح فعلی بهره‌وری انرژی دشوار باشد.^[۶]

همان‌طور که نخستین بار توسط رالف لاندائر در زمان کار در شرکت IBM مطرح شد، ^[۷] برای اینکه یک فرآیند محاسباتی به‌صورت فیزیکی برگشت‌پذیر باشد، باید به لحاظ منطقی نیز برگشت‌پذیر باشد. اصل لاندائر این مشاهده را بیان می‌کند که پاک کردن بی‌اطلاع n بیت اطلاعات شناخته‌شده همواره باید هزینه‌ای معادل nkTln(2) در آنتروپی ترمودینامیکی به همراه داشته باشد. یک فرآیند محاسباتی گسسته و قطعی زمانی منطقی برگشت‌پذیر نامیده می‌شود که تابع انتقال آن که حالات محاسباتی قدیمی را به حالات جدید نگاشت می‌کند، یک تابع یک‌به‌یک باشد؛ به عبارت دیگر، حالت‌های منطقی خروجی به طور منحصربه‌فرد حالت‌های منطقی ورودی عملیات محاسباتی را تعیین کنند.

برای فرآیندهای محاسباتی که غیرقطعی هستند (به این معنا که احتمال‌محور یا تصادفی‌اند)، رابطه بین حالات قدیمی و جدید یک تابع تک‌مقداری نیست. در این موارد، شرط لازم برای دستیابی به برگشت‌پذیری فیزیکی کمی ضعیف‌تر می‌شود، به این معنا که اندازه مجموعه‌ای از حالت‌های اولیه ممکن نباید، به طور میانگین، با پیشرفت محاسبه کاهش یابد

اصل لاندائر (و در واقع، قانون دوم ترمودینامیک) را می‌توان به‌عنوان نتیجه منطقی مستقیم برگشت‌پذیری ذاتی فیزیک در نظر گرفت. این برگشت‌پذیری در فرمول‌بندی کلی همیلتونی مکانیک بازتاب یافته است و به‌طور خاص‌تر در عملگر تک‌وحدتی تکامل زمانی در مکانیک کوانتومی نمود پیدا می‌کند.^[۸]

پیاده‌سازی محاسبات برگشت‌پذیر در واقع به یادگیری نحوه‌ی توصیف و کنترل دینامیک فیزیکی مکانیزم‌ها برای انجام عملیات محاسباتی مطلوب با دقتی بالا منجر می‌شود، به‌گونه‌ای که در هر عملیات منطقی، مقدار کل عدم قطعیت در مورد حالت فیزیکی کامل مکانیزم تقریباً ناچیز باشد. به بیان دیگر، باید به‌طور دقیق وضعیت انرژی فعال دخیل در انجام عملیات محاسباتی درون ماشین را ردیابی کرده و ماشین را به گونه‌ای طراحی کرد که بخش عمده‌ای از این انرژی به شکلی سازمان‌یافته بازیابی شود و برای عملیات بعدی مجدداً استفاده شود، به‌جای اینکه به‌صورت گرما تلف شود.

اگرچه دستیابی به این هدف چالشی بزرگ در طراحی، ساخت، و توصیف مکانیزم‌های فیزیکی فوق‌العاده دقیق برای محاسبات به شمار می‌رود، در حال حاضر هیچ دلیل اساسی وجود ندارد که تصور شود این هدف در نهایت غیرقابل دستیابی است. تحقق این هدف می‌تواند در آینده امکان ساخت کامپیوترهایی را فراهم کند که برای هر عملیات منطقی مفید داخلی، بسیار کمتر از یک بیت آنتروپی فیزیکی تولید کنند (و بسیار کمتر از kTln(2) انرژی به‌صورت گرما تلف کنند).

امروزه این حوزه دارای بدنه‌ای قابل‌توجه از ادبیات علمی است. طیف گسترده‌ای از مفاهیم دستگاه‌های برگشت‌پذیر، گیت‌های منطقی، مدارهای الکترونیکی، معماری‌های پردازنده، زبان‌های برنامه‌نویسی و الگوریتم‌های کاربردی توسط فیزیکدانان، مهندسان برق و دانشمندان علوم کامپیوتر طراحی و تحلیل شده‌اند.

این حوزه پژوهشی در انتظار توسعه دقیق فناوری دستگاه‌های منطقی تقریباً برگشت‌پذیر با کیفیت بالا و مقرون‌به‌صرفه است؛ فناوری‌ای که شامل مکانیزم‌های ساعت‌زنی و همگام‌سازی با بهره‌وری انرژی بسیار بالا باشد یا با طراحی ناهمگام نیاز به این مکانیزم‌ها را برطرف کند. چنین پیشرفت‌های مهندسی اساسی برای آن ضروری است تا حجم گسترده پژوهش‌های نظری در زمینه محاسبات برگشت‌پذیر بتواند کاربردهای عملی پیدا کند و فناوری واقعی کامپیوتر را قادر سازد تا از موانع کوتاه‌مدت مرتبط با بهره‌وری انرژی، از جمله محدودیت فون نویمان-لاندائر، عبور کند. این محدودیت تنها با استفاده از محاسبات منطقی برگشت‌پذیر قابل عبور است، زیرا قانون دوم ترمودینامیک آن را تحمیل می‌کند.^[۹]

برای اینکه یک عملیات محاسباتی به لحاظ منطقی برگشت‌پذیر باشد، باید خروجی (یا حالت نهایی) عملیات بتواند از ورودی (یا حالت اولیه) محاسبه شود و برعکس. توابع برگشت‌پذیر به صورت یک‌به‌یک و پوشا (بیش‌نما) هستند. این بدان معناست که گیت‌های برگشت‌پذیر (و مدارها، یعنی ترکیب چند گیت) معمولاً تعداد بیت‌های ورودی برابر با تعداد بیت‌های خروجی دارند، به شرطی که تمام بیت‌های ورودی در عملیات مصرف شوند و همه حالت‌های ممکن ورودی/خروجی مجاز باشند.

یک گیت معکوس‌کننده (NOT) به لحاظ منطقی برگشت‌پذیر است زیرا می‌توان عملیات آن را معکوس کرد. با این حال، گیت NOT ممکن است به لحاظ فیزیکی برگشت‌پذیر نباشد، بسته به نحوه‌ی پیاده‌سازی آن.

گیت XOR غیرقابل‌برگشت است زیرا دو ورودی آن را نمی‌توان به طور منحصربه‌فرد از خروجی منفرد آن بازسازی کرد، یا به‌عبارت دیگر، به دلیل اینکه پاک کردن اطلاعات غیرقابل‌برگشت است. با این حال، نسخه برگشت‌پذیر گیت XOR، یعنی گیت کنترل‌شده NOT (CNOT)، را می‌توان با حفظ یکی از ورودی‌ها به‌عنوان خروجی دوم تعریف کرد.

نوع سه‌ورودی گیت CNOT، که گیت توفولی نامیده می‌شود، دو ورودی a,b را حفظ می‌کند و ورودی سوم c را به صورت c⊕(a⋅b) جایگزین می‌کند.

• اگر c=0، این گیت عملکرد AND را ارائه می‌دهد.
• اگر a⋅b=1، عملکرد NOT را ارائه می‌دهد.

از آنجا که AND و NOT به‌تنهایی یک مجموعه عملکردی کامل هستند، گیت توفولی یک گیت جهانی است و می‌تواند هر تابع بولی را پیاده‌سازی کند (به شرطی که تعداد کافی از بیت‌های کمکی اولیه‌شده در دسترس باشد).

به‌طور مشابه، در مدل ماشین تورینگ برای محاسبات، یک ماشین تورینگ برگشت‌پذیر ماشینی است که تابع انتقال آن معکوس‌پذیر باشد، به‌طوری که هر حالت ماشین حداکثر یک پیشینه (حالت قبلی) داشته باشد.

ایو لسر در سال 1963 در مقاله‌ای یک ماشین تورینگ برگشت‌پذیر پیشنهاد کرد، ^[۱۰] اما به نظر می‌رسد که از اصل لاندائر آگاه نبود و این موضوع را بیشتر دنبال نکرد. او بیشتر بقیه‌ی دوران حرفه‌ای خود را به زبان‌شناسی قوم‌شناسانه اختصاص داد. در سال 1973، چارلز اچ. بنت از بخش تحقیقات IBM نشان داد که یک ماشین تورینگ عمومی می‌تواند هم به لحاظ منطقی و هم به لحاظ ترمودینامیکی برگشت‌پذیر باشد، ^[۱۱] و بنابراین، در اصل قادر است تعداد دلخواهی از گام‌های محاسباتی را به ازای هر واحد انرژی فیزیکی اتلاف‌شده، در صورت اجرای به‌اندازه کافی آهسته، انجام دهد. کامپیوترهای ترمودینامیکی برگشت‌پذیر می‌توانند محاسبات مفیدی را با سرعت مفید انجام دهند، در حالی که انرژی بسیار کمتری از kT را به ازای هر گام منطقی اتلاف می‌کنند.

در سال 1982، ادوارد فردکین و توماسو توفولی کامپیوتر توپ بیلیاردی را پیشنهاد کردند؛ مکانیزمی که از کره‌های سخت کلاسیک برای انجام محاسبات برگشت‌پذیر با سرعت محدود و بدون اتلاف انرژی استفاده می‌کند، اما به هم‌ترازی اولیه‌ی کامل مسیر توپ‌ها نیاز داشت. بررسی بنت ^[۱۲] این الگوهای "براونی" و "بالستیک" را برای محاسبات برگشت‌پذیر مقایسه کرد.

علاوه بر انگیزه‌ی محاسبات با بهره‌وری انرژی بالا، گیت‌های منطقی برگشت‌پذیر بهبودهای عملی در تبدیل‌های دست‌کاری بیت در رمزنگاری و گرافیک کامپیوتری ارائه کردند. از دهه 1980 به بعد، مدارهای برگشت‌پذیر به‌عنوان اجزای الگوریتم‌های کوانتومی مورد توجه قرار گرفتند و اخیراً در فناوری‌های محاسبات نانویی و فوتونی، جایی که برخی دستگاه‌های سوئیچینگ بدون تقویت سیگنال عمل می‌کنند، علاقه‌مند شده‌اند.

بررسی‌هایی درباره مدارهای برگشت‌پذیر، روش‌های ساخت و بهینه‌سازی آن‌ها، و همچنین چالش‌های تحقیقاتی اخیر در این زمینه موجود است.^{[۱۳][۱۴][۱۵][۱۶][۱۷]}

1. ↑ Williams, Colin P. (2011). Explorations in Quantum Computing. Springer. pp. 25–29. ISBN 978-1-84628-887-6.
2. ↑ «The Reversible and Quantum Computing Group (Revcomp)».
3. ↑ Landauer, Rolf (1961), "Irreversibility and heat generation in the computing process" (PDF), IBM Journal of Research and Development, 5 (3): 183–191, doi:10.1147/rd.53.0183, retrieved 2015-02-18, The entropy of a closed system, e.g., a computer with its own batteries, cannot decrease; hence this entropy must appear elsewhere as a heating effect, supplying 0.6931 kT per restored bit to the surroundings.
4. ↑ Third lecture: Statistical Theories about Information
5. ↑ Costall, B.; Naylor, R. J.; Neumeyer, J. L. (1975-11). "Dissociation by the aporphine derivatives of the stereotypic and hyperactivity responses resulting from injections into the nucleus accumbens septi". The Journal of Pharmacy and Pharmacology. 27 (11): 875–877. doi:10.1111/j.2042-7158.1975.tb10237.x. ISSN 0022-3573. PMID 1503. {{cite journal}}: Check date values in: |date= (help)
6. ↑ Michael P. Frank. Foundations of Generalized Reversible Computing. Conference on Reversible Computation, July 6–7, 2017, Kolkata, India. doi:10.1007/978-3-319-59936-6 2 Preprint available at https://www.osti.gov/servlets/purl/1456440 (PDF).
7. ↑ Landauer, R. (1961-07). "Irreversibility and Heat Generation in the Computing Process". IBM Journal of Research and Development. 5 (3): 183–191. doi:10.1147/rd.53.0183. ISSN 0018-8646. {{cite journal}}: Check date values in: |date= (help)
8. ↑ Frank, Michael P.; Shukla, Karpur (2021-06-01). "Quantum Foundations of Classical Reversible Computing". Entropy (به انگلیسی). 23 (6): 701. doi:10.3390/e23060701. ISSN 1099-4300. PMC 8228632. PMID 34206044.{{cite journal}}: نگهداری یادکرد:فرمت پارامتر PMC (link)
9. ↑ Marveeva, A. A.; Valueva, I. M.; Bukin, Y. V. (1975). "[Effect of the antibiotic D-cycloserine and its dimer on the activity of tyrosine aminotransferase in liver tissue of intact, adrenalectomized and hypophysectomized rats]". Voprosy Meditsinskoi Khimii. 21 (3): 272–276. ISSN 0042-8809. PMID 1901.
10. ↑ Lecerf (Y.): Logique Mathématique : Machines de Turing réversibles. Comptes rendus des séances de l'académie des sciences, 257: 2597–2600, 1963.
11. ↑ C. H. Bennett, "Logical reversibility of computation", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973
12. ↑ Bennett, Charles H. (1982-12). "The thermodynamics of computation—a review". International Journal of Theoretical Physics (به انگلیسی). 21 (12): 905–940. doi:10.1007/BF02084158. ISSN 0020-7748. {{cite journal}}: Check date values in: |date= (help)
13. ↑ Rolf Drechsler, Robert Wille. From Truth Tables to Programming Languages: Progress in the Design of Reversible Circuits. International Symposium on Multiple-Valued Logic, 2011. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf
14. ↑ Bezborodova, S. I.; Markelova, N. Y.; Gulayeva, V. I. (1975). "[Specificity of extracellular alkaline RNAase from Penicillium chrysogenum 152A]". Biokhimiia (Moscow, Russia). 40 (3): 592–597. ISSN 0320-9725. PMID 1110.
15. ↑ Rolf Drechsler and Robert Wille. Reversible Circuits: Recent Accomplishments and Future Challenges for an Emerging Technology. International Symposium on VLSI Design and Test, 2012. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf
16. ↑ Cohen, Eyal; Dolev, Shlomi; Rosenblit, Michael (2016-04-26). "All-optical design for inherently energy-conserving reversible gates and circuits". Nature Communications. 7: 11424. doi:10.1038/ncomms11424. ISSN 2041-1723. PMC 4853429. PMID 27113510.
17. ↑ "Reports of six individual workshops". Nursing Mirror and Midwives Journal. 142 (2): 56–59. 1976-01-08. ISSN 0143-2524. PMID 1711.