Algoritmo de Deutsch

O algoritmo de Deutsch resolve o problema de paridade para o caso especial em que $n = 1$. No contexto da computação quântica, esse problema é às vezes chamado de problema de Deutsch, e seguiremos essa nomenclatura nesta lição.

Para ser preciso, a entrada é representada por uma função $f:\Sigma \rightarrow \Sigma$ de um bit para um bit. Existem quatro funções desse tipo:

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

A primeira e a última dessas funções são constantes, e as duas do meio são balanceadas, o que significa que os dois possíveis valores de saída da função ocorrem o mesmo número de vezes conforme variamos as entradas. O problema de Deutsch consiste em determinar a qual dessas duas categorias a função de entrada pertence: constante ou balanceada.

Problema de Deutsch

Entrada: uma função $f:\{0,1\}\rightarrow\{0,1\}$
Saída: $0$ se $f$ é constante, $1$ se $f$ é balanceada

Se interpretarmos a função de entrada $f$ no problema de Deutsch como representando acesso aleatório a uma string, estamos pensando em uma string de dois bits: $f(0)f(1).$

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

Visto dessa forma, o problema de Deutsch consiste em calcular a paridade (ou, equivalentemente, o OU-exclusivo) dos dois bits.

Todo algoritmo de consulta clássico que resolve corretamente esse problema precisa consultar os dois bits: $f(0)$ e $f(1).$ Se soubermos que $f(1) = 1,$ por exemplo, a resposta ainda pode ser $0$ ou $1$, dependendo se $f(0) = 1$ ou $f(0) = 0$, respectivamente. Os demais casos são análogos; conhecer apenas um dos dois bits não fornece nenhuma informação sobre a paridade deles. Portanto, o circuito booleano descrito na seção anterior é o melhor que podemos fazer em termos do número de consultas necessárias para resolver esse problema.

Descrição do circuito quântico

O algoritmo de Deutsch resolve o problema de Deutsch usando uma única consulta, fornecendo assim uma vantagem quantificável da computação quântica sobre a clássica. Essa pode ser uma vantagem modesta — uma consulta em vez de duas — mas precisamos começar em algum lugar. Avanços científicos às vezes têm origens aparentemente modestas.

Aqui está um circuito quântico que descreve o algoritmo de Deutsch:

Análise

Para analisar o algoritmo de Deutsch, vamos percorrer a ação do circuito acima e identificar os estados dos qubits nos momentos sugeridos por esta figura:

O estado inicial é $\vert 1\rangle \vert 0 \rangle$, e as duas operações de Hadamard no lado esquerdo do circuito transformam esse estado em

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(Como sempre, seguimos a convenção de ordenação de qubits do Qiskit, que coloca o qubit do topo à direita e o qubit de baixo à esquerda.) Pode parecer pouco intuitivo escrever esse estado de produto parcialmente distribuído (deixando os estados do qubit 1 em evidência), mas isso tornará nossas expressões posteriores mais compactas.

Em seguida, a porta $U_f$ é aplicada. De acordo com a definição da porta $U_f$, o valor da função $f$ para o estado clássico do qubit do topo/mais à direita é aplicado via XOR no qubit de baixo/mais à esquerda, o que transforma $\vert \pi_1\rangle$ no estado

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

Podemos simplificar essa expressão observando que a fórmula

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

é válida para ambos os possíveis valores $a\in\Sigma$. De forma mais explícita, os dois casos são os seguintes.

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

Assim, podemos expressar $\vert\pi_2\rangle$ alternativamente da seguinte forma:

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Algo interessante acabou de acontecer! Embora a ação da porta $U_f$ sobre estados da base padrão deixe o qubit do topo/mais à direita intacto e aplique o XOR do valor da função no qubit de baixo/mais à esquerda, aqui vemos que o estado do qubit do topo/mais à direita mudou (em geral), enquanto o estado do qubit de baixo/mais à esquerda permanece o mesmo — especificamente no estado $\vert - \rangle$ antes e depois da aplicação da porta $U_f$. Esse fenômeno é conhecido como phase kickback (retrocesso de fase), e falaremos mais sobre ele em breve.

Com uma simplificação final, que consiste em extrair o fator $(-1)^{f(0)}$ para fora da soma, obtemos esta expressão para o estado $\vert\pi_2\rangle$:

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{se $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{se $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Observe que nessa expressão temos $f(0) \oplus f(1)$ no expoente de $-1$, em vez de $f(1) - f(0)$, que seria o esperado de um ponto de vista puramente algébrico, mas obtemos o mesmo resultado de qualquer forma. Isso ocorre porque o valor $(-1)^k$ para qualquer inteiro $k$ depende apenas de $k$ ser par ou ímpar.

Aplicando a porta de Hadamard final ao qubit do topo, chegamos ao estado

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{se $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{se $f(0) \oplus f(1) = 1$}, \end{cases}$$

o que leva ao resultado correto com probabilidade $1$ quando o qubit mais à direita/topo é medido.

Observações adicionais sobre o phase kickback

Antes de prosseguir, vamos analisar a discussão acima sob um ângulo ligeiramente diferente, o que pode lançar alguma luz sobre o fenômeno do phase kickback.

Primeiro, observe que a seguinte fórmula é válida para todas as escolhas de bits $b,c\in\Sigma$.

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

Isso pode ser verificado checando os dois possíveis valores $c = 0$ e $c = 1$:

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

Usando essa fórmula, vemos que

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

para toda escolha de bits $a,b\in\Sigma$. Como essa fórmula é verdadeira para $b=0$ e $b=1$, vemos por linearidade que

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

para todos os vetores de estado de qubit $\vert \psi\rangle$, e portanto

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

A chave que faz isso funcionar é que $X\vert - \rangle = - \vert - \rangle$. Em termos matemáticos, o vetor $\vert - \rangle$ é um autovetor da matriz $X$ com autovalor $-1$.

Discutiremos autovetores e autovalores com mais detalhes na próxima lição sobre Estimativa de fase e fatoração, onde o fenômeno do phase kickback é generalizado para outras operações unitárias.

Lembrando que escalares se propagam livremente pelos produtos tensoriais, encontramos uma forma alternativa de raciocinar sobre como a operação $U_f$ transforma $\vert \pi_1\rangle$ em $\vert \pi_2\rangle$ na análise acima:

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Implementação no Qiskit

Agora vamos ver como podemos implementar o algoritmo de Deutsch no Qiskit. Começaremos com uma verificação de versão e em seguida faremos as importações necessárias exclusivamente para esta implementação. Para as implementações de outros algoritmos que se seguem, faremos as importações necessárias separadamente em prol de maior modularidade.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"qiskit": "qiskit", "qiskit_aer": "qiskit-aer"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

Primeiro definiremos um circuito quântico que implementa uma porta de consulta para uma das quatro funções $f_1,$ $f_2,$ $f_3,$ ou $f_4$ de um bit para um bit descritas anteriormente. Como já mencionamos, a implementação de portas de consulta não é realmente parte do próprio algoritmo de Deutsch; aqui estamos essencialmente mostrando uma maneira de preparar a entrada, na forma de uma implementação em circuito de uma porta de consulta.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

Podemos visualizar cada circuito usando o método draw. Aqui está o circuito para a função $f_3$.

display(deutsch_function(3).draw(output="mpl"))

Em seguida, criaremos o circuito quântico real para o algoritmo de Deutsch, substituindo a porta de consulta por uma implementação em circuito quântico fornecida como argumento. Em breve, vamos conectar um dos quatro circuitos definidos pela função deutsch_function que definimos anteriormente. Barreiras são incluídas para mostrar a separação visual entre a implementação da porta de consulta e o restante do circuito.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

Novamente podemos ver como o circuito se parece usando o método draw.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

Por fim, criaremos uma função que executa o circuito definido anteriormente uma única vez e retorna o resultado apropriado: "constant" ou "balanced."

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

Agora podemos executar o algoritmo de Deutsch em qualquer uma das quatro funções definidas acima.

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'