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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

**[[:fr:Yves Lecerf|ایو لسر]]** در سال 1963 در مقاله‌ای یک ماشین تورینگ برگشت‌پذیر پیشنهاد کرد،  اما به نظر می‌رسد که از اصل لاندائر آگاه نبود و این موضوع را بیشتر دنبال نکرد. او بیشتر بقیه‌ی دوران حرفه‌ای خود را به زبان‌شناسی قوم‌شناسانه اختصاص داد. در سال 1973، **[[:en:Charles H. Bennett (physicist)|چارلز اچ. بنت]]** از بخش تحقیقات IBM نشان داد که یک ماشین تورینگ عمومی می‌تواند هم به لحاظ منطقی و هم به لحاظ ترمودینامیکی برگشت‌پذیر باشد،  و بنابراین، در اصل قادر است تعداد دلخواهی از گام‌های محاسباتی را به ازای هر واحد انرژی فیزیکی اتلاف‌شده، در صورت اجرای به‌اندازه کافی آهسته، انجام دهد. کامپیوترهای ترمودینامیکی برگشت‌پذیر می‌توانند محاسبات مفیدی را با سرعت مفید انجام دهند، در حالی که انرژی بسیار کمتری از kT را به ازای هر گام منطقی اتلاف می‌کنند.

در سال 1982، **[[:en:Edward Fredkin|ادوارد فردکین]]** و **[[:en:Tommaso Toffoli|توماسو توفولی]]** کامپیوتر توپ بیلیاردی را پیشنهاد کردند؛ مکانیزمی که از کره‌های سخت کلاسیک برای انجام محاسبات برگشت‌پذیر با سرعت محدود و بدون اتلاف انرژی استفاده می‌کند، اما به هم‌ترازی اولیه‌ی کامل مسیر توپ‌ها نیاز داشت. بررسی بنت  این الگوهای "براونی" و "بالستیک" را برای محاسبات برگشت‌پذیر مقایسه کرد.

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

بررسی‌هایی درباره مدارهای برگشت‌پذیر، روش‌های ساخت و بهینه‌سازی آن‌ها، و همچنین چالش‌های تحقیقاتی اخیر در این زمینه موجود است.
رده:الکترونیک دیجیتال
رده:مدل‌های محاسباتی
رده:ترمودینامیک