Sequência mais curta de portões quânticos universais que correspondem a uma dada unidade

Pergunta: Dada uma matriz unitária atuando em qubits, podemos encontrar a menor seqüência de portas Clifford + T que corresponde a essa unidade?$n$

Para um pano de fundo sobre a questão, duas referências importantes:

1. Síntese exata rápida e eficiente de unidades de um único qubit geradas por Clifford e T gates por Kliuchnikov, Maslov e Mosca
2. Síntese exata de circuitos Clifford + T multiqubit por Giles e Selinger.

Obter uma decomposição ideal é definitivamente um problema em aberto. (E, é claro, a decomposição é intratável, gates para n . Grande ). Uma pergunta "mais simples" que você pode perguntar primeiro é qual é a menor seqüência de cnots e rotações de qubit único por qualquer ângulo (o que IBM, Rigetti e, em breve, o Google oferece atualmente, essa base universal de portões pode ser expressa em termos de sua base de Cliffords e t-gates). Essa pergunta "mais simples" também está aberta e tem uma resposta não exclusiva. Uma questão relacionada é o que é uma decomposição ideal exata dos portões de uma base universal para ir do estado fundamental para um determinado estado final.$\exp(n)$$n$

Suponho que você esteja se referindo a decomposições exatas. Se você deseja decomposições aproximadas, existem métodos diferentes para isso, como a decomposição Trotter-Suzuki ou aproximação aproximada de uma decomposição exata.

O "compilador quântico de csd" no Qubiter faz uma decomposição não otimizada de qualquer n qubit unitário em cnots e rots de qubit único usando a famosa sub-rotina csd (Cosine-Sine Decomposition) do LAPACK. Alguma pessoa empreendedora poderia tentar encontrar otimizações para o compilador quântico do Qubiter. Você pode usar o compilador do Qubiter, por exemplo (escrevi um artigo sobre isso), para deixar seu computador clássico redescobrir a decomposição quântica da Transformada de Fourier da Coppersmith!

O Qubiter é de código aberto e está disponível no github (divulgação completa - escrevi).

Suponha que fosse possível uma síntese exata para o seu unitário fornecido (o número de restrição teórica nas entradas) e, portanto, os algoritmos descritos na pergunta forneceram uma sequência de portas Clifford + T que implementaram esse unitário. Conforme declarado no artigo de Giles-Selinger, você obtém uma sequência que está muito longe do ideal. Portanto, nesse ponto, você reduziu o problema da palavra no grupo gerado pelo conjunto de portas Clifford + T. Alguns grupos têm algoritmos para encurtar uma determinada palavra enquanto ainda representam o mesmo elemento do grupo em uma forma normal que é a mais curta dentro dessa classe. Outros não fazem.

$2$$S_1$$1$$CNOT_{12}$$1$$S_i^4=1$$X_i Y_j = Y_j X_i$$i \neq j$$S_1 S_1 S_2 S_1 S_1$$S_1 S_2 = S_2 S_1$$S_1^4=1$$S_2$como uma palavra mais curta que representa o mesmo elemento do grupo. Para uma determinada apresentação em grupo, é necessário um algoritmo que pegue uma palavra arbitrária e a reduz. Em geral, isso não é possível.

Isenção de responsabilidade para abaixo: Projeto futuro / implementação conjunta de Haskell com Jon Aytac.

$r_i$$(r_i r_j)^{m_{ij}}=1$. Esse é um grupo de Coxeter relacionado ao conjunto de portas Clifford + T, mas com um problema de palavras solucionável com eficiência. Portanto, pode-se pegar o resultado do algoritmo de Giles-Selinger e potencialmente encurtá-lo usando apenas essas relações muito simples (depois de examinar segmentos com apenas aquelas letras de involução). De fato, qualquer algoritmo que pega um dado unitário e o aproxima ou sintetiza exatamente no Clifford + T pode ser alimentado nesse procedimento para encurtá-lo um pouco.