Гроверын квант хайлтын алгоритм нь сонгодог алгоритмтай харьцуулахад индексийн хайлтын асуудалд экспоненциал хурдыг нэвтрүүлдэг. 1996 онд Лов Гроверын санал болгосон энэхүү алгоритм нь O(√N) цагийн нарийн төвөгтэй N оруулгууд бүхий эрэмблэгдээгүй мэдээллийн сангаас хайлт хийх боломжтой квант алгоритм бөгөөд харин хамгийн сайн сонгодог алгоритм болох бүдүүлэг хүчний хайлт нь O(N) хугацаа шаарддаг. нарийн төвөгтэй байдал. Энэхүү экспоненциал хурдасгах нь квант тооцооллын салбарт гарсан томоохон дэвшил бөгөөд мэдээллийн сан хайх, криптографи, оновчлолын асуудал гэх мэт хайлтын үйл ажиллагаа шаардсан төрөл бүрийн програмуудад нөлөөлсөн.
Гроверын алгоритм хэрхэн энэхүү экспоненциал хурдыг олж авдгийг ойлгохын тулд түүний ажиллах зарчмыг судалцгаая. Сонгодог хайлтын асуудалд хэрэв бид N зүйлийн эрэмблэгдээгүй жагсаалттай бөгөөд бид тодорхой зүйлийг олохыг хүсч байвал хамгийн муу хувилбар нь бүх N зүйлийг шалгах шаардлагатай бөгөөд үүний үр дүнд O(N) цагийн нарийн төвөгтэй байдал үүсдэг. Гэсэн хэдий ч Гроверын алгоритм нь мужуудын суперпозиция дахь хайлтыг гүйцэтгэхийн тулд квант параллелизм ба хөндлөнгийн оролцоог ашигладаг бөгөөд ингэснээр бүх боломжит шийдлүүдийг нэгэн зэрэг хайх боломжийг олгодог.
Алгоритм нь эхлүүлэх, oracle, дундаж утгыг эргүүлэх гэсэн гурван үндсэн алхмаас бүрдэнэ. Эхлэх шатанд бүх боломжит төлөвүүдийн суперпозиция бий болно. Оркулын алхам нь зорилтот төлөвийг фазыг нь урвуулж тэмдэглэдэг бөгөөд дундаж алхамын тухай урвуу байдал нь бүх муж дахь зорилтот төлөвийн далайцыг тусгадаг. Эдгээр алхмуудыг давталттайгаар хэрэгжүүлснээр алгоритм нь зорилтот төлөвийн магадлалын далайцыг нэмэгдүүлж, зорилтот зүйлийг олоход шаардагдах давталтын тоог квадрат хурдасгахад хүргэдэг.
Жишээлбэл, 16 зүйлээс бүрдсэн мэдээллийн санд сонгодог алгоритм нь хамгийн муу тохиолдолд бүх 16 зүйлийг шалгах шаардлагатай болно. Үүний эсрэгээр Гроверын алгоритм зорилтот зүйлийг ердөө 4 давталтаар (O(√16) = 4) олдог бөгөөд энэ нь түүний экспоненциал хурдыг харуулдаг. Өгөгдлийн сангийн хэмжээ өсөхийн хэрээр энэ хурдац нь илүү тодрох бөгөөд энэ нь Гроверын алгоритмыг том хэмжээний хайлтын асуудлуудад өндөр үр ашигтай болгодог.
Гроверын алгоритм нь квант механикийн үндсэн зарчмууд эсвэл тооцооллын нарийн төвөгтэй байдлын онолыг зөрчөөгүй гэдгийг анхаарах нь чухал юм. Түүний хурдыг √N хүчин зүйлээр хязгаарладаг бөгөөд энэ нь бүх асуудлыг шууд шийдэж чадахгүй, харин бүтэцгүй хайлт гэх мэт тодорхой ажлуудад зориулсан сонгодог алгоритмуудаас мэдэгдэхүйц сайжруулалтыг үзүүлдэг болохыг харуулж байна.
Гроверын квант хайлтын алгоритм нь сонгодог алгоритмуудын O(N) нарийн төвөгтэй байдалтай харьцуулахад O(√N) цагийн нарийн төвөгтэй байдлаар эрэмблэгдээгүй мэдээллийн санг хайхад квант параллелизм болон хөндлөнгийн оролцоог ашиглан индекс хайлтын асуудалд экспоненциал хурдыг нэвтрүүлдэг. Квантын тооцооллын энэхүү дэвшил нь янз бүрийн хэрэглээнд өргөн хүрээтэй нөлөө үзүүлж, тооцооллын асуудлыг үр дүнтэй шийдвэрлэх квант алгоритмын хүчийг харуулж байна.
Сүүлийн үеийн бусад асуулт, хариулт EITC/QI/QIF квант мэдээллийн үндэс:
- Квант үгүйсгэх хаалга (квант БИШ эсвэл Паули-Х хаалга) хэрхэн ажилладаг вэ?
- Хадамард хаалга яагаад өөрөө эргэх боломжтой вэ?
- Хэрэв Bell төлөвийн 1-р кубитийг тодорхой үндэслэлээр хэмжиж, дараа нь 2-р кубитийг тета өнцгөөр эргүүлсэн суурь дээр хэмжвэл харгалзах вектор руу проекцийг олж авах магадлал тетагийн синусын квадраттай тэнцүү байна уу?
- Дурын кубит суперпозицияны төлөвийг дүрслэхийн тулд хэдэн бит сонгодог мэдээлэл шаардлагатай вэ?
- 3 кубит зайтай хэдэн хэмжээст вэ?
- Кубитийн хэмжилт нь түүний квант суперпозицияг устгах уу?
- Квантын хаалга нь сонгодог хаалгатай адил гаралтаас илүү их оролттой байж чадах уу?
- Квантын хаалганы бүх нийтийн гэр бүлд CNOT хаалга, Хадамард хаалга багтдаг уу?
- Давхар ангархай туршилт гэж юу вэ?
- Туйлшруулагч шүүлтүүрийг эргүүлэх нь фотоны туйлшралын хэмжилтийн суурийг өөрчлөхтэй тэнцэх үү?
Бусад асуулт, хариултыг EITC/QI/QIF Quantum Information Fundamentals хэсгээс үзнэ үү