Existe um conjunto de portas unitárias finitas que pode realizar exatamente todos os QFTs da ordem ?

11

Estou pensando em idéias sobre algoritmos quânticos exatos. Em particular, estou considerando as prováveis ​​limitações de , que consiste em linguagens exatamente decidíveis por famílias de circuitos quânticos uniformes em tempos polimórficos sobre um conjunto de portas finitas arbitrárias.EQP

A transformada quântica de Fourier (QFT), dada por é uma parte célebre da teoria computacional quântica. No caso de , existe uma decomposição bem conhecida de em Hadamards, portas 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=2nFN
CZ2T=diag(1,1,1,e2πi/2T)
T1 , devido ao Coppersmith. Se EQPP tiver algum problema, pode-se esperar que um deles faça uso dos QFTs F2n , caso em que seria necessário a família de operações F2n para se decompor em algum conjunto de portas finitas específico. Usando a decomposição recursiva do QFT, isso equivale a uma decomposição de todos os portões CZ2n em um único conjunto de portas finitas.

Obviamente, pelo teorema de Solovay-Kitaev, podemos aproximar os portões F2n ou CZ2n arbitrariamente bem com qualquer conjunto de portas aproximadamente universal que seja fechado sob inversão. O que eu gostaria de saber é se existe um conjunto de portas finito que pode realizar exatamente essas famílias de operadores - ou, o que eu suspeito é mais provável, se existe uma prova de que não existe esse conjunto de portas finito.

Questão. Existe uma decomposição de {F2n}n1 como uma família de circuitos policitem uniforme em um conjunto de portas finito ou uma prova de que isso é impossível?

Niel de Beaudrap
fonte

Respostas:

7

Não, não há decomposição de toda a família em um único conjunto de portas finito. Aqui está o porquê.{F2n}n1

Os QFTs envolvem apenas coeficientes acima de , o complexo fechamento algébrico dos números racionais. Em analogia a [ Adleman + Demarrais + Huang – 1997 ], se envolvermos portas que incluam números transcendentais, poderíamos escolher um conjunto mínimo de transcendentais e descrever os coeficientes de porta essencialmente como funções racionais . Para obter o QFT como um produto desses portões, precisamos providenciar o cancelamento de todos os componentes transcendentais (algo semelhante deve ocorrer para garantir que cada um deles seja unitário); mas então podemos substituir todos os transcendentais porQ¯{τ1,τ2,}Q¯(τ1,τ2,)0, para que todos os coeficientes sejam algébricos. Portanto, nos restringimos a conjuntos de portas algébricas sem perda de generalidade.

Os coeficientes de uma porta finita configurada sobre podem estar todos contidos em uma extensão em grau finito de , que pode ser construído estendendo por esses coeficientes. Entretanto, os portões obviamente têm coeficientes pertencentes a extensões de campo acima de do grau , isto é, de grau ilimitado. Assim, a família de QFTs da ordem não se decompõe em nenhum conjunto finito de portas.Q¯QQCZ2nQ2n12n

Como corolário, não podemos esperar ter nenhum algoritmo em que dependa de QFTs em anéis cíclicos de tamanho ilimitado - observe que o mesmo problema ocorre em qualquer família de circuitos que possam usar QFTs de ordem arbitrária.EQP

Niel de Beaudrap
fonte