о квантовых алгоритмах

[avva]

I’d claim that Shor’s algorithm is one of the most significant discoveries about algorithms in modern history. There are a certain group of algorithms, like Euclid’s algorithm for computing a greatest common denomenator, which, in my mind are among the most beautiful, eternal algorithms which we know. (Algorithms from the code book, so to speak.) I would like to make the claim that Shor’s algorithm belongs in the same category as these algorithms.

from the blog "The Quantum Pontiff"

И это говорится об алгоритме, который ещё ни разу никто не смог применить для того, чтобы сделать что-то конкретное и полезное!

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

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

Comments

[kobak.livejournal.com]

Это, действительно, интересная тема.

При некоторых разумных предположениях о матрице плотности (след единица, положительная определённость и тд) можно показать, что максимально общее уравнение эволюции, которое сохраняет эти свойства, -- это так называемое уравнение Линдблада. Оно выглядит как обычное уравнение для эволюции ро-матрицы (производная равна коммутатору с гамильтонианом) плюс добавка специального вида. Так вот ровно это же самое уравнение получается в теории декогеренции.

Поэтому на уровне матрицы плотности возможные поправки к теории, похоже, действительно должны быть эквиваленты взаимодействию со средой. Для данной дискуссии этого, думаю, достаточно. Но вообще-то можно спуститься на уровень ниже и спрашивать, как нужно изменить уравнение Шрёдингера, чтобы из него получалась такая эволюция ро-матрицы. Оказывается, что можно добавить стохастические члены, эффективно редуцирующие (коллапсирующие) волновую функцию макроскопических тел. Это называется теория GRW (Гирарди, Римини, Вебер, ~1990), ну и то, что из неё вырастает.

[ded-maxim.livejournal.com]

Уравнение Линдблада выводится при разных "упрощающих" предположениях (типа марковости, приближении Борна и пр). Они соблюдаются далеко не всегда. Вот, например, неплохая статья, где эти предположения подробно анализируются применительно к квантовым кодам:
http://arxiv.org/abs/quant-ph/0506201.

А вот интересная работа, где предлагается альтернатива теории GRW:
http://arxiv.org/abs/quant-ph/0208087

[kobak.livejournal.com]

Вы имеете в виду вывод в теории декогеренции? Насчёт приближения Борна я что-то не уверен, а марковость там базовое предположение -- это конечно, да. Но я-то говорил о другом: о выводе этого уравнения как максимально общего для ро-матрицы. Тут приближение Борна точно не при чём (хотя кое-какие дополнительные предположения, увы, нужны -- вывод в общем виде неизвестен).

Ссылки посмотрю, спасибо. Особенно вторую -- судя по абстракту, я об этом совсем ничего не знаю, но, кажется, к GRW это не имеет большого отношения?

[ded-maxim.livejournal.com]

Передо мной лежит книга H.J. Carmichael, "Statistical Methods in Quantum Optics", первый том. Уравнение Линдблада там выводится в первой главе, с перечислением всех приближений и предположений, в том числе и приближения Борна (т.е., предположения о слабой связи между системой и окружающей средой, weak coupling). В теории декогеренции это предположение тоже делается, см. статью Алицкого и др

По поводу второй статьи: там тоже строится более общее стохастическое уравнение, которое при определенных условиях (эквивалентных стандартному набору аксиом квантовой механики) сводится к уравнению Шредингера. Насколько я помню, там есть ссылка на GRW.

[kobak.livejournal.com]

Насчёт Линдблада. Хорошо, передо мной книжки не лежит, так что охотно готов признать необходимость приближения Борна в выводах декогеренции.

Но я не понимаю, какое это может иметь отношение к тому, о чем я пытаюсь сказать: к выводу этого уравнения *просто из аксиом*, накладываемых на ро-матрицу. Для этого никакой среды вообще не нужно, поэтому мне не ясно, при чем тут приближение Борна. Нужна марковость (т.е. полугрупповая структура) + пара дополнительных предположений самого Линдблада (усиленная положительная определённость и ещё одна вещь). Разве не так?

[leblon.livejournal.com]

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

[ded-maxim.livejournal.com]

Именно так. Но среда возникает как раз благодаря предположениям Линдблада, в частности, благодаря свойству вполне положительности (complete positivity). Дело в том, что существует достаточно общая теорема (т.наз. теорема Стайнспринга), сформулированная в C*-алгебраических терминах, из которой следует, что любое вполне положительное линейное (плюс еще некоторые технические требования) преобразование матрицы плотности представимо в виде частичного следа унитарного преобразования на некоторой расширенной системе (т.е., к собственно системе добавляется "среда" -- берется тензорное произведение гильбертова пространства системы с дополнительным гильбертовым пространством, которое без потери общности можно взять той же размерности, что и для системы). Математически строгое изложение есть в книжке Дэвиса "Квантовая теория открытых систем" (E.B. Davies, "Quantum Theory of Open Systems") -- там как раз вводится аксиоматика квантовых марковских полугрупп и смежных вещей.

[kobak.livejournal.com]

Спасибо за объяснение, очень интересно. Но по сути дела мы здесь неформально говорили именно про результат Стайнспринга, о теореме которого Вы рассказали: вполне положительность => ур-е Линдблада (с одной стороны) и декогеренция, то есть частичный след и тд, => тоже ур-е Линдблада (с другой стороны). Поэтому ясно, что эти вещи тесно связаны.

Скажите, а Вы знаете что-нибудь о релятивисткой теории декогеренции и ур-я Линдбалада? Я, собственно, не знаю, существует ли такая вообще. Но изучаю сейчас попытки сделать из GRW/CSL теорию поля, а темы, как мы выяснили, связанные.

[ded-maxim.livejournal.com]

Я тоже не уверен, существует ли релятивистская теория декогеренции, во всяком случае, в том же объеме, что и в нерелятивистском случае. Правда, теория открытых систем в релятивистской КТП есть, это я знаю -- всякие там состояния Кубо-Мартина-Швингера и термодниамика, диссипация, релаксация к равновесному состоянию. В книге Р. Хаага "Локальная квантовая физика" это все подробно разбирается.