Quadratic Speedup of Grover’s Search Algorithm

Spread the love

Grover’s Search Algorithm : L. K. Grover (1996), “A fast quantum mechanical algorithm for database search”, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC 1996)
https://dl.acm.org/doi/10.1145/237814.237866

Problem:
Dengan array elemen m yang tidak terurut, temukan elemen tertentu.
Secara klasik, rata-rata kita akan menemukan elemen yang diinginkan dalam kueri m/2, dan dalam kasus terburuk, semua m.
Algoritme pencarian Lov Grover melakukan pekerjaan dalam √m queries.
Algoritma Grover memiliki banyak aplikasi untuk teori basis data dan bidang lainnya

Secara klasik, dalam kasus terburuk, kita harus mengevaluasi semua string biner 2n untuk menemukan x0 yang diinginkan.
Algoritma Grover hanya akan menuntut evaluasi sebanyak √2n.

Grover’s algorithm:
Step 1. Start with a state |0>
Step 2. Apply Hadamard gate
Step 3. Repeat √2n times:
Step 3a. Apply the phase inversion operation
Step 3b. Apply the inversion about the mean operation
Step 4. Measure the qubits.

Phase Inversion operation (Reflection)

Inversion About the Mean (the Average)

Amplitude Amplification

amplifikasi amplitudo, yang merupakan cara komputer kuantum secara signifikan meningkatkan probabilitas.
Prosedur ini merentangkan (memperbesar) amplitudo dari item yang ditandai, yang mengecilkan amplitudo item lain, sehingga mengukur keadaan akhir akan mengembalikan item yang tepat dengan hampir pasti.

Amplitude Amplification adalah operasi yang sangat kuat yang memisahkan amplitudo dari keadaan yang diinginkan dari semua keadaan lainnya

Download pdf artikel ini = Grover’s Search Algorithm

Tinggalkan Balasan

This site uses Akismet to reduce spam. Learn how your comment data is processed.