Quantum Search Algorithm (Grover's Algorithm)
It is the search of one or more target element(s) found in an unstructured database (unstructured: a wrong answer does not provide information about the correct answer).
Let there be \(N\) number of elements in the database.
We can represent them with \(n\) number of qubits. \(N=2^n\)
\(\ket{\psi}=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\ket{x}\) olmak üzere veritabanındaki her bir elemanı temsilen \(\ket{x}\), veritabanını temsilen \(\ket{\psi}\) kullanılabilir.
Veritabanındaki tüm elemanlar aynı ağırlığa sahip. (All the elements have equal weights.)
Hedefi arama aracımız olarak bir Oracle var. Oracle çözümü tanıyormuş. Burada anlamadığım şey, çözümü/çözümleri tanıyorsa neden direk ortaya çıkarmıyor? Oracle ve insan arasındaki ilişki ne, neden tanıdığını "çözüm budur" diye ortaya atmıyor? Bu algoritma benim için çözümü bulmaya yönelik değil, çözülmek istenirse çözümü elde etme ihtimalini arttırmaya yönelik. Ya da olay şu: tüm bazlarda (computational basis veya başka bir basis olabilir) aynı anda ölçüm yapılmak zorunda, yani tüm bazları deney setup'ında bulundurmak zorundasın. Ama sen yapılacak bir ölçümün istenen sonuca çökme olasılığını arttırıyorsun bu protokolle. Bütün olası ölçüm sonuçları eşit olasılıkla bulunmayacak, bu worst case scenario, onun yerine biased bir havuz olacak. Çünkü ölçüm üstünde kontrolün yok, ölçüm olasılıksal. Sen sadece olasılıkları değiştirebilirsin. Bu protokolün anlamı bu olabilir.
Protokol şu şekilde ilerler: çözümün probability amplitude'unu eksi ile çarpıyor. Yani sanki kendine göre yansımasını (reflection) alıyor.
Bu şekilde veritabanındaki tüm elemanların ortalaması (mean) düşüyor. Tüm elemanların ortalamaya göre yansımasını alıyor.
Böylelikle çözüm olmayan elemanların probability amplitude'ları azalmış, çözüm olan elemanınki artmış oluyor.
Aynı prosedürü (buna Grover algorithm deniyor) belirli sayıda tekrarlayarak çözüm olmayan (not targeted) elemanların amplitude'larını minimize, çözüm (target) olanınkini mazimize ediyorsun.
Ve bir ölçüm sonucunda aranan elemanın, çözümün elde edilme olasılığını arttırmış oluyorsun.
Problemi %100 çözmemesinin sebebi algoritma uygulandıktan sonra elemanlar superposed durumda ise genliklerinin sıfırdan farklı olup ölçüm sonucunda herhangi birinin gelebilme ihtimalidir. Çözümün genliğini 1, diğer elemanlarınkini 0 yapabilirse %100 çözer ancak solution'ın amplitude'u 1 olmadığı sürece ölçüm sonunda solution'ı elde etme olasılığı da %100 olmaz.
Circuit
MATLAB code for the algorithm
