Сейчас весьма абстрактные идеи, лежащие в основе квантовой физики, воплощаются в реальность благодаря новым технологическим возможностям в области нанотехнологий и оптических взаимодействий. Об одной из таких идей, идее квантового компьютера, далее и пойдет речь. Постараюсь как можно более популярней.
Чтобы быть последовательными, нельзя не упомянуть о теоретических достижениях квантовой физики, которые сделали возможными на практике создавать такие устройства.
Вообще что же такое квантовая механика? Известно, что квантовая механика – теория, которой подчиняются микроскопические системы, например атомы. Микромир — атомы, электроны, фотоны и другие частицы — живет по особым законам. Там не просто все очень маленькое, там все совсем другое, и многие явления микромира не имеют аналогов в привычном нам макромире, из-за чего кажутся фантастическими.
Характерная черта квантовой механики, которая запечатлелась в названии – в некоторых физических системах энергия квантуется, т.е может быть равно одному из некоторого дискретного множества чисел, а может даже и никакого иного значения (запрещенная зона). Если пытаться вообразить такую ситуацию в макромире, то можно представить, например, что предметы имеют температуру, которая выражается только целым числом градусов. То есть 10, 20, 31, 36 градусов — может быть, а вот 36,6 — просто невозможно. Нагревать и охлаждать предметы можно, но при этом температура будет скакать туда-сюда сразу на градус.
В частности, энергия электромагнитного поля излучается только в виде дискретных неделимых порций. Вот такая порция и называется квантом. Предположение о существовании квантов сделал в 1900-1901 годах Макс Планк, положив тем самым начало квантовой теории, квантовой механике и еще много чему с прилагательным квантовый — в том числе и компьютерам.
Другим удивительным свойством фотонов, электронов и иных частиц является то, что они могут проявлять свойства как частиц, так и волн. Свет представлявшйся в классической физике как электромагнитная волна, оказался в квантовой физике совокупностью фотонов, подобных частицам. Но и наоборот, частицы, такие как электроны, обнаруживают свойства, характерные для волны: они интерферируют друг с другом и дифрагируют на препятствиях (то есть огибают их). Это свойство частиц дало основание в первые годы называть описывающую их теорию волновой механикой, и лишь впоследствии утвердилось название «квантовая механика»
И наконец третье фундаментальное свойство: квантовый объект, в отличие от классического, изначально статистический. Описать местонахождение не наблюдаемой непосредственно частицы в некотором месте можно только с некоторой вероятностью
На наблюдения и измерения в микромире тоже есть существенное ограничение: принцип неопределенности Гейзенберга: нельзя точно измерить одновременно скорость и координаты частиц.
Пока мы объекты не измеряем, они ведут себя и того хуже. Если квантовая система может находиться в нескольких состояниях и неизвестно, в каком именно она находится, то говорят о суперпозиции состояний. Можно говорить, что неизвестно, в каком состоянии находится система, или что она находится в нескольких состояниях одновременно, это вопрос интерпретации. В любом случае при измерении система выбирает одно из состояний.
Известным наглядным примером является мысленный эксперимент, называемый «кот Шредингера»: в закрытый ящик помещены живой кот, емкость с ядовитым газом и радиоактивное ядро. Если ядро распадается, оно приводит в действие механизм, который открывает емкость с газом и тем самым убивает кота. Вероятность того, что ядро распадется за час, — 50 процентов. Через час кот в ящике жив с вероятностью 50 процентов. С точки зрения квантовой механики, пока ящик закрыт, кот находится в суперпозиции двух состояний (то ли жив, то ли мертв; и жив, и мертв; ни жив ни мертв — как угодно). В тот момент, когда наблюдатель открывает ящик, он видит, жив кот или мертв.
Наконец, еще одно важное для нас явление — квантовая запутанность (entanglement), она же спутанность, сцепление, иногда связанность. О запутанности говорят, когда состояние двух (или более) квантовых систем должно описываться во взаимосвязи друг с другом, даже если сами системы разнесены в пространстве. Соответственно, физические свойства каждой из систем связаны с физическими свойствами другой, при том что они могут находиться не рядом и ничем не соединяться.
Если две запутанные системы находятся в суперпозиции состояний, то, измерив состояние одной, можно узнать состояние другой. Например, можно запутать два атома, спин (определенная квантовая характеристика) одного из которых будет направлен вверх, а другого — вниз, причем мы не будем знать, у какого атома какой спин. Но измерив спин одного атома, мы тут же узнаем и спин другого, даже если они разнесены в пространстве.
Все эти и многие другие особенности микромира и позволяют построить квантовый компьютер.
Квантовый компьютер, как и любое другое устройство для вычислений, должен оперировать с числами. Простейшее устройство, способное представлять числа — это устройство, которое может находиться в двух устойчивых состояниях. Так, проводники с током могут находится в двух устойчивых состояниях: когда нет тока — соответствует значению 0, и когда ток есть — соответствует значению 1. Никакого другого устойчивого состояния быть не должно. Использование таких устройств для проведения действий над числами возможно благодаря двоичной записи чисел — в такой ячейке хранится информация, соответствующая выбору между двумя вариантами (цифрами 0 и 1 или, эквиалентно, двумя состояниями системы). Говорят, что количество информации, хранящееся в двоичной ячейке, равно 1 биту. В двух двоичных ячейках хранится 2 бита информации. Это соответствует выбору между 2-разрядными двоичными числами 00, 01, 10 и 11. В регистре, состоящем из N двоичных ячеек, хранится N бит информации, что соответствует выбору одного N — разрядного двоичного числа из всех возможных (всего таких чисел 2^N).
Посмотрим теперь, чем отличается хранение информации в квантовом компьютере. Сама информация тоже может быть представлена в форме двоичных чисел, то есть цепочек нулей и единиц. Одна цифра двоичного числа хранится в двоичной ячейке. Эта ячейка называется кубитом и представляет собой квантовую систему, одно из состояний которой соответствует цифре 0, а второе — цифре 1. Обозначим эти состояния ψ1 и ψ2. До сих пор не видно никаких отличий от классического компьютера. Но именно в этом пункте появляется существенное отличие. Дело в том, что для квантовых систем имеет место так называемый принцип суперпозиции: если квантовая система может находиться в одном из двух состояний, скажем, в состоянии ψ1 и в состоянии ψ2, то она может также находиться в целом семействе состояний, которые строятся как линейные комбинации исходных. Это значит, что исходные состояния умножаются на некоторые (комплексные) числа и складываются. Если выбираются числа c1 и c2, то получается состояние c1ψ1+ c2ψ2.
В частности, если кубит приводится в состояние (∣0〉+∣1〉)/√2, то это значит, что в нем одновременно записаны и цифра 0, и цифра 1.
Итак, в одной двоичной ячейке квантового компьютера, называемой кубитом, может храниться не только одна из двух цифр двоичного счисления, 0 или 1 (как было бы в случае классического компьютера), но одновременно обе эти цифры. НАпример, в двух кубитах могут храниться одновременно 4 двоичных числа 00, 01, 10 и 11. А если в некотором регистре квантового компьютера содержится N кубитов, то в таком регистре может храниться одновременно 2^N двоичных чисел длины N. И при действии квантового компьютера одновременно обрабатываются все эти числа. Это и есть квантовый параллелизм. Если бы в нашем распоряжении были только классические компьютеры, каждый из которых работает с двоичными числами длины N, то для одновременной обработки 2^N таких чисел было бы необходимо 2^N компьютеров. Если же мы сумели построить квантовый компьютер, содержащий N кубитов, то один (!!!) этот компьютер одновременно обрабатывает все 2^N чисел.
В отличие от классических, квантовые компьютеры не универсальны: не для всяких вычислительных задач существует алгоритм их решения на квантовом компьютере. До сих пор найдено лишь небольшое число квантовых алгоритмов.
Наиболее известные квантовые алгоритмы:
1) Алгоритм Шора (факторизация)
2) Алгоритм Гровера (быстрый поиск в неупорядоченной базе данных)
3) Алгоритм Дойча — Джоза (ответ на вопрос, постоянная или сбалансированная функция)
Квантовые алгоритмы благодаря использованию явления квантовой запутанности и принципа суперпозиции обладают значительным приростом скорости выполнения по сравнению с соответствующими классическими алгоритмами.
Чуть подробней остоновимся на алгоритме Шора, который позволяет решить любую из двух математически эквивалентных задач:
1) найти период сложной периодической функции или
2) разложить на простые множители очень большое число
Вторая из этих задач имеет важное прикладное значение, потому что она используется в криптографии. Дело в том, что в одной из криптографических методик для шифровки и дешифровки секретных посланий (шифрование с открытым ключом) используют большие числа, для которых известны их разложения на множители. Ясно, что такие числа получить легко: достаточно перемножить большое число простых чисел, и мы получим очень большое число, для которого разложение на простые множители известно. Получатель закодированного секретного послания может его декодировать потому, что в процедуре декодирования используется разложение на множители длинного числа, а он знает это разложение.
Если бы противник смог разложить это число на простые множители, он также смог бы декодировать послание. Однако для такого разложения требуется огромное время. Поэтому с практической точки зрения декодировать такое послание невозможно. Но если бы в распоряжении противника был квантовый компьютер (достаточной мощности, то есть работающий с достаточно большими числами), то он мог бы разлагать длинные числа на простые множители и значит легко мог бы расшифровывать такого рода послания. Этот распространенный в криптографии метод перестал бы работать. Это один из аргументов, которые делают важным создание квантового компьютера.
Физические:
Математические:
Эти проблемы можно описать одним словом — масштабируемость. Присоединить дополнительную память к обычному компьютеру — простая рутинная процедура. Присоединение каждого нового кубита к КК — пока что штучная работа.
Явление декогеренции заключается в том, что измеряемая система теряет свои специфические квантовые свойства. Иными словами, чистое состояние быстро превращается в смесь при взаимодействии квантовой системы с окружающей средойю.
Для борьбы с декогеренцией разрабатываются, с одной стороны, различные методы изоляции квантовой системы, включая использование крайне низких температур и высокого вакуума, а с другой — введение в квантовые вычисления кодов, устойчивых к ошибкам, связанным с декогеренцией (обычно в таких схемах состояние логического кубита кодируется состоянием нескольких связанных физических кубитов).
Точность унитарных операторов по разным оценкам должна быть от 99,99 до 99,999999 (зависит от конкретной реализации).
Ионные ловушки — первая и наиболее хорошо разработанная идея. Об одном из сверхпроводниковых компьютеров пойдет речь далее. Ну а квантовые точки считаются наиболее перспективным вариантом.
В феврале 2007 года канадская компания D-Wave Systems собрала 16-кубитовый квантовый компьютер, который основатель и генеральный технический директор Джорджи Роуз (Geordie Rose) назвал самым мощным квантовым компьютером, когда либо построенным, и первым, который может запускать коммерчески-значимые приложения. В ноябре 2007 года на конференции, посвященной суперкомпьютерам, та же компания D-Wave продемонстрировала работу образца уже 28-кубитного компьютера (чип Leda) онлайн. Сейчас компания тестирует прототип 128-кубитного чипа, который получил кодовое название Rainier. В дальнейших планах компании — создать уже в ближайшем будущем 1024-кубитный компьютер.
Всё это, согласитесь, намного превосходит большинство других разработок квантовых компьютеров, причём D-Wave смогла создать компьютер, используя технологии производства полупроводников и существующие полупроводниковые заводы, не прибегая к помощи оптических схем, квантовых точек, сдерживания лазера или других экзотических технологий производства. D-Wave работает и над второй половиной проблемы, а именно над инструментами программирования для создания приложений, способных получить преимущество от возможностей, которые обещают дать квантовые вычисления.
Материал в квантовом чипе D-Wave — это ниобий; охладите его до достаточно низкой температуры, и он станет сверхпроводником. Когда обычный металл проводит электрический ток, электроны, носители электрического заряда, сталкиваются с неидеальной структурой металла, в результате чего появляется сопротивление. Когда вы охлаждаете сверхпроводящий металл подобно ниобию, электроны металла формируют куперовские пары. Когда куперовские пары входят в переходы Джозефсона на чипе (состоящие из двух сегментов сверхпроводящего ниобия, связанных слабым изолирующим барьером), их можно представить как электроноподобные квазичастицы, которые могут туннельно проходить через изолятор в переходе, эффективно проводя через него ток.
Ниобий расположен в виде колец, через которые ток может протекать по часовой стрелке, против неё или смешанно, в обоих направлениях — соответствуя, по словам Роуза, «0», «1» или в суперпозиции двух значений в квантовом бите информации (кубите), на которых базируются квантовые вычисления. «Чип представляет собой последовательность металлических дорожек на кремниевой подложке; подложка здесь та же самая, которая используется для любого полупроводникового процесса, но сверху расположены слои металла, разделённые изолятором. Перед нами полностью металлическое магнитное устройство, где вся информация хранится в виде направлений течения тока по металлическим петлям и переходам.»
Направление тока преобразуется в значение кубита, в зависимости от того, есть ли у кубита смещение в сторону одного направления (0 или 1), движутся ли соседние кубиты в том же или противоположном направлении, а также от энергетического барьера между разными состояниями кубита. Нынешний чип Leda оснащён 28 кольцами, что даёт 28 кубитов, но они не связаны каждый друг с другом, только с некоторым количеством «соседей». Куперовская пара в ниобии — это, точно говоря, бозоны, поэтому все они существуют в одном квантовом состоянии, пояснил Роуз, что даёт всему сверхпроводнику квантовые свойства даже без соединения каждого кубита. Снижение числа межсоединений упрощает производство.
В экспериментах была получена точность квантовых вычислений 99,98%. Сегодня это лучший результат в мире. Как видите, нашей стране тоже есть чем похвастать;)
Для каких же задач квантовые вычисления дают выигрыш по сравнению с классическими?
Во-первых, квантовая система эффективно «решает» сложную вычислительную задачу — моделирует саму себя. На квантовом компьютере можно моделировать любую квантовую систему за полиномиальное число шагов. Это позволит (при наличии квантового компьютера) предсказывать свойства молекул и кристаллов, проектировать микроскопические электронные устройства размером в несколько десятков ангстрем. Сейчас такие устройства находятся на пределе технологических возможностей, но в будущем они, вероятно, будут применяться в обычных компьютерах.
Второй пример — разложение на множители и аналогичные теоретико-числовые задачи, связанные с абелевыми группами. Про алгоритм Шора уже было сказано ранее — предполагаемая сложность задачи факторизации лежит в основе криптостойкости некоторых алгоритмов шифрования с открытым ключом, таких как RSA. И этот красивый результат может иметь скорее вредное, чем полезное применение: разлагая числа на множители, можно подбирать ключи к шифрам, подделывать электронные подписи и т.д. Впрочем, трудности на пути создания квантового компьютера столь велики, что в течение ближайших 10 лет пользователи шифров могут спать спокойно.
Третий пример — это поиск нужной записи в неупорядоченной базе данных (алгоритм Гровера) и аналогичные задачи (например распознавание изображений — то, что демонстрировала D-Wave на своих первых чипах). В перспективе квантовый компьютер может приблизить нас к решению задачи создания искусственного интеллекта.
Квантовые компьютеры – «святой грааль» современной физики. Идея квантового компьютера выглядит столь же заманчиво, сколь нереалистично. Наверное так же воспринимался проект обычного компьютера во времена Чарльза Бэббиджа, изобретение которого было реализовано лишь сто лет спустя. Проблема создания квантового компьютера по сложности эквиалентна проблеме межзвездных перелетов и проблеме термоядерного синтеза. КК на двух-трех кубитах существуют уже сейчас, но и они требуют для своего построения высоких технологий (очень чистых веществ, очень точной имплантации отдельных атомов, сверхточной системы измерений). Но, как было сказано ранее, главный вызов не технологический, а фундаментальный — масштабируемость.
Будем надеяться, что в наше время научно-технический прогресс идет быстрее, поэтому не придется ждать так долго. Возможно, достаточно одной свежей идеи плюс несколько лет на разработку новой технологии…
1) Менский М.Б. — Человек и квантовый мир. Москва, «Век2», 2007. ISBN: 5-85099-161-1
2) Google Tech Talks series on Quantum Computing by Hartmut Neven and Geordie Rose at Google | Santa Monica, CA
3) Статьи Википедии
4) Статьи Компьютерры
5) С.Я. Килин. Квантовая информация. УФН, т. 169, №5, с. 507-527, 1999 г
6) Квантовый ликбез. Лента.ру
7) Tom's Hardware guide. D-Wave Orion: первый квантовый компьютер. Дмитрий Чеканов, 6 августа 2008
8) 8) А.Х. Шень, М.Н. Вялый. Курс лекций «Классические и квантовые вычисления». Интернет-университет информационных технологий
9) Квантовый компьютер и квантовые вычисления. Под ред. Садовничего В. А.
10) Квантовые вычисления: за и против. Под ред. Садовничего В. А.
Немного физики
Чтобы быть последовательными, нельзя не упомянуть о теоретических достижениях квантовой физики, которые сделали возможными на практике создавать такие устройства.
Вообще что же такое квантовая механика? Известно, что квантовая механика – теория, которой подчиняются микроскопические системы, например атомы. Микромир — атомы, электроны, фотоны и другие частицы — живет по особым законам. Там не просто все очень маленькое, там все совсем другое, и многие явления микромира не имеют аналогов в привычном нам макромире, из-за чего кажутся фантастическими.
Характерная черта квантовой механики, которая запечатлелась в названии – в некоторых физических системах энергия квантуется, т.е может быть равно одному из некоторого дискретного множества чисел, а может даже и никакого иного значения (запрещенная зона). Если пытаться вообразить такую ситуацию в макромире, то можно представить, например, что предметы имеют температуру, которая выражается только целым числом градусов. То есть 10, 20, 31, 36 градусов — может быть, а вот 36,6 — просто невозможно. Нагревать и охлаждать предметы можно, но при этом температура будет скакать туда-сюда сразу на градус.
В частности, энергия электромагнитного поля излучается только в виде дискретных неделимых порций. Вот такая порция и называется квантом. Предположение о существовании квантов сделал в 1900-1901 годах Макс Планк, положив тем самым начало квантовой теории, квантовой механике и еще много чему с прилагательным квантовый — в том числе и компьютерам.
Другим удивительным свойством фотонов, электронов и иных частиц является то, что они могут проявлять свойства как частиц, так и волн. Свет представлявшйся в классической физике как электромагнитная волна, оказался в квантовой физике совокупностью фотонов, подобных частицам. Но и наоборот, частицы, такие как электроны, обнаруживают свойства, характерные для волны: они интерферируют друг с другом и дифрагируют на препятствиях (то есть огибают их). Это свойство частиц дало основание в первые годы называть описывающую их теорию волновой механикой, и лишь впоследствии утвердилось название «квантовая механика»
И наконец третье фундаментальное свойство: квантовый объект, в отличие от классического, изначально статистический. Описать местонахождение не наблюдаемой непосредственно частицы в некотором месте можно только с некоторой вероятностью
На наблюдения и измерения в микромире тоже есть существенное ограничение: принцип неопределенности Гейзенберга: нельзя точно измерить одновременно скорость и координаты частиц.
Пока мы объекты не измеряем, они ведут себя и того хуже. Если квантовая система может находиться в нескольких состояниях и неизвестно, в каком именно она находится, то говорят о суперпозиции состояний. Можно говорить, что неизвестно, в каком состоянии находится система, или что она находится в нескольких состояниях одновременно, это вопрос интерпретации. В любом случае при измерении система выбирает одно из состояний.
Известным наглядным примером является мысленный эксперимент, называемый «кот Шредингера»: в закрытый ящик помещены живой кот, емкость с ядовитым газом и радиоактивное ядро. Если ядро распадается, оно приводит в действие механизм, который открывает емкость с газом и тем самым убивает кота. Вероятность того, что ядро распадется за час, — 50 процентов. Через час кот в ящике жив с вероятностью 50 процентов. С точки зрения квантовой механики, пока ящик закрыт, кот находится в суперпозиции двух состояний (то ли жив, то ли мертв; и жив, и мертв; ни жив ни мертв — как угодно). В тот момент, когда наблюдатель открывает ящик, он видит, жив кот или мертв.
Наконец, еще одно важное для нас явление — квантовая запутанность (entanglement), она же спутанность, сцепление, иногда связанность. О запутанности говорят, когда состояние двух (или более) квантовых систем должно описываться во взаимосвязи друг с другом, даже если сами системы разнесены в пространстве. Соответственно, физические свойства каждой из систем связаны с физическими свойствами другой, при том что они могут находиться не рядом и ничем не соединяться.
Если две запутанные системы находятся в суперпозиции состояний, то, измерив состояние одной, можно узнать состояние другой. Например, можно запутать два атома, спин (определенная квантовая характеристика) одного из которых будет направлен вверх, а другого — вниз, причем мы не будем знать, у какого атома какой спин. Но измерив спин одного атома, мы тут же узнаем и спин другого, даже если они разнесены в пространстве.
Все эти и многие другие особенности микромира и позволяют построить квантовый компьютер.
Классический и квантовый бит информации
Квантовый компьютер, как и любое другое устройство для вычислений, должен оперировать с числами. Простейшее устройство, способное представлять числа — это устройство, которое может находиться в двух устойчивых состояниях. Так, проводники с током могут находится в двух устойчивых состояниях: когда нет тока — соответствует значению 0, и когда ток есть — соответствует значению 1. Никакого другого устойчивого состояния быть не должно. Использование таких устройств для проведения действий над числами возможно благодаря двоичной записи чисел — в такой ячейке хранится информация, соответствующая выбору между двумя вариантами (цифрами 0 и 1 или, эквиалентно, двумя состояниями системы). Говорят, что количество информации, хранящееся в двоичной ячейке, равно 1 биту. В двух двоичных ячейках хранится 2 бита информации. Это соответствует выбору между 2-разрядными двоичными числами 00, 01, 10 и 11. В регистре, состоящем из N двоичных ячеек, хранится N бит информации, что соответствует выбору одного N — разрядного двоичного числа из всех возможных (всего таких чисел 2^N).
Посмотрим теперь, чем отличается хранение информации в квантовом компьютере. Сама информация тоже может быть представлена в форме двоичных чисел, то есть цепочек нулей и единиц. Одна цифра двоичного числа хранится в двоичной ячейке. Эта ячейка называется кубитом и представляет собой квантовую систему, одно из состояний которой соответствует цифре 0, а второе — цифре 1. Обозначим эти состояния ψ1 и ψ2. До сих пор не видно никаких отличий от классического компьютера. Но именно в этом пункте появляется существенное отличие. Дело в том, что для квантовых систем имеет место так называемый принцип суперпозиции: если квантовая система может находиться в одном из двух состояний, скажем, в состоянии ψ1 и в состоянии ψ2, то она может также находиться в целом семействе состояний, которые строятся как линейные комбинации исходных. Это значит, что исходные состояния умножаются на некоторые (комплексные) числа и складываются. Если выбираются числа c1 и c2, то получается состояние c1ψ1+ c2ψ2.
В частности, если кубит приводится в состояние (∣0〉+∣1〉)/√2, то это значит, что в нем одновременно записаны и цифра 0, и цифра 1.
Квантовый параллелизм
Итак, в одной двоичной ячейке квантового компьютера, называемой кубитом, может храниться не только одна из двух цифр двоичного счисления, 0 или 1 (как было бы в случае классического компьютера), но одновременно обе эти цифры. НАпример, в двух кубитах могут храниться одновременно 4 двоичных числа 00, 01, 10 и 11. А если в некотором регистре квантового компьютера содержится N кубитов, то в таком регистре может храниться одновременно 2^N двоичных чисел длины N. И при действии квантового компьютера одновременно обрабатываются все эти числа. Это и есть квантовый параллелизм. Если бы в нашем распоряжении были только классические компьютеры, каждый из которых работает с двоичными числами длины N, то для одновременной обработки 2^N таких чисел было бы необходимо 2^N компьютеров. Если же мы сумели построить квантовый компьютер, содержащий N кубитов, то один (!!!) этот компьютер одновременно обрабатывает все 2^N чисел.
Квантовые алгоритмы
В отличие от классических, квантовые компьютеры не универсальны: не для всяких вычислительных задач существует алгоритм их решения на квантовом компьютере. До сих пор найдено лишь небольшое число квантовых алгоритмов.
Наиболее известные квантовые алгоритмы:
1) Алгоритм Шора (факторизация)
2) Алгоритм Гровера (быстрый поиск в неупорядоченной базе данных)
3) Алгоритм Дойча — Джоза (ответ на вопрос, постоянная или сбалансированная функция)
Квантовые алгоритмы благодаря использованию явления квантовой запутанности и принципа суперпозиции обладают значительным приростом скорости выполнения по сравнению с соответствующими классическими алгоритмами.
Алгоритм Шора — убийца public-key криптографии
Чуть подробней остоновимся на алгоритме Шора, который позволяет решить любую из двух математически эквивалентных задач:
1) найти период сложной периодической функции или
2) разложить на простые множители очень большое число
Вторая из этих задач имеет важное прикладное значение, потому что она используется в криптографии. Дело в том, что в одной из криптографических методик для шифровки и дешифровки секретных посланий (шифрование с открытым ключом) используют большие числа, для которых известны их разложения на множители. Ясно, что такие числа получить легко: достаточно перемножить большое число простых чисел, и мы получим очень большое число, для которого разложение на простые множители известно. Получатель закодированного секретного послания может его декодировать потому, что в процедуре декодирования используется разложение на множители длинного числа, а он знает это разложение.
Если бы противник смог разложить это число на простые множители, он также смог бы декодировать послание. Однако для такого разложения требуется огромное время. Поэтому с практической точки зрения декодировать такое послание невозможно. Но если бы в распоряжении противника был квантовый компьютер (достаточной мощности, то есть работающий с достаточно большими числами), то он мог бы разлагать длинные числа на простые множители и значит легко мог бы расшифровывать такого рода послания. Этот распространенный в криптографии метод перестал бы работать. Это один из аргументов, которые делают важным создание квантового компьютера.
Проблемы построения квантового компьютера
Физические:
- декогеренция (главная на сегодняшний день проблема, о ней будет сказано далее)
- поиск конкретных процессов, выполняющих логические операции
Математические:
- поиск новых алгоритмов
- поиск методов коррекции ошибок
Эти проблемы можно описать одним словом — масштабируемость. Присоединить дополнительную память к обычному компьютеру — простая рутинная процедура. Присоединение каждого нового кубита к КК — пока что штучная работа.
Декогеренция
Явление декогеренции заключается в том, что измеряемая система теряет свои специфические квантовые свойства. Иными словами, чистое состояние быстро превращается в смесь при взаимодействии квантовой системы с окружающей средойю.
Для борьбы с декогеренцией разрабатываются, с одной стороны, различные методы изоляции квантовой системы, включая использование крайне низких температур и высокого вакуума, а с другой — введение в квантовые вычисления кодов, устойчивых к ошибкам, связанным с декогеренцией (обычно в таких схемах состояние логического кубита кодируется состоянием нескольких связанных физических кубитов).
Требования для построения КК
Точность унитарных операторов по разным оценкам должна быть от 99,99 до 99,999999 (зависит от конкретной реализации).
Современные варианты реализации квантового регистра
- ионные ловушки
- сверхпроводники
- квантовые точки
- ЯМР
- фотоны
- множество других экзотических идей (анионы и проч.)
Ионные ловушки — первая и наиболее хорошо разработанная идея. Об одном из сверхпроводниковых компьютеров пойдет речь далее. Ну а квантовые точки считаются наиболее перспективным вариантом.
Сверхпроводниковые квантовые компьютеры D-Wave
В феврале 2007 года канадская компания D-Wave Systems собрала 16-кубитовый квантовый компьютер, который основатель и генеральный технический директор Джорджи Роуз (Geordie Rose) назвал самым мощным квантовым компьютером, когда либо построенным, и первым, который может запускать коммерчески-значимые приложения. В ноябре 2007 года на конференции, посвященной суперкомпьютерам, та же компания D-Wave продемонстрировала работу образца уже 28-кубитного компьютера (чип Leda) онлайн. Сейчас компания тестирует прототип 128-кубитного чипа, который получил кодовое название Rainier. В дальнейших планах компании — создать уже в ближайшем будущем 1024-кубитный компьютер.
Всё это, согласитесь, намного превосходит большинство других разработок квантовых компьютеров, причём D-Wave смогла создать компьютер, используя технологии производства полупроводников и существующие полупроводниковые заводы, не прибегая к помощи оптических схем, квантовых точек, сдерживания лазера или других экзотических технологий производства. D-Wave работает и над второй половиной проблемы, а именно над инструментами программирования для создания приложений, способных получить преимущество от возможностей, которые обещают дать квантовые вычисления.
Материал в квантовом чипе D-Wave — это ниобий; охладите его до достаточно низкой температуры, и он станет сверхпроводником. Когда обычный металл проводит электрический ток, электроны, носители электрического заряда, сталкиваются с неидеальной структурой металла, в результате чего появляется сопротивление. Когда вы охлаждаете сверхпроводящий металл подобно ниобию, электроны металла формируют куперовские пары. Когда куперовские пары входят в переходы Джозефсона на чипе (состоящие из двух сегментов сверхпроводящего ниобия, связанных слабым изолирующим барьером), их можно представить как электроноподобные квазичастицы, которые могут туннельно проходить через изолятор в переходе, эффективно проводя через него ток.
Ниобий расположен в виде колец, через которые ток может протекать по часовой стрелке, против неё или смешанно, в обоих направлениях — соответствуя, по словам Роуза, «0», «1» или в суперпозиции двух значений в квантовом бите информации (кубите), на которых базируются квантовые вычисления. «Чип представляет собой последовательность металлических дорожек на кремниевой подложке; подложка здесь та же самая, которая используется для любого полупроводникового процесса, но сверху расположены слои металла, разделённые изолятором. Перед нами полностью металлическое магнитное устройство, где вся информация хранится в виде направлений течения тока по металлическим петлям и переходам.»
Направление тока преобразуется в значение кубита, в зависимости от того, есть ли у кубита смещение в сторону одного направления (0 или 1), движутся ли соседние кубиты в том же или противоположном направлении, а также от энергетического барьера между разными состояниями кубита. Нынешний чип Leda оснащён 28 кольцами, что даёт 28 кубитов, но они не связаны каждый друг с другом, только с некоторым количеством «соседей». Куперовская пара в ниобии — это, точно говоря, бозоны, поэтому все они существуют в одном квантовом состоянии, пояснил Роуз, что даёт всему сверхпроводнику квантовые свойства даже без соединения каждого кубита. Снижение числа межсоединений упрощает производство.
Российские технологии: лаборатория квантовых компьютеров ФТИАНа (Физико-технический институт РАН)
- кубиты на основе цепочек ядерных спинов. Используя современную технологию создания структур в полупроводнике размером в несколько нанометров, мы можем имплантировать в узкий канал в кремнии линейную цепочку ионов фосфора. Одна такая цепочка содержит от десяти тысяч до миллиона атомов (ядерный спин очень мал, и чтобы управлять им и надежно его детектировать, надо набрать достаточно большое число частиц). Это один логический кубит.
- высокотемпературными сверхпроводниками (ВТСП). р-контакта. В этом случае кубит создается на границе ВТСП двух разных типов (SDS-переход). Потенциальная энергия такого перехода имеет два минимума, при значениях фазовой переменной 0 и р. Они соответствуют двум базовым состояниям кубита.
- кубиты на ионных ловушках
- квантовые точки с оптическим управлением
В экспериментах была получена точность квантовых вычислений 99,98%. Сегодня это лучший результат в мире. Как видите, нашей стране тоже есть чем похвастать;)
Зачем нужен квантовый компьютер?
Для каких же задач квантовые вычисления дают выигрыш по сравнению с классическими?
Во-первых, квантовая система эффективно «решает» сложную вычислительную задачу — моделирует саму себя. На квантовом компьютере можно моделировать любую квантовую систему за полиномиальное число шагов. Это позволит (при наличии квантового компьютера) предсказывать свойства молекул и кристаллов, проектировать микроскопические электронные устройства размером в несколько десятков ангстрем. Сейчас такие устройства находятся на пределе технологических возможностей, но в будущем они, вероятно, будут применяться в обычных компьютерах.
Второй пример — разложение на множители и аналогичные теоретико-числовые задачи, связанные с абелевыми группами. Про алгоритм Шора уже было сказано ранее — предполагаемая сложность задачи факторизации лежит в основе криптостойкости некоторых алгоритмов шифрования с открытым ключом, таких как RSA. И этот красивый результат может иметь скорее вредное, чем полезное применение: разлагая числа на множители, можно подбирать ключи к шифрам, подделывать электронные подписи и т.д. Впрочем, трудности на пути создания квантового компьютера столь велики, что в течение ближайших 10 лет пользователи шифров могут спать спокойно.
Третий пример — это поиск нужной записи в неупорядоченной базе данных (алгоритм Гровера) и аналогичные задачи (например распознавание изображений — то, что демонстрировала D-Wave на своих первых чипах). В перспективе квантовый компьютер может приблизить нас к решению задачи создания искусственного интеллекта.
Квантовые компьютеры – «святой грааль» современной физики. Идея квантового компьютера выглядит столь же заманчиво, сколь нереалистично. Наверное так же воспринимался проект обычного компьютера во времена Чарльза Бэббиджа, изобретение которого было реализовано лишь сто лет спустя. Проблема создания квантового компьютера по сложности эквиалентна проблеме межзвездных перелетов и проблеме термоядерного синтеза. КК на двух-трех кубитах существуют уже сейчас, но и они требуют для своего построения высоких технологий (очень чистых веществ, очень точной имплантации отдельных атомов, сверхточной системы измерений). Но, как было сказано ранее, главный вызов не технологический, а фундаментальный — масштабируемость.
Будем надеяться, что в наше время научно-технический прогресс идет быстрее, поэтому не придется ждать так долго. Возможно, достаточно одной свежей идеи плюс несколько лет на разработку новой технологии…
Литература
1) Менский М.Б. — Человек и квантовый мир. Москва, «Век2», 2007. ISBN: 5-85099-161-1
2) Google Tech Talks series on Quantum Computing by Hartmut Neven and Geordie Rose at Google | Santa Monica, CA
- Introduction to Quantum Computing
- Image Recognition with an Adiabatic Quantum Computer
- Does an Explanation of Higher Brain Function require references to quantum mechanics?
3) Статьи Википедии
4) Статьи Компьютерры
- Кванты ради квантов. «Компьютерра» №23 от 21 июня 2006 года
- D-Wave: кубитное шоу с моралью. «Компьютерра» №9 от 09 марта 2007 года
- Пространство свободы (интервью Юрия Манина) «Компьютерра» №2 от 22 января 2001 года
5) С.Я. Килин. Квантовая информация. УФН, т. 169, №5, с. 507-527, 1999 г
6) Квантовый ликбез. Лента.ру
7) Tom's Hardware guide. D-Wave Orion: первый квантовый компьютер. Дмитрий Чеканов, 6 августа 2008
8) 8) А.Х. Шень, М.Н. Вялый. Курс лекций «Классические и квантовые вычисления». Интернет-университет информационных технологий
9) Квантовый компьютер и квантовые вычисления. Под ред. Садовничего В. А.
10) Квантовые вычисления: за и против. Под ред. Садовничего В. А.
