گیت تفلی

گیت توفولی

در مدارهای منطقی گیت توفولی که توسط شخص توماس توفولی اختراع شده‌است یک گیت منطقی برگشت‌پذیر جامع می‌باشد. بدین معنی که هر مدار برگشت‌پذیر می‌تواند از گیتهای توفولی ساخته شود. آن همچنین به عنوان گیت "controlled-controlled-not" که عملکرد آن را بیان می‌کند شناخته شده‌است. گیت توفولی دارای ورودیها و خروجیهای ۳ بیتی می‌باشد. اگر دو بیت اول یک شوند، بیت سوم را معکوس می‌کند، در غیر اینصورت همه بیتها به همان صورت باقی می‌مانند.

Circuit representation of Toffoli gate

گیت منطقی L بازگشت‌پذیر می‌باشد اگر برای هر خروجی Y یک ورودی منحصربفرد X وجود داشته باشدبه طوری که L(X)=Yهمواره برقرار باشد. اگر یک گیت L برگشت‌پذیر باشد آنگاه یک گیت برگشت‌پذیر L’ وجود دارد به گونه‌ای که Y را به X نگاشت کند تا معادله L’(Y)=X برقرار باشد. از گیت‌های منطقی رایج گیت Not همانگونه که در جدول صحت زیر دیده می‌شود بازگشت‌پذیر می‌باشد.

INPUT	OUTPUT
۰	۱
۱	۰

به هر حال گیت عمومی AND بازگشت‌پذیر نمی‌باشد. همه ورودیهای ۰۰ , ۰۱ و ۱۰ به خروجی ۰ نگاشت می‌شوند. گیتهای بازگشت‌پذیر از زمان ۱۹۶۰ مورد مطالعه قرار گرفته‌اند. انگیزه اصلی این بود که گیتهای برگشت‌پذیر حرارت بسیار کمی از خود تولید می‌کنند (یا در اصل بدون حرارت هستند). در یک گیت معمولی حالات ورودی گم می‌شوند، بخاطر اینکه اطلاعاتی که در خروجی ظاهر می‌شوند نسبت به اطلاعاتی که در ورودی ظاهر می‌شوند کمتر است. این گم شدن اطلاعات باعث هدر رفتن انرژی به پیرامون به صورت گرما می‌شود .(بخاطر خاصیت Thermodynamic entropy)

انگیزه اخیر بیشتر از محاسبه کوانتومی سرچشمه می‌گیرد. ماشینهای کوانتومی به دگرگونیهایی نیاز دارند که بازگشت‌پذیر باشند، اما اجازه محاسبات حالات عمومی بیشتری را می‌دهد (انطباق). بنابراین گیتهای برگشت‌پذیر تشکیل زیرمجموعه‌ای از گیتها را می دهندکه به وسیلهٔ ماشینهای کوانتومی تأیید شده‌اند واگر ما بتوانیم چیز قابل برگشتی را محاسبه کنیم ما همچنین می‌توانیم آن را روی کامپیوتر کوانتومی محاسبه کنیم.

گیت توفولی و جامعیت

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

Truth table	Permutation matrix form
INPUT OUTPUT ۰ ۰ ۰ ۰ ۰ ۱ ۰ ۱ ۱ ۰ ۱ ۱ ۱ ۱ ۱ ۰	${\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\\end{bmatrix}}$

متأسفانه توابع برگشت‌پذیری وجود دارد که نمی‌توانند توسط گیتهای دیگری محاسبه شوند. به عبارت دیگر مجموعه تشکیل شده از گیتهای NOT و XOR جامع نیستند. اگر ما بخواهیم یک تابع دلخواه را با استفاده از گیتهای برگشت‌پذیر محاسبه کنیم به گیت دیگری نیاز داریم که گیت توفولی می‌باشد که توسط توفولی در سال ۱۹۸۰ مطرح گردید. این گیت ورودیها و خروجیهای ۳ بیتی دارد. اگر دو بیت اول ۱ باشند آن بیت سوم را معکوس می‌کند. جدول زیر بیتهای ورودی و خروجی را نشان می‌دهد.

Truth table	Permutation matrix form
INPUT OUTPUT ۰ ۰ ۰ ۰ ۰ ۰ ۰ ۰ ۱ ۰ ۰ ۱ ۰ ۱ ۰ ۰ ۱ ۰ ۰ ۱ ۱ ۰ ۱ ۱ ۱ ۰ ۰ ۱ ۰ ۰ ۱ ۰ ۱ ۱ ۰ ۱ ۱ ۱ ۰ ۱ ۱ ۱ ۱ ۱ ۱ ۱ ۱ ۰	${\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\\\end{bmatrix}}$

آن همچنین می‌تواند به عنوان نگاشت بیتهای b , a و c به b , a و c (a AND b) XOR تشریح شوند. گیت توفولی جامع می‌باشد، یعنی اینکه برای هر تابع منطقی (f(x1,x2,…xm یک مدار که از گیتهای توفولی تشکیل شده‌است وجود دارد که x1 ,x2, … xm و تعدادی مجموعه بیتهای صفر و یک را می‌گیرد و خروجیهای x1 ,x2, … xm و تعدادی بیتهای اضافی را تولید می‌کند. در اصل به این معنی است که می‌توان از گیتهای تفلی برای ساخت سیستمهایی استفاده کرد که هر تابع حقیقی را در راستای بازگشت پذیری محاسبه و اجرا می‌کند.

ارتباط با محاسبات کوانتومی

هر گیت بازگشت پذیری می‌تواند روی یک کامپیوتر کوانتومی اجرا شود. از این رو گیت توفولی یک عملگر کوانتومی می‌باشد، به هرحال گیت توفولی نمی‌تواند برای محاسبات کوانتومی جهانی مورد استفاده قرار گیرد، گرچه معنی آن این است که یک کامپیوتر کوانتومی می‌تواند تمامی محاسبات کلاسیک ممکن را اجرا کند. گیت تفلی با موفقیت در ژانویه سال ۲۰۰۹ در دانشگاه اینسبراک اتریش منتشر شد.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Toffoli gate». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۵ آوریل ۲۰۱۴.