Computações clássicas em computadores quânticos

Vamos agora voltar nossa atenção para a implementação de algoritmos clássicos em computadores quânticos. Veremos que qualquer computação que pode ser realizada com um circuito booleano clássico também pode ser realizada por um circuito quântico com um custo computacional assintótico similar. Além disso, isso pode ser feito de forma "limpa", como descreveremos em breve, o que é um requisito importante para usar essas computações como sub-rotinas dentro de computações quânticas maiores.

Simulando circuitos booleanos com circuitos quânticos

Circuitos booleanos são compostos de portas AND, OR, NOT e FANOUT. Para simular circuitos booleanos com circuitos quânticos, começaremos mostrando como cada uma dessas quatro portas pode ser simulada por portas quânticas. Feito isso, converter um circuito booleano em um circuito quântico é uma simples questão de simular uma porta por vez. Precisaremos apenas de portas NOT, portas CNOT (NOT controlado) e portas de Toffoli para isso, que são operações determinísticas além de serem unitárias.

Portas de Toffoli

As portas de Toffoli podem ser descritas alternativamente como portas NOT duplamente controladas (controlled-controlled-NOT), cuja ação sobre estados da base padrão é mostrada na figura a seguir.

Tendo em mente que estamos usando a convenção de ordenação do Qiskit, onde os qubits são ordenados em ordem crescente de significância de cima para baixo, a representação matricial dessa porta é a seguinte.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Outra forma de pensar sobre as portas de Toffoli é que elas são essencialmente portas de consulta para a função AND, no sentido de que seguem o padrão visto na lição anterior para implementações unitárias de porta de consulta de funções arbitrárias com entradas e saídas em strings binárias.

As portas de Toffoli não estão incluídas no conjunto de portas padrão discutido anteriormente na lição, mas é possível construir uma porta de Toffoli a partir de portas $H,$ $T,$ $T^{\dagger}$ e CNOT da seguinte forma.

Simulando portas booleanas com portas de Toffoli, CNOT e NOT

Uma única porta de Toffoli, usada em conjunto com algumas portas NOT, pode implementar portas AND e OR, e portas FANOUT podem ser facilmente implementadas usando portas CNOT, como sugerem os diagramas a seguir.

Nos três casos, os qubits sobre os quais as portas AND, OR e FANOUT atuam chegam pela esquerda como entradas, e também precisamos de um qubit de espaço de trabalho (workspace) inicializado no estado zero para cada uma delas. Esses qubits de espaço de trabalho aparecem dentro das caixas que representam as implementações das portas para sugerir que são novos e, portanto, fazem parte do custo dessas implementações.

Para as portas AND e OR, também ficam dois qubits sobrando, além do qubit de saída. Por exemplo, dentro da caixa no diagrama que representa a simulação de uma porta AND, os dois qubits superiores ficam nos estados $\vert a\rangle$ e $\vert b\rangle.$ Esses qubits são ilustrados como permanecendo dentro das caixas porque não são mais necessários e não fazem parte da saída. Eles podem ser ignorados por ora, embora voltemos nossa atenção a eles em breve.

A porta booleana restante, a porta NOT, está incluída em nosso conjunto padrão de portas quânticas, portanto não precisamos de uma simulação para ela.

Simulação porta a porta de circuitos booleanos

Agora suponha que temos um circuito booleano ordinário chamado $C,$ composto de portas AND, OR, NOT e FANOUT, com $n$ bits de entrada e $m$ bits de saída. Seja $t = \operatorname{size}(C)$ o número de portas em $C,$ e vamos dar o nome $f$ à função que $C$ computa, que tem a forma

$$f:\Sigma^n\rightarrow\Sigma^m$$

para $\Sigma = \{0,1\}.$

Agora considere o que acontece quando percorremos uma a uma as portas AND, OR e FANOUT de $C,$ substituindo cada uma pela simulação correspondente descrita acima, incluindo a adição dos qubits de espaço de trabalho necessários. Vamos nomear o circuito resultante $R,$ e ordenar os qubits de $R$ de modo que os $n$ bits de entrada de $C$ correspondam aos $n$ qubits superiores de $R$ e os qubits de espaço de trabalho fiquem na parte inferior.

Aqui, $k$ é o número de qubits de espaço de trabalho necessários — um para cada porta AND, OR e FANOUT de $C$ — e $g$ é uma função da forma $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ que descreve os estados dos qubits restantes criados pelas simulações de porta após a execução de $R$. Na figura, os qubits correspondentes à saída $f(x)$ estão na parte superior e os qubits restantes que armazenam $g(x)$ estão na parte inferior. Podemos forçar que isso aconteça, se desejarmos, reorganizando os qubits usando portas SWAP, que podem ser implementadas com três portas CNOT desta forma:

Como veremos na próxima seção, não é realmente essencial reorganizar os qubits de saída dessa forma, mas é simples o suficiente fazê-lo se escolhermos.

A função $g$ que descreve os estados clássicos dos qubits restantes é determinada pelo circuito $C,$ mas na verdade não precisamos nos preocupar muito com ela; não nos importamos especificamente com qual estado esses qubits estão quando a computação termina. A letra $g$ vem depois de $f,$ então é um nome razoável para essa função por conta disso, mas há uma razão melhor para escolher o nome $g$ — é abreviação de lixo (garbage).

Limpando o lixo

Se nosso único interesse é avaliar a função $f$ computada por um dado circuito booleano $C$ com um circuito quântico, não precisamos ir além da simulação porta a porta recém-descrita. Isso significa que, além da saída da função, teremos uma porção de lixo sobrando.

No entanto, isso não é suficiente se quisermos realizar computações clássicas como sub-rotinas dentro de computações quânticas maiores, pois esses qubits de lixo causarão problemas. O fenômeno de interferência é de importância crítica para algoritmos quânticos, e os qubits de lixo podem arruinar os padrões de interferência necessários para que os algoritmos quânticos funcionem.

Felizmente, não é difícil limpar o lixo, por assim dizer. A chave é usar o fato de que, como $R$ é um circuito quântico, podemos executá-lo em sentido inverso, simplesmente substituindo cada porta pelo seu inverso e aplicando-as na ordem inversa, obtendo assim um circuito quântico para a operação $R^{\dagger}.$ As portas de Toffoli, CNOT e NOT são, na verdade, seus próprios inversos, então executar $R$ em sentido inverso é realmente apenas uma questão de aplicar as portas na ordem inversa — mas, de forma mais geral, qualquer circuito quântico pode ser invertido como descrito.

Especificamente, o que podemos fazer é adicionar mais $m$ qubits (lembrando que a função $f$ tem $m$ bits de saída), usar portas CNOT para copiar a saída de $R$ para esses qubits e inverter $R$ para limpar o lixo. A figura a seguir ilustra o circuito resultante e descreve sua ação sobre estados da base padrão.

Se colocarmos uma caixa em volta de todo o circuito e o chamarmos de $Q,$ ele tem esta aparência:

Dado que $C$ tem $t$ portas, o circuito $Q$ terá $O(t)$ portas.

Se desconsiderarmos os $k$ qubits adicionais de espaço de trabalho, o que temos é um circuito $Q$ que funciona exatamente como uma porta de consulta para a função $f.$ Se simplesmente quisermos calcular a função $f$ em alguma string $x,$ podemos definir $y = 0^m$ e o valor resultante $f(x)$ aparecerá nos $m$ qubits inferiores — ou podemos alimentar um estado diferente nos $m$ qubits inferiores se desejarmos (talvez para fazer uso de um phase kickback, como no algoritmo de Deutsch ou no algoritmo de Deutsch-Jozsa).

Isso significa que, para qualquer algoritmo de consulta, se tivermos um circuito booleano que computa a função de entrada, podemos substituir cada porta de consulta por uma implementação em circuito, e o algoritmo de consulta funcionará corretamente.

Observe que os qubits de espaço de trabalho são necessários para fazer esse processo funcionar, mas são devolvidos aos seus estados iniciais após a execução do circuito combinado. Isso permite que esses qubits sejam usados novamente como qubits de espaço de trabalho para outros fins. Também existem estratégias conhecidas para reduzir o número de qubits de espaço de trabalho necessários (com o custo de tornar os circuitos maiores), mas não discutiremos essas estratégias aqui.

Implementando funções invertíveis

A construção recém-descrita nos permite simular qualquer circuito booleano com um circuito quântico de forma livre de lixo. Se $C$ é um circuito booleano que implementa uma função $f:\Sigma^n \rightarrow \Sigma^m,$ obtemos um circuito quântico $Q$ que opera da seguinte forma sobre estados da base padrão.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

O número $k$ indica quantos qubits de espaço de trabalho são necessários no total. Isso é suficiente para os propósitos deste curso, mas é possível levar essa metodologia um passo adiante quando a própria função $f$ é invertível.

Para ser preciso, suponha que a função $f$ tenha a forma $f:\Sigma^n \rightarrow \Sigma^n,$ e suponha também que existe uma função $f^{-1}$ tal que $f^{-1}(f(x)) = x$ para todo $x\in\Sigma^n$ (que é necessariamente única quando existe). Isso significa que a operação que transforma $\vert x \rangle$ em $\vert f(x) \rangle$ para todo $x\in\Sigma^n$ é unitária, então podemos esperar construir um circuito quântico que implementa a operação unitária definida por

$$U \vert x \rangle = \vert f(x) \rangle$$

para todo $x\in\Sigma^n.$

Para ficar claro, o fato de que essa é uma operação unitária depende de $f$ ser invertível — não é unitária quando $f$ não é invertível. Desconsiderando os qubits de espaço de trabalho, $U$ é diferente da operação que o circuito $Q$ implementa porque não estamos mantendo uma cópia da entrada e fazendo XOR com uma string arbitrária, estamos substituindo $x$ por $f(x).$

A questão é: quando $f$ é invertível, podemos fazer isso?

A resposta é sim, desde que possamos usar qubits de espaço de trabalho e, além de ter um circuito booleano que computa $f,$ também tenhamos um que computa $f^{-1}.$ Portanto, isso não é um atalho para inverter funções computacionalmente quando ainda não sabemos como fazer isso! O diagrama a seguir ilustra como isso pode ser feito compondo dois circuitos quânticos, $Q_f$ e $Q_{f^{-1}},$ que são obtidos individualmente para as funções $f$ e $f^{-1}$ pelo método descrito acima, juntamente com $n$ portas swap, tomando $k$ como o máximo dos números de qubits de espaço de trabalho necessários por $Q_f$ e $Q_{f^{-1}}.$