Временные плоские односторонние квантовые вычисления

18

В глубине души я физик, и поэтому я считаю, что односторонние квантовые вычисления великолепны. В частности, Quantum Computing (MBQC), основанная на измерениях графических состояний, была действительно хорошей разработкой в ​​исследованиях Quantum Computing, созданной Raussendorf & Briegel . Нужно просто подготовить многораздельное запутанное состояние, как описано графиком, а затем выполнить последовательные измерения на каждом узле или кубите (адаптивные измерения для детерминированных вычислений).

Другой превосходный аспект этого подхода заключается в том, что схемы Клиффорда могут быть реализованы за один цикл измерений, как показано Рауссендорфом, Брауном и Бригелем . Эти схемы могут быть классически смоделированы (эффективно), как показано Gottesman и Knill, так что это интересная связь между классическим моделированием и временными ресурсами.

Однако не все схемы MBQC состояния графа с плоским графиком (состоящие из одного цикла измерений) считаются классически симулируемыми. Например, семейства схем в модели квантовых цепей, состоящих из коммутирующих вентилей, называемых схемами IQP, представленных Шепардом и Бремнером, могут быть реализованы за один временной шаг в MBQC. Считается, что эти схемы IQP не являются классически симулируемыми (в терминах сложности вычислений это приведет к коллапсу полиномиальной иерархии) .

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

Во всяком случае, мой вопрос:

Существуют ли другие интересные схемы, которые могут быть реализованы за один временной шаг в MBQC?

Хотя я предпочел бы отношения вычислительной сложности или классическому моделированию, я нашел бы что-нибудь интересное.

Изменить: После превосходного ответа Джо ниже, я должен уточнить пару вещей. Как сказал Джо (и несколько смущающе, как я уже говорил в одной из моих собственных статей), схемы IQP с одним циклом измерений находятся в IQP. Если быть более точным, меня интересуют интересные схемы проблем IQP, которые могут быть реализованы за один цикл измерений в MBQC. Схемы Клиффорда - интересный пример. Если есть какие-либо другие примеры, которые являются классически симулируемыми, это было бы чрезвычайно интересно. Поскольку классическое моделирование IQP-схем считается маловероятным, было бы интересно найти примеры таких схем.

Мэтти Хобан
источник

Ответы:

5

Учитывая обновленную информацию по этому вопросу, я подумал, что лучше всего опубликовать это как новый ответ, так как он полностью отличается от моего предыдущего ответа и, надеюсь, будет интересным.

По новой формулировке вопроса кажется, что есть скрытое предположение, что состояние ресурса MBQC имеет много кубитов, полиномиальных по числу логических кубитов. Это не обязательно должно иметь место, что приводит к потенциально интересной ситуации. Можно построить вычисления на основе одноуровневых измерений, для которых состояние ресурса обязательно будет экспоненциальным по количеству логических кубитов, .N

JИксZехр(яθΠяZя)яJJ|00|я+|11|ΠяZя|+12(|0я+|1ΠяZя)ехр(яθИкс)12(|0(созθя+ягрехΠяZя)+|1(ΠяZя)(созθя+ягрехΠяZя)ΠяZясозθя+ягрехΠяZяехр(яθΠяZя)

NС,,,,СZgate) является примером такой операции, которая требует экспоненциального числа коммутирующих вентилей, хотя это может быть достигнуто с линейным числом не коммутирующих вентилей. Таким образом, можно построить вычисления на основе однослойного измерения, которые реализуют X-программы, которые имеют экспоненциальное число логических кубитов и, следовательно, вне IQP для логических кубитов (хотя внутри IQP для физических кубитов).

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

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

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

На самом деле, я считаю, что вы просматриваете IQP более узко, чем вы, вероятно, должны. Ответ на ваш вопрос заключается в том, что любой MBQC, который может быть реализован на одном уровне измерения в MBQC, содержится в IQP. Это просто потому, что вместо выражения результата в терминах логического гильбертова пространства вы можете выразить его как последовательность коммутирующих операций на физических кубитах. Шепард и Бремнер на самом деле имеют дело с этим в своей статье (в разделе 5.2, где такие операции называются граф-программами).

Джо Фитцсимонс
источник
Спасибо, Джо. Я думал об этих граф-программах именно тогда, когда говорил об IQP и о том, где они показали, что каждая X-программа может быть реализована с помощью граф-программы. Тем не менее, каждый создает граф-программу предписывающим способом для выполнения X-программы. Возможно, моя формулировка в вопросе немного пренебрежительно. Я предполагаю, что моя проблема с некоммутирующими воротами состоит в том, чтобы искать пример, такой как схема Клиффорда, которая может быть реализована за один временной шаг.
Мэтти Хобан
@Matty: Моя точка зрения заключается в том, что групповые ворота Клиффорда коммутируют ворота в физической системе, а не в логической картине Гейзенберга, которую мы обычно используем, чтобы посмотреть на вычисления в MBQC. Поскольку они коммутируют в физической системе, они попадают в IQP. Это просто интерпретация логических кубитов, которая ставится поверх этого, что меняет вещи. По сути, любые однослойные вычисления MBQC находятся в IQP именно по этой причине.
Джо Фитцзимонс
Ах, конечно. Теперь я понимаю, что вы имеете в виду. Извините за медлительность. Конечно, в IQP также есть схемы, которые не могут быть реализованы за один шаг по времени в MBQC. Спасибо за это, Джо. Моей первоначальной мотивацией было в основном найти примеры схем в IQP, которые могли бы представлять интерес - в основном для пары абзацев в моей диссертации.
Мэтти Хобан
1
Я отредактировал вопрос, чтобы быть немного менее расплывчатым. Еще раз спасибо за ваш ответ. Кстати, я чертовски люблю TP.SE, так что спасибо за это тоже :).
Мэтти Хобан