گیت تفلی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

گیت تفلی

در مدارهای منطقی گیت تفلی که توسط شخص توماس تفلی اختراع شده است یک گیت منطقی برگشت‌پذیر جامع می‌باشد. بدین معنی که هر مدار برگشت‌پذیر می‌تواند از گیتهای تفلی ساخته شود. آن همچنین به عنوان گیت "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»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۵ آوریل ۲۰۱۴).