Группа исследователей, работающая в области квантовых вычислительных технологий, установила рекорд в области квантовой факторизации (разложения числа на простые множители). Самым большим числом, которое было факторизовано при помощи квантового алгоритма, стало число 56153, и это число существенно больше числа 143, которое было факторизовано в 2012 году. Для разложения числа на множители исследователи использовали туже самую технологию высокотемпературного ядерного магнитного резонанса (nuclear magnetic resonance, NMR), которая использовалась и для разложения числа 143, и четыре кубита квантовой вычислительной системы. Этим самым было продемонстрировано, что использованный алгоритм квантовой минимизации подходит для факторизации любых чисел гораздо лучше, нежели достаточно известный в определенных кругах алгоритм Шора, при помощи которого удавалось разложить число 21, задействовав для этого целых 10 кубитов квантовой системы.

В статье, опубликованной в онлайн-издании arXiv, Найк Дэттэни из университета Киото и Оксфордского университета, совместно с Натаниэлем Брайансом из университета Калгари, пишут, что

при помощи метода квантовой минимизации им удалось также сделать первое «тройное» разложение. Используя всего 3 кубита квантовой системы, они разложили число 175 на множители 5, 5 и 7. А пока только в теории, имеющаяся у них система позволит факторизовать большие числа, к примеру, число 291311, для разложения которого потребуется всего 6 кубитов.

Разработанный учеными алгоритм квантовой минимизации, с момента его первого появления в 2001 году, проходил через процесс постоянных улучшений и модификаций. В отличие от этого, алгоритм Шора так и остался неизменным с момента его появления в 1994 году.

«Число 56153 состоит всего из 16 бит» – рассказывает Найк Дэттэни, – «Тем не менее, в этом числе заключено в два раза больше бит, чем в самом большом числе, факторизованном при помощи алгоритма Шора. При помощи нашего алгоритма процесс факторизации числа 56153 потребовал всего 4 кубитов, в то время, как факторизация числа 21 алгоритмом Шора была проведена при помощи 10 кубитов».

«Несмотря на эти достижения, мы все еще очень и очень сильно отстаем от классических компьютеров» – рассказывает Дэттэни, – «Самое большое число, разложенное на обычных компьютерах, было ключом алгоритма RSA, длиной 768 бит. Правда, для разложения этого числа потребовалось почти два года, с 2007 по 2009, непрерывной работы не самой слабой вычислительной системы».

Рис. 1.

Напомним нашим читателям, что открытые ключи алгоритма шифрования RSA, как и ключи некоторых других подобных алгоритмов, являются большими числами, имеющими два главных простых множителя. Из-за большой величины этих чисел факторинг ключей RSA является крайне сложной и крайне длительной процедурой, которой требуются значительные вычислительные ресурсы.

Именно поэтому алгоритм RSA используется правительствами многих стран, вооруженными силами, банками и другими организациями, которым требуется держать в безопасности критическую для них информацию.

Появление квантового компьютера с динамическим количеством квантовых битов (кубитов), способных эффективно за короткое время выполнять алгоритм Шора или алгоритм квантовой минимизации для больших чисел, может сделать большинство современных криптографических технологий неактуальными и поставить под угрозу системы банковской, военной и других видов связи.

«Алгоритм Шора, использующий квантовую оптимизацию при помощи квантовых цепей определенной конфигурации, в теории, может справиться с факторизацией больших чисел гораздо быстрее обычных классических компьютеров» – рассказывает Дэттэни, – "Однако, выполнение квантовых операций заранее сконфигурированной схемой лишает квантовый компьютер вариативности, и, поэтому, еще совершенно непонятно, кто сможет стать победителем в факторинге ключа RSA-896, к примеру.

Наш алгоритм, альтернатива алгоритму Шора, все еще является истинно квантовым алгоритмом, который не привязан к определенной конфигурации кубитов. И в ближайшем будущем мы собираемся проверить то, что такой подход может помочь достичь того, что абсолютно недостижимо для обычных компьютеров".