Файл: деп_тукс_10_11.doc

Стоит, однако, отметить, что существует класс задач, для которых квантовые алгоритмы не дают значительного ускорения по сравнению с классическими. Одним из первых это показал российский математик Ю. Ожигов, построивший ряд примеров алгоритмов, принципиально не ускоряемых на квантовом компьютере ни на один такт.

И, тем не менее, нет сомнения, что компьютеры, работающие по законам квантовой механики, - новый и решающий этап в эволюции вычислительных систем.

7.3. Задачи поиска.

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

В задаче неупорядоченного поиска ничего не известно о структуре пространства решений и об утверждении Р. Например, определение Р(х₀) не дает никакой информации о возможном значении P(x_j) для х₀ х_j. В задаче упорядоченного поиска можно использовать информацию о пространстве поиска и об утверждении Р.

Например, поиск по алфавитному списку является задачей упорядоченного поиска, и алфавитный порядок используется для построения алгоритма. В других случаях, скажем, в задачах, где нужно найти хотя бы одно решение структуру задачи можно использовать для построения эвристических алгоритмов, которые быстро дают решения для некоторых отдельных случаев. Но в общем случае, когда мы имеем задачу неупорядоченного поиска, лучшее, что можно сделать классическим путём — это последовательно проверять истинность каждого утверждения P(x_j). Для поискового пространства из N элементов обычная задача неупорядоченного поиска требует Q(N) проверок Р. На квантовом же компьютере, как показал Гровер, задачу неупорядоченного поиска можно решить с большой вероятностью производя около Q(W) проверок Р. Таким образом, квантовый алгоритм Гровера является заведомо более эффективным, чем любой алгоритм для неупорядоченного поиска, выполняемый на классическом компьютере.

Оказывается, для неупорядоченного поиска алгоритм Гровера является оптимальным. Однако, для большинства поисковых задач требуется упорядоченный поиск. Поскольку существуют классические эвристические алгоритмы, использующие упорядоченность, то можно ожидать, что существуют также и эффективные квантовые алгоритмы для упорядоченного поиска. Серф и др. (1998 г.) используют алгоритм Гровера вместо классического поиска внутри эвристического алгоритма, чтобы показать, что возможно квадратичное ускорение, когда речь идёт о решении сложных задач.

Брассард и др. (1998), опираясь на алгоритм Гровера, показали, что общий классический эвристический поиск имеет квантовый аналог с квадратичным ускорением.

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

Т. Хогг также разработал несколько эвристических квантовых алгоритмов упорядоченного поиска. Его подход является совершенно неклассическим, в нём используются весьма нетривиальные свойства квантовых вычислений. Единственный минус его подхода заключается в том, что, как и во многих эвристических алгоритмах, использование упорядоченности является усложнённым, и при этом очень трудно определить вероятность получения верного ответа при одной итерации алгоритма. Следовательно, пока ещё не понятно, насколько эффективны алгоритмы Хогга. В классической теории эффективность эвристических алгоритмов оценивается с помощью эмпирического тестирования. Но, по­скольку, при моделировании квантовых операций на классическом компьютере наблюдается экспоненциальное замедление, то эмпирическое тестирование квантовых алгоритмов сегодня невозможно, разве что за небольшими исключением. Алгоритм Хогга в применении к некоторым задачам упорядоченного поиска, является более эффективным, чем алгоритм Гровера, но ускорение при этом является полиномиальным. С теоретической точки зрения — это менее интересно, но с практической — даже малое полиномиальное ускорение этих вычислительных задач имеет огромное значение. До тех пор, пока не будет создано больших квантовых компьютеров или лучших приёмов для анализа таких алгоритмов, эффективность нельзя будет определить точно.

7.4. Квантовые алгоритмы

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

Прежде чем ответить на этот вопрос, рассмотрим сами предпосылки обращения к квантовой механике как к теории, способной дать новые вычислительные алгоритмы. О каком же компьютере идет речь, когда говорят о моделировании законов физики? В науке о вычислениях обычно не рассматривается вопрос о конкретном вычислительном устройстве - речь идет об универсальном компьютере. Поэтому вопрос перефразируется так - могут ли законы физики быть смоделированы при помощи универсального компьютера? Будем считать, что элементы такого компьютера локально соединены между собой, но пусть это не будет бесконечно большое число соединений. Какого рода физические законы мы хотим моделировать на этом компьютере? Прежде всего - законы в классическом приближении, когда работают локальные дифференциальные уравнения. Но реальный мир - это квантовый мир, поэтому хотелось бы симулировать квантовую физику. Что же за симуляции мы будем рассматривать? Это, конечно, аппроксимационное моделирование, в котором строятся численные алгоритмы решения дифференциальных уравнений. Затем компьютер производит вычисления на основе этих алгоритмов, и мы получаем примерное представление о том, как работает физика. Это законный подход, но речь пойдет о другом. Хочется говорить о том, насколько возможно точное моделирование, т.е. так как это происходит на самом деле в природе. Если существование такой возможности было бы доказано и такой тип компьютера стал бы реальностью, то оказалось бы, что все, что происходит в ограниченном объеме пространства и времени точно бы анализировалось за ограниченное число логических операций. Очевидно, что существующие физические теории не позволяют сделать это. В противном случае мы бы работали с бесконечно малыми элементами пространства, бесконечно большими длинами волн, суммировались бесконечные ряды и т.д., т.е. если бы такое предположение было бы верным, то законы физики не работали.

Но теперь мы имеем представление о том, как модифицировать законы физики. Например, мы должны изменить наше представление о том, что пространство непрерывно и представлять его как решетку, т.е. ввести дискретизацию. Дискретизация означает, что элемент пространства можно описать конечным числом, а время описывается прерывистыми скачками. Каким бы был в этом случае физический мир и как бы представлялась задача о его моделировании? Во-первых, возникла бы проблема того, что скорость света слегка зависела бы от направления; кроме того появились бы другие элементы анизотропии, которые можно было бы зарегистрировать экспериментально. Эта анизотропия могла бы быть очень малой. Конечно, физическое знание всегда неполно и всегда можно сказать, что можно построить модель, выводы которой лежат вне области, доступной на сегодняшний день. Можно предположить, что такая анизотропия будет обнаружена в будущем. С точки зрения физики было бы очень красиво, если можно предсказать новый результат, совместимый с существующими теориями и известными фактами и не находящий пока объяснения, но похоже, таких примеров в настоящее время нет (ситуация в физике в конце XIX - начале ХХ века была не такой - имелись экспериментальные результаты, несовместимые с физическими теориями). Поэтому возражений против анизотропии, в принципе, нет. Вопрос только в величине такой анизотропии.

Другой важный момент заключается в том, что законы природы обратимы, а правила компьютерных вычислений - нет. Однако это утверждение может быть оспорено - компьютерные вычисления могут быть сделаны обратимыми и соответствующие методы очень пригодятся нам в дальнейшем. Это то самое место, на котором изменяются взаимоотношения между физикой и вычислениями: появляются новые возможности для вычислений. Более того, возможно, что эти новые вычислительные возможности позволят нам понять что-то о физике.

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

Привычная для нас классическая логика является лишь частным случаем квантовой и справедлива для незначительной части реальности, описываемой классической физикой. Моментом зарождения квантовой логики, как самостоятельного направления в квантовой теории, можно считать 1936 год, когда Бирхгов и фон Нейман опубликовали статью «Логика квантовой механики»

Хотя чуть раньше, в 1932 году, фон Нейман в своей знаменитой книге «Математические основы квантовой механики» уже обратил внимание на возможность существования особой квантовой логики, обобщающей логику классическую: «Наряду с физическими величинами R существует еще нечто, являющееся предметом физики: именно альтернативные свойства системы L». То есть предметом физики являются не только некоторые конкретные физические величины, полученные при измерении, но и вся совокупность «непроявленных» результатов — тех, которые могли иметь место, но в данном случае не были реализованы.

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

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