Квантовый компьютер
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
1;перестановка переводит первоначальное состояние сортировки в желаемое являлось бы верным.
В задаче неупорядоченного поиска ничего не известно о структуре пространства решений и об утверждении . Например, определение не дает никакой информации о возможном значении для . В задаче упорядоченного поиска можно использовать информацию о пространстве поиска и об утверждении .
Например, поиск по алфавитному списку является задачей упорядоченного поиска, и алфавитный порядок используется для построения алгоритма. В других случаях, скажем, в задачах, где нужно найти хотя бы одно решение, структуру задачи можно использовать для построения эвристических алгоритмов, которые быстро дают решения для некоторых отдельных случаев. Но в общем случае, когда мы имеем задачу неупорядоченного поиска, лучшее, что можно сделать классическим путем - это последовательно проверять истинность каждого утверждения . Для поискового пространства из элементов обычная задача неупорядоченного поиска требует проверок . На квантовом же компьютере, как показал Гровер, задачу неупорядоченного поиска можно решить с большой вероятностью производя около проверок. Таким образом, квантовый алгоритм Гровера является заведомо более эффективным, чем любой алгоритм для неупорядоченного поиска, выполняемый на классическом компьютере.
Гровер также показал, что некоторые поисковые задачи, которые на классических компьютерах выпоняются за могут быть решены за на квантовом компьютере. Поиск Гровера можно использовать в других квантовых вычислениях в качестве подпрограммы. Байрон показал, что алгоритм Гровера можно применять для произвольного начального распределения амплитуд, и что при этом сохраняется сложность порядка .
2. Реализация квантового компьютера
В данном разделе кратко описаны основные принципы работы и построения любого квантового компьютера, а также направления в развитии их элементной базы.
2.1Основные принципы работы и реализации квантового компьютера
Квантовые методы выполнения вычислительных операций, а также передачи и обработки информации, уже начинают воплощаться в реально функционирующих экспериментальных устройствах, что стимулирует усилия по реализации квантовых компьютеров - этого нового направления в вычислительной технике.
Количество публикаций по квантовой теории информации и квантовым вычислениям приобрело в последнее время лавинообразный характер, появились и экспериментальные работы.
Принципиальная схема работы любого квантового компьютера может быть представлена следующим образом (см. рис.2.1).
Рис. 2.1. Схематическая структура квантового компьютера
Основной его частью является квантовый регистр - совокупность некоторого числа L кубитов. До ввода информации в компьютер все кубиты регистра должны быть приведены в основные базисные (булевы) состояния, то есть в состояние . Эта операция называется подготовкой начального состояния или инициализацией. Далее каждый кубит подвергается селективному воздействию, например, с помощью импульсов внешнего электромагнитного поля, управляемых классическим компьютером, которое переведет основные базисные состояния определенных кубитов в неосновное состояния . При этом состояние всего регистра перейдет в суперпозицию базисных состояний вида , где , задающую бинарное представление числа .
При вводе информации в квантовый компьютер состояние входного регистра, с помощью соответствующих импульсных воздействий преобразуется в соответствующую когерентную суперпозицию базисных ортогональных состояний . В таком виде информация далее подвергается воздействию квантового процессора, выполняющего последовательность квантовых логических операций, определяемую унитарным преобразованием , действующим на состояние всего регистра. К некоторому моменту времени t в результате преобразований исходное квантовое состояние становится новой суперпозицией вида , которая и определяет результат преобразования информации на выходе компьютера.
Совокупность всех возможных операций на входе данного компьютера, формирующих исходные состояния, а также осуществляющих унитарные локальные преобразования, соответствующие алгоритму вычисления, способы подавления потери когерентности - так называемой декогерентизации (decoherence) квантовых состояний и исправления случайных ошибок, играют здесь ту же роль, что и "программное обеспечение" (software) в классическом компьютере.
Теперь обратимся к аппаратной части квантового компьютера. При выборе конкретной схемы любого квантового компьютера необходимо решить три вопроса: во-первых, выбрать физическую систему, представляющую требуемую систему кубитов, во-вторых, определить физический механизм, определяющий взаимодействие между кубитами, необходимое для выполнения двухкубитовых операций, в-третьих, определить способы селективного управления кубитами и измерения их состояния на выходе. Все это вместе взятое аналогично "аппаратному обеспечению" (hardware) классического компьютера.
Считается, что для реализации полномасштабного квантового компьютера, превосходящего по производительности любой классический компьютер, на каких бы физических принципах он не работал, следует обеспечить выполнение следующих пяти основных требований:
.Физическая система, представляющая полномасштабный квантовый компьютер, должна содержать достаточно большое число хорошо разл