Созданы прототипы квантовых компьютеров
Сразу две группы исследователей, одна из Китая, одна из Австралии, построили управляемые лазером прототипы квантовых компьютеров, которые способны реализовать алгоритм Шора, сообщает новостная служба EurekAlert со ссылкой на журнал NewScientist.
Алгоритм Шора, разработанный Питером Шором (Peter Shor) в 1994 году, - квантовый алгоритм разложения числа на простые множители. Значимость его в том, что он делает потенциально возможным взлом мощнейших современных криптографических систем, в частности, шифра RSA.
Система RSA сейчас широко применяется в протоколах, использующихся в электронной коммерции, в защите программного обеспечения, в цифровых подписях. Шифр был создан в 1977 году американскими математиками Райвестом (Rivest), Шамиром (Shamir) и Адлеманом (Adleman). RSA является шифром с открытым ключом, то есть ключ, который нужен для шифрования данных, не хранится в тайне, зашифровать сообщение может кто угодно. Для расшифровки, однако, необходим второй ключ, секретный.
Для взлома шифра необходимо, в частности, разложить открытый ключ на два простых множителя. Эта задача решается перебором вариантов, поэтому надежность шифра зависит от длины ключа. Шифр с коротким ключом можно взломать даже на персональном компьютере, но если ключ достаточно длинный, то и современным суперкомпьютерам, и сетям распределенных вычислений для взлома потребуются десятки лет.
Алгоритм Шора, однако использует сильные стороны квантовых компьютеров, не имеющие аналогов в классических компьютерах: способность их информационных единиц - кубитов - принимать несколько значений одновременно и находиться в состоянии "запутанности". Теоретические работы показывают, что при наличии достаточно мощного квантового компьютера алгоритм способен взломать RSA за ограниченное время.
Прототипы квантовых компьютеров, созданные китайскими и австралийскими исследователями, очень примитивны: пока на два простых множителя удалось разложить лишь число 15. Однако эти работы показывают, что реализация алгоритма Шора возможна в принципе, дальнейшее - скорее инженерная задача (правда, по мнению некоторых специалистов, нерешаемая).
В 2001 году корпорация IBM также создала управляемый ядерно-магнитным резонансом (ЯМР) квантовый компьютер из семи кубит, который тоже мог разложить число 15 на 5 и 3. Однако и китайская, и австралийская группы считают, что компьютер IBM имел серьезные недостатки: во-первых, использование ЯМР (сложной и дорогой технологии) при возрастании числа кубитов приводит к помехам, так что возможности развития сильно ограничены, во-вторых, исследователи сомневаются, что в компьютере действительно использовалась квантовая запутанность.
Управляемые короткими вспышками обычного лазера новые компьютеры свободны от этих недостатков, утверждают их разработчки.
Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время O(N3(log N)k), где k=const, затратив O(log N) места.
Значимость алгоритма заключается в том, что при использовании достаточно мощного квантового компьютера, он сделает возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ N, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители N. При достаточно большом N это практически невозможно сделать, используя известные классические алгоритмы. Так как алгоритм Шора работает только на квантовом компьютере, в настоящее время не существует технических средств, позволяющих за полиномиальное время разложить достаточно большое число на множители. Алгоритм Шора в свою очередь, используя возможности квантовых компьютеров, способен произвести факторизацию числа за полиномиальное время. Это может поставить под угрозу надёжность большинства криптосистем с открытым ключом, основанных на сложности проблемы факторизации чисел.
Как и другие алгоритмы для квантовых компьютеров, алгоритм Шора вероятностный: он даёт верный ответ с высокой вероятностью. Вероятность ошибки может быть уменьшена при повторном использовании алгоритма. Тем не менее, так как возможна проверка предложенного результата (в частности простоты числа) в полиномиальное время, алгоритм может быть модифицирован так, что ответ, полученный в полиномиальное время, будет верным с единичной вероятностью.
Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.
Основные идеи алгоритма ШораАлгоритм Шора основан на возможности быстро вычислить собственные значения унитарного оператора с высокой точностью, если можно эффективно вычислять любые его степени. Взяв в качестве такого оператора умножение на x по модулю N (этот оператор действует в 2n мерном пространстве, где , преобразуя базисный вектор, соответствующий числу a, в базисный вектор, соответствующий числу xa(modN)), мы сможем вычислить такое n, что xn = 1(modN), что позволяет (с высокой вероятностью) разложить N на множители на обычном компьютере.
Взято здесь-http://ru.wikipedia.org/wiki/Алгоритм_Шора
Квантовая запутанность
Ква́нтовая запу́танность (спутанность, реже — сцепление) (entanglement) — квантовомеханическое явление, при котором квантовое состояние двух или большего количества объектов должно описываться во взаимосвязи друг с другом, даже если отдельные объекты разнесены в пространстве. Вследствие этого возникают корреляции между наблюдаемыми физическими свойствами объектов. Например, можно приготовить две частицы, находящиеся в едином квантовом состоянии так, что когда одна частица наблюдается в состоянии со спином, направленным вверх, то спин другой оказывается направленным вниз, и наоборот, и это несмотря на то, что согласно квантовой механике, предсказать, какие фактически каждый раз получатся направления, невозможно. Иными словами, создаётся впечатление, что измерения, проводимые над одной системой, оказывают мгновенное воздействие на запутанную с ней. Однако то, что понимается под информацией в классическом смысле, всё-таки не может быть передано через запутанность быстрее, чем со скоростью света.Квантовая запутанность является основой таких будущих технологий, как квантовый компьютер и квантовая криптография, а также она была использована в опытах по квантовой телепортации. В теоретическом и философском плане данное явление представляет собой одно из наиболее революционных свойств квантовой теории, так как можно видеть, что корреляции, предсказываемые квантовой механикой, совершенно несовместимы с представлениями о, казалось бы, очевидной локальности реального мира, при которой информация о состоянии системы может передаваться только посредством её ближайшего окружения. Различные взгляды на то, что в действительности происходит во время процесса квантовомеханического запутывания, ведут к различным интерпретациям квантовой механики.
Истоки
Запутывание — это одно из тех свойств квантовой теории, за которое её не любил А. Эйнштейн и некоторые другие учёные. В 1935 г. Эйнштейн, Подольский и Розен сформулировали знаменитый ЭПР парадокс, который показал, что из-за запутывания квантовая механика становится нелокальной теорией. Известно, как Эйнштейн высмеивал запутывание, называя его «кошмарным дальнодействием».
С другой стороны, квантовая механика отлично зарекомендовала себя в предсказании экспериментальных результатов, и фактически наблюдались даже сильные корреляции, происходящие благодаря феномену запутывания. Есть способ, который позволяет, казалось бы, успешно объяснить квантовое запутывание — подход «теории скрытых параметров» при котором за корреляции отвечают определённые, но неизвестные микроскопические параметры. Однако, в 1964 г. Дж. С. Белл показал, что «хорошую» локальную теорию таким образом построить всё равно не удастся, то есть, запутывание, предсказываемое квантовой механикой, можно экспериментально отличить от результатов, предсказываемых широким классом теорий с локальными скрытыми параметрами. Результаты последующих экспериментов дали ошеломляющее подтверждение квантовой механики. Некоторые проверки показывают, что в этих экспериментах есть ряд узких мест, но общепризнано, что они несущественны.
Запутывание приводит к интересным взаимоотношениям с принципом относительности, который утверждает, что информация не может переноситься с места на место быстрее, чем со скоростью света. Хотя две системы могут быть разделены большим расстоянием и быть при этом запутанными, передать через их связь полезную информацию невозможно, поэтому причинность не нарушается из-за запутанности. Это происходит по двум причинам:
1.результаты измерений в квантовой механике носят принципиально вероятностный характер
2.теорема о клонировании квантового состояния запрещает статистическую проверку запутанных состояний.Взято здесь-http://ru.wikipedia.org/wiki/Квантовая_запутанность
Алгоритм шифрования RSA
Шифрование — это обратимое преобразование данных с целью их сокрытия от посторонних. Методов шифрования было придумано множество — от шифров простой замены (наиболее известный пример — "Пляшущие человечки" Конан Дойля) до принципиально не вскрываемого шифра Вернама (двоичное сложение исходного текста с однократно используемой случайной последовательностью). Почти все методы шифрования используют ключ шифрования — секретную кодовую последовательность, используемую в процессе преобразования информации.
Большинство современных стойких симметричных алгоритмов используют ключ длиной 64—256 бит (8—32 байта). Ниже, в таблице 1.1 перечислены основные, используемые в настоящее время алгоритмы, их длины блока и длины ключа.
RSA (авторы: Rivest, Shamir и Alderman) это система с открытым ключом (public-key) предназначенная как для шифрования, так и для аутентификации была разработана в 1977 году. Она основана на трудности разложения очень больших целых чисел на простые сомножители.
RSA очень медленный алгоритм. Для сравнения, на программном уровне DES по меньше мере в 100 раз быстрее RSA, на аппаратном аж в 1,000-10,000 раз, в зависимости от выполнения.
источник
