Инженеры и физики из британского Университета города Бристоль разработали компактный кремниевый чип, использующий так называемый Алгоритм Шора для решения математических задач. Размер чипа не превышает размера монеты, а в его основе лежат квантовые принципы.
Алгоритм Шора является квантовым алгоритмом факторизации (разложения числа на простые множители). Значимость алгоритма заключается в том, что при использовании достаточно мощного квантового компьютера, он сделает возможным взлом криптографических систем с открытым ключом. Так как алгоритм Шора работает только на квантовом компьютере, в настоящее время не существует технических средств, позволяющих за полиномиальное время от длины числа разложить достаточно большое число на множители.
Используя возможности квантовых компьютеров, алгоритм способен произвести факторизацию числа за полиномиальное время. Это может поставить под угрозу надёжность большинства криптосистем с открытым ключом, основанных на сложности проблемы факторизации чисел.
Джереми О'Брайен, руководитель разработки чипа, говорит, что над процессором группа из местных преподавателей и аспирантов трудилась несколько месяцев. "Вначале мы создали прототип чипа в увеличенном масштабе, он занял почти всю лабораторию, позже был создан реальный прототип. Работа с алгоритмом Шора стала возможной благодаря усложнению чипа и добавления туда нескольких логических схем", - говорит он.
Как и другие алгоритмы для квантовых компьютеров, алгоритм Шора вероятностный: он даёт верный ответ с высокой вероятностью. Вероятность ошибки может быть уменьшена при повторном использовании алгоритма. Тем не менее, так как возможна проверка предложенного результата (в частности простоты числа) в полиномиальное время, алгоритм может быть модифицирован так, что ответ, полученный в полиномиальное время, будет верным с единичной вероятностью.
Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.
Изюминка чипа состоит в том, что для соединения между узлами устройства используются не обычные медные соединения, а оптические мини-каналы, по которым передаются фотоны. "Наш чип имеет ограниченную возможность разложения факторингового алгоритма, чтобы система работала в практическом масштабе, мощность современных процессоров надо увеличить минимум в миллион раз", - говорит специалист.
Источник: CyberSecurity
|
