'Gezgin Satıcı Sorunu'nu Kuantum Hesaplamayla Çözmek

Bilgisayar bilimleri alanında Gezgin Satıcı Problemi (TSP) olarak bilinen klasik bir algoritmik problem, kombinatoryal optimizasyon probleminin en iyi örneğidir.

TSP tam olarak nedir? Bu matematik klasiği, başlangıç ​​şehre dönmeden önce N sayıda şehri tam olarak bir kez ziyaret etmek için mümkün olan en kısa rotayı bulmayı içerir. Ancak şehir sayısı arttıkça olası rotalar ve en uygun çözümü bulmak için gereken hesaplama süresi de artar. Bu sorun yaklaşık yöntemler kullanılarak çözülebilirken, kuantum bilgisayarlar çok daha iyi ve çok daha hızlı çözümler sağlayabilir. 

Bu tam olarak teorik fizikçinin Prof. Dr. Jens Eisert'in ekibi gösterdi: Bu tür problemlerin kuantum bilgisayarlarla daha iyi ve daha hızlı çözülebileceği.

Kuantum hesaplama, süper bilgisayarlar da dahil olmak üzere geleneksel yöntemlerin ötesindeki karmaşık sorunları çözmek için kuantum mekaniğini kullanan donanım ve algoritmaları kullanır. Süper bilgisayarlar (binlerce CPU ve GPU çekirdeğine sahip devasa klasik bilgisayarlar) güçlerine rağmen, yüksek derecede karmaşıklığa sahip sorunları çözerken 20. yüzyıl transistör teknolojisine güvenmeleri nedeniyle sınırlıdır. 

Kuantum fiziğinin devreye girdiği yer burasıdır. Bilgileri ikili bitler (0'lar ve 1'ler) halinde kodlayan klasik bilgisayarların aksine, kuantum bilgisayarlar, çok boyutlu kuantum algoritmalarını çalıştırmak için kuantum bitleri veya kübitleri kullanır. 

Üstelik soğutma için fan kullanan geleneksel bilgisayarların aksine kuantum bilgisayarları, kuantum durumlarını korumak için kuantum işlemcilerinin aşırı soğuk sıcaklıklarda tutulmasını gerektirir. Bu, aşırı soğutulmuş süper akışkanlar aracılığıyla elde edilir. 

Süperiletkenler, kritik bir kuantum mekaniksel etki sergileyen ve elektronların direnç olmadan içlerinden geçmesine izin veren malzemelerdir. Elektronlar geçerken çiftleşerek bariyerlerin üzerinden bir yük taşırlar. Bir yalıtkanın her iki tarafına iki süper iletken yerleştirildiğinde, süper iletken kubitleri iletmek için kullanılan bir Josephson bağlantısı oluşuyor.  

Bir kübit, kuantum bilgisini, kübitin olası konfigürasyonlarının bir kombinasyonu olan bir süperpozisyon durumuna yerleştirme gibi önemli bir görevde faydalıdır. Süperpozisyondaki kübit grupları, karmaşık sorunların temsil edilebileceği karmaşık, çok boyutlu hesaplama alanları yaratma kapasitesine sahiptir.

Burada iki kübitin dolaşıklaşmasıyla birinde meydana gelen değişiklikler diğerini doğrudan etkileyebilirken, bu dolaşık kübitler süperpozisyon durumuna getirildiğinde pek çok olasılıkla karşılaşıyoruz. Kuantum bilgisayarındaki hesaplama, tüm olası hesaplama durumlarının bir süperpozisyonunu hazırlayarak çalışır ve girişim yoluyla çözümler bulunur.

Elbette çok sayıda kubit içeren bir kuantum bilgisayar oluşturmak oldukça karmaşık bir prosedür, ancak bu tür bilgisayarların neler başarabileceği konusunda çeşitli yöntemler araştırılıyor. 

Enerji malzemeleri araştırmalarına yönelik bir araştırma merkezi olan Helmholtz-Zentrum Berlin'de (HZB) ve kamu araştırma üniversitesi Freie Universität Berlin'de ortak bir araştırma grubuna liderlik eden Eisert'e göre:

“Bu konuda pek çok efsane var ve bazen de bir miktar sıcak hava ve abartı var. Ancak biz konuya matematiksel yöntemler kullanarak titizlikle yaklaştık ve bu konuda somut sonuçlar elde ettik. Her şeyden önce, hangi anlamda avantajların olabileceğini açıklığa kavuşturduk.” 

Kritik Gezgin Satıcı Problemi

Bir optimizasyon sorunu olan TSP, lojistik ve tedarik zinciri endüstrisinde büyük ekonomik öneme sahiptir. Hepsi çeşitli sektörler için kritik olan iş planlamayı, kaynak tahsisini, portföy optimizasyonunu ve hatta protein katlamayı da içeren kombinatoryal optimizasyon sorunlarının daha geniş kategorisine girer.

Bu sorunların sosyal ve ekonomik önemi göz önüne alındığında yoğun araştırmalara konu olmuştur. Hal böyle olunca en verimli tedarik zinciri, en ucuz teslimat rotası gibi sorunlara cevap bulmak günlük hayatımıza olumlu etki yapıyor.

Ancak trafik sıkışıklığı, artan operasyonel maliyetler, ani rota değişiklikleri, son dakika iş randevuları ve müşteri talepleri gibi çeşitli kısıtlamaları göz önünde bulundurarak birden fazla varış noktası için teslimat rotalarını optimize etmek, TSP'yi çözmeyi daha da zorlaştırıyor. Bu zorluklara rağmen, TSP'nin çözülmesi, malların verimli bir şekilde teslim edilmesi ve uygulanabilir bir iş modelinin sağlanması açısından hayati öneme sahiptir. 

Bu sorunu çözmenin, kat edilen mesafeyi ve saati azaltmak ve yakıt kullanımından tasarruf etmek de dahil olmak üzere birçok faydası vardır. Kat edilen mesafenin en aza indirilmesi, karbon ayak izinin önemli ölçüde azaltılmasına yardımcı olabilir; bu da daha iyi hava kalitesi, iklim değişikliğinin yavaşlaması ve ekonomik büyüme anlamına gelir. Üstelik TSP'yi çözmek, malların zamanında teslim edilmesine ve müşterilerle zamanında toplantı yapılmasına yardımcı olabilir, bu da müşteri deneyimini ve saha hizmeti işlerini geliştirir.

Gördüğümüz gibi, sorunu çözmek yalnızca işletmelere yardımcı olmakla kalmıyor, aynı zamanda bu faydalar müşterilere de yansıyor ve ilgili herkesin deneyimini zenginleştiriyor.

TSP problemini çözmek için çeşitli yöntemler kullanılabilir. Böyle bir yöntem, en kısa rotayı bulmak için tüm olası permütasyonları hesaplayan 'Kaba Kuvvet' yaklaşımıdır. Dal-sınır yönteminde problem birkaç alt problem serisine bölünür ve her aşamadaki çözüm sonraki aşamalarda bulunan çözümü etkiler.

Dinamik programlamada, gereksiz hesaplamaların önlenmesine odaklanılır. Bu arada En Yakın Komşu, başlangıç ​​konumuyla başlayıp ardından en yakın konumda durduğunuz bir yaklaşım algoritmasıdır. Tüm şehirler dolduğunda başlangıç ​​noktasına geri dönersiniz. Pratik ve nispeten hızlı olmasına rağmen bu yöntem her zaman etkili bir yol sağlamayabilir.

Teknoloji ilerledikçe rota planlama ve optimizasyonu çok daha etkili bir şekilde yapılabilmektedir. Özellikle Yapay Zeka (AI), birçok modern işletmenin operasyonel ve stratejik kararlar almasına yardımcı olmak için büyük miktarda veriyi hızlı bir şekilde analiz ederek sorunun çözülmesine de yardımcı olabilir.

Sorunun çözümü için kuantum bilgisayarlar da araştırılıyor; sonuçta klasik bilgisayarlara göre kayda değer hesaplama hızları sunuyorlar. Bu bilgisayarların aslında bu sorunlara yaklaşımların geliştirilmesine yardımcı olabileceği uzun süredir öne sürülüyor. 

TSP'yi Çözmek İçin Kuantum Hesaplama Tekniklerini Kullanmak

Kuantum bilişimi büyük ilgi toplayıp belirli problemler için umut verici sonuçlar sağlarken, bu kuantum avantajının boyutu büyük ölçüde keşfedilmemiş durumda. 

Bu nedenle çalışma, kuantum bilgisayarların kombinatoryal optimizasyon problemlerine yaklaşımlar bulma konusunda geleneksel bilgisayarlardan daha iyi performans gösterebileceğinin tam yapıcı kanıtını sağladı.

Eisert ve meslektaşı Jean-Pierre Seifert tarafından yürütülen son çalışma, kübitli bir kuantum bilgisayarın TSP sorununu nasıl çözebileceğini değerlendirmek için yalnızca analitik yöntemler kullandı. 

Vincent Ulitzsch, "Fiziksel gerçekleşmeden bağımsız olarak, yeterli miktarda kübit olduğunu varsayıyoruz ve bunlarla bilgi işlem işlemleri gerçekleştirme olasılıklarına bakıyoruz" diye açıkladı; bu, kriptografide yaygın bir sorun olan verilerin şifrelenmesiyle benzerlik gösteriyor, diye açıkladı , doktora derecesi Berlin Teknik Üniversitesi öğrencisi. 

Daha sonra ekip, bir tamsayının asal çarpanlarını bulmak ve bu optimizasyon problemlerinin bir alt sınıfını çözmek için bir kuantum algoritması olan Shor algoritmasını kullandı. Böylece şehir sayısı arttıkça hesaplama süresi artık artmayacak. Yalnızca polinom olarak, yani x'in bir sabit olduğu Nx ile artacaktır. Bu şekilde elde edilen çözüm, geleneksel algoritma kullanılarak yaklaşık çözümden elde edilen çözümden niteliksel olarak da çok daha iyidir.

Kriptografik kavramları ve hesaplamalı öğrenme teorisini kullanan çalışma, "kuantum bilgisayarların, kombinatoryal optimizasyon problemlerine yaklaşımda klasik bilgisayarlara göre süper polinom avantajına sahip olduğuna dair tamamen yapıcı bir kanıt" sunuyor. 

Çalışma ayrıca, araştırma ekibinin, önemli sosyal ve ekonomik etkileri olan kombinatoryal optimizasyon problemlerinin çözümüne yaklaşmak için potansiyel kuantum bilgisayarların neler sunabileceğine dair önemli soru üzerinde önemli ilerleme kaydettiğini belirtti.

Çalışma, Einstein Araştırma Birimi, Berlin Matematik Araştırma Merkezi (MATH+ Cluster of Excellence), BMBF (Hybrid), BMWK (EniQmA), Münih Quantum Valley ve DFG tarafından finanse edildi. Almanya Federal Eğitim ve Araştırma Bakanlığı da mali destek sağladı.

Kuantum Bilişimin Potansiyelini Keşfetmek 

Büyük bir başarı olsa da bu, kuantum hesaplamanın gezgin satıcı problemini çözmek için kullanıldığı ilk sefer değildi. Kuantum hesaplamayı kullanarak sorunu çözmeye çalışan meraklıların ve araştırmacıların pek çok örneği var. 

Aralık 2022'te bir kâğıt Grover Uyarlanabilir Aramayı (GAS) temel alan TSP için bir kuantum algoritması önerdi. GAS çerçevesinde en az iki temel zorluk vardır: çözümler mümkün olmayabilir ve mevcut kuantum bilgisayarların kübit sayısı çok sınırlıdır ve minimum gereksinimleri karşılayamaz, bu da kombinatoryal optimizasyon sorunları için kuantum algoritmalarının uygulanmasını kısıtlar. 

Bu nedenle makale, algoritmanın yürütülmesi sırasında pratik olmayan çözümleri otomatik olarak kaldırabilen Hamilton Döngüsü Algılama (HCD) kehanetini cilaladı. Ayrıca, kuantum hesaplamanın tersine çevrilebilirlik gerekliliğini tamamen göz önünde bulundurarak ve kullanılan kübitlerin üzerine yazılmaması veya serbest bırakılmaması sorununun üstesinden gelerek, kübit kullanımından tasarruf etmek için bir "sabit kayıt" stratejisi tasarladılar. Çalışmanın yalnızca 31 kübit gerektirmesine olanak sağladı ve çözümün başarı oranı %86.71 oldu.

2019'da kendini fizik uzmanı olarak tanımlayan Joseph Cammidge yazdı yedi şehir için gezici satıcı problemini çözmesine olanak tanıyan ve teknolojik sınırlamalar ortadan kaldırıldığında dokuz şehir için teorik olarak çözme potansiyeline sahip olan tavlama kuantum işlemcisinin kullanılması hakkında. 

Yeni bir hesaplama yöntemi olan Kuantum tavlama, optimizasyon problemlerini klasik tekniklere göre daha hızlı çözme potansiyelini göstermiştir. Teorisi, kübitlerin aşırı soğutulduğunda optimal düşük enerji durumuna ulaşacağını ima ediyor. 

Ancak 2021'de bir ders çalışma Supply Chain Digital & Data Science tarafından finanse edilen Johnson & Johnson, kuantum tavlayıcının yalnızca 8 veya daha az düğümden oluşan problem boyutunu kaldırabildiğini ve performansının klasik çözücüyle karşılaştırıldığında hem zaman hem de doğruluk açısından ortalamanın altında olduğunu buldu.

TSP sorununu çözmek için kuantum hesaplamanın kullanımı bir süredir devam ediyor. Yirmi yılı aşkın bir süre önce, 2001'de bir çalışma başladı. arama Sorunu çözecek bir kuantum algoritması için.

Makalede Alabama Üniversitesi'nden Buckley Hopper, Grover ve Shor'un kuantum bilgisayar algoritmalarını inceledi. Grover'ın algoritmasının yalnızca karekökte bir iyileşme sağladığını, bunun da klasik olarak çözülmesi zor bir sorunu kuantum bilgisayarda çözülemez hale getiremeyeceğini ima ettiğini belirtti. Shor'un algoritmasına gelince, Hopper, çözümü mümkün olmayan bir asal faktör sorununu kuantum makinesinde çözülebilir bir soruna dönüştürebilmesine rağmen, yalnızca çok spesifik bir sorun türü için uygun olduğunu gözlemledi. 

Genel olarak Hopper "gezgin satıcı problemine yaklaşık çözümler bulmaya yönelik bir algoritma için tatmin edici bir sonuç bulamadı."

Bundan birkaç yıl sonra Elektrik ve Elektronik Mühendisleri Enstitüsü (IEEE) sundu Sorunu çözmek için hem genetik algoritmalardan hem de kuantum hesaplamadan ilham alan yeni bir algoritma. IEEE, önerilen algoritmanın Gezgin Satıcı Probleminin bazı örneklerine uygulanmasından elde edilen sonuçların, standart genetik algoritmalar tarafından sağlananlardan önemli ölçüde daha iyi olduğunu buldu.

Kuantum hesaplamanın mevcut durumu hakkında bilgi edinmek için burayı tıklayın.

Kuantum Bilişimle Çalışan Şirketler 

Şimdi kuantum hesaplamanın araştırma ve geliştirmesi üzerinde çalışan birkaç isme göz atalım:

# 1. IBM

International Business Machines Corporation, yapay zeka, bulut hizmetleri, BT, müşteri finansmanı ve ticari finansman dahil olmak üzere çok çeşitli sektörlerde faaliyet göstermektedir. Teknoloji devi aynı zamanda bulut tabanlı kuantum bilgi işlem hizmetlerine genel ve ayrıcalıklı erişim sağlayan IBM Quantum Platformu aracılığıyla kuantum bilişimle de ilgileniyor. Bunlar arasında IBM'in bir dizi prototip kuantum işlemcisi, kuantum hesaplamaya ilişkin eğitimler ve etkileşimli bir ders kitabı yer alıyor.

Son zamanlarda IBM bilim insanları belirtilen kuantum bilgisayarların oyunun kurallarını değiştiren potansiyelini ortaya çıkaran bir engeli aşmaya bir adım daha yaklaştıklarını söylüyorlar. Bunun için önceki yöntemlere göre yaklaşık on kat daha verimli olduğunu söyledikleri yeni bir kuantum hata düzeltme kodunu tanıttılar. 

Geçtiğimiz yılın sonlarında şirket, bal peteği şeklinde düzenlenmiş 1,121 süper iletken kübit içeren Condor adlı kuantum bilgisayarını da piyasaya sürdü. IBM ayrıca, ölçeklenebilir ve dolayısıyla önümüzdeki beş yıl içinde piyasaya sürülecek çiplerle yükseltilebilen ilk modüler kuantum bilgisayarı ve kuantum merkezli süper bilgi işlem mimarisi olan IBM Quantum System Two'yu da tanıttı.

Piyasa değeri 175 milyar dolar olan IBM'in hisseleri, yılbaşından bugüne (YTD) %190.86 artışla 16.66 dolardan işlem görüyor. IBM, 61.86 milyar dolarlık gelir (TTM) açıklarken, EPS (TTM) 8.03, F/K (TTM) 23.76 ve ROE (TTM) %33.36 oldu. Şirket %3.48 temettü getirisi ödüyor.

# 2. D-Wave Systems

Bu kuantum bilişim şirketi ilgili sistemleri, yazılımları ve hizmetleri geliştirir ve sunar. Ürünleri arasında The Leap ve The Advantage yer alıyor ve planlama, lojistik, ilaç keşfi, üretim süreçleri ve daha fazlası için kuantum uygulamaları sağlıyor. 

Bu ayın başlarında D-Wave, kuantum makinelerinin artık gerçek dünya uygulamalarındaki sorunları sıradan bilgisayarlardan daha hızlı çözebileceğini söyledi. Bu yılın başlarında şirket, 1,200 kübit, 10,000 bağlaştırıcı ve zor optimizasyon problemlerinde 20 kat daha hızlı çözüm süresine sahip bir kuantum bilgisayarını duyurdu.

Şirketin hisseleri şu anda yılbaşından bugüne (YTD) %1.86 artışla 138.6 dolardan işlem görüyor ve piyasa değeri 267 milyon dolar. 8.247 milyon dolarlık satış (TTM), -0.66 hisse başı kazanç (TTM) ve -3.19 F/K (TTM) bildirdi ve hem 20'ün 4. çeyreği hem de yıl sonu sonuçları için satışlarda %2023'nin üzerinde büyüme açıkladı. Sırasıyla %34 ve %89. 

İlginç bir şekilde, şirketin CEO'su Dr. Alan Baratz, şirketin Zapata AI ile çok yıllı stratejik ortaklığına, 1,200'den fazla kübit Advantage2 prototipinin piyasaya sürülmesine, NEC Avustralya ve Deloitte Kanada ile ortak girişimlere ve atamaya atıfta bulunarak firmanın momentumunu açıkladı. Eski İç Güvenlik Bakanı Kirstjen Nielsen'in yönetim kuruluna dahil edilmesi.

Sonuç

Kuantum hesaplama pazarının büyümesi bekleniyor 6.5 milyar dolara ulaş Gezgin Satıcı Sorununu (TSP) çözme potansiyelinin imalat, lojistik, tedarik zinciri yönetimi, e-ticaret, taşımacılık ve araştırma gibi çeşitli sektörler için sonuçları olacak. Sonuçta, özellikle üretkenliği artırmak, giderleri azaltmak ve çeşitli sektörlerde yenilikçiliği teşvik etmek gibi önemli faydalar sağlayabilir.

En iyi beş kuantum bilişim şirketinin listesi için buraya tıklayın.