Toffoli Kapısı

Kuantum kapıları serisinde tek kübitli kapıları ve tek kontrollü CNOT’u gördük; şimdi sıra üç kübitin aynı anda görev aldığı güçlü bir kapıda: Toffoli kapısı. Bu derste Toffoli’nin (CCNOT) ne yaptığını, matris biçimini, neden klasik hesaplamanın evrensel kapısı sayıldığını ve kuantum devrelerinde nasıl kurulduğunu sıfırdan işleyeceğiz. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin; tek kontrollü öncül için önce CNOT Kapısı dersine göz at.

Toffoli Kapısı Nedir?

Toffoli kapısı, 1980’de Tommaso Toffoli’nin tanımladığı üç kübitli bir kapıdır ve CCNOT (controlled-controlled-NOT) adıyla da anılır. İki kübit kontrol, bir kübit hedef olarak çalışır: iki kontrol birden |1⟩ iken hedef kübit ters çevrilir (|0⟩ ↔ |1⟩); kontrollerden biri bile |0⟩ ise kapı hiçbir şeye dokunmaz. Kontrollü Kapılar dersindeki hiyerarşiyle Toffoli, “iki kontrolün VE’sine bağlanmış bir X kapısı”dır.

Kural tek satıra sığar: |a, b, c⟩ → |a, b, c ⊕ (a·b)⟩; buradaki ⊕, mod 2 toplama yani XOR’dur. Sekiz olası girişi teker teker yazmak kuralı somutlaştırır:

• |000⟩ → |000⟩, |001⟩ → |001⟩, |010⟩ → |010⟩, |011⟩ → |011⟩ (en az bir kontrol 0: dokunulmaz),
• |100⟩ → |100⟩, |101⟩ → |101⟩ (tek kontrol 1: dokunulmaz),
• |110⟩ → |111⟩ ve |111⟩ → |110⟩ (iki kontrol de 1: hedef ters çevrilir).

Matris Gösterimi ve Temel Özellikler

Tabanı |000⟩, |001⟩, …, |111⟩ sırasıyla dizince Toffoli’nin 8×8 matrisi blok blok yazılır: üstte ilk altı taban durumunu yerinde bırakan 6×6’lık birim blok, altta |110⟩ ile |111⟩’yi yer değiştiren 2×2’lik X bloğu vardır. Toffoli bir permutasyon matrisidir: taban durumlarını taban durumlarına taşır, hiçbir genliğe faz eklemez. Kapı ayrıca kendi kendinin tersidir: iki kez uygulamak hedefi iki kez çevirdiği için T·T = I; dolayısıyla T† = T’dir ve özdeğerleri yalnızca +1 ile −1’dir. Üniteryenlik, Hermitlik ve permutasyon oluşu bu matris biçiminden doğrudan okunur.

Üst üste binmiş girişlerde işler ilginçleşir; küçük bir hesap yapalım. Girişimiz |1⟩ ⊗ |+⟩ ⊗ |0⟩ olsun, yani (|100⟩ + |110⟩)/√2. Toffoli yalnızca iki kontrolü de 1 olan |110⟩ terimine dokunur ve onu |111⟩’e taşır; çıkış (|100⟩ + |111⟩)/√2 olur. Bu durum |1⟩ ⊗ (|00⟩ + |11⟩)/√2 olarak yeniden yazılır — ikinci ve üçüncü kübitler artık bir Bell çiftidir. Toffoli taban durumları arasında faz üretmese de, süperpozisyonlu girişlerde dolanıklık kurabilen gerçek bir kuantum kapısıdır.

Klasik Hesaplamanın Evrensel Kapısı: Ters Çevrilebilir AND

Toffoli’nin ünü kuantumdan çok, klasik hesaplamanın bir sorunundan gelir: AND kapısı bilgi kaybeder. Çıkışa 0 okunduğunda girişin 00 mı, 01 mi, 10 mu olduğunu bilmek imkânsızdır; klasik kapılar geri döndürülemez. Toffoli bu ezmeyi kaldırır: çıkışta iki kontrol bitini ve sonucu birlikte taşır. Hedefi |0⟩’a hazırlarsan çıkışta a·b, yani AND; hedefi |1⟩’e hazırlarsan 1 ⊕ (a·b), yani NAND elde edersin. NAND’in klasik evrenselliği bilindiğinden, Toffoli klasik hesaplamanın evrensel kapısıdır — üstelik hiçbir bilgi kaybetmeden.

Bu yüzden Toffoli, tersine çevrilebilir hesaplamanın ana taşıdır: her klasik fonksiyon, çöp bitleriyle beslenip temizlenerek tersine çevrilebilir bir devreye çevrilebilir; AND benzeri işleri Toffoli üstlenir. Örneğin yarım toplayıcıda toplam biti bir CNOT ile (a ⊕ b), elde biti ise tam olarak a·b’dir ve Toffoli ile üretilir. Aynı yapı Grover oracle’larından aritmetik devrelerine kadar her yerde karşına çıkar; tersine çevrilebilirliğin kurallarını Klasik Kontrol dersinde, yakın akraba kapıyı ise Fredkin Kapısı dersinde bulursun.

Kuantum Devrelerinde Toffoli: Açılımlar ve Evrensellik

Gerçek donanım hazır bir üç kübitli kapı vermez; tek kübitli kapılar ve CNOT (ya da CZ) sunar. Bu yüzden Toffoli bir açılımla kurulur: yaygın standart açılımlardan biri 6 CNOT ile H, T ve T† dizisini birlikte kullanır; bir yardımcı kübit kabul etmek ya da görece fazlı (relative-phase) Toffoli’yle yetinmek kapı sayısını düşürür. Kapı özdeşlikleriyle düşünmek de şart: X = HZH olduğu için Toffoli, hedefe uygulanan H sandviçiyle çift kontrollü faz kapısına dönüşür — CCX = (I ⊗ I ⊗ H)·CCZ·(I ⊗ I ⊗ H). Bu tür dönüşümleri Devre Özdeşlikleri dersinde işliyoruz.

Evrensellikte iki soru netleşmelidir. Birincisi, Toffoli tek başına kuantum için evrensel değildir: |000⟩’dan başlayan bir devre asla süperpozisyon üretemez. İkincisi, taban durumlarını korumayan neredeyse herhangi bir tek kübit kapısı — Hadamard tipik örnektir — eklendiğinde küme evrensel hâle gelir; bu, Yaoyun Shi’nin 2002 makalesinin ana bulgusudur. Küme seçiminin genel mantığını Evrensel Kapı Setleri dersinde bulursun. Son not: Toffoli Clifford kümesinde değildir; hataya dayanıklı hesaplamada “Toffoli durumu”, damıtma yoluyla üretilen temel kaynaklardandır.

Sık Yapılan Hatalar ve Yanılgılar

Toffoli’de en sık düşülen beş yanılgı şunlardır:

• “Toffoli kuantum için evrenseldir” sanmak. Değil; tek başına süperpozisyon üretemez. Evrensellik için Hadamard gibi bir tek kübit kapısı gerekir.
• CCX ile CCZ’yi karıştırmak. CCX hedefi bit düzeyinde çevirir; CCZ hedefe −1 fazı koyar. H sandviçiyle birbirine dönüşürler ama aynı kapı değildirler.
• Kontrol ve hedefi şemada karıştırmak. Devre çiziminde dolu nokta (•) kontrolü, hedefteki ⊕ ise çevrilen kübiti gösterir; hedef telini ters yazmak sonucu kökten değiştirir.
• “Üç kübitli ama tamamen klasik” demek. Bell örneğinde gördüğün gibi Toffoli süperpozisyonlu girişlerde dolanıklık üretir ve Clifford kümesinin dışındadır; gerçek bir kuantum kaynağıdır.
• Hedefi hazırlamayı atlamak. AND için hedef |0⟩, NAND için |1⟩ olmalıdır; hedefi hazırlamadan hesap yaptığını sanmak, sonucu hedef girişiyle XORlamış olmaktan öteye gitmez.

Toffoli’yi doğru kurmak, oracle ve aritmetik devrelerinin kapısını aralar; devrelere nasıl yerleştiğini Kuantum Devreleri dersinde sürdüreceğiz.

Kaynaklar ve İleri Okuma

Toffoli gate — Wikipedia — kapının tanımı, doğruluk tablosu ve açılım şemaları için genel başvuru maddesi.

Elementary gates for quantum computation (Barenco ve ark., 1995) — Toffoli’nin CNOT ve tek kübit kapılarına açılımlarını sistematik biçimde veren klasik makale.

Both Toffoli and Controlled-NOT need little help to do universal quantum computation (Yaoyun Shi, 2002) — Toffoli’nin taban durumlarını korumayan az sayıda tek kübit kapısıyla evrensel hâle geldiğini gösteren makale.

Qiskit CCXGate dokümantasyonu — Toffoli’nin Qiskit’teki karşılığı CCXGate’in matrisi ve kullanımı.