Grover Algoritması
Grover's Algorithm for Quantum Search · Ayrıca şöyle bilinir: quantum search, amplitude amplification
Grover Algoritması, sıralanmamış bir veritabanında arama yapmak için kullanılan, klasik doğrusal aramaya göre karesel bir hızlanma sunan bir kuantum algoritmasıdır. Lov Grover tarafından 1996 yılında önerilen algoritma, N öğe arasından hedef bir öğeyi klasik O(N) sorgu gereksinimine karşılık O(√N) sorguda bulmak için kuantum süperpozisyonunu ve genlik yükseltmesini kullanır.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Grover algoritması, yapılandırılmamış arama problemlerinde, yani saptırılabilir bir yapıya (sıralama veya indeksleme gibi) sahip olmayan problemler için kullanılır. Kısıtlılık tatmin problemleri, veritabanı sorguları ve kombinatoryal aramalar için geçerlidir. Çözüm uzayının büyük olduğu (N >> 2^10) ve klasik kaba kuvvet aramanın aşırı maliyetli olduğu durumlarda etkilidir.
Güçlü yönler & sınırlılıklar
- Karesel hızlanmayı (√N'ye karşılık N) kanıtlanabilir şekilde elde eder, bu da büyük veritabanları için önemli bir iyileştirmedir.
- Shor algoritmasından daha uygulanabilir olan yalnızca O(log N) kübit ve O(√N) kuantum işlemi gerektirir.
- Herhangi bir yapılandırılmamış arama problemine uygulanabilen genel amaçlı bir algoritmadır.
- Kuantum sayma ve genlik tahmin gibi genellemelere olanak tanıyan genlik tahmin yoluyla çözüm sayısını saymak için uyarlanabilir.
- Problem özelinde yapı gerektirmeyen kuantum üstünlüğünü gösterir.
- Karesel hızlanma, önemli olmasına rağmen, Shor algoritması gibi üstel hızlanmalardan daha zayıftır.
- Bir oracle fonksiyonu gerektirir; oracle'ın tasarımı aramanın kendisi kadar zor olabilir.
- Optimal iterasyon sayısı (O(√N)) tahmin edilmelidir; çok fazla iterasyon başarı olasılığını azaltır.
- Veritabanına kuantum erişimi varsayar; pratik uygulamalar pahalı oracle yapıları gerektirebilir.
- Gürültü ve hatalar iterasyon sayısıyla birikir, bu da NISQ cihazlarındaki etkinliği sınırlar.
SSS
Grover algoritması neden yalnızca karesel, üstel değil, hızlanma sağlıyor?
Hızlanma, kuantum mekaniğinin kendisiyle sınırlıdır. Hedefin karesel genliği en az 1/N'ye kadar toplamalıdır ve genlik yükseltme, yeniden başlatma gerektirmeden önce onu en fazla O(√N) kat artırabilir. Bu temel sınır, Zalka-Cleve teoremi ile kanıtlanmıştır.
Oracle nedir ve nasıl oluşturulur?
Oracle, hedef öğe için +1 ve diğerleri için -1 döndüren bir kara kutu fonksiyonudur (kuantum terimleriyle fazı çevirir). Bir oracle oluşturmak, arama koşulunuzu uygulayan bir kuantum devresi gerektirir; bu zorsa, Grover algoritması yardımcı olmayabilir.
Grover algoritmasının kaç iterasyonuna ihtiyacım var?
Optimal sayı π/4 × √N'dir, bu da başarısızlık olasılığını en aza indirir. Bu değer tahmin edilmeli veya uyarlanabilir olarak belirlenmelidir. Çok fazla iterasyon çalıştırmak, genliğin hedefi aşarak salınmasına neden olur ve başarı olasılığını azaltır.
Grover algoritması yapılandırılmış bir veritabanını (sıralı liste) arayabilir mi?
Grover, yapılandırılmamış arama için optimize edilmiştir. Veritabanı sıralı veya indekslenmişse, klasik algoritmalar (ikili arama, hash tabloları) Grover algoritmasından daha iyi performans sunar.
Grover algoritması birden fazla hedef çözümle çalışır mı?
Evet. N öğe arasından M çözüm varsa, Grover algoritması O(√(N/M)) iterasyonda birini bulur. Bu, birden fazla geçerli atamanın bulunduğu kısıtlılık tatmin problemleri için önemli bir özelliktir.
Kaynaklar
- Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 212–219. DOI: 10.1145/237814.237866 ↗
- Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79, 325–328. DOI: 10.1103/PhysRevLett.79.325 ↗
- Brassard, G., Hoyer, P., Tapp, A. (2002). Quantum amplitude amplification and estimation. arXiv preprint quant-ph/0005055. link ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Grover's Algorithm for Quantum Search. ScholarGate. https://scholargate.app/tr/quantum-computing/grovers-algorithm
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Kuantum Monte CarloKuantum hesaplama↔ karşılaştır
- Kuantum Faz KestirimiKuantum hesaplama↔ karşılaştır
- Shor AlgoritmasıKuantum hesaplama↔ karşılaştır