Compilação automática de circuitos quânticos

Uma pergunta recente aqui perguntou como compilar o portão CCCZ de 4 qubit (Z controlado-controlado-controlado) em portas simples de 1 e 2 qubit, e a única resposta dada até agora requer 63 portas !

O primeiro passo foi usar a construção C U dada por Nielsen & Chuang:$^n$

Com isso significa 4 portas CCNOT e 3 portas simples (1 CNOT e 2 Hadamards são suficientes para fazer a CZ final no qubit de destino e no último qubit de trabalho).$n=3$

O teorema 1 deste artigo diz que, em geral, o CCNOT requer 9 portas de um qubit e 6 de dois qubit (15 no total):

Isso significa:

(4 CCNOTs) x (15 portas por CCNOT) + (1 CNOT) + (2 Hadamards) = 63 portas totais .

Em um comentário , foi sugerido que os 63 portões possam ser posteriormente compilados usando um "procedimento automático", por exemplo, da teoria dos grupos automáticos .

Como essa "compilação automática" pode ser feita e quanto isso reduziria o número de portas de 1 e 2 qubit nesse caso?

Vamos $g_1 \cdots g_M$ ser as portas básicas que você tem permissão para usar. Para os fins deste $\operatorname{CNOT}_{12}$ e $\operatorname{CNOT}_{13}$ etc, são tratados como separados. Então $M$ é polinomialmente dependente de $n$ , o número de qubits. A dependência preciso envolve detalhes dos tipos de portas que você usa e como $k$ -local eles são. Por exemplo, se existem $x$ portas de um qubit e $y$ portas de 2 qubit que não dependem de ordem como $CZ$ então .$M = xn+\binom{n}{2}y$

Um circuito é então um produto desses geradores em alguma ordem. Mas existem vários circuitos que não fazem nada. Como . Então, aqueles dão relações ao grupo. Ou seja, é uma apresentação em grupo em que existem muitas relações que não conhecemos.$\operatorname{CNOT}_{12} \operatorname{CNOT}_{12} = \mathrm{Id}$ ⟨ g 1 ⋯ g M | R 1 ⋯ ⟩ $\langle g_1 \cdots g_M \mid R_1 \cdots \rangle$

O problema que queremos resolver recebe uma palavra nesse grupo, qual é a palavra mais curta que representa o mesmo elemento. Para apresentações em grupo, isso é inútil. O tipo de apresentação em grupo em que esse problema está acessível é chamado de automático.

Mas podemos considerar um problema mais simples. Se jogarmos fora alguns dos , as palavras de antes ficarão no formato onde cada um dos são palavras apenas nas letras restantes. Se conseguirmos torná-los mais curtos usando as relações que não envolvem o , teremos tornado o circuito inteiro mais curto. Isso é semelhante à otimização dos CNOTs por conta própria, feita na outra resposta.$g_i$$w_1 g_{i_1} w_2 g_{i_2} \cdots w_k$$w_i$$g_i$

Por exemplo, se houver três geradores e a palavra for , mas não quisermos lidar com , encurtamos e para e . Em seguida, os reunimos como e isso é um encurtamento da palavra original.$aababbacbbaba$$c$$w_1=aababba$$w_2=bbaba$W 1 W 2 W 1 C w 2$\hat{w}_1$$\hat{w}_2$$\hat{w}_1 c \hat{w}_2$

Portanto, WLOG (sem perda de generalidade), vamos supor que já estamos nesse problema onde agora usamos todos os portões especificados. Novamente, este provavelmente não é um grupo automático. Mas e se jogarmos fora algumas das relações. Depois, teremos outro grupo que possui um mapa de quociente para o que realmente queremos.$\langle g_1 \cdots g_M \mid R_1 \cdots \rangle$

O grupo sem relações é um grupo livre , mas se você colocar como uma relação, obterá o produto gratuito e existe um mapa de quociente do anterior para o posterior, reduzindo o número de 's em cada módulo do segmento .$\langle g_1 g_2 \mid - \rangle$g 2 1 = i d Z 2 ⋆ Z g 1 2$g_1^2=\mathrm{id}$ $\mathbb{Z}_2 \star \mathbb{Z}$$g_1$$2$

As relações que lançamos serão tais que a de cima (a fonte do mapa de quociente) será automática por design. Se usarmos apenas as relações que permanecem e encurtar a palavra, ainda será uma palavra mais curta para o grupo de quocientes. Apenas não será o ideal para o grupo de quocientes (o destino do mapa de quocientes), mas terá o comprimento do comprimento com o qual começou.$\leq$

Essa foi a ideia geral, como podemos transformar isso em um algoritmo específico?

Como escolhemos o e as relações a serem descartadas para obter um grupo automático? É aqui que entra o conhecimento dos tipos de portões elementares que normalmente usamos. Existem muitas involuções, portanto, mantenha-as apenas. Preste muita atenção ao fato de que essas são apenas as involuções elementares; portanto, se o seu hardware tiver dificuldade em trocar qubits amplamente separados no seu chip, isso será gravado apenas naqueles que você pode fazer com facilidade e reduzindo essa palavra a seja o mais curto possível.$g_i$

Por exemplo, suponha que você tenha a configuração da IBM . Então são os portões permitidos. Se você deseja fazer uma permutação geral, decomponha-a em fatores. Essa é uma palavra no grupo que queremos reduzir .$s_{01},s_{02},s_{12},s_{23},s_{24},s_{34}$$s_{i,i+1}$$\langle s_{01},s_{02},s_{12},s_{23},s_{24},s_{34} \mid R_1 \cdots \rangle$

Observe que essas não precisam ser as involuções padrão. Você pode inserir além de por exemplo. Pense no teorema de Gottesman-Knill , mas de uma maneira abstrata que significa que será mais fácil generalizar. Como usar a propriedade que, em sequências exatas curtas, se você possui sistemas de reescrita finitos e completos para os dois lados, obtém um para o grupo do meio. Esse comentário é desnecessário para o restante da resposta, mas mostra como você pode criar exemplos maiores e mais gerais a partir dos apresentados nesta resposta.$R(\theta) X R(\theta)^{-1}$$X$

As relações mantidas são apenas as da forma . Isso fornece um grupo Coxeter e é automático. De fato, nem precisamos começar do zero para codificar o algoritmo dessa estrutura automática. Ele já está implementado no Sage (baseado em Python) de propósito geral. Tudo o que você precisa fazer é especificar o e a implementação restante já foi feita. Você pode fazer algumas acelerações em cima disso.$(g_i g_j)^{m_{ij}} = 1$$m_{ij}$

$m_{ij}$ é realmente fácil de calcular devido às propriedades de localidade dos portões. Se os portões estiverem no máximo , o cálculo de poderá ser feito em um espaço Hilbert bidimensional de . Isso ocorre porque se os índices não se sobrepõem, então você sabe que . é para quando e comutarem. Você também precisa calcular menos da metade das entradas. Isso ocorre porque a matriz é simétrica, possui na diagonal ( ). Além disso, a maioria das entradas está apenas renomeando os qubits envolvidos; portanto, se você souber a ordem de$k$$m_{ij}$$2^{2k-1}$$m_{ij}=2$$m_{ij}=2$$g_i$$g_j$$m_{ij}$$1$$(g_i g_i)^1 = 1$$(\operatorname{CNOT}_{12} H_1)$ , você conhece a ordem do sem fazer o cálculo novamente.$\operatorname{CNOT}_{37} H_3$

Isso cuidava de todas as relações que envolviam apenas dois portões distintos (prova: exercício). As relações que envolveram ou mais foram descartadas. Agora, nós os colocamos de volta. Digamos que temos isso, para que possamos executar o algoritmo ganancioso de Dehn usando novas relações. Se houve uma mudança, ligamos de volta para percorrer o grupo Coxeter novamente. Isso se repete até que não haja alterações.$3$

Toda vez que a palavra está diminuindo ou mantendo o mesmo comprimento, estamos usando apenas algoritmos com comportamento linear ou quadrático. Este é um procedimento bastante barato, então é melhor fazê-lo e garantir que você não tenha feito nada estúpido.

Se você mesmo quiser testar, forneça o número de geradores como , o comprimento da palavra aleatória que você está tentando experimentar e a matriz de Coxeter como .$N$$K$$m$

edge_list=[]
for i1 in range(N):
    for j1 in range(i):
        edge_list.append((j1+1,i1+1,m[i1,j1]))
G3 = Graph(edge_list)
W3 = CoxeterGroup(G3)
s3 = W3.simple_reflections()
word=[choice(list([1,..,N])) for k in range(K)]
print(word)
wTesting=s3[word[0]]
for o in word[1:]:
    wTesting=wTesting*s3[o]
word=wTesting.coset_representative([]).reduced_word()
print(word)

Um exemplo com N=28e K=20, as duas primeiras linhas são a palavra não reduzida de entrada, as duas seguintes são a palavra reduzida. Espero não ter digitado um erro ao entrar na matriz .$m$

[26, 10, 13, 16, 15, 16, 20, 22, 21, 25, 11, 22, 25, 13, 8, 20, 19, 19, 14, 28]

['CNOT_23', 'Y_1', 'Y_4', 'Z_2', 'Z_1', 'Z_2', 'H_1', 'H_3', 'H_2', 'CNOT_12', 'Y_2', 'H_3', 'CNOT_12', 'Y_4', 'X_4', 'H_1', 'Z_5', 'Z_5', 'Y_5', 'CNOT_45']

[14, 8, 28, 26, 21, 10, 15, 20, 25, 11, 25, 20]

['Y_5', 'X_4', 'CNOT_45', 'CNOT_23', 'H_2', 'Y_1', 'Z_1', 'H_1', 'CNOT_12', 'Y_2', 'CNOT_12', 'H_1']

esses geradores como , apenas recolocamos relações como e que comuta com portões que não envolvem o qubit . Isso nos permite fazer a decomposição antes de ter o maior tempo possível. Queremos evitar situações como . (No Cliff + T, geralmente se busca minimizar a contagem de T). Para esta parte, o gráfico acíclico direcionado mostrando a dependência é crucial. Esse é um problema de encontrar um bom tipo topológico do DAG. Isso é feito alterando a precedência quando se pode escolher qual vértice usar a seguir. (Eu não perderia tempo otimizando muito essa parte.)$T_i$$T_i^n = 1$$T_i$$i$$w_1 g_{i_1} w_2 g_{i_2} \cdots w_k$$w_i$$X_1 T_2 X_1 T_2 X_1 T_2 X_1$

Se a palavra já estiver próxima do tamanho ideal, não há muito o que fazer e esse procedimento não ajudará. Mas, como o exemplo mais básico do que ele encontra, se você tiver várias unidades e esquecer que havia um no final de uma e um no início da próxima, ele se livrará desse par. Isso significa que você pode colocar rotinas comuns de caixa preta com mais confiança de que, quando reuni-las, todos os cancelamentos óbvios serão resolvidos. Faz outros que não são tão óbvios; aqueles que usam quando .$H_i$$H_i$$m_{ij} \neq 1,2$

Usando o procedimento descrito em https://arxiv.org/abs/quant-ph/0303063 ¹ , qualquer porta diagonal - qualquer uma em particular a porta CCCZ - pode ser decomposta em termos de, por exemplo, CNOTs e portas diagonais de um qubit, onde os CNOTs podem ser otimizados por conta própria, seguindo um procedimento clássico de otimização.

A referência fornece um circuito usando 16 CNOTs para portas diagonais arbitrárias de 4 qubit (Fig. 4).

Observação: Embora possa, em princípio, haver um circuito mais simples (o referido circuito foi otimizado com uma arquitetura de circuitos mais restrita), ele deve estar próximo do ideal - o circuito precisa criar todos os estados da forma para qualquer subconjunto não trivial , e há 15 deles para 4 qubits.$\bigoplus_{i\in I}x_i$$I\subset\{1,2,3,4\}$

Observe também que essa construção de forma alguma precisa ser ideal.

^{1 Nota: sou um autor}