Yıllar boyunca ara ölçümler, kuantum algoritmalarının karmaşıklığını ölçmeyi zorlaştırdı. Yeni çalışma, bu ölçümlerin gerekli olmadığını ortaya koyuyor.
Kuantum bilgisayarlar daha işlevsel hale geldikçe, onlara dair anlayışımız bulanık kaldı. İki bilgisayar bilimcisi tarafından yapılan çalışma, bu fütüristik makinelerle nelerin hesaplanabileceğine dair fikir vererek, resmin bir kısmını netleştirdi.
Ontario’daki Waterloo Üniversitesi’nden John Watrous, “Kuantum hesaplama için etkileri olan gerçekten güzel bir sonuç” dedi.
Chicago Üniversitesinden Bill Fefferman ve Zachary Remscrim tarafından Haziran 2020’de yayınlanan araştırma, herhangi bir kuantum algoritmasının nihai sonucunu değiştirmeden veya görevi yerine getirmek için gereken bellek miktarını büyük ölçüde arttırmadan, hesaplamanın ortasında gerçekleştirilen ölçümleri sürecin sonuna taşımak için algoritmanın yeniden düzenlenebileceğini kanıtlıyor. Daha önce, bilgisayar bilimciler, bu ölçümlerin zamanlamasının bellek gereksinimlerini etkilediğini ve kuantum algoritmalarının karmaşıklığına ilişkin çatallı bir görünüm yarattığını düşünüyorlardı.
Fefferman, “Bu oldukça sinir bozucuydu. İki karmaşıklık sınıfından bahsetmemiz gerekiyordu – biri ara ölçümlerle, diğeri ara ölçümler olmadan” dedi.
Bu sorun, benzersiz çalışma biçimleri nedeniyle yalnızca kuantum bilgisayarlar için geçerlidir. Kuantum bilgisayarlar ile evimizde bulunan bilgisayarlar arasındaki temel fark, her birinin bilgi depolama şeklidir. Kuantum bilgisayarlar, bilgiyi tipik bitlerin 0 ve 1’lerinde kodlamak yerine, bilgiyi kübit adı verilen bitlerin daha yüksek boyutlu kombinasyonlarında kodlar.
Bu yaklaşım, daha yoğun bilgi depolama ve bazen daha hızlı hesaplamalar sağlar. Ama aynı zamanda bir sorunu da beraberinde getirir. Bir hesaplamanın herhangi bir noktasında, bir kübitte bulunan bilgilere erişmeniz gerekiyorsa ve onu ölçerseniz, kübit, aynı anda olası bitlerin hassas bir kombinasyonundan tek bir duruma çöker ve bu sistemdeki diğer tüm kübitleri de etkileyebilir.
Bu bir sorun olabilir, çünkü neredeyse tüm algoritmalar devam ederken bir hesaplamanın değerini bilmeyi gerektirir. Örneğin, bir algoritma şöyle bir ifade içerebilir: “x değişkeni bir sayı ise onu 10 ile çarpın; değilse, kendi haline bırakın.” Bu adımları gerçekleştirmek, hesaplamada o anda x’in ne olduğunu bilmeyi gerektiriyor gibi görünüyor – Kuantum bilgisayarlar için potansiyel bir zorluk, bir parçacığın durumunu ölçmenin (x’in ne olduğunu belirlemek için) doğal olarak onu değiştiriyor olmasıdır.
Ancak 28 yıl önce, bilgisayar bilimcileri bu tür durumlardan kaçınmanın mümkün olduğunu kanıtladı. Kuantum algoritmalarında, nihai sonucu değiştirmeden ara ölçümler yapmak için bir hesaplamanın sonuna kadar bekleyebileceğimizi belirlediler.
Bu sonucun önemli bir kısmı, toplam çalışma süresini büyük ölçüde artırmadan ara ölçümleri bir hesaplamanın sonuna kadar itebileceğimizi gösterdi. Kuantum algoritmalarının bu özellikleri -ölçümlerin, cevabı ve çalışma zamanını etkilemeden ertelenebilmesi – ertelenmiş ölçüm ilkesi olarak adlandırıldı.
Bu ilke kuantum algoritmalarını güçlendirir, ancak bunun bir bedeli vardır. Ölçümleri ertelemek esasen ertelenen ölçüm başına bir ekstra kübit olmak üzere çok fazla ekstra bellek alanı kullanır. 4 trilyon bitlik klasik bir bilgisayarda, ölçüm başına bir bit önemsizken, şu anda en büyük kuantum bilgisayarlarda bulunan sınırlı sayıdaki kübit göz önüne alındığında yasaklayıcıdır.
Fefferman ve Remscrim’in çalışması bu sorunu şaşırtıcı bir şekilde çözüyor. Soyut bir ispatla, birkaç küçük gedik dışında, ara ölçümlerle hesaplanabilen herhangi bir şeyin ara ölçümsüz hesaplanabileceğini gösterdiler. Kanıtları, ara ölçümleri ertelemek için bellek açısından verimli bir yol sunuyor ve bu tür ölçümlerin yarattığı bellek sorunlarını atlatıyor.
Fefferman, “En standart senaryoda, ara ölçümlere ihtiyacınız yok” dedi.
Fefferman ve Remscrim sonuçlarına, iyi koşullandırılmış matris üssü alma adı verilen temsili bir problemin, bir bakıma, önemli özelliklere sahip farklı türde bir probleme eşdeğer olduğunu göstererek ulaştılar.
İyi koşullandırılmış matris üssü alma problemi, verilen bazı koşullar altında, bir matris türündeki belirli girdilerin değerlerini bulmanızı ister. Fefferman ve Remscrim, matris üssü almanın, ara ölçümlere izin veren diğer kuantum hesaplama problemleri kadar zor olduğunu kanıtladı. Bu problem grubuna BQL denir ve ekibin çalışması, matris üssü almanın o sınıftaki diğer tüm problemler için bir temsilci olarak hizmet edebileceği anlamına geliyor – bu nedenle matris üssü alma hakkında kanıtladıkları her şey, ara ölçümleri içeren diğer tüm problemler için de doğru.
Bu noktada, araştırmacılar daha önceki bazı çalışmalarından yararlandılar. 2016’da Fefferman ve Cedric Lin, iyi koşullandırılmış matris tersi bulma olarak adlandırılan ilgili bir problemin, BQUL adı verilen çok benzer bir problem sınıfındaki en zor probleme eşdeğer olduğunu kanıtladı. Bu sınıf, BQL’in küçük kardeşi gibidir. BQL ile aynıdır, ancak sınıftaki her problemin de aynı zamanda tersine çevrilebilir olması gerekliliği ile birlikte gelir.
Kuantum hesaplamada, tersinir ve tersinmez ölçümler arasındaki ayrım esastır. Bir hesaplama bir kübiti ölçerse, kübitin durumunu çökerterek ilk bilgilerin kurtarılmasını imkansız hale getirir. Sonuç olarak, kuantum algoritmalarındaki tüm ölçümler doğuştan geri döndürülemez.
Bu, BQUL’un sadece BQL’in tersine çevrilebilir versiyonu olmadığı anlamına gelir; aynı zamanda herhangi bir ara ölçüm olmaksızın BQL’dir (çünkü tüm kuantum ölçümleri gibi ara ölçümler, sınıfın durumunu ihlal ederek geri döndürülemez olur). 2016 çalışması, matris tersi bulmanın ara ölçümler içermeyen prototipik bir kuantum hesaplaması olduğunu kanıtladı – yani, BQUL için tamamen temsili bir problem.
Yeni makale, ara ölçümlerle ilgili tüm problemleri temsil eden iyi koşullandırılmış matris üssü alma probleminin, ara ölçümleri içermeyen tüm problemleri temsil eden iyi koşullandırılmış matris tersi bulma problemine çevrilebileceğini kanıtlayarak iki problemi birbirine bağlıyor. Başka bir deyişle, ara ölçüm içeren herhangi bir kuantum hesaplama problemi, ara ölçümler olmaksızın bir kuantum hesaplama problemine indirgenebilir.
Bu, sınırlı belleğe sahip kuantum bilgisayarlar için, araştırmacıların artık farklı türdeki kuantum algoritmalarının bellek ihtiyaçlarını sınıflandırırken ara ölçümler hakkında endişelenmelerine gerek olmadığı anlamına gelir.
2020’de Princeton Üniversitesi’nden bir grup araştırmacı – Ran Raz, Uma Girish ve Wei Zhan – bağımsız olarak, Fefferman ve Rimscrim’in çalışmasından üç gün sonra yayınladıkları makalede, biraz daha zayıf olsa da neredeyse aynı sonucu kanıtladılar. Raz ve Girish daha sonra sonucu genişleterek, daha sınırlı bir bilgisayar sınıfı için ara ölçümlerin hem zaman açısından hem de bellek açısından verimli bir şekilde ertelenebileceğini kanıtladı.
Sonuç olarak, son çalışma, sınırlı hafızalı kuantum hesaplamanın nasıl çalıştığına dair çok daha iyi bir anlayış sağlıyor. Bu teorik garanti ile araştırmacılar, teorilerini uygulamalı algoritmalara dönüştürmek için bir yol haritasına sahip olacaklar. Kuantum algoritmaları artık bir anlamda, ertelenmiş ölçümlerin maliyetleri olmadan ilerlemekte özgürdür.
BQL: Bounded-error quantum logarithmic space – Sınırlı hata kuantum logaritmik bellek
Yazar: Hüseyin Türker
Editör: Hatice Boyar
Yoruma kapalı.