Квантовий алгоритм пошуку в неструктурованій базі даних

DOI:10.31673/25187678.2022.021014

Анотація

Квантовий алгоритм Гровера розроблено для вирішення задачі проведення пошуку в неструктурованій базі даних певного унікального елемента. В загальному вигляді ця проблема може бути сформульована так: неструктурована база даних складається з N елементів та містить один унікальний елемент, що має певну властивість з поліноміальною складністю, який потрібно знайти з мінімальними витратами часу та складністю. Як і в квантових алгоритмах, в алгоритмі Гровера здійснюється повтор процедури (ітерації Гровера).

Ключові слова: Квантовий алгоритм Гровера, неструктурована база даних, унікальний елемент, колізія, функція гешування.

Список використаної літератури
1. Neal Koblitz and Alfred J. Menezes A Riddle wrapped in an Enigma. Department of Mathematics, Box 353.350, University of Washington, Seattle, WA 98195 U.S.A. – Access mode: https://eprint.iacr.org/2015/1018.pdf.
2. Lily Chen Report on Post-Quatum Cryptography. NISTIR 8105 (DRAFT) / Lili Chen, Stephen Jordan, Yi-Kai-Liu, Dustin Moody, Rene Peralta, Ray Perlner, Daniel Smith-Tone // – Access mode: http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf.
3. Горбенко Ю. І. Методи побудування та аналізу, стандартизація та застосування криптографічних систем : монографія. / Ю. І. Горбенко. Х. : Форт, 2016. – 959 с.
4. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. Round 3 Submissions. [Електронний ресурс]. Режим доступу: https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions.
5. Сутність та особливості реалізації методу Гровера на класичному комп’ютері для симетричного криптоаналізу / Ю. І. Горбенко, Є. Ю. Каптьол // Радіотехніка : Всеукр. міжвід. наук.-техн. зб. – 2018. Вип. 195. – С. 89-100.
6. Дирак П., Принципы квантовой механики / П. Дирак.- М.: Наука, 1979.- 480 с.
7. D.Aharonov, Quantum computation, In D.Stauffer, editor, Annual Reviews of computational Physics VI., World Scientific, Singapore, 1999.