Seyyah Satıcı Problemini Çözmek için Kuantum Hesaplaması

Bilgisayar bilimi alanındaki bir klasik algoritmik problem olan Seyyah Satıcı Problemi (TSP), bir kombinatoryal optimizasyon probleminin mükemmel bir örneğidir.

TSP nedir? Bu matematik klasikleri, N sayıda şehri exact olarak bir kez ziyaret ederek ve orijinal şehre dönmek için en kısa olası rotayı bulmayı içerir. Ancak, şehirlerin sayısı arttıkça, olası rotalar ve optimal çözümü bulmak için gereken hesaplama zamanı da artar. Bu problem yaklaşık yöntemler kullanılarak çözülebilse de, kuantum bilgisayarlar çok daha iyi çözümler sağlayabilir ve çok daha hızlı bir şekilde bunu yapabilir.

Bu, teorik fizikçi Prof. Dr. Jens Eisert’in ekibinin gösterdiği şeydir: böyle sorunlar kuantum bilgisayarlarla daha iyi ve daha hızlı çözülebilir.

Kuantum hesaplama, karmaşık sorunları klasik bilgisayarların, hatta süper bilgisayarların erişemeyeceği sorunları çözmek için kuantum mekaniğini kullanarak donanım ve algoritmalar kullanır. Güçlü olsalar da, süper bilgisayarlar -binlerce CPU ve GPU çekirdeğine sahip devasa klasik bilgisayarlar- karmaşık sorunları çözerken 20. yüzyıl transistör teknolojisine bağımlılıklarıyla sınırlıdır.

Burada kuantum fiziği devreye girer. Klasik bilgisayarların aksine, kuantum bilgisayarlar ikili bits (0’lar ve 1’ler) yerine kuantum bits veya kubitler kullanarak çok boyutlu kuantum algoritmaları çalıştırır.

Daha fazla olarak, klasik bilgisayarların aksine, kuantum bilgisayarlar fanlar yerine süper soğutulmuş süper akışkanlar kullanarak kuantum işlemcilerini son derece soğuk sıcakliklarda tutmak zorundadır.

Süper iletkenler, elektronların onlara karşı hiçbir direnç olmadan geçmesine izin veren kritik bir kuantum mekanik etkisini gösteren malzemelerdir. Elektronlar geçerken, bir yükü engeller boyunca taşımak için eşleştirilirler. İki süper iletken bir yalıtkanın her iki tarafına yerleştirildiğinde, süper iletken kubitler için kullanılan bir Josephson bağlantısı oluşturulur.

Bir kubit, kuantum bilgilerini süper pozisyon durumuna yerleştirme görevinde yararlıdır, bu da kubitin olası yapılandırmalarının bir kombinasyonudur. Süper pozisyon durumundaki kubitler grubu, karmaşık, çok boyutlu hesaplamalı alanlar oluşturabilir ve burada karmaşık sorunlar temsil edilebilir.

Burada, iki kubitin kuantum bağlantısı, birine yapılan değişikliklerin diğerini doğrudan etkileyebileceği bir durumdur ve bu bağlı kubitler süper pozisyon durumuna yerleştirildiğinde, birçok olasılık elde edilir. Kuantum bilgisayarda hesaplama, tüm olası hesaplamalı durumların süper pozisyonunu hazırlayarak ve ardından girişim yoluyla çözümler bulunarak çalışır.

Elbette, birçok kubitle bir kuantum bilgisayarı inşa etmek çok karmaşık bir işlemdir, ancak böyle bilgisayarların neler başarmabileceği konusunda çeşitli yöntemler araştırılıyor.

Helmholtz-Zentrum Berlin’de (HZB) ve kamu araştırma üniversitesi Freie Universität Berlin’de ortak bir araştırma grubunu yöneten Eisert’e göre:

“Bunda birçok efsane var ve bazen belirli bir miktar sıcak hava ve hype. Ancak, bu konuya rijit bir şekilde, matematiksel yöntemler kullanarak yaklaştık ve konuya ilişkin avantajların olabileceği anlamında net sonuçlar elde ettik.”

Kritik Seyyah Satıcı Problemi

Bir optimizasyon problemi olan TSP, lojistik ve tedarik zinciri endüstrisinde büyük ekonomik öneme sahiptir. İş zamanlamaları, kaynak tahsisi, portföy optimizasyonu ve hatta protein katlanması gibi çeşitli sektörler için kritik olan kombinatoryal optimizasyon sorunlarının daha geniş kategorisi içinde yer alır.

Bu sorunların sosyal ve ekonomik önemi nedeniyle, yoğun bir araştırma konusu olmuşlardır. Dolayısıyla, en verimli tedarik zincirini ve en ucuz teslimat rotasını bulmak gibi sorunların çözümü, günlük hayatımızda olumlu bir etkiye sahiptir.

Ancak, çoklu varış noktaları için teslimat rotalarını optimize ederken, trafik tıkanıklığı, artan operasyonel maliyetler, aniden değişen rotalar, son dakika iş toplantıları ve müşteri talepleri gibi çeşitli kısıtlamaları dikkate almak, TSP’yi çözme sorununu daha da zorlaştırır. Bu zorluklara rağmen, TSP’yi çözmek, malların verimli teslimatı için kritiktir ve bu da iş modelinin sürdürülebilir olmasını sağlar.

Bu problemi çözmek, birçok faydaya sahiptir, mesafeyi ve seyahat süresini azaltma, yakıt kullanımını tasarruf etme gibi. Seyahat edilen mesafeyi en aza indirmek, karbon ayak izini önemli ölçüde azaltabilir, bu da daha iyi hava kalitesi, yavaşlayan iklim değişikliği ve ekonomik büyüme anlamına gelir. Ayrıca, TSP’yi çözmek, malların zamanında teslim edilmesini ve müşterilerle zamanında toplantıları sağlayabilir, bu da müşteri deneyimini ve saha hizmetleri işlerini geliştirir.

Gördüğümüz gibi, problemi çözmek sadece işleri değil, bu faydaların herkesin dahil olduğu deneyimi zenginleştirmesine yol açar.

TSP sorununu çözmek için çeşitli yöntemler kullanılabilir. Bu yöntemlerden biri, en kısa rotayı bulmak için tüm olası permütasyonları hesaplayan ‘Kaba Kuvvet’ yaklaşımıdır. Şube ve sınırlama yönteminde, sorun birkaç dizi alt soruna bölünür ve her aşama çözümü, sonraki aşamalarda bulunan çözümü etkiler.

Dinamik programlamada, amaç, gereksiz hesaplamaları önlemektedir. En Yakın Komşu ise, başlangıç konumunuzla başladığınız ve sonra en yakın olanı ziyaret ettiğiniz bir yaklaşım algoritmasıdır. Tüm şehirler kapsandığında, başlangıç noktasına geri dönersiniz. Uygulamalı ve nispeten hızlı olsa da, bu yöntem her zaman verimli bir rota sağlamayabilir.

Teknoloji ilerledikçe, rota planlama ve optimizasyon çok daha etkili bir şekilde yapılabilir. Özellikle Yapay Zeka (AI), büyük miktarda veriyi hızlı bir şekilde analiz ederek modern işletmelerin operasyonel ve stratejik kararlar almasına yardımcı olabilir.

Kuantum bilgisayarlar da bu sorunu çözmek için araştırılıyor; çünkü bunlar klasik bilgisayarlara göre önemli hesaplama hızlandırmaları sunuyor. Uzun süredir, bu bilgisayarların bu sorunlara yaklaşık çözümlerini geliştirmeye yardımcı olabileceği önerildi.

TSP’yi Çözmek için Kuantum Hesaplama Tekniklerini Kullanma

Kuantum hesaplama, belirli sorunlar için vaat edilen sonuçlar sunarken büyük bir ilgi görüyor, ancak kuantum avantajının kapsamı büyük ölçüde keşfedilmemiş durumda.

Bu nedenle, çalışma, kuantum bilgisayarların klasik bilgisayarlardan daha iyi performans gösterebileceğini ve kombinatoryal optimizasyon sorunlarına yaklaşık çözümler sağlayabileceğini kanıtladı.

Eisert ve meslektaşı Jean-Pierre Seifert tarafından yürütülen son çalışma, yalnızca analitik yöntemler kullanarak, kuantum bits ile donatılmış bir kuantum bilgisayarının TSP sorununu nasıl çözebileceğini değerlendirdi.

“Basitçe, fiziksel realizasyondan bağımsız olarak, yeterli kuantum bits olduğu varsayımı ile ve bunlarla hesaplama işlemlerini nasıl gerçekleştirebileceğimizi inceliyoruz,” dedi Technical University of Berlin’den Ph.D. öğrencisi Vincent Ulitzsch.

Ardından, ekip, bir tamsayının asal faktörlerini bulmak ve bu optimizasyon sorunlarının bir alt sınıfını çözmek için Shor algoritmasını, bir kuantum algoritmasını kullandı. Böylece, hesaplama zamanı arttıkça, sorunların sayısı artık patlamayacak, sadece polinomiyal olarak artacaktır, yani Nx, burada x bir sabittir. Bu şekilde elde edilen çözüm, klasik algoritmalarla yaklaşık çözümden çok daha nitelikli olacaktır.

Kriptografik kavramlar ve hesaplama öğrenme teorisi kullanarak, çalışma “kuantum bilgisayarların, kombinatoryal optimizasyon sorunlarını yaklaşık olarak çözmekte klasik bilgisayarlara göre süper polinom bir avantaja sahip olduğunu kanıtladı”.

Çalışma, ayrıca, kuantum bilgisayarların kombinatoryal optimizasyon sorunlarının çözümüne yaklaşık çözümler sunma konusundaki potansiyelleri hakkında önemli bir soruya önemli ilerleme kaydettiğini belirtti ve bu sorunların önemli sosyal ve ekonomik etkileri vardır.

Çalışma, Einstein Araştırma Birimi, Berlin Matematik Araştırma Merkezi (MATH+ Mükemmellik Kümesi), BMBF (Hibrit), BMWK (EniQmA), Münih Kuantum Vadisi ve DFG tarafından finanse edildi. Almanya’nın Federal Eğitim ve Araştırma Bakanlığı da mali destek sağladı.

Kuantum Hesaplamasının Potansiyelini Araştırma

Bu, kuantum hesaplamasının TSP sorununu çözmek için kullanıldığı ilk kez değildi. Birçok meraklı ve araştırmacı, kuantum hesaplamasını kullanarak bu sorunu çözmeye bakıyordu.

2022 Aralık ayında, bir makale, TSP için Grover Adaptive Search (GAS) temelinde bir kuantum algoritması önerdi. GAS çerçevesi altında, iki temel zorluk vardır – çözümler uygulanabilir olmayabilir ve mevcut kuantum bilgisayarlarının kubit sayısı çok sınırlıdır ve kombinatoryal optimizasyon sorunları için kuantum algoritmalarının minimum gereksinimlerini karşılayamaz, bu da uygulamalarını kısıtlar.

Bu nedenle, makale, uygulamalı olmayan çözümleri otomatik olarak algoritma yürütme sırasında kaldıran Hamiltonian Cycle Detection (HCD) oracle’yi geliştirdi. Ayrıca, kuantum hesaplamasının tersinebilirlik gereksinimini tam olarak dikkate alarak ve kullanılan kubilerin basitçe üzerine yazılmaması veya serbest bırakılmamasının zorluğunu aşarak, “anchor register” stratejisi tasarladılar. Bu, sadece 31 kubite ihtiyaç duyulmasını sağladı ve çözüme ulaşma oranı %86,71 idi.

2019 yılında, kendini fizik bilgini olarak tanımlayan Joseph Cammidge yazdı, bir soğuma kuantum işlemcisi kullanarak, yedi şehri çözebileceğini ve teknoloji sınırlamaları ortadan kaldırılırsa dokuz şehri çözebileceğini belirtti.

Yeni bir hesaplama yöntemi olan Kuantum Soğuma, optimizasyon sorunlarını klasik tekniklerden daha hızlı çözebilme potansiyeline sahiptir. Teorisi, kubilerin optimal düşük enerji durumuna ulaşacağını öngörür.

Ancak, 2021 yılında, bir çalışma, kuantum annealer’in sadece 8 veya daha az düğüm boyutunda bir sorunu işleyebileceğini ve hem zaman hem de doğruluk açısından klasik çözücüye göre performansının daha düşük olduğunu buldu.

TSP sorununu çözmek için kuantum hesaplamasının kullanımı uzun süredir devam ediyor. İki thập yıl önce, 2001 yılında, bir çalışma, bu sorunu çözmek için bir kuantum algoritması aramaya başladı.

Makalede, Alabama Üniversitesi’nden Buckley Hopper, Grover ve Shor’un kuantum bilgisayar algoritmalarını inceledi. Hopper, Grover’in algoritmasının sadece karekök bir iyileştirme sağladığını ve klasik olarak çözülemez bir problemi kuantum bilgisayarda çözülebilir hale getiremeyeceğini belirtti. Shor’un algoritması için, Hopper, bu algoritmanın sadece belirli bir sorun türünü çözebileceğini ve bu nedenle kombinatoryal optimizasyon sorunları için uygun olmadığını gözlemledi.

Genel olarak, Hopper “Seyyah Satıcı Problemi’ne yaklaşık çözümler hesaplamak için bir algoritma için tatmin edici bir sonuç bulamadı”.

Birkaç yıl sonra, Elektrik ve Elektronik Mühendisleri Enstitüsü (IEEE) yeni bir algoritma sundu, bu algoritma hem genetik algoritmalar hem de kuantum hesaplamasından esinlenmiştir. IEEE, önerilen algoritmanın TSP’nin bazı örneklerinde standard genetik algoritmalarından daha iyi sonuçlar verdiğini buldu.

Buraya tıklayarak kuantum hesaplamasının güncel durumunu öğrenin.

Kuantum Hesaplamayla Çalışan Şirketler

Şimdi, kuantum hesaplamasının araştırma ve geliştirme çalışmalarına odaklanan birkaç şirkete göz atalım:

#1. IBM

Uluslararası İşletme Makineleri Şirketi, yapay zeka, bulut hizmetleri, BT, müşteri finansmanı ve ticari finansman gibi çeşitli sektörlerde faaliyet göstermektedir. Teknoloji devi ayrıca IBM Quantum Platform aracılığıyla kuantum hesaplamayla da ilgilenmektedir ve bu platform, kamu ve premium erişim sunar.

En son olarak, IBM bilim adamları bildirdi ki, kuantum bilgisayarların oyun değiştirici potansiyelini açığa çıkaran bir engeli aşmak için bir adım daha yakınlar. Bunu yapmak için, daha önceki yöntemlerden yaklaşık on kat daha verimli bir kuantum hata düzeltme kodu tanıttılar.

Geçen yıl, şirket ayrıca 1,121 süper iletken kubitle Condor adlı bir kuantum bilgisayarını ve ilk modüler kuantum bilgisayarını ve kuantum merkezli süper bilgisayarlı mimarisi olan IBM Quantum System Two’yu tanıttı.

175 milyar dolarlık bir piyasa değerine sahip olan IBM’nin hisseleri, yıl başından bu yana %16,66 artışla 190,86 dolar seviyesinde işlem görüyor. IBM, 61,86 milyar dolarlık gelir (TTM) ve 8,03 dolarlık EPS (TTM) ile 23,76 P/E (TTM) ve 33,36 ROE (TTM) oranlarına sahip. Şirket %3,48’lik bir temettü verimi ödüyor.

#2. D-Wave Systems

Bu kuantum hesaplaması şirketi, ilgili sistemler, yazılımlar ve hizmetler geliştirir ve sunar. Ürünleri arasında The Leap ve The Advantage bulunur ve şirket, zamanlama, lojistik, ilaç keşfi, üretim süreçleri ve daha fazlası için kuantum uygulamaları sağlar.

Bu ay, D-Wave, kuantum makinelerinin gerçek dünya uygulamalarına sahip sorunları normal bir bilgisayardan daha hızlı çözebileceğini söyledi. Bu yılın başlarında, şirket 1,200 kubite, 10,000 kuplaj ve zor optimizasyon sorunlarında zamanına çözümün 20 kat daha hızlı olduğu bir kuantum bilgisayarını duyurdu.

Şirketin hisseleri şu anda %138,6’lık bir yıl başı artışla 1,86 dolar seviyesinde işlem görüyor ve 267 milyon dolarlık bir piyasa değerine sahip. Şirket, 8,247 milyon dolarlık satış (TTM), -0,66 EPS (TTM) ve -3,19 P/E (TTM) raporladı ve 2023’ün dördüncü çeyreği ve yılına ait sonuçlarında %20’den fazla satış artışı ve %34 ve %89’luk rezerv artışını açıkladı.

İlginç bir şekilde, şirketin CEO’su Dr. Alan Baratz, şirketin momentumunu, Zapata AI ile çok yıllı stratejik ortaklık, 1,200’den fazla kubite sahip Advantage2 prototipinin tanıtımı, NEC Australia ve Deloitte Canada ile ortaklıklar ve eski İç Güvenlik Bakanı Kirstjen Nielsen’in yönetim kuruluna atanmasını belirterek açıkladı.

Sonuç

Kuantum hesaplaması pazarı 2028’de 6,5 milyar doları ulaşması bekleniyor ve TSP’yi çözme potansiyeli, imalat, lojistik, tedarik zinciri yönetimi, e-ticaret, ulaşım ve araştırma gibi çeşitli endüstriler için sonuçlar doğurabilir. Sonuç olarak, bu, verimliliği artırma, masrafları azaltma ve çeşitli sektörlerde yenilikleri teşvik etme gibi önemli faydalar sağlayabilir.

Buraya tıklayarak en iyi beş kuantum hesaplaması şirketini görün.