Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 30
×

Квантовая информатика с человеческим лицом

1. Внимательно вглядись, или Квантовые вычисления для ленивого программиста

Когда я слышу про кота Шрёдингера, мне хочется достать ружье.
Стивен Хокинг

В университете все «юные химики», а не только программисты, могут узнать (но не обязательно понять), что квантовый способ описания окружающего мира является чуть ли не единственно возможным средством сохранить прогностическую ценность теоретической химии. Еще Дойч и Фейнман указали, что моделирование квантовохимических процессов, лежащих в основе мироздания, на классических компьютерах, даже полных по Тьюрингу, с вычислительной точки зрения — почти безнадежное занятие (см., например, [Fe1982, Deu1985]. Объем пространства состояний системы с ростом числа вовлеченных в расчет атомов растет так, что потребление памяти становится экспоненциальным. Вычислительная химия, в частности, и развивалась так, чтобы как-то преодолевать возникающие в связи с этим трудности.

В 1982 г. Бенёв показал [Ben1982], что вычислительная мощность компьютеров, использующих манипулирование квантовомеханическими объектами — атомами и молекулами, — может превосходить возможности классических компьютеров, и ввел аналогичное классическому понятие квантовой машины Тьюринга.

В 1992 г. появился первый алгоритм, существенным образом использующий явление квантового параллелизма (об этом подробнее здесь), то есть тот факт, что вычислительные элементы квантового компьютера (кубиты, от qu(antum) bits) могут находиться, по существу, одновременно в нескольких состояниях, а не в одном четко определенном, как элементы компьютера классического. Иначе говоря, применяя некоторую программу эволюции (нас сейчас не интересует точная ее природа) к начальному состоянию регистров такой машины, мы получаем одновременно все возможные результаты ее выполнения. То есть мы можем вместо того, чтобы вовлекать в процесс N классических регистров, каждый из которых находится в определенном начальном состоянии |x>, применить квантовую суперпозицию классических состояний |x>. О системе, принятой для записи состояний отдельных кубитов |x> , можно подробнее почитать здесь.

В 1994 г. Шор заметил, что в рамках классической теории чисел задачу о взломе алгоритма RSA можно свести к вычислению периода некоторой функции. Этот процесс удается экспоненциально ускорить, переписав классический алгоритм с учетом ограничений, налагаемых квантовомеханической природой «железа», и применив квантовый аналог преобразования Фурье. В результате, мы будем наблюдать Фурье-интерференцию образов периодической функции, все значения которых вычисляются одновременно и независимо друг от друга. Надо особо отметить, что Шор не пользовался приемами избыточности и не прибегал к кодам с коррекцией ошибок, поскольку в квантовой информатике оператор простого копирования запрещен (почему это так, отдельный вопрос, можно пока сказать, что в квантовой механике допустимы только линейные преобразования, а клонирование состояния кубита нелинейно по своей природе). В итоге ему удалось разработать метод взлома системы RSA для квантового компьютера, требующий полиномиального времени работы. Таким образом, было получено прямое доказательство того, что внедрение квантовых алгоритмов может иметь революционные последствия для современной криптографии. Это достижение привлекло значительный интерес к квантовой информатике, и работы по созданию действительно дееспособных квантовомеханических вычислительных устройств резко интенсифицировались. Вся эта область сейчас уже совершенно необъятна, и я не буду ее детально касаться в первом очерке. Нужно подчеркнуть, что создание такой машины — задача технически чрезвычайно сложная. Вот один из наиболее продуманных вариантов: такой квантовый компьютер уже знает, что 3×5 = 15, но это только начало!

Но, во-первых, технология не стоит на месте, и следует ожидать такого же прорыва, как в свое время при переходе от электронных ламп к полупроводникам, а во-вторых, ничто не препятствует создать симуляторы квантовых компьютеров «внутри» классических устройств.

В частности, Эмер разработал императивный язык квантового программирования QCL (лично я предпочитаю использовать реализацию для AMD64), а Альтенкирх и Виццотто применили для моделирования квантовых эффектов на классических компьютерах библиотеки Haskell. Ван Тондер, вдохновленный LINQ, разработал квантовый аналог ламбда-выражений и позаботился об их реализации средствами Scheme; квантовый симулятор недавно интегрировали также в Common Lisp. Наконец, Сэлингер предложил функциональный язык квантового программирования QPL, в котором допускается сочетать классические и квантовые инструкции, а также раздельно обрабатывать классические коды управления и квантовые данные.

Теперь, когда некоторое общее представление о квантовой информатике, надеюсь, получил даже тот читатель, который ленился кликать по ссылкам, я хочу проиллюстрировать некоторые неочевидные свойства квантовых алгоритмов, рассказав об интересном и малоизвестном эффекте, как нельзя лучше соответствующей старой заповеди советского инженера: «Работает? Не трогай!»

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

Я буду в дальнейшем следовать терминологии, принятой у Джозсы, первооткрывателя этого эффекта.

* * *

Представим себе квантовый компьютер, снабженный переключателем по принципу «мертвой руки», изначально установленным в положении «ВЫКЛ». Пусть изначальное состояние квантовых регистров — |QC>, а регистр, предназначенный для вывода результатов, может содержать два значения — 0 и 1, или, с квантовомеханической точки зрения, пребывать в состояниях |0> и |1>. Заставим квантовый компьютер выполнить алгоритм решения некоторой задачи, предусматривающий выбор из многих альтернатив, среди которых правильна только единственная. И пусть регистр результатов, изначально пребывающий в состоянии |0>, примет значение k = 0 или 1 в зависимости от неуспеха или успеха нашего эксперимента. Вычисления проводятся только в том случае, если переключатель переводится в положение «ВКЛ». По окончании эксперимента компьютер возвращают в первоначальное состояние.

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

(|ВЫКЛ> + |ВКЛ>)/sqrt(2) * |QC> * |0>.

Теперь просто подождем время, отведенное на прогон алгоритма. Система переходит в состояние

1/sqrt(2) * (|ВЫКЛ> * |QC> * |0> + |ВКЛ>*|QC> *|k>)

После этого переключатель оказывается, в зависимости от того, что с ним было до запуска алгоритма, в одном из двух новых состояний:

|ВЫКЛ> → 1/sqrt(2) * (|ВЫКЛ> + |ВКЛ>); |ВКЛ> → 1/sqrt(2) * (|ВЫКЛ> — |ВКЛ>)

Результирующее конечное состояние системы будет таким:

1/sqrt(2) * ((1/sqrt(2) * (|ВЫКЛ> + |ВКЛ>)) * |QC> * |0> + (1/sqrt(2) * (|ВЫКЛ> — |ВКЛ>)) *|QC> *|k>) =
= 1/sqrt(2) * ((1/sqrt(2) * (|0> + |k>)*|ВЫКЛ> + (1/sqrt(2) * (|0> — |k>)*|ВКЛ>)) * |QC>

Теперь мы измеряем состояние переключателя, а следом заглядываем в регистр результатов. Пусть мы видим, что переключатель ВКЛЮЧЕН. Тогда в регистре должно быть значение 1.

Но с вероятностью 50% проверка состояния регистра даст значение 0. И если это происходит, то мы должны заключить, что вычисления по алгоритму не осуществлялись, потому что в противном случае в регистре результатов содержалось бы значение 1.

Заметьте, что если k = 0, то мы никогда не увидим положение ВКЛ. Если же k = 1, то у нас 50%-е шансы наблюдать положение ВКЛ. Итак, если мы обнаружили, что k = 1, то с вероятностью 25% мы можем получить решение задачи (и при этом верное), не включая компьютер.

Откуда же в таком случае появляется результат? Мы что, получаем его просто так, не расходуя никаких вычислительных ресурсов? Существует любопытное объяснение этого эффекта: с точки зрения многомировой интерпретации квантовой механики, если даже измерение состояния регистра результатов показало, что вычисление не имело места, то в некоторой параллельной вселенной, где переключатель все-таки оказался в положении ВКЛ, компьютер продолжал работать. Именно там этот ответ и был вычислен.

Элицур и Вайдман отметили, что компьютер потенциально может быть сконструирован таким образом, чтобы после получения верного ответа он самоуничтожался (например, это касается сверхтьюринговых машин). Если вышеописанный эксперимент проводится именно с таким «компьютером для шахидов», то с вероятностью 25% мы обнаружим, что k = 1, и, тем не менее, компьютер продолжает работать. По очевидным причинам описанную модификацию эксперимента называют «задачей сапера». Немало у нее общего и с квантовым бессмертием. О том, как все это может выглядеть на практике, можно почитать в отличном романе Нила Стивенсона.

Говорят, что все беды от лени, но мы только что убедились, что лень может быть и очень полезна для постижения природы окружающей Вселенной!

Продолжение: Квантовая информатика для котов и людей: антропный принцип, эффект Зенона и фермент в роли машины Тьюринга

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn

Схожі статті




23 коментарі

Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.

@ hellip 3.07.2010 в 21: 45 Задачей «квантовых компьютеров» будет перебор всего разнообразия вариантов задачи и выделения из этого всего перИодных «снимков», своего рода дорожных знаков куда ведет тот или иной параметр «уравнения» при повторных расчетов когда новая задача считается по такой же схеме.Будет время когда весь Мир будет посчитан! И перед человечеством станут задачи инициирования условий для жизнеспособных систем на подобии нашей Солнечной системы.:)

@ Серж

Аналогия квантового компьютера — наше сознание, по принципу работы

Да-да, именно так. http://en.wikipedia.org/wiki/C...На этой идее основано всемерно рекомендуемое мной тут произведение Нила Стивенсона Anathem.

что такое квантовый компьютер — это когда для задачи делается своего рода перфокарта правил, на подобии как ДНК, а из нее уже развертывается разнообразие, и решение задачи сводится к ожиданию того момента хода развертывания правил, при котором достигается требуемое состояние

Бесспорно, КК — существенно аналоговое устройство. Возможность успешного решения задачи определяется пригодностью системы к тому, чтобы быть ее моделью.

Аналогия квантового компьютера — наше сознание, по принципу работы.:)

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

Спасибо, очень познавательно.

Есть такая компания, но мне она кажется мутной: -) Пока они в общем недалеко от стартапа ушли. По такому описанию трудно что-то сказать о принципе работы их криптографического девайса. Может быть, в данном случае используют в качестве кубитов фотоны, эмиттированные гетеропереходом на каком-то полупроводнике типа А (III) B (V). Они при определенных условиях возникают сразу в виде перепутанных пар. Но это пока крайне кропотливый процесс, требующий предварительного охлаждения зоны эмиссии до весьма низких температур.PS. До меня наконец (когда стали минусовать топик) дошла суть трабла с постом на Хабрахабре, но я так понимаю, что исправить недочет уже поздно.: (

Вот какая-то квантовая криптография: http://www.magiqtech.com/MagiQ...

The QPN 8505 is a next-generation quantum cryptography system that relies on the laws of physics rather than computational difficulty for safeguarding keys. It is easily integrated into existing network infrastructures and incorporates real-time key generation based on quantum key distribution protocols. MagiQ’s QPN delivers always-on industry standard IPSec based VPN protection while providing an additional layer of security via quantum cryptography. The system offers cost-effective protection from both internal threats, such as disgruntled employees, and from external threats. MagiQ’s QPN 8505 is targeted at government applications including military, intelligence gathering and homeland defense. Commercial applications include financial services, Telco carriers and disaster recovery.

http://www.magiqtech.com/MagiQ...

@ ~arumad

про задачу сапера можна зіслатися на російсько-мовний ресурс “Реально ли многомирие? ” на “Наука и Жизнь”...

Если есть возможность, я предпочитаю англоязычные источники, а русскоязычный академический научпоп вообще недолюбливаю.

що таке “принцип ‘мёртвой руки’”?

Это значит, что если уж переключатель переводится в положение ВКЛ, то дальнейший вычислительный процесс на ключевом шаге контролируется самОй квантовомеханической природой регистров ( “ожидание” ), а если он остается в положении ВЫКЛ, то никакого вычисления не должно происходить.

чи пов’язаний він з тим, що “После этого переключатель оказывается, в зависимости от того, что с ним было до запуска алгоритма, в одном из двух новых состояний”?

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

чому цей новий стан — це вихід рандомізатора?

А потому что все квантовые состояния, пребывающие в суперпозиции, до наблюдения равновероятны.

яким чином досягається задання регістрів доки перемикач у невизначеному стані?

Во-первых, вы могли заметить из выкладок, что в данном случае точная природа программы для наблюдения эффекта несущественна. Во-вторых, нельзя дать однозначного ответа на этот вопрос в отрыве от конкретной задачи: квантовый компьютер с аппаратной точки зрения ближе к аналоговым машинам, чем к цифровым. В-третьих, регистры данных могут управляться классическим контроллером, а переключатель — ГСЧ, чтобы сделать вычислительный процесс предельно рандомизированным и максимально использовать квантовый параллелизм.

і головне, чому стан регістрів не змінився, якщо обчислення на них були виконані?

Он не изменится только с определенной вероятностью = 50%. А с вероятностью 50% он изменится.

про задачу сапера можна зіслатися на російсько-мовний ресурс “Реально ли многомирие? ” на “Наука и Жизнь”, або з класичної точки зору “Квантовое видение в темноте”.перепрошую, але кілька незрозумілих моментів.- що таке “принцип ‘мёртвой руки’”? — чи пов’язаний він з тим, що “После этого переключатель оказывается, в зависимости от того, что с ним было до запуска алгоритма, в одном из двух новых состояний”? — чому цей новий стан — це вихід рандомізатора? — яким чином досягається задання регістрів доки перемикач у невизначеному стані? — і головне, чому стан регістрів не змінився, якщо обчислення на них були виконані?

andrew1, спасибо, много дельных аналогий Про оптический компьютер у меня в одном комменте сказано, и вы правильно тут написали

Швидкодія передачі по оптоволокну приблизно така ж, як і по міді — порядку гігабіт/сек.Але по оптоволокну можна передавати одночасно багато променів з різними довжинами хвилі

Тут работает в общем-то тот же самый эффект интерференции. Помню книжку Макса 1982 г., там целая глава посвящена оптическим коррелометрам и прочим преобразователям сигналов. Кто же знал, что финансирование после 1985 так урежут... Там описаны действительно уникальные (по принципу действия, а не по показателям) разработки. @ All однако, приятно, что здесь уровень дискуссии повыше будет, чем на хабре...

Сама крута стаття, яку я тут читав:) І багато цікавих лінків.Хочу додати пару слів про одночасне обчислення багатьох результатів на одному обчислювальному елементі.Такі речі досліджувалися задовго до квантових комп’ютерів і були досягнуті дуже великі (як на ті часи) результати.Основною ідеєю було використання оптичних обчислювальних елементів. Потенціал звичайного електричного провідника завжди має одне конкретне значення.Іншими словами, один провідник може проводити «один електричний струм», котрий відповідно несе одну одиницю інформації (умовно).Але оптичний елемент може проводити багато променів світла в різних напрямках або на різних довжинах хвилі. Тому оптичний обчислювальний елемент може здійснювати багато (наприклад тисячі чи мільйони) операцій одночасно.Найбільш потужні такі обчислювальні елементи (матричні перемножувачі) могли б виконувати мільйони матричних множень одночасно, а враховуючи, що кожне множення може мати еквівалентну трудомісткість 1е6−1е9, результуюча швидкодія могла б досягати 1е15 арифметичних операцій в секунду.Після закінчення холодної війни дослідження перестали фінансуватися, так що в практику впровадили тільки обчислювачі перетворення Фур’є на двозаломлюючих кристалах.Швидкодія була порівняна із мікропроцесором, але оскільки обчислювалися одночасно тисячі гармонік, то результуюча продуктивність виходила набагато вища. Ну і переваги по надійності та енергоефективності у зв’язку з простотою конструкції (порівняно з процесором).Ці пристрої отримали широке застосування в радіостанціях, мобільних телефонах і т.п.Ще один приклад цього принципу (правда без обчислень, а тільки для передачі інформації) — оптоволокно.Швидкодія передачі по оптоволокну приблизно така ж, як і по міді — порядку гігабіт/сек.Але по оптоволокну можна передавати одночасно багато променів з різними довжинами хвилі.І в лабораторних умовах досягнута результуюча швидкодія порядку терабіт/сек.Якщо оптичні комп’ютери загального призначення все ж таки будуть побудовані, то NVIDIA CUDA може стати анахронізмом:)

Начиная со второй части, обсуждение статьи будет проводиться также на Хабрахабре, куда мне любезно предоставили инвайт. Приношу благодарность камраду Habroche.

@ Сергей Ярошенко спасибо за участие, ваш коммент особенно ценен, поскольку вы пребываете географически ближе к эпицентру событий в этой отрасли. @ Дима первую версию коммента я потер, моя нежная душа не выдержала издевательства над Гейзенбергом: -)) @ clewer_one в тексте есть ссылка на википедию по бра-кет нотации, читайте внимательнее

Ну вобщем было интересно составить какое-то впечатление об сабже. Спасибо.

Это стандартный мат аппарат квантовой информатики, который базируется на квантовой физике и обозначениях квантовых состояний введенных Дираком.

Вопрос о нотации выкладок. Это вообще что такое, из какой области человеческих знаний и как это парсить?

Отличная статья, спасибо автору.Тема весьма перспективная, например в MIT курируется DARPA’ой и NSA.Кстати, для тех кому нужны основы, есть чудесный набор обучалок по quantum information: http://www.quantiki.org/wiki/M...

Странно, комент пропал = (. Да — Гейзенберга, точно =). Странно что в школе не было это очень старые теории ибо мой отец лет так 30 назад, а универе теорию струн изучал, с тех пор теор. физ. практически не сдвинулась с места.

@Дима, Гейзенберга, принцип неопределенности Гейзенберга. у Вас была хорошая школа, в моей среднестатистической таких высоких материй не преподавали:) @hellip, понятно. спасибо.

Применяется ограниченно в квантовой оптике и в астрономии — ограниченно потому, что сами квантовые компьютеры пока пачкают пеленки Есть такая штука — называется «замороженный свет»: это когда пучок света пропускают через разреженный газ, подвергнутый лазерному охлаждению до сверхнизких температур. В этом случае он существенно замедляется, примерно до 0.6 световой скорости в вакууме. Получается настраиваемый световод для core CPU оптического компьютера — или миниатюрный аналог очень разреженного скопления межзвездной материи, по выбору. На описанном у меня алгоритме построен наилучший (пока) способ считать информацию с такого облака, остальные методы будут его разрушать. Еще японцы думают этот фокус внедрить в рентгеновские аппараты, чтобы снизить дозу, необходимую для просвечивания пациента. В перспективе, вероятно, в голографических дисплеях будет использоваться.

очень занимательно. у меня пока только один вопрос по существу — это из области чистого знания или имеет какое-то практическое, прикладное применение? и если применяется, то где?

Взрыв мозга! Спасибо автору — жду продолжения!

Підписатись на коментарі