Существует ли конечный унитарный набор затворов, который может точно реализовать все КТП порядка

11

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

Квантовое преобразование Фурье (QFT), заданное является знаменитой частью квантовой вычислительной теории. В случае хорошо известно разложение на Адамара, ворота SWAP,N = 2 n F N C Z 2 T = d i a g ( 1 , 1 , 1 , e 2 π i / 2 T

FN=1N[111111ωω2ω3ωN11ω2ω4ω6ωN21ω3ω6ω9ωN31ωN1ωN2ωN3ω(N1)2]for ω=e2πi/N,
N=2nFNT 1
CZ2T=diag(1,1,1,e2πi/2T)
T1 , который принадлежит Копперсмиту. Если EQPP должен содержать какие-либо проблемы, можно надеяться, что один из них будет использовать QFT F2n , и в этом случае потребуется семейство операций F2n чтобы разложить в некоторый определенный конечный набор ворот. Используя рекурсивное разложение QFT, это эквивалентно разложению всех вентилей CZ2n в один конечный набор ворот.

Очевидно, что по теореме Соловея – Китаева мы можем сколь угодно хорошо аппроксимировать вентили или любым приблизительно универсальным набором вентилей, замкнутым относительно инверсий. Я хотел бы знать, существует ли конечное множество ворот, которое может точно реализовать эти семейства операторов, или, что я подозреваю, более вероятно, есть ли доказательство того, что такого конечного множества ворот не существует. C Z 2 nF2nCZ2n

Вопрос. Есть ли разложение как семейства многоуровневых схем на конечном множестве ворот или доказательство того, что это невозможно?{F2n}n1

Ниль де Бодрап
источник

Ответы:

7

Нет, нет разложения всего семейства в один конечный набор ворот. Вот почему{F2n}n1

QFT содержат только коэффициенты над , комплексным алгебраическим замыканием рациональных чисел. По аналогии с [ Adleman + Demarrais + Huang – 1997 ], если бы мы включили какие-либо врата, которые включали какие-либо трансцендентные числа, мы могли бы выбрать минимальный набор трансцендентальных и описать коэффициенты гейта по существу, как рациональные функции . Чтобы получить QFT как продукт таких врат, мы должны принять меры к отмене всех трансцендентных компонентов (подобное должно происходить, чтобы гарантировать, что каждый из врат унитарен); но тогда мы могли бы также заменить все трансцендентные на {τ1,τ2,} ¯ Q (τ1,τ2,)0Q¯{τ1,τ2,}Q¯(τ1,τ2,)0, так что все коэффициенты алгебраичны. Таким образом, мы ограничимся алгебраическими воротами без потери общности.

Коэффициенты конечного вентиля, заданного над могут содержаться в расширении конечной степени , которое можно построить, расширяя по этим самым коэффициентам. Однако ворота очевидно, имеют коэффициенты, принадлежащие расширениям полей над степени , т.е. неограниченной степени. Таким образом, семейство КТП порядка не разлагается ни в какое конечное множество ворот. QQСZ 2 п Q2п-12нQ¯QQCZ2nQ2n12n

Как следствие, мы не можем надеяться на наличие каких-либо алгоритмов в которые опираются на КТП над циклическими кольцами неограниченного размера - отметим, что та же проблема возникает для любого семейства схем, которые могут использовать КТП произвольного порядка.EQP

Ниль де Бодрап
источник