Что такое квантовая вычислительная модель?

32

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

Casebash
источник
8
Пожалуйста, исправьте орфографию в названии вопроса.
Шейн
Некоторые истории и ссылки здесь en.wikipedia.org/wiki/Universal_quantum_simulator
Раду GRIGore
Примечание мод: слил закрытый вопрос с точной копией с этим вопросом и удалил комментарии из дубликата, которые больше не были актуальны.
Каве

Ответы:

24

Я повторю рекомендацию Мартина Шварца о Nielsen & Chaung в качестве стандартной ссылки; Есть и много других.

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

Я хотел бы дать несколько качественных ответов, чтобы дополнить ответ Мартина.

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

    По крайней мере, можно сказать, что квантовый компьютер рассматривает несколько возможностей одновременно только в той степени, в которой рандомизированные вычисления с использованием монеты flips рассматривает несколько возможностей одновременно. Это потому что:

  2. Квантовые состояния являются обобщением «обычных» распределений вероятностей - с некоторыми простыми, но важными отличиями. Распределение вероятностей может быть представлено как неотрицательный действительный вектор, чьи записи составляют 1: то есть единичный вектор в норме ℓ 1 . Вероятностные вычисления должны отображать ℓ 1 -единичные векторы на другие такие векторы, и поэтому они описываются стохастическими отображениями. Можно описать квантовые вычисления аналогичным образом, за исключением использования using 2 -единичных векторов над ℂ (не ограничиваясь реальными или неотрицательными); преобразования осуществляются с помощью тех отображений, которые сохраняют. Это различие, конечно, не тривиально и пока не объясняет, что означают коэффициенты векторов квантового состояния. 2 -норму, т. е. унитарные операции.

    . Но это может помочь объяснить, что происходит с гильбертовыми пространствами и тензорными произведениями в квантовых вычислениях: то есть, точно так же, как в вероятностных вычислениях. Пространство конфигурации случайного бита - это вектор из ℝ + 2 (где ℝ + - неотрицательные вещественные числа); но поскольку случайные биты могут коррелироваться, мы объединяем пространства конфигурации одного или нескольких случайных битов, беря тензорное произведение. Таким образом, пространство конфигурации двух случайных битов равно ℝ + 2  ⊗ ℝ + 2  ≅ ℝ + 4 или полностью общее пространство распределений вероятностей по четырем различным двухбитным строкам. Операция A на первом из этих случайных битов, которая не действует на второй, представлена ​​оператором A  ⊗  I 2  . И так далее. Те же конструкции применяются к квантовым битам; и мы можем рассматривать квантовые регистры по множествам различимых элементов так же, как мы рассматриваем распределения вероятностей по таким множествам, снова используя using 2 -нормальные векторы над ℂ.

    Это описание фактически описывает «чистые» квантовые состояния - те, для которых вы можете в принципе преобразовать информацию сохраняющий путь к дельта-распределению по битовой строке 00 ... 0 (или, точнее, к состоянию, произвольно близкому к этому в ℓ 2норма). Помимо квантовой случайности (о которой я еще не упомянул ничего явного), вы можете рассмотреть случайную случайную выпуклость, соответствующую вероятностным смесям квантовых состояний: они представлены тем, что важно, в то время как квантовые состояния часто описываются как «экспоненциально большие», это потому, что они обычно описываются с использованием тех же математических структур, что и распределения вероятностей; почему распределения вероятностей не описываются как «экспоненциально большие» таким же образом, неясно (но в конечном счете неважно). Трудность моделирования квантовых состояний проистекает из этого факта вместе с тем, что комплексные коэффициенты этих ℓ 2 операторами плотности , которые могут быть представлены положительно определенными матрицами. со следом 1 (снова обобщая «классические» распределения вероятностей, которые могут быть представлены частным случаем положительных диагональных матриц со следом 1).

    -распределения (или сложные недиагональные члены операторов плотности, если вы предпочитаете) могут отменяться так, как это невозможно с вероятностями, что затрудняет их оценку.

  3. Запутанность - это просто еще одна форма корреляции. Для вероятностных вычислений, например, на булевых строках, единственными «чистыми» состояниями (которые могут быть преобразованы с помощью сохраняющих информацию преобразований в распределение с дельта-пиком на 000 ... 0) являются «стандартная основа» распределений с дельта-пикой различные логические строки. Таким образом, эта основа ℝ + 2 nотличается Но, насколько мы можем судить, в квантовой механике нет такого выдающегося базиса - это наиболее ясно для квантовых битов (посмотрите на частицы со спином 1/2, если хотите знать почему). Как следствие, существует больше сохраняющих информацию преобразований, чем просто перестановок: фактически, их непрерывная группа. Это позволяет потенциальным квантовым компьютерам преобразовывать состояния способами, которые не возможны для вероятностных компьютеров, возможно получая асимптотическое преимущество над ними.

    Но как насчет запутывания, которое многие люди считают загадочным и утверждают, что оно является причиной ускорения квантовых компьютеров по сравнению с классическими? «Запутывание» здесь на самом деле является просто формой корреляции: так же, как две случайные переменные коррелируют, если их распределение представляет собой выпуклую комбинацию более чем одного распределения продукта (с разными маргиналами на каждой переменной), две «квантовые переменные» запутываются, если их распределение представляет собой линейную комбинацию (с единицей ℓ 2-норма) двух действительных дистрибутивов продукта; это та же концепция в другой норме, и она играет аналогичную роль в задачах коммуникации. (Например: «квантовая телепортация» в квантовой связи соответствует кодированию и декодированию сообщения с использованием одноразовой клавиатуры классически.) Это форма корреляции, которая является более общей, чем просто классически коррелированные биты; но единственный способ показать это состоит в том, что корреляции, закодированные в запутанном состоянии, применяются более чем к одной привилегированной основе . В некотором смысле, запутывание является следствием отсутствия привилегированного основания.

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

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

Ниль де Бодрап
источник
1
Я должен признать, я не согласен с вами по вопросу запутанности. Операции над состояниями чистого продукта эффективно моделируются. Бумага "слишком запутанная, чтобы вычислять" немного вводит в заблуждение. Эта статья действительно о ресурсах для вычислений на основе измерений, а MBQC - о ранге Шмидта, а не о запутанности как таковой.
Джо Фицсимонс
1
Вы, конечно, правы, что если вычисление остается в многообразии состояний чистого продукта, оно (эффективно) классически симулируется; но значит ли это, что запутывание делает квантовые компьютеры «более быстрыми» (допускает более короткие вычислительные траектории), а не просто «трудным для следования» (имея «запутанные» вычислительные траектории)? Моя позиция заключается в том, что если происходит квантовое ускорение, то запутывание - это выпускной шлейф, а не ракетное топливо.
Ниль де Бодрап
Что ж, запутанность смешная, так как она зависит от размеров ваших локальных систем. Я думаю, что настоящая сила просто заключается в существовании суперпозиций и, следовательно, сложных амплитуд. Запутанность, кажется, является следствием этого. Есть хорошее кодирование, которое позволяет выполнять универсальные квантовые вычисления с чисто реальными амплитудами, которые, я думаю, способствуют определению этого. Современные алгоритмы используют какой-либо эффект интерференции.
Джо Фицсимонс
Я частично согласен с Джо в вопросе о помехах, но вопрос о том, чтобы строго говорить об этом, заключается в том, какие (разумно проверенные) меры помех существуют на рынке ? Вы, люди, знаете о работах в этом направлении? Единственный пример, который мне приходит в голову, - это (пока я не читал его подробно).
Хуан Бермехо Вега
@JuanBermejoVega: вмешательство кажется лишь следствием того факта, что существуют сохраняющие информацию преобразования, которые не сохраняют стандартные базовые состояния. Единственной очевидной альтернативой помехам является потеря информации, как в классической вероятности. Тогда то, что мы имеем, - это просто обратимые преобразования, которые не сохраняют стандартную основу; Повествование о помехах, столь же продуктивное, как и при разговоре о распространении в космосе, является просто способом описания того, как это выглядит, если вы продолжите пытаться анализировать это несохранение в терминах стандартной основы.
Ниль де Бодрап,
12

Лэнс Фортноу написал статью, которая объясняет квантовые вычисления без использования квантовой механики. Он представляет это по существу так же, как и вероятностные вычисления. Я подозреваю, что это может быть более быстрой отправной точкой, чем что-то вроде Нильсона и Чуанга (хотя я согласен, что если вы действительно хотите заняться этим, то Нильсон и Чанг обязательно должны быть в вашем списке для чтения).

Л. Фортноу. Один взгляд теоретика сложности на квантовые вычисления. Теоретическая информатика, 292 (3): 597-610, 2003. Специальный выпуск докладов, представленных на втором семинаре по алгоритмам в квантовой обработке информации.

Джошуа Грохов
источник
11

Ну, стандартный текст, используемый Нильсеном и Чуаном, - это « Квантовые вычисления» и «Квантовая информация ». Он охватывает целый ряд различных аспектов на разумном уровне. Почти каждый, кто работает в этой области, имеет копию этого на своей полке. Книга Kaye, Laflamme и Mosca также хороша, но охватывает меньше (хотя немного больше внимания уделяется алгоритмам).

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

Тем не менее, квантовая механика, необходимая для понимания квантовых вычислений, довольно проста и достаточно хорошо описана в Nielsen и Chuang. На самом деле, вы можете почувствовать это, прочитав соответствующую главу и выполнив упражнения. Это та вещь, которую вы можете получить честное понимание за пару дней работы. Мой совет, однако, не идите для стандартного вступительного текста к квантовой механике. Подход, использованный для моделирования атомов, молекул и материалов, использует бесконечномерные системы и требует гораздо больших усилий, чтобы достичь вершины. Для квантовой информации гораздо лучше начать смотреть на конечномерных системах. Кроме того, традиционно проблемы, изучаемые физиками, имеют тенденцию вращаться вокруг нахождения основных состояний и поведения в устойчивом состоянии, и это то, что охватит большинство вводных текстов (начиная с не зависящего от времени волнового уравнения Шредингера). Что касается квантовых вычислений, мы, как правило, более заинтересованы во временной эволюции систем, и это гораздо более кратко рассматривается в текстах квантовых вычислений, чем в общих текстах квантовой механики (которые по определению являются более общими).

Джо Фитцсимонс
источник
8

ВQп

|φ в двумерном гильбертовом пространстве ЧАС2, Большие регистры формируются тензорными произведениямиЧАС2,,,ЧАС2основного двумерного гильбертова пространства. Размерность составного пространства является произведением размерности составляющих пространств и, таким образом, экспоненциально масштабируется с количеством кубитов в квантовом регистре. Квантовое состояние в регистре снова является единичным вектором|ψв сложном пространстве. Компоненты этого вектора являются комплексными значениями, называемыми амплитудами вероятности, и могут быть помечены классическими битовыми строками. Эволюция состояния осуществляется с помощью унитарного оператораU(также известный как квантовые ворота) к некоторому подмножеству кубитов постоянной ширины. В конце вычисления кубиты измеряются, приводя к классической битовой строке как результат с распределением вероятностей, которое связано сsQUaре амплитуды вероятности, связанной с этой битовой строкой.

Для более подробного ознакомления, пожалуйста, обратитесь к стандартному учебнику Nielsen and Chuang.

Мартин Шварц
источник
Наряду с моделями, упомянутыми Мартином, существует несколько других: основанные на измерениях, адиабатические и топологические квантовые вычисления.
Джо Фицсимонс
5

Во-первых, вам нужно понять квантовую физику.

Несколько рекомендаций:

  1. « Квантовые вычисления для компьютерных ученых » Носона С. Янофски и Мирко А. Маннуччи
  2. «Введение в квантовые вычисления» Филиппа Кея, Рэймонда Лафламма и Мишеля Моски

И о более интересной стороне вещей, «Сокращение во времени: путь к квантовому компьютеру» Джорджа Джонсона.

Шейн
источник
5

Вы можете получить хорошее вступление в статье Элеоноры Риффель и Вольфганга Полака «Введение в квантовые вычисления для нефизиков». Возможно, он немного староват, но все же это хорошее, краткое, самостоятельное введение в тему: http://arxiv.org/abs/quant-ph/9809016

Еще одна статья, гораздо более обобщенная, - это «Квантовые вычисления, объясненные моей маме» Пабло Арири на http://arxiv.org/abs/quant-ph/0305045.

Алехандро, округ Колумбия
источник
1
Риффель и Полак, похоже, тоже выпустили книгу: « Квантовые вычисления: приятное введение»
Логан Мэйфилд
4

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

Если вы хотите введение в книгу, но что-то более мягкое, чем текст, такой как Нильсен и Чуанг, я бы порекомендовал Квантовые вычисления для компьютерных ученых » Янофски и Маннуччи. Они тратят немало времени на изучение математических предпосылок, прежде чем погрузиться в сам КК. Если у вас сильный математический фон, эта книга может показаться слишком простой, но я нашел ее весьма полезной.

Kurt
источник
3

Если вы достаточно продвинуты, вы можете начать с обзора де Вольф-Друкером квантовых методов для классических задач. Это хороший способ понять квантовые методы, прежде чем вы перейдете к квантовым проблемам .

Суреш Венкат
источник
2

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

Алехандро, округ Колумбия
источник
2

Помимо своего стандартного текста с Чуаном, Майкл Нильсен имеет серию видео-лекций на Youtube под названием « Квантовые вычисления для детерминированных», которые пока дают обзор вычислительной модели. Видеоролики очень интересны для тех, кто немного разбирается в информатике и линейной алгебре.

Максимум
источник