Кванттық іздеу алгоритмі және Grover алгоритмі

Кіріспе

Кванттық іздеу алгоритмі

Кванттық есептеуде Гровер алгоритмі, сонымен қатар кванттық іздеу алгоритмі деп аталады, бұл құрылымдалмаған іздеуге арналған кванттық алгоритм. Ол функцияның доменінің мөлшері болғанда, белгілі бір нәтиже шығаратын «қара жәшік» функциясының бірегей кірісін жоғары ықтималдықпен табады, функцияны тек бағалау арқылы. Классикалық есептеудегі осыған ұқсас мәселені функцияны кемінде бағалаусыз шешу мүмкін емес (өйткені, орташа есеппен, дұрыс кірісті табудың 50% мүмкіндігі үшін доменнің жартысын тексеру қажет). Чарльз Х. Беннетт, Итан Бернштейн, Жиль Брассард және Умеш Вазирани кез келген кванттық шешім функцияны бағалауы керек екенін дәлелдеді, сондықтан Гровер алгоритмі асимптотикалық жағынан ең жақсы алгоритм болып табылады. NP-толық проблемалар үшін классикалық алгоритмдерге экспоненциалды түрде көп қадамдар қажет болғандықтан, ал Гровер алгоритмі құрылымдалмаған іздеу үшін классикалық шешімге қарағанда ең көптеген жағдайда квадраттық жылдамдық береді, бұл Гровер алгоритмінің өзі NP-толық проблемалар үшін полиномиалдық уақыт шешімін қамтамасыз етпейтінін көрсетеді (экспоненциалды функцияның квадрат түбірі экспоненциалды, полиномиалдық емес). Басқа кванттық алгоритмдер классикалық аналогтарына қарағанда экспоненциалды жылдамдық бере алатынымен салыстырғанда, Гровер алгоритмі тек квадраттық жылдамдық береді. Дегенмен, тіпті квадраттық жылдамдық та мөлшері үлкен болғанда маңызды, және Гровер алгоритмін алгоритмдердің кең кластарын жылдамдату үшін қолдануға болады.

Қолданылу және шектеулер

Гровер алгоритмі, амплитуданы күшейту сияқты түрлерімен бірге, алгоритмдердің кең спектрін жылдамдату үшін қолданылуы мүмкін. Атап айтқанда, Grover алгоритмімен толық іздеуді қосалқы процедура ретінде қамтитын NP-толық есептерге арналған алгоритмдерді жылдамдатуға болады. Бұл алгоритмдер кірісті оракул түрінде беруді қажет етпейді, себебі Гровер алгоритмі нақты функциямен қолданылады, мысалы, биттер жинағының 3SAT мысалын қанағаттандыратынын тексеру функциясы. Гровер алгоритмі кванттық сұраныс күрделілігіндегі қара жәшік есептері үшін де нақты жылдамдықтарды ұсынуы мүмкін, соның ішінде элементтердің өзгешелігі және соқтығысу есебі (Brassard–Høyer–Tapp алгоритмімен шешілген). Мұндай есептерде оракул функциясы f деректер базасы ретінде қарастырылады, ал мақсат – осы функцияға кванттық сұранысты мүмкіндігінше аз рет қолдану.

Криптография

Гровер алгоритмі функцияны инверсиялау есебін шешеді. Шамамен айтқанда, егер кванттық компьютерде есептеуге болатын функция болса, Гровер алгоритмі берілгенде оның мәнін табуға мүмкіндік береді. Осының салдарынан, Гровер алгоритмі симметриялық кілттік криптографияға қарсы көптеген күшпен іздеу шабуылдарына, соның ішінде соқтығысу шабуылдарына және алдын ала бейне шабуылдарына айтарлықтай асимптотикалық үдеуді қамтамасыз етеді. Дегенмен, бұл міндетті түрде ең тиімді алгоритм болмауы мүмкін, мысалы, параллельді rho алгоритмі SHA2-де Гровер алгоритмінен гөрі тиімдірек соқтығысуды таба алады.

Шектеулер

Гровердің алғашқы мақаласында алгоритм дерекқорды іздеу алгоритмі ретінде сипатталған, және бұл сипаттама әлі де жиі қолданылады. Бұл салыстырудағы дерекқор – функцияның барлық нәтижелерінің тізімі, кіріс деректерімен индекстелген. Дегенмен, бұл дерекқор нақты түрде көрсетілмейді. Оның орнына, индексі арқылы элементті бағалау үшін оракул шақырылады. Дерекқордың әрбір элементін біртіндеп оқып, оны осындай форматқа келтіру Гровердің іздеуінен әлдеқайда көп уақыт алады. Мұндай жағдайларды ескере отырып, Гровер алгоритмін теңдеуді шешу немесе шектеуді орындау ретінде қарастыруға болады. Мұндай қолданыстарда оракул – шектеуді тексеру құралы, және ол іздеу алгоритмімен байланысты емес. Бұл айырмашылық көбінесе алгоритмдік оңтайландыруларға кедергі келтіреді, ал дәстүрлі іздеу алгоритмдері мұндай оңтайландыруларға сүйеніп, толық іздеуден қашады. Құрметтісіміз, көптеген шектеулерді орындау және оптимизациялау мәселелері үшін Гровердің оракулын жылдам іске асыруға болады. Гровер алгоритмінен жылдамдық күте білуге кедергі келтіретін басты фактор – қол жеткізілген квадраттық жылдамдық, қазіргі кванттық компьютерлердің үлкен жүктемесін жеңу үшін жеткіліксіз. Алайда, жақсартылған аппараттық мүмкіндіктері бар, қателерге төзімді кванттық компьютерлердің келесі буындары деректердің нақты жағдайлары үшін осы жылдамдықты іске асыра алады.

Кванттық ішінара іздеу

Гроввердің алгоритмінің кванттық ішінара іздеу деп аталатын модификациясын 2004 жылы Гроввер мен Радхакришнан сипаттады. Ішінара іздеу кезінде мақсатты нысанның нақты мекенжайын табуға қызығушылық жоқ, тек мекенжайдың алғашқы бірнеше цифрлары ғана қызықтырады. Балама ретінде, іздеу кеңістігін блоктарға бөліп, «мақсатты нысан қай блокқа жатады?» деген сұраққа жауап табуға болады. Көптеген жағдайларда, егер мақсатты мекенжайда қажетті ақпарат болса, мұндай іздеу жеткілікті мәліметтер береді. Мысалы, Л.К. Гроввердің берген мысалына сәйкес, егер студенттердің тізімі сыныптық рейтингі бойынша реттелген болса, біз студенттің төменгі 25%, 25–50%, 50–75% немесе 75–100% пайыздық диапазонда екеніне ғана қызығушылық танытамыз. Ішінара іздеуді сипаттау үшін, әрқайсысы өлшемді блоктарға бөлінген деректер базасын қарастырайық. Ішінара іздеу мәселесі оңайырақ. Классикалық тәсілмен қарастырайық – біз бір блокты кездейсоқ таңдап, қалған блоктарды қалыпты іздеу арқылы тексереміз (жинақтар теориясының тілімен, толықтыру). Егер нысанды таппасақ, онда ол іздемеген блокқа кіретінін білеміз. Итерациялардың орташа саны Гровер алгоритміне қарағанда төмендейді. Ішінара іздеу, блоктардың санына байланысты сандық фактормен жылдамырақ болады. Ішінара іздеу жаһандық итерацияларды және жергілікті итерацияларды пайдаланады. Жаһандық Гровер операторы деп белгіленеді, ал жергілікті Гровер операторы деп белгіленеді. Жаһандық Гровер операторы блоктарға әсер етеді. Негізінен, ол келесідей беріледі:
Деректер базасының барлығы бойынша стандартты Гровер итерацияларын орындаңыз. Жергілікті Гровер итерацияларын орындаңыз. Жергілікті Гровер итерациясы – әрбір блок бойынша Гровер итерацияларының тікелей қосындысы. Бір стандартты Гровер итерациясын орындаңыз. және мәндерінің оптималды шамалары Гроввер мен Радхакришнанның мақаласында талқыланады. Сондай-ақ, «ажыратымдылықтың» әртүрлі деңгейлерінде бір-бірінен кейін ішінара іздеулерді қолданғанда не болатынын қарастыруға болады. Бұл идеяны Владимир Корепин мен Сюй егжей-тегжейлі зерттеді және оны екілік кванттық іздеу деп атады. Олар мұның бір ғана ішінара іздеуден жылдам емес екенін дәлелдеді.

A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004. In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L. K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25–50%, 50–75% or 75–100% percentile. To describe partial search, we consider a database separated into blocks, each of size The partial search problem is easier. Consider the approach we would take classically – we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the complement). If we don't find the target, then we know it's in the block we didn't search. The average number of iterations drops from to
Grover's algorithm requires iterations. Partial search will be faster by a numerical factor that depends on the number of blocks Partial search uses global iterations and local iterations. The global Grover operator is designated and the local Grover operator is designated
The global Grover operator acts on the blocks. Essentially, it is given as follows:
Perform standard Grover iterations on the entire database. Perform local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block. Perform one standard Grover iteration. The optimal values of and are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by Vladimir Korepin and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.

Оптималдылық

Гровер алгоритмі субконстанталық факторларға дейін оңтайлы. Яғни, дерекқорға тек Uω операторы арқылы қол жететін кез келген алгоритм, Гровер алгоритмінен кем емес, Uω операторын белгілі бір үлес ретінде қолдануы тиіс. Гровер алгоритмінің k сәйкес жазбаға дейін кеңейтілуі (N/k)1/2/4 де оңтайлы.