Современная электроника №1/2023

СОВРЕМЕННЫЕ ТЕХНОЛОГИИ 12 WWW.SOEL.RU СОВРЕМЕННАЯ ЭЛЕКТРОНИКА • № 1 / 2023 ● проверка наибольшего общего делителя с помощьювыражения НОД ( a ,N)=1 ; ● определение порядка r остатка a по модулю N ; ● вычисление НОД ( a r/2 − 1,N) в случае , если порядок r является чётным чис - лом . Следует иметь в виду , что минималь - ное значение r , при котором a в степени r тождественно равно единице ( mod N ), называется порядком a по модулю N . Именно в этом смысле в дальнейшем будет употребляться термин « порядок » (order). Порядок r является периодом функции f( x ) = a x mod N . Наиболее трудным этапом в реализа - ции квантового алгоритма Шора явля - ется как раз определение порядка a по модулю N . В этом эксперименте использова - лись спиновые кубиты на базе моле - кул C 4 F 5 Fe (perfluorobutadienyl iron) с изотопом углерода C13. Лаборатор - ный образец квантового компьюте - ра с ядерным магнитным резонансом позволил реализовать простейший пример факторизации числа « пятнад - цать » (15 = 3 × 5) с помощью алгоритма Шора . Следует подчеркнуть , что семь кубитов не позволяли реализовать фак - торизацию следующего числа без уве - личения количества кубитов , что в те времена и при данной конструкции квантового компьютера не представ - лялось возможным . Схема оригинального эксперимента по факторизации числа « пятнадцать » с помощью квантового компьютера и алгоритма Шора показана на рис . 2. Идея эксперимента заключалась в том , чтобы с помощью универсального квантового компьютера с вентильной обработкой (UDQGC) при использова - нии квантового преобразования Фурье (QuantumFourier Transform – QFT), дис - кретного логарифма (Discrete logarithm– DL) и оператора Адамара (Hadamard operator – H) последовательно переби - рать возможные варианты искомых сомножителей , следуя перечисленным выше шагам алгоритма Шора . В квантовом алгоритме Шора используется известная процедура квантовой оценки фазы (Quantum Phase Estimation – QPE), а также после - дующее определение собственного значения для некоторой унитарной матрицы U, соответствующего соб - ственному вектору |u ⟩ . Задача факто - ризации при этом сводится к нахож - дению за полиномиальное время количества битов , целевого числа , порядок которого определяется лога - рифмом log 2 N. Решив задачу поиска порядка целевого числа с помощью QPE и выполнив несколько допол - нительных шагов , можно уже дальше разложить на множители целое чис - ло N. В настоящее время неизвестен алгоритм , способный решить эту зада - чу для « больших чисел » за полиноми - альное время с помощью стандартно - го цифрового компьютера с бинарной логикой SBLC (Standard Binary Logic Computer) [19]. В верхней части на рис . 2 схематиче - ски показаны основные этапы экспе - римента в соответствии с алгоритмом Шора . В нижней части на рис . 2 при - ведена детальная квантовая схема экс - перимента для числа N = 15 и количе - ства кубитов a = 7. На рис . 2 квадратиками обозначе - ны вентили определённых операто - ров . Например , « H » – оператор Ада - мара , а « 45 » и « 90 » – это унитарные гейты вращения кубитов . Операция QFT (Quantum Fourier Transform) позволяет разложить задан - ную матрицу в произведение более простых унитарных матриц . Опера - тор Адамара используется в качестве разделителя кубита на его возможные состояния . Решение задачи ищется в форме дискретного логарифма . Функ - цию HD выполняют соответствующие вентили (Hadamard quantum gate – H ). Фактически оператор H разделяет кубит на равновероятные состояния . Например , если кубит соответствовал состоянию ноль , то H переведёт его в суперпозицию между нулём и едини - цей . После окончания процесса в тот момент , когда будет производиться измерение кубита , он случайным обра - зом может оказаться как в нуле , так и в единице . Функционально квантовый процесс вычислений состоит из четырёх после - довательных этапов , включающих задание начального состояния терми - ческого равновесия для семи кубитов , дискретное логарифмирование , кван - товое преобразование Фурье , измере - ние конечных состояний . В соответствии с алгоритмомШора , в котором рассматриваются только чёт - ные порядки , инициализация начина - лась со значения первого регистра , рав - ного n = 2[log 2 N] ( где n – количество кубитов , N – целевое число процес - са факторизации ). Во второй регистр записывалось значение m = 2[log 2 N] и т . д . На следующем этапе оператор Адамара применялся к первым «n» кубитам . Далее второй регистр умно - жался на функцию [f( x ) = a x mod N] , где a < N не имеет общих множите - лей с N. Затем выполнялось обратное квантовое преобразование Фурье ( QFT ) на первом регистре . На последнем чет - вёртом этапе проводилось измерение состояний первого регистра . Необходимо особо подчеркнуть , что в использованной схеме перебора зна - чений для реализации операции QFT необходимо такое количество вентилей H , которое будет кратно квадрату коли - чества вычислительных кубитов ( n 2 ). При использовании стандартного ком - пьютера с двоичной логикой для разло - жения числа в ряд с помощью преобра - зования Фурье потребуется количество управляемых ячеек памяти , кратное Рис . 2. Схема оригинального эксперимента по факторизации числа « пятнадцать » с помощью квантового компьютера и алгоритма Шора [1] В р е м е н н о е у с р е д н е н и е Обратное а ) б )