|
|
Субботний блик науки № 70
Спутаные кванты
Все переплелось, как хорошие спагетти. Короли безнадежно смешаны с капустой, мед с пчелами, а компьютеры с фундаментальной физикой. Причем в последнем случае кто-то, не поскупясь на фантазию, подмешал в салат еще и криптографию, дабы придать настоящей остроты.
Связь физики с компьютерами. Что может быть банальнее? Вычислительное моделирование давно и прилежно используется физиками. Всякий сколь-нибудь тянущий на серьезность современный ускоритель частиц вообще немыслим без сонма компьютерных сетей, которые только и способны разгрести сыплющийся из детектора водопад данных.
А стоит ли говорить о вычислительном моделировании процессов в разнообразных жидких, газообразных и твердых средах? Нет. Не стоит. Старо. Но есть одна действительно интересная связь, установившаяся в последние лет двадцать между компьютерами и физикой. Причем физикой фундаментальной. Эта связь — квантовый компьютер. Его придумали в восьмидесятых годах прошлого века. Придумали хорошо: смелая концепция жива до сих пор, и развивается.
Если в том «классическом» компьютере, с помощью которого делается доступной через Интернет эта страница, каждое элементарное «арифметическое устройство» вынуждено работать с наборами чисел поочередно, обрабатывая сперва одно, потом следующее, то компьютер квантовый способен обрабатывать в своем, квантовом же, «арифметическом устройстве» сразу несколько чисел. Одновременно. Благодаря законам квантовой механики.
Вы думаете, это параллельные вычисления? Нет. Это вычисления квантовые: элементарная «микросхема» квантового компьютера способна одновременно пребывать во всех разрешенных состояниях. Каждый «бит» (именуемый «кубитом») в квантовом вычислителе готов одновременно быть и нулем, и единицей. Это листок блокнота может быть либо чистым, либо заляпаным кляксой. А квантовый вычислитель, благодаря тому что он квантовый, пребывает сразу в двух состояниях: он и чистый, и заляпаный. Вот, правда, стоит вам лишь на него взглянуть, как магия тут же разрушится: квантовый листок станет либо белым, либо с кляксой. Такая вот нестрогая арифметика, не мешающая тем не менее считать, — надо лишь придумать специальные, квантовые алгоритмы, базирующиеся на вероятностях.
Может, это и сложно представить. Может. Но в нашей колонке речь о другом аспекте.
Квантовый компьютер (коли его удастся создать в том виде, в каком он задуман) теоретически способен сильно превзойти компьютер обычный в решении некоторых видов проблем. Да. Самая популярная из них — это алгоритм Шора для факторизации чисел. Под факторизацией понимается нахождение разложения числа на множители (см. заметки на полях), и изящный в своей техничности алгоритм Шора способен находить такое разложение очень быстро, одновременно проверяя большой набор вариантов. Конечно, только на квантовом компьютере.
А факторизация чисел важна для «прикладной» коммерческой криптографии, потому как такие сверхпопулярные системы шифрования с открытым ключом, как RSA, целиком и полностью полагаются на трудность проблемы факторизации (а ее, надо отметить, сейчас простым способом решать не умеют; пока — не умеют). Если кто-то научится факторизовать большие числа за разумное время, то современной коммерческой криптографии больше не станет. Не станет одномоментно.
Поэтому строят квантовые компьютеры.
Но если у вас на руках число в тысячу двоичных разрядов, то, для того чтобы пропустить цифры числа сквозь решето алгоритма Шора, вам и квантовый компьютер понадобится соответствующего размера. В тысячу кубитов — это как утрированный минимум; в реальности — на порядки больше, ибо ошибки, ошибки и имманентные неточности — вот спутники вероятностных квантовых вычислений.
И тут возникает та связь, ради которой весь сыр-бор: квантовый компьютер с числом кубитов в тысячу имеет 21000 состояний. 21000 — это не просто много. Это в невероятно большое число раз больше, чем предполагаемое количество атомов во Вселенной, умноженное само на себя. И кто там его знает, работает ли современная квантовая механика для столь большого числа состояний. А ведь именно она, современная квантовая механика, лежит в основе концепции квантового компьютера, шустро факторизующего числа, шурша алгоритмом Шора.
Нет, конечно не идет и речи о том, что большой квантовый компьютер вдруг станет «классическим» — тут все более-менее ясно. Но кто его знает, не вскроются ли при запуске такой машины некоторые новые, куда как более глубокие и фундаментальные свойства нашего Мира? И квантовую механику придется сильно уточнять. А хотелось-то всего ничего: взломать криптосистему с открытым ключом.
Вот так все переплелось. Теперь и физика связана с компьютерами самым фундаментальным образом: через кванты и криптографию. Что-то там нового вычислят в квантовой механике?
***
Автор благодарит Игоря Иванова и Андрея Сидоренко за небольшую, но содержательную виртуальную дискуссию, подтолкнувшую к написанию этого текста.
***
Еще со времен Древних греков известно, что всякое натуральное число (>1) либо является простым, либо может быть представлено в виде произведения простых чисел. Нахождение разложения числа на простые множители называется факторизацией. Например, число 21 можно представить как 7*3. И хотя неспециалисту задача может показаться несложной, универсального и эффективного метода факторизации чисел пока не найдено (по крайней мере, он не опубликован в открытой печати). Под универсальным и эффективным понимается метод, факторизующий за разумное время числа порядка, скажем, как 10100 (именно такие числа используются в криптографии).
На настоящий момент, алгоритм Шора применялся на практике в квантовом компьютере из семи кубитов. Этот кроха, собранный из набора атомов в исследовательском центре IBM, сумел факторизовать число 15=3*5.
Не стоит путать квантовые компьютеры и квантовую криптографию — это и математически, и физически совсем разные вещи, похожие куда меньше, чем морской слон и слон африканский.
24.12.2005
Теги: квантовые вычисления
математика
физика
|
Ваш отзыв автору
|
|
|
