Кіріспе
Компьютерлік ғылымдағы өте жалпы проблема
Жасырын кіші топтар проблемасы (HSP) – математика және теориялық компьютерлік ғылымдағы зерттеу тақырыбы. Бұл құрылым факторлау, дискретті логарифм, граф изоморфизмі және ең қысқа вектор мәселесі сияқты мәселелерді қамтиды. Бұл оны кванттық есептеу теориясында ерекше маңызды етеді, себебі Шор алгоритмі кванттық есептеуде факторлау үшін шекті абельдік топтардағы жасырын кіші топтар проблемасының мысалы болып табылады, ал қалған проблемалар абельдік емес шекті топтарға сәйкес келеді.
Мәселе туралы мәлімдеме
Топ, кіші топ және жиын берілген жағдайда, функция кіші топты жасырады деуге болады, егер барлық үшін егер және тек егер болса, . Басқаша айтқанда, функция H-тың косеттерінде тұрақты, ал H-тың әр түрлі косеттерінде әр түрлі болады.
Hidden subgroup problem: Let be a group, a finite set, and a function that hides a subgroup The function is given via an oracle, which uses bits. Using information gained from evaluations of via its oracle, determine a generating set for
A special case is when is a group and is a group homomorphism in which case corresponds to the kernel of .
Жасырын кіші топтар мәселесі: Топ , шекті жиын және кіші топты жасыратын функция болсын. Функция биттерді қолданатын оракул арқылы беріледі. Оның оракулы арқылы бағалаудан алынған ақпаратты пайдалана отырып, үшін генерациялық жиынтықты анықтаңыз.
Hidden subgroup problem: Let be a group, a finite set, and a function that hides a subgroup The function is given via an oracle, which uses bits. Using information gained from evaluations of via its oracle, determine a generating set for
A special case is when is a group and is a group homomorphism in which case corresponds to the kernel of .
Арнайы жағдай - бұл топ және топ гомоморфизмі, онда функция гомоморфизмнің ядросына сәйкес келеді.
Hidden subgroup problem: Let be a group, a finite set, and a function that hides a subgroup The function is given via an oracle, which uses bits. Using information gained from evaluations of via its oracle, determine a generating set for
A special case is when is a group and is a group homomorphism in which case corresponds to the kernel of .
Мотивация
Жасырын кіші топтар мәселесі кванттық есептеу теориясында келесі себептерге байланысты ерекше маңызды. Шор алгоритмі, сандарды факторизациялау және дискретті логарифмдерді табу (сондай-ақ оның бірнеше кеңейтімдері) үшін, шекті абельдік топтар үшін ЖКМ-ді (Жасырын Кіші Математикалық) шеше алу қабілетіне негізделген. Егер белгілі бір абельдік емес топтар үшін ЖКМ-ге тиімді кванттық алгоритмдер болса, онда екі маңызды мәселе үшін тиімді кванттық алгоритмдердің болуын білдіреді: граф изоморфизмі мәселесі және торлардағы ең қысқа вектор мәселелері (ЕҚВМ). Нақтырақ айтқанда, симметриялық топ үшін ЖКМ-ге тиімді кванттық алгоритм граф изоморфизмі үшін кванттық алгоритм береді. Диэдрлік топ үшін ЖКМ-ге тиімді кванттық алгоритм бірегей ЕҚВМ үшін кванттық алгоритм береді.
Алгоритмдер
Уақыт бойынша полиномдық болатын шекті абельдік топтардағы HSP мәселесін шешуге арналған тиімді кванттық алгоритм бар. Кез келген топтар үшін, жасырын кіші топ мәселесі оракулға сұрау жасаудың полиномдық санымен шешіледі. Дегенмен, мұны іске асыратын тізбектердің мөлшері экспоненциалды болуы мүмкін, бұл алгоритмді жалпы тиімсіз етеді; тиімді алгоритмдер оракулға сұрау жасау саны мен орындалу уақыты бойынша полиномдық болуы керек. Кез келген топтар үшін мұндай алгоритмнің бар екені әлі де ашық мәселе. Кванттық полиномдық уақыт алгоритмдері, мысалы, кейбір абельдік топтардың жартылай тікелей көбейтінділері сияқты, топтардың белгілі бір кіші топтары үшін бар.
Абельдік топтар алгоритмі
Абельдік топтар алгоритмі бейнелеулерді, яғни -тан -ға гомоморфизмдерді пайдаланады, мұнда - күрделі сандар бойынша жалпы сызықтық топ. Егер оны екі немесе одан көп бейнелеулердің тікелей қосындысы ретінде жазу мүмкін болмаса, бейнелеу түгелдей (қайталанбайтын) болып саналады. Абельдік топ үшін барлық түгелдей бейнелеулер бір өлшемді, яғни сипаттамалар болып табылады; абельдік топтар үшін үлкен өлшемді түгелдей бейнелеулер жоқ.
Кванттық Фурье түрлендірмесін анықтау
Кванттық Фурье түрлендіруі, ретіндегі аддитивті циклдік топ ретінде анықталады. осы топтың ретін енгізе отырып, және оның белгісін таныстыра отырып, кванттық Фурье түрлендіруінің анықтамасы былай беріледі. Сонымен қатар, кез келген абелдік топты бірнеше циклдік топтардың тікелей қосындысы ретінде жазуға болады. Кванттық компьютерде бұл тиісінше өлшемдері бар бірнеше тізілімдердің тензорлық көбейтіндісі ретінде көрсетіледі, ал жалпы кванттық Фурье түрлендіруі .