Algoritma Runtime of Grover

Apa kompleksitas waktu (bukan kompleksitas kueri) dari algoritma Grover? Tampak jelas bagi saya bahwa itu adalah karena adaΩ($\Omega(\log(N) \sqrt{N})$iterasi dan setiap iterasi membutuhkan penggunaan operasi refleksi yang pada gilirannya membutuhkan waktuΩ(log(N))menggunakan setiap set standar gerbang universal.$\Omega(\sqrt{N})$$\Omega(\log(N))$

Masalahnya adalah, saya tidak dapat menemukan satu pun referensi yang mengatakan kompleksitas waktu dari algoritma Grover adalah . Wikipedia, dan beberapa halaman web lainnya, ucapkanO($\Omega(\log(N) \sqrt{N})$kompleksitas waktu. Makalah Grover mengklaimO($O(\sqrt{N})$"langkah".$O(\sqrt{N})$

Apakah saya melewatkan sesuatu? Mungkin orang mendefinisikan operasi refleksi untuk mengambil satuan waktu. Tetapi itu tidak masuk akal bagi saya karena jika kita dapat memainkan permainan yang memungkinkan unitarian sewenang-wenang untuk mengambil satuan waktu maka tidak akan ada perbedaan antara kompleksitas kueri dan kompleksitas waktu.

Pertanyaan biasanya diambil untuk diperdebatkan, karena alasan berikut. Algoritma Grover adalah algoritma pencarian kombinatorial untuk menemukan solusi predikat sewenang-wenang. Sementara, ya, adalah kompleksitas gerbang kuantum di setiap tahap algoritma kotak-hitam, predikat perlu dihitung juga. Kompleksitas gerbang kuantum yaitu Ω ( log N $\Theta(\log N)$$\Omega(\log N)$, karena jika tidak, ia tidak akan membaca seluruh input dan Anda dapat membuang beberapa bit input dari pencarian. Di sisi lain, predikat yang menarik bisa memakan waktu lebih banyak dari itu. Oleh karena itu, jumlah panggilan ke predikat dianggap sebagai koin standar, seperti halnya analog klasik algoritma Grover, yaitu menebak acak.

Ternyata ada cara untuk mengimplementasikan algoritma Grover dengan kurang dari gerbang! Itu sebabnya Anda tidak dapat menemukan referensi yang mengklaim bahwaΩ($O(\sqrt{N}\log N)$diperlukan gerbang. Setidaknya dalam kasus di mana ada satu item yang ditandai dimungkinkan untuk melakukan yang lebih baik.$\Omega(\sqrt{N}\log N)$

Pracetak baru-baru ini oleh Arunachalam dan de Wolf menyediakan algoritma baru untuk menyelesaikan masalah pencarian dengan satu item yang ditandai dengan kompleksitas kueri dan hanyaO($O(\sqrt{N})$gerbang (dari gerbang mengatur Toffoli + semua gerbang satu-qubit).$O(\sqrt{N}\log(\log^* N))$

$\log(\log^* N)$$N$$\log(\log^* N)$