Кратчайшая последовательность универсальных квантовых вентилей, соответствующих данному унитарному

9

Вопрос: Учитывая унитарную матрицу, действующую на кубитов, можем ли мы найти кратчайшую последовательность гейтов Клиффорда + T, которые соответствуют этой унитарной?N

Для справки по вопросу, две важные ссылки:

  1. Быстрый и эффективный точный синтез унитарных единичных кубитов, порожденных Клиффордом и Т- гейтсом Ключниковым, Масловым и Моской
  2. Точный синтез многокбитных цепей Клиффорда + Т Джайлза и Селинджера.
user120404
источник
3
Добро пожаловать! Я добавил две ссылки на тему для контекста. Пожалуйста, откат или исправить, если они не подходят. Кроме того, если бы к вопросу можно было добавить больше деталей, это было бы здорово :)
agaitaarino

Ответы:

9

Получение оптимальной декомпозиции - определенно открытая проблема. (И, конечно же, декомпозиция неразрешима, gates для больших .) «Более простой» вопрос, который вы могли бы сначала задать, - какова самая короткая последовательность узлов и вращений одного кубита под любым углом (что IBM , Rigetti, и скоро Google предлагает, эта универсальная основа Гейтса может быть выражена с точки зрения вашей базы Клиффордса и Т-Гейтса). Этот «более простой» вопрос также открыт и имеет неуникальный ответ. С этим связан вопрос, что такое точное оптимальное разложение вентилей из универсальной основы для перехода из основного состояния в данное конечное состояние.ехр(N)N

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

«Квантовый csd-компилятор» в Qubiter выполняет неоптимизированную декомпозицию любого n-кубитного унитарного числа в узлы и гниды одиночного кубита, используя знаменитую подпрограмму csd (Cosine-Sine Decomposition) из LAPACK. Некоторые предприимчивые люди могут попытаться найти оптимизации для квантового компилятора Qubiter. Например, вы можете использовать компилятор Qubiter (я написал статью об этом), чтобы позволить вашему классическому компьютеру заново обнаружить квантовое разложение Фурье-преобразования Фурье!

Qubiter с открытым исходным кодом и доступен на github (полное раскрытие - я написал его).

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

Предположим, что точный синтез был возможен для предоставленного вами унитарного (число теоретических ограничений на записи), и поэтому алгоритмы, описанные в этом вопросе, дали вам последовательность гейтов Клиффорда + Т, которые реализовали этот унитарный. Как указано в статье Джайлза-Селинджера, вы получаете последовательность, которая очень далека от оптимальной. Таким образом, в этот момент вы сократили проблему со словом в группе, порожденной множеством вентилей Клиффорд + Т. Некоторые группы имеют алгоритмы для сокращения заданного слова, в то же время представляя один и тот же элемент группы в нормальной форме, которая является самой короткой в ​​этом классе. Другие нет.

Более подробно, чтобы проиллюстрировать принцип: допустим, есть 2кубитов. ОбозначимS1 и т.д. для генератора, который делает фазовые затворы на кубите 1, СNОT12 за 1контроль и т. д. Каждый из них рассматривается как письмо. Алгоритм выдаст какое-то слово в этих генераторах. Группа - это группа с этими генераторами и многими отношениями, такими какSя4знак равно1 а также ИксяYJзнак равноYJИкся когда яJсреди многих других отношений. Так что это определяет некоторую конечно порожденную группу. Поскольку у нас есть слово из предоставленных алгоритмов, но оно не было оптимизировано, задача состоит в том, чтобы предоставить удобную кратчайшую нормальную форму в словесной задаче для этой группы. Так что, если дать словоS1S1S2S1S1 можно использовать отношение S1S2знак равноS2S1 дважды и S14знак равно1 отношение один раз, чтобы получить S2как более короткое слово, представляющее тот же элемент группы. Для данной групповой презентации нужен алгоритм, который берет произвольное слово и сокращает его. В общем, это невозможно.

Отказ от ответственности ниже: будущий проект / совместная реализация Haskell с Jon Aytac.

Я не знаю о разрешимости проблемы слов для множества ворот Клиффорда + Т, но можно сделать что-то попроще только с инволюциями (назовите их ря) в этом наборе и только отношения вида (рярJ)мяJзнак равно1, Это группа Кокстера, связанная с набором гейтов Клиффорда + Т, но с эффективно разрешимой проблемой слов. Таким образом, можно взять результат алгоритма Джайлса-Селинджера и потенциально сократить его, используя только эти очень простые отношения (после просмотра сегментов только с этими буквами инволюции). Фактически любой алгоритм, который принимает данное унитарное значение и аппроксимирует или точно синтезирует его в Clifford + T, может быть введен в эту процедуру, чтобы потенциально его немного сократить.

AHusain
источник