Deutsch'un orijinal algoritması neden yalnızca %50 oranında başarılı oldu?

[Kemal Ayhan]

Deutsch , 1985 tarihli dönüm noktası niteliğindeki makalesinde " Kuantum teorisi, Kilise-Turing ilkesi ve evrensel kuantum bilgisayarı" hesaplamak için bir kuantum algoritması verir.G ( f) = f(0)⊕f(1)�(�)=�(0)⊕�(1)yalnızca tek bir sorguyla, ancak algoritması çoğu zaman başarısız olarak işaretliyordu. Bu soruda belirtildiği gibi ve benim anladığım kadarıyla Deutsch, yüzde elli başarısızlık olasılığını artıramayacağımızı düşünüyordu.

Ancak, Deutsch'un algoritmasını (veya Deutsch-Jozsa algoritmasını) herhangi bir hata olmadan çalıştırabileceğimizi ve devrenin "sadece" iki Hadamard'ın sorguyu sandviçlemesinden ibaret olduğunu biliyoruz. Peki Deutsch neden ilk algoritmasıyla yalnızca %50 başarı olasılığına ulaşıyor?

Henüz devre modelini kullanmıyordu ve Turing bantlarını süperpozisyonda hayal ediyordu. Süperpozisyonu düzgün bir şekilde hazırlamış ve değerlendirmiş gibi görünüyorF( X )�(�), ama müdahaleyi kapatmamak konusunda takılıp mı kaldı?

 

[Kemal Ayhan]

Deutsch hata yapmadı. Sadece orijinal algoritması faz geri tepmesini kullanmıyordu çünkü henüz keşfedilmemişti. Bu keşif bu makalede daha sonra ortaya çıktı:

Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca. Kuantum Algoritmalarına Yeniden Bakış. Londra Kraliyet Cemiyeti Bildirileri A , 454(1969): 339-354, 1998.

---

Daha fazla ayrıntı:

Deutsch'un beklenti değerinin iyileştirilememesiyle ilgili yazdıklarını okuduğumda onun sadece sınırlı bir yaklaşımı düşündüğü yönündeydi. Özellikle makalesindeki ilgili cümle şu şekildedir:

Şimdi önemsiz olmayan herhangi bir şeyi hesaplamak için gereken zamanın beklenti değerinin olduğunu göstereceğim.N�-katlama paralelleştirilebilir işleviG ( f)�(�)hepsindenN�(3.16) gibi kuantum paralelliği yoluyla elde edilen değerler, (2.11) aracılığıyla seri olarak hesaplanması için gereken süreden daha az olamaz.

Tabii ki denklem referansları makaledeki belirli denklemlere yöneliktir ve bunları burada tekrarlamayacağım, ancak asıl mesele şu ki, fonksiyonun değerinin her zaman başlatılmış bir sisteme yazıldığı (kullanmanın aksine) kendi özel yaklaşımından bahsediyor. örneğin faz geri tepmesi). Fonksiyonlardan bahsediyorN�farklı girdiler, ancak ikili girdilere odaklanırsak fikir şu ki, durumla başlarsak



12–√| 0 , f(0)⟩+12–√| 1 , f(1)⟩,12|0,�(0)⟩+12|1,�(1)⟩,


o zaman (üniteye göre) çıkaramayızF(0)⊕f(1)�(0)⊕�(1)kesin olarak, çünkü bu, ortogonal olmayan durumlar arasında ayrım yapmak anlamına gelir. Bu iddia doğrudur; ancak işlev değerlerini, başlatılmış bir kubit üzerine yazmak yerine doğrudan faza yerleştiren faz geri tepmesinin kullanılmasıyla bu durum aşılmıştır.