Алгоритм квантовой минимизации позволил факторизовать самое большое число на сегодняшний день Версия для слабовидящих
Алгоритм квантовой минимизации позволил факторизовать самое большое число на сегодняшний день Печать Email
Новости об инновациях
08.12.2014

Группа исследователей, работающая в области квантовых вычислительных технологий, установила рекорд в области квантовой факторизации (разложения числа на простые множители). Самым большим числом, которое было факторизовано при помощи квантового алгоритма, стало число 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, непрерывной работы не самой слабой вычислительной системы».

20141201_1_2.jpg Рис. 1.

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

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

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

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

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

Источник - http://www.nanonewsnet.ru/news/2014/algoritm-kvantovoi-minimizatsii-pozvolil-faktorizovat-samoe-bolshoe-chislo-na-segodnyashni

 

Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта