Arama problemi

Tamamlandı

Bir adım geri gidelim ve Grover algoritmasının nasıl çalıştığını ve uzay istasyonları arasındaki iletişim problemimizi çözmek için neden bunu kullanabileceğimizi görelim.

Bu bölümde Grover'ın arama algoritması tarafından çözülen sorunu ("arama sorunu" olarak adlandırılır) tanımlayacak ve çeşitli gerçek yaşam sorunlarının bu sorun açısından nasıl temsil edilebileceğine daha yakından bakacağız.

Arama problemi

Arama sorunu şu şekilde formüle edilir: size $N$-bit girişi alan ve 0 veya 1 bit çıkış döndüren bir $f$ işlevi verilir. Burada amacınız, $f(x_0) = 1$ değerini veren $x_0$ girişlerini bulmaktır.

Not

İşlevin yapısıyla ilgili herhangi bir bilgi verilmediğine dikkat edin. Yalnızca bu işlevi uygulayan, yani girişi alıp ilgili çıkışı veren bir "opak kutuya" erişiminiz vardır.

Hangi problemler arama problemi olarak sınıflandırılabilir?

Arama problemi tasarımı gereği genel bir problemdir. Aslında verilen $x$ değerinin geçerli bir çözüm olup olmadığını denetlemenize olanak tanıyan tüm problemler ("evet veya hayır problemi"), arama problemi olarak formüle edilebilir. Bu durumda $f(x)$ değeri "ancak $x$ değeri problemimiz için geçerli bir çözümse 1" olacak şekilde tanımlanabilir.

İşte bazı örnekler:

  • Boolean sağlanabilirlik problemi: Boolean değerlerinden oluşan bir küme olan $x$ değeri verilen Boolean formülünü sağlayan bir yorumlama (değişkenlere değer atanması) mıdır?
  • Gezici satış temsilcisi problemi: $x$ değeri tüm şehirleri birbirine bağlayan mümkün olan en kısa döngüyü tanımlıyor mu?
  • Veritabanı arama problemi: Veritabanı tablosu $x$ kaydını içeriyor mu?
  • Tamsayıyı çarpanlarına ayırma problemi: $N$ sabit sayısı $x$ sayısına bölünebilir mi?

Bu problemlerden bazıları, Grover algoritması kullanıldığında diğer problemlere kıyasla daha iyi sonuçlar verebilir.

Uzay filosunun galaksiye dağılmış birkaç uzay istasyonu var. Gürültü ve girişim, iletişim bölümünün çözmeye çalıştığı sorunlardır. Uzay istasyonlarının aralarında iletişim kurması gerekir, ancak iki istasyon çok yakınsa, radyo sinyalleri karışıyor ve bilgilerin kodunu çözemiyoruz. Bu nedenle, her bir uzay istasyonuna belirli bir bant genişliği atamamız gerekir. Ancak kullanılabilir bant genişlikleri sınırlı olduğundan ve uzay filosu yıldan yıla büyüdükçe her uzay istasyonuna benzersiz bir bant genişliği atayamıyoruz. Etkili olmak için, iki uzay istasyonu müdahale etmeyen uzaklarsa aynı bant genişliğini paylaşabilir. Buna bağlı olarak, atanan farklı bant genişliklerinin sayısını olabildiğince düşük tutmaya çalışırken her istasyona bir bant genişliği atamanız gerekir.

Bu sorun, köşelerin uzay istasyonları olduğu, etiketlerin/renklerin bant genişliği olduğu ve sinyallerinin karışması için yeterince yakın olmaları durumunda iki köşenin bağlandığı graf renklendirme sorununun bir örneğidir.

Bu modülde graf renklendirme problemi üzerinden ilerleyeceğiz. Son ünitede kuantum hızlandırma ve klasik algoritma yerine Grover algoritması kullanılarak daha hızlı çözülebilecek sorun türleri sorusuna geri döneceğiz.

Graf renklendirme problemi

Doğru köşe renklendirme sorunu olarak da bilinen graf renklendirme sorunu şu şekilde formüle edilir: Bir grafik ve bir dizi $k$ etiketi ("renkler") verildiğinde, grafiğin köşelerinin her birine bağlı iki köşenin aynı etikete sahip olmaması için bir etiket atayın. Renkleri etiket olarak kullanmak, grafik gösteriminde iyi bir görsel yardımcıdır. Uygulamada, bu etiketler herhangi bir şey olabilir: atanacak işlerin listesi, uzay istasyonları arasında iletişim kurmak için kullandığımız radyo frekanslarının listesi veya uzay istasyonlarına sunduğumuz farklı malzemelerin listesi.

Beş köşesi ve yedi kenarı olan örnek bir grafik aşağıda verilmiştir:

Beş köşesi ve yedi kenarı olan bir grafiği gösteren şekil.

Bu grafiğin köşelerini üç renk kullanarak etiketleme girişimi aşağıda açıklanmıştır.

Geçersiz köşe renklendirmesini gösteren şekil.

Tanımımızı kullanarak bu etiketleme denemesinin geçerli olmadığını görüyoruz. Köşe 0 ve 3'e, bir kenarı paylaşsalar bile aynı etiket atanır.

Aslında, bu grafiğin köşelerini yalnızca üç renk kullanarak etiketleyemezsiniz; bunu yapmak için en az dört renge ihtiyacınız vardır.

Geçerli bir köşe renklendirmesini gösteren şekil.

Bu modülde grafın dört renkle renklendirilmesine (en çok dört renk kullanan bir çözüm) bulma sorununu ele alacağız. (Kullanılan renk sayısında bir kısıtlama olmadığında grafı geçerli bir şekilde renklendirmek kolaydır. Tek yapmanız gereken gördüğünüz her köşeye yeni bir etiket atamaktır.)

Graf renklendirme genellikle bir NP-tam problem olarak kabul edilir ve bu problem için bilinen çözümlerin çalıştırılması çok uzun zaman almaktadır.

Bu modülün ilerleyen ünitelerinde kuantum bilgi işlemin bu probleme daha hızlı bir çözüm bulmanıza nasıl yardımcı olabileceğini göreceksiniz.