Toffoli kapısı - Toffoli gate

Toffoli kapısının devre gösterimi

İçinde mantık devreleri , Toffoli kapısı (aynı zamanda CCNOT kapısı tarafından icat), Tommaso Toffoli , evrensel bir tersinir mantık geçidi bir klasik döner devre Toffoli kapılarından inşa edilebileceği anlamına gelir. Eylemini tanımlayan "kontrollü-kontrollü değil" kapısı olarak da bilinir. 3 bitlik giriş ve çıkışlara sahiptir; ilk iki bitin her ikisi de 1'e ayarlanmışsa, üçüncü biti tersine çevirir, aksi takdirde tüm bitler aynı kalır.

Arka plan

Giriş tüketen bir mantık kapısı L , aşağıdaki koşulları karşılıyorsa tersine çevrilebilir: L ( x ) = y , herhangi bir y çıkışı için benzersiz bir x girişinin olduğu bir kapıdır . y ile x'i eşleyen bir L '( y ) = x kapısı varsa, L kapısı tersine çevrilebilir . Aşağıdaki doğruluk tablosundan görülebileceği gibi, ortak mantık kapılarından NOT, tersine çevrilebilir.

GİRİŞ ÇIKTI
0 1
1 0

Bununla birlikte, ortak AND kapısı tersine çevrilemez. 00, 01 ve 10 girişlerinin tümü 0 çıkışına eşlenir.

Tersinir kapılar 1960'lardan beri incelenmiştir. Orijinal motivasyon, ters çevrilebilir kapıların daha az ısı yaymasıydı (veya prensipte ısı yok). Bir mantık geçidinin girdisini tükettiğini düşünürsek, çıktıda girdide olduğundan daha az bilgi bulunduğundan bilgi kaybolur. Bu bilgi kaybı, termodinamik entropi ( Landauer ilkesi ) nedeniyle çevredeki alana ısı olarak enerji kaybeder . Bunu anlamanın başka bir yolu da, bir devre üzerindeki yüklerin topraklanması ve böylece durum değiştiklerinde yanlarında az miktarda enerji alarak akıp gitmesidir. Tersinir bir kapı sadece durumları hareket ettirir ve hiçbir bilgi kaybolmadığından enerji korunur.

Daha yeni motivasyon kuantum hesaplamadan geliyor . Kuantum mekaniği , dönüşümlerin tersine çevrilebilir olmasını gerektirir, çünkü kuantum mekaniği üniter teoridir ve üniter dönüşümler tersine çevrilebilir. Ayrıca, kuantum mekaniği, klasik bilgisayarlardan ( süperpozisyonlar ) daha genel hesaplama durumlarına izin verir .

Evrensellik ve Toffoli kapısı

Girdilerini tüketen ve tüm girdi hesaplamalarına izin veren herhangi bir tersinir geçit, güvercin deliği ilkesine göre, çıktı bitlerinden daha fazla girdi bitine sahip olmamalıdır . Bir giriş biti için iki olası tersinir kapı vardır. Bunlardan biri DEĞİLDİR. Diğeri, girdisini çıktıya değişmeden eşleyen kimlik kapısıdır. İki giriş biti için, önemsiz olmayan tek kapı , birinci biti ikinci bit ile XOR yapan ve ilk biti değiştirmeden bırakan kontrollü NOT kapısıdır .

Doğruluk şeması Permütasyon matris formu
GİRİŞ ÇIKTI
 0   0   0   0 
0 1 0 1
1 0 1 1
1 1 1 0

Ne yazık ki, sadece bu kapılar kullanılarak hesaplanamayan tersine çevrilebilir fonksiyonlar vardır. Diğer bir deyişle, NOT ve XOR kapılarından oluşan küme evrensel değildir . Tersinir kapıları kullanarak rastgele bir işlevi hesaplamak için başka bir kapıya ihtiyaç vardır. Bir olasılık, 1980 yılında Toffoli tarafından önerilen Toffoli kapısıdır .

Bu geçidin 3 bitlik giriş ve çıkışları vardır. İlk iki bit ayarlanmışsa, üçüncü biti çevirir. Aşağıdaki giriş ve çıkış bitlerinin bir tablosudur:

Doğruluk şeması Permütasyon matris formu
GİRİŞ ÇIKTI
 0   0   0   0   0   0 
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0

Ayrıca {a, b, c} bitlerinin {a, b, c XOR (a VE b)} ile eşlenmesi olarak da tanımlanabilir.

Toffoli kapısı evrenseldir; bu, herhangi bir Boole fonksiyonu f ( x 1 , x 2 , ..., x m ) için x 1 , x 2 , ..., x m alan Toffoli kapılarından ve bazı ekstra bit setlerinden oluşan bir devre olduğu anlamına gelir. 0 veya 1'e x 1 , x 2 , ..., x m , f ( x 1 , x 2 , ..., x m ) ve bazı ekstra bitler (çöp olarak adlandırılır) çıktılarına . Esasen bu, istenen herhangi bir Boole fonksiyonu hesaplamasını tersine çevrilebilir bir şekilde gerçekleştirecek sistemler oluşturmak için Toffoli kapılarının kullanılabileceği anlamına gelir.

İlgili mantık kapıları

Toffoli kapısı, tekli kübit kapılardan ve en az altı CNOT'tan inşa edilebilir .
  • Fredkin kapısı evrensel tersinir 3-bit kapı olduğunu takas son iki biti, ilk biti 1 ise,; kontrollü bir takas işlemi.
  • N bitlik Toffoli kapısı Toffoli kapısının bir genellemedir. Girdi olarak n bit x 1 , x 2 , ..., x n alır ve n bit çıktı verir. İlk n −1 çıkış bitleri yalnızca x 1 , ..., x n −1'dir . Son çıkış biti ( x 1 AND ... AND x n -1 ) XOR x n'dir .
  • Toffoli kapısı, beş adet iki kübitlik kuantum kapısı ile gerçekleştirilebilir , ancak beşten azının kullanılmasının mümkün olmadığı gösterilebilir.
  • İlgili bir kuantum kapısı, Deutsch kapısı , nötr atomlu beş optik darbe ile gerçekleştirilebilir. Deutsch kapısı, kuantum hesaplama için evrensel bir kapıdır.

Kuantum hesaplama ile ilişkisi

Herhangi bir tersinir kapı bir kuantum bilgisayarda uygulanabilir ve dolayısıyla Toffoli kapısı da bir kuantum operatörüdür . Bununla birlikte, Toffoli kapısı evrensel kuantum hesaplama için kullanılamaz, ancak bu, bir kuantum bilgisayarının tüm olası klasik hesaplamaları uygulayabileceği anlamına gelir. Kuantum hesaplaması için evrensel olması için Toffoli kapısının bazı doğal olarak kuantum kapı(lar) ile birlikte uygulanması gerekir. Aslında, önemsiz olmayan bir kuantum durumu yaratabilen gerçek katsayılara sahip herhangi bir tek-kübitlik geçit yeterlidir. Kuantum mekaniğine dayalı bir Toffoli kapısı Ocak 2009'da Avusturya'nın Innsbruck Üniversitesi'nde başarıyla gerçekleştirildi. Devre modeli ile bir n -qubit Toffoli'nin uygulanması 2 n CNOT kapısı gerektirirken , en iyi bilinen üst sınır 6 n -12 CNOT kapısındadır. Çok-cisim etkileşiminin uygulanması, kapının tuzaklanmış iyonlarda, Rydberg atomlarında ve süper iletken devre uygulamalarında doğrudan çalışması için kullanılabilir. Koyu hal manifoldu sonra, Khazali-Mølmer Cı n -DEĞİL kapı devre modeli paradigma ayrılmadan, sadece üç darbeleri ile çalışır.

Ayrıca bakınız

Referanslar

Dış bağlantılar