Ana Sayfa Kuantum Algoritmaları Kuantum Üstünlüğü

Kuantum Üstünlüğü

976
162

Klasik bilgisayarlar tarafından çözülmesi çok uzun zaman alacak problemlerin kuantum bilgisayarlar tarafından makul sürelerde çözülebilmesi olarak özetlenebilecek kuantum üstünlüğü veya kuantum avantajı kavramı, son dönemdeki deneysel gelişmelerle birlikte popüler bilim yayınlarının gözde konularından biri olmaya başlamıştır. Ancak bunun tam olarak ne olduğu ve nasıl ortaya çıktığı çoğu zaman yanlış anlaşılmakta, bu da kuantum bilgisayarlara yönelik toplumda gerçekçi olmayan beklentilerin ortaya çıkmasına neden olmaktadır. Buna ek olarak bazı popüler bilim yazarlarının ve haber sitelerinin daha fazla okunmak için bilinçli olarak aldatıcı söylemlerde bulunması, konuyla ilgili abartılı hatta düpedüz yanlış bilgilerin yayılmasıyla sonuçlanmaktadır. Bu dezenformasyonu ortadan kaldırmak için kuantum üstünlüğünün nasıl sağlandığını ve ne tür problemler için geçerli olduğunu genel hatlarıyla anlamak önemlidir.

Öncelikle sıklıkla yanlış anlaşılan bir noktayı düzeltmek için kuantum üstünlüğünün kaynağının ne olmadığı sorusuna cevap verelim: kuantum üstünlüğünün kaynağı paralel hesaplama değildir. Klasik bilgisayarlarda paralel hesaplama, karmaşık bir işlemin parçalara bölünüp birçok işlemcide eş zamanlı olarak gerçekleştirilmesidir. Kuantum sistemlerinde süperpozisyon prensibi geçerli olduğu, yani farklı kuantum durumlarının üst üste binmesi mümkün olduğu için bu üst üste binen durumlara bilgi kodlayarak paralel hesaplamaya benzer şekilde aynı anda birçok işlem yapılabileceği ve bu şekilde bir avantaj elde edilebileceği düşünülebilir, ancak bu doğru değildir. Bunun nedeni ne kadar çok kuantum durumunu üst üste bindirirsek bindirelim, ölçüm yaptığımızda olasılıksal olarak tek bir durumu ölçebilecek olmamızdır. Yani ölçüm yapıldığı anda dalga fonksiyonu tek bir duruma çökecek ve geri kalan durumlara erişme imkanımız kalmayacaktır. Diğer durumları öğrenmek için aynı işlemi tekrar tekrar yapmamız gerekecek, bu da klasik hesaplamaya kıyasla ortaya çıkabilecek herhangi bir avantajı ortadan kaldıracaktır. Dolayısıyla bu şekilde herhangi bir avantaj elde edilemez.

Peki kuantum üstünlüğünün kaynağı paralel hesaplama değilse o zaman nedir? Bu soruya “Kuantum üstünlüğünün kaynağı süperpozisyondur” veya “Kuantum üstünlüğünün kaynağı dolanıklıktır” gibi son derece kesin ve net cevaplar vermeye çalışan araştırmacılar olmuşsa da bu tür denemeler tatmin edici cevaplar sağlamaktan uzaktır. Tüm bu kavramlar tutarlı bir teori oluşturacak şekilde birbirleriyle bağlantılı olduğu için birinin tek başına kuantum üstünlüğünün nedeni olduğunu söylemek doğru bir yaklaşım olmaz. Bunun yerine kuantum mekaniğini bir bütün olarak ele alıp hangi durumlarda avantaj sağladığını incelemek daha isabetli olacaktır. Bunu yapmak için de klasik karşılıklarına kıyasla avantaj sağlayan kuantum algoritmalarını iki sınıfa ayırabiliriz:

1) Düzensiz bir veri tabanında belirli bir veriyi bulmak.

2) Bir fonksiyonun belirli bir özelliğini (örneğin periyodunu) tespit etmek.

Bu iki durumu örnekler üzerinden inceleyelim.

Samanlıkta İğne Aramak: Grover Algoritması

Grover algoritması 1996 yılında Lov Grover tarafından ortaya atılan bir kuantum algoritmasıdır (şurada ve şurada Grover algoritmasıyla kuantum üstünlüğü sağlanması üzerine güncel bir tartışmayı okuyabilirsiniz). Düzensiz bir veri tabanında belirli bir veriyi bulmayı sağlayan bu algoritma çok kaba bir şekilde şöyle çalışır:

1) Sistem, veri tabanındaki her bir veriyi temsil eden kuantum durumlarının süperpozisyonu olarak başlatılır.

2) Aşağıda verilen Grover iterasyonu veri miktarına göre belirlenen bir sayıda tekrarlanır.

a) Süperpozisyon halindeki durumlar, temsil ettikleri verinin bulunmak istenen veri olması durumunda negatif işaret alacakları bir operatöre tabi tutulur. Başka bir deyişle aranan verinin temsil edildiği kuantum durumuna bir faz farkı eklenir.

b) Çıkan sonuca, içerdiği tüm kuantum durumlarını ortalama genliğe göre yansıtan bir operatör uygulanır.

3) Ölçüm yapılır.

Burada yapılan işlem basitçe aranan verinin genliğinin yükseltilerek ölçüm sonucunda o verinin çıkma olasılığını arttırmaktır, yani bir başka deyişle süperpozisyon halindeki durumları istenilen sonucun olasılığını yükseltecek şekilde girişime uğratmaktır. 2-a ve 2-b adımlarında yapılan işlemler birimsel (unitary) işlemler oldukları, yani toplam olasılığı korudukları için kuantum sistemleri tarafından gerçekleştirilebilen işlemlerdir.

Görsel olarak anlatmak gerekirse, Görsel 2’de görüldüğü gibi ilk olarak tüm durumların eşit genlikte olduğu bir süperpozisyon durumu yaratılır. Daha sonra aranan veriye faz eklenerek negatif işaret alması sağlanır (Görsel 3). Son olarak tüm durumlar ortalamaya göre yansıtıldığında karşımıza Görsel 4’teki gibi bir grafik çıkar. Görüldüğü gibi istediğimiz sonucun olasılık genliği artmıştır. Bu işlem tekrarlanarak genlik daha da arttırılıp ölçüm sonucunda çok yüksek olasılıkla istenen sonucun çıkması sağlanabilir.

Görsel 2 [1]
Görsel 3 [1]
Görsel 4 [1]

Fonksiyon Periyodu Bulma: Shor Algoritması

Kuantum algoritmaların klasik benzerlerine kıyasla fark yaratabileceği üzerine ilk ikna edici çalışmalar periyot bulmayla ilişkili problemler üzerinden yapılmıştır. Bunların en bilinen örneği olan Shor algoritması 1994 yılında Peter Shor tarafından, bir sayının asal çarpanlarını bulma problemine çözüm olarak ortaya atılmıştır. Bu problemin önemi, birçok şifreleme tekniğinin, çarpımları bilinen büyük asal sayıları bulmanın zorluğu üzerine inşa edilmesidir. Dolayısıyla Shor algoritması kuantum bilgisayarlar tarafından gerçekleştirilebilirse bu tür şifreleri kırmak çok kolaylaşacaktır.

Algoritmaya geçmeden önce asal çarpanları bulma probleminin periyot bulma problemine nasıl indirgenebildiğinden kısaca bahsedelim. Asal çarpanlarını bulmak istediğimiz sayıya N diyelim. N’den küçük rastgele bir pozitif sayı seçip ona da a diyelim. Bu iki sayının ortak çarpanı yoksa eğer (varsa zaten N’nin çarpanlarından biri bu ortak çarpandır), şöyle bir fonksiyon oluşturalım: f(r) = a^r (modN). Bu fonksiyon a^r N’ye bölündüğünde kalan sayıyı ifade eder. Ayrıca periyodik bir fonksiyondur ve periyodu f(r) = 1 eşitliğini sağlayan en küçük r pozitif tam sayısına eşittir. Böylece fonksiyonu bire eşitleyip denklemi düzenlersek a^r(modN) — 1 = 0 eşitliğine ulaşırız. Sağ taraftaki 0 yerine N’nin herhangi bir tamsayı katını (modN) olarak yazabileceğimiz için eşitlik k tamsayı olacak şekilde a^r — 1 = k×N (modN) şeklinde yazılabilir. r’nin çift sayı olması durumunda bu denklem (a^(r/2)–1) (a^(r/2) + 1) = k×N (modN) olarak düzenlenebilir ve bunun anlamı sol taraftaki iki çarpanla N’nin ortak çarpanlar içerdiğidir ve bu ortak çarpanlardan biri yüksek ihtimalle aradığımız çarpanlardan biridir.

Bu algoritmanın en zorlu kısmı f(r)’nin periyodunun bulunduğu kısımdır, ki kuantum hesaplama da burada devreye girer. Bir fonksiyonu frekans bileşenleri cinsinden yazmaya yarayan Fourier dönüşümüyle benzer olarak, kuantum Fourier dönüşümü adı verilen işlem süperpozisyon halindeki kuantum durumlarına uygulandığında bu durumlar arasındaki periyodik ilişkiye bağlı bir sonuç verir. Dolayısıyla bu dönüşümü kullanarak süperpozisyon halindeki durumlar şeklinde ifade edilen bir fonksiyonun periyodunu elde etmek mümkündür. Bu nedenle bu yazının amacına uygun olarak Shor algoritmasının geriye kalan kısmını ihmal edip kuantum Fourier dönüşümünün nasıl bir işlem olduğuna odaklanmak yerinde olacaktır. Bir kuantum durumunun Fourier dönüşümü basitçe onu tüm kuantum durumlarının süperpozisyonuna dönüştürmektir. Bu süperpozisyondaki her elemanın genliği dönüşüme uğrayan durum, elemanın kendisi ve toplam eleman sayısına bağlı olarak hesaplanır. Elbette dönüşüme maruz kalan durumun kendisi de süperpozisyon şeklinde ifade edilmiş olabilir. Bu durumda, işlemin doğrusallığından dolayı süperpozisyondaki her eleman ayrı ayrı dönüşüme tabi tutulup sonra toplanarak tüm ifadenin Fourier dönüşümü bulunabilir. İlk süperpozisyon periyodik bir yapı içeriyorsa, dönüşümden sonra periyodun katlarına denk gelen kuantum durumlarının genlikleri yüksek olurken diğer genlikler düşük olacaktır, ki bunun anlamı da ölçüm yapıldığında elde edilecek sonucun yüksek ihtimalle periyodun katı olacağıdır. Fiziksel olarak bu işlem bir dalgayı girişime uğratarak yapıcı girişim sayesinde istenilen kuantum durumlarında yüksek genlik elde etmeye karşılık gelir.

Sonuç Yerine: Fiziği Simüle Etmek

Bu iki örnekte görüldüğü gibi kuantum üstünlüğü temelde süperpozisyon halindeki durumların girişime uğratılmasıyla ortaya çıkmaktadır, ki zaten kuantum mekaniğinin klasik mekanikten en önemli farkı bu tür durumların oluşturulması olduğu için bu akla yatkındın. Peki buna benzer, veya bununla aynı görevi üstlenecek süreçler klasik bilgisayarlarda taklit edilebilir mi? Bu soru aslında Feynman’ın yıllar önceki konuşmasında cevapladığı “Kuantum fiziğini klasik bilgisayar kullanarak simüle edebilir miyiz?” sorusuna eşdeğerdir [6]. Feynman bu soruya “hayır” cevabını verir. Öncelikle bir kuantum sürecini klasik bilgisayarda taklit etmek için tüm olasılıkların tek tek hesaplanması gerekir, ki bu da işe yarar bir sonuç üretmek için makul sürede işlenebilecek sayıda değişkenden katbekat fazla değişkenin hesaba katılması demektir. Bunun yerine olasılıksal bir klasik bilgisayar kullanıp olasılıkları hesaplamaya çalışırsak ise yine kuantum sürecini taklit edemeyiz, çünkü süperpozisyon durumlarında girişimi açıklayabilmek için negatif olasılıklara ihtiyacımızın vardır, ki böylece kimi kuantum durumları birbirlerini güçlendirirken diğerleri birbirlerini zayıflatabilsin. Ancak klasik fizikte negatif olasılık söz konusu olamaz. Kuantum fiziğinde ise mutlak değer karesi olasılığı veren negatif hatta kompleks olasılık genlikleri tanımlanmıştır ve bunlar birbirleriyle girişim yapabilir. Dolayısıyla kuantum sistemleri klasik bilgisayarlarda tam olarak temsil edilemezler. Bu durum da, eğer uygun algoritmalar işletilirse bazı problemlerin kuantum bilgisayarlarda klasik karşılıklarına kıyasla çok daha kolay çözülebilmesine yol açar, ki kuantum üstünlüğünün altında yatan da budur.

Yazar: Yalın Başay

Kaynaklar ve İleri Okuma

[1] https://qiskit.org/textbook/ch-algorithms/grover.html

[2] https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm

[3] https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm

[4] https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html

[5] “How Quantum Computers Break The Internet… Starting Now”, https://www.youtube.com/watch?v=-UrdExQW0cs

[6] Richard P. Feynman, “Simulating physics with computers”. Int J Theor Phys 21, 467–488 (1982).

Bu içeriği paylaş
Önceki İçerikANU (The Australian National University), AWS Marketplace’te Kuantum Destekli Rastgele Sayı Oluşturucusunu (AQN) Piyasaya Sürdü!
Sonraki İçerik2022: Kuantum Bilgisayarlarının Son Durumu
Yalın Başay
Yazar, Teknik Redaktör

Yoruma kapalı.