М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 16
Текст из файла (страница 16)
С другой стороны, со временем может быть доказано, что квантовые компьютеры намного эффективнее классических. Сейчас мы кратко изложим то, что известно об эффективности квантовых вычислений. Классификацией сложности различных вычислительных задач, как классических, так и квантовых, занимается теория сложности емчислекЩ и чтобы понять, какова эффективность квантовых компьютеров, мы сначала рассмотрим некоторые обшде идеи нз этой теории.
Наиболее фундаментальным понятием является понятие класса сложности. Класс сложности можно представить как совокупность вычислительных задач, имеющих некоторое общее свойство по отношению к вычислительным ресурсам, требуемым для их решения. Два из наиболее важных класса — это Р и ХР. Грубо говоря, Р— это класс вычислительных задач, которые можно быстро решить на классическом компьютере. МР— это класс задач, решеипл которых можно быстро проверить на классическом компъютере.
Чтобы понять различие между Р и ХР, рассмотрим задачу поиска простых делителей целого числа и. Как известно, пока не существует быстрого способа решения этой задачи на классическом компьютере, и есть основания полагать, что данная задача не входит в Р. С другой стороны, если кто-то скажет вам, что некоторое число р есть делитель п, мы можем быстро проверить, так ли это, рэзделнв и на р, поэтому факторизация— это задача, принадлежащая классу ХР. Очевидно, что Р является подмножеством ХР, так как возможность решения задачи подразумевает возможность проверки потенциальных решений. Неясно, однако, есть ли в г(Р задачи, не входящие в Р. Возможно, самой важной нерешенной проблемой в теоретической информатике является определение того, различны ли эти два класса: РАПИР.
(1.55) Большинство исследователей полагают, что 1чР содержит задачи, не входящие в Р. В частности, существует важный подкласс задач ХР, г(Р-полные задачи, который представляет особый интерес по двум причинам. Во-первых, есть тысячи задач, и среди ннх много крайне важных, которые известны как ХР-полные. Во-вторых, любая ХР-полная задача является в некотором смысле не менее трудной, чем все другие задачи в (чР. Точнее говоря, алгоритм решения конкретной ХР-полной задачи может быть адаптирован для решения любой другой задачи из ХР, причем с небольшими издержками.
В часпюсги, если Р ф (чР, то отсюда следует, что никакая ХР-полная задача не может быть эффективно решена на классическом компьютере. Можно ли использовать квантовые компьютеры для быстрого решения всех задач из ИР— неизвестно, несмотря на тот факт, что на них можно решать некоторые задачи (вроде факторизации), которые, как полагают многие, принадлежат ХР, но не Р. (Заметим, что ХР-полнота факторизации не доказа- 1.4. Квантовые алгоритмы 67 на, иначе мы бы уже знали, как эффективно решать все задачи из ХР при помощи квантовых компьютеров.) Было бы очень хорошо, если бы оказалось возможным эффективно решать на квантовом компьютере все задачи из ХР.
В этом направлении известен очень интересный отрицательный результат, который искшочает использование простого варианта квантового параллелизма для решения всех задач из ХР. В частности, один из подходов к проблеме решения задач из ХР на квантовом компьютере состоит в попьпке использовать какую-либо разновидность квантового параллелизма для параллельного поиска среди всех возможных решений.
В равд. 6.6 мы покажем, что никакой подход, основанный на такой поисковой методологии, не может обеспечить эффе1«тинного решения всех ХР-полных задач из ХР. Невозможность применения такого подхода разочаровывает, но не исключает существования в задачах ХР некоторой более глубокой структуры, которая позволит быстро решать их при помощи квантового компьютера. Р и ХР— это лишь два из множества известных классов сложности.
Другам важным классом сложности является РЯРАСЕ. Грубо говоря, РВРАСЕ состоит из задач, которые можно решить при использовании ресурсов, небольших по пространственному размеру («малый» компьютер), но не обязательно по времени (допустимы «длинные» вычисления). Считается, что РБРАСЕ строго больше, чем Р и ХР в совокупности, хотя это никогда не было доказано. Наконец, класс сложности ВРР содержит задачи, которые могут быть решены с использованием вероятностных алгоритмов за полиномиальное время, если в решении допускается ограниченная вероятность ошибки (скажем, 1~4). ВРР широко признан (даже более, чем Р) как класс задач, которые следует считать эффективно разрешимыми на классическом Компьютере.
Мы сосредоточимся здесь на Р, а не на ВРР, поскольку Р изучен более подробно, однако много похожих идей и выводов возникает и относительно ВРР. Рис. 1.21. взаимосвязь между классическими и квантовыми классами сложности. Квантовые компьютеры могут быстро решить любую задачу из Р, причем известно, что они не могут аффективно решать задачи вне РБРАСЕ. Какое место между Р и РЯРАСЕ занимают квантовые компьютеры-неизвестно, в частности.
потому. что мы не знаем даже, больше ли РЗРАСЕ, чем Р! 68 Глава 1. Введение и общий обзор А как насчет квантовых классов сложности? Мы можем определить ВЯР как класс всех вычислительных задач, которые эффективно решаются на квантовом компьютере, когда допустима ограниченная вероятность ошибки. (Строго говоря, при таком определении ВЦР более подобен классическому классу сложности ВРР, чем Р, но сейчас мы игнорируем эту тонкость и будем рассматривать его как аналог Р.) Как именно Вь?Р соотносится с Р, ХР и РЯРАСŠ— пока неизвестно. Известно лишь, что квантовые компьютеры могут эффективно решать все задачи из Р, но вне РЯРАСЕ нет таких задач, которые они могли бы решать эффективно.
Это означает, что ВЯР находится где-то между Р и РЯРАСЕ, как показано на рис. 1.21. Поэтому если доказать, что квантовые компьютеры строго эффективнее классических, то тогда Р не равен РЯРАСЕ. Доказать последнее безуспешно пытались многие специалисты в области информатики, и это говорит о том, что доказательство превосходства квантовых компьютеров над классическими может оказаться нетривиальным, несмотря на многие доводы в пользу этого утверждения. Дальнейшие рассуждения о предельной эффективности квантовых компьютеров мы отложим до тех пор, пока не начнем лучше понимать принципы, лежащие в основе быстрых квантовых алгоритмов; этой теме отведено значительное место во второй части книги. Но и сейчас уже ясно, что квантовая шеорпл вычислений бросает интересный и серьезный вызов традиционным представлениям о вычислениях.
Особую важность этому вызову придает то, что теоретическая модель квантовых вычислений считается экспериментально реализуемой, ибо, насколько мы знаем, эта теория согласуется с законами Природы. Если бы это было не так, то квантовые вычисления оставались бы просто еще одним математическим курьезом.
1.5 Экспериментальная обработка квантовой информации Квантовые вычисления и квантовая информация — это замечательное теоретическое открытие, но его центральные понятия, такие как суперпозиция и запутанность, противоречат интуиции, формируемой повседневными наблюдениями за окружающим нас миром. Как доказать, что эти представления соответствуют действительности? Возможна ли экспериментальная реализация больших квантовых компьютеров? Есть ли какие-нибудь физические принципы, запрещающие их потенциальное масштабирование? Эти вопросы рассматриваются в двух следующих разделах. Мы начнем с обзора знаменитого эксперимента Штерна-Герлаха, который свидетельствует о существовании кубитов в Природе.
Затем мы рассмотрим более широкую проблему практического построения систем обработки квантовой информации. 1.5.1 Эксперимент Штерна — Герлаха Кубит является фундаментальным элементом в области квантовых вычислений и квантовой информации. Откуда мы знаем, что системы со свойствами 1.5. Экспериментальная обработка квантовой информации 69 кубитов существуют в Природе? На момент написания книги накоплено громадное количество доказательств, но на заре квантовой механики кубитовая структура была совсем не очевидной, и люди бились над объяснением явлений, которые мы сейчас можем понять в терминах кубитов, т.
е. в терминах двухуровневых квантовых систем. Первый решающий (и очень известный) эксперимент, свидетельствующий о кубитовой структуре, был задуман в 1921 г. Штерном и проведен Герлахом в 1922 г. во Франкфурте. В оригинальном эксперименте Штерна-Герлаха «горячие» атомы из печи пролетали через магнитное поле, которое заставляло их отклоняться, после чего положение каждого атома регистрировалось (рис.
1.22). Оригинальный эксперимент проводился с атомами серебра, которые имеют сложную структуру, затушевывающую обсуждаемые эффекты. То, что описано ниже, в действительности относится к эксперименту 1927 гч проведенному с использованием атомов водорода. Основной наблюдаемый эффект тот же, но с атомами водорода легче следить за рассуждениями.
Учтите, однако, что эта привилегия была недоступна людям в начале 20-х гг. ХХ в.; им требовалось проявить немало сообразительности, чтобы придумать объяснения более сложным эффектам, которые они наблюдали. ~+л) ~-г) Рис. 1.22. Абстрактная схема вксперимента Штерна-Герлаха. Горячие атомы водорода из печи пролетают через магнитное поле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
