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 mais preciso, a entrada é representada por uma função $f:\Sigma \rightarrow \Sigma$ de um bit para um bit. Há quatro funções desse tipo:

A primeira e a última dessas funções são constantes e as duas do meio são equilibradas, o que significa que os dois valores de saída possíveis para a função ocorrem o mesmo número de vezes à medida que percorremos as entradas. O problema de Deutsch é determinar a qual dessas duas categorias a função de entrada pertence: constante ou equilibrada.

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

Quando visto dessa forma, o problema de Deutsch é calcular a paridade (ou, de forma equivalente, o OU exclusivo) dos dois bits.

Todo algoritmo de consulta clássico que resolve corretamente esse problema deve consultar ambos os bits: $f(0)$ e $f(1).$ Se soubermos que $f(1) = 1,$, por exemplo, a resposta ainda poderá ser $0$ ou $1,$, dependendo de $f(0) = 1$ ou $f(0) = 0,$, respectivamente. Todos os outros casos são semelhantes; conhecer apenas um dos dois bits não fornece nenhuma informação sobre sua paridade. 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, proporcionando, portanto, uma vantagem quantificável da computação quântica em relação à clássica. Essa pode ser uma vantagem modesta - uma consulta em vez de duas - mas temos que começar por algum lugar. Os avanços científicos às vezes têm origens aparentemente humildes.

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

Análise

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

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

(Como sempre, estamos seguindo a convenção de ordenação de qubits do Qiskit, que coloca o qubit superior à direita e o qubit inferior à esquerda) Pode parecer pouco intuitivo escrever esse estado de produto parcialmente distribuído (deixando os estados do qubit 1 sem fatoração), mas isso tornará nossas expressões posteriores mais compactas.

Em seguida, a porta $U_f$ é executada. De acordo com a definição da porta $U_f$, o valor da função $f$ para o estado clássico do qubit superior/direito é XORed no qubit inferior/esquerdo, o que transforma $\vert \pi_1\rangle$ no estado

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

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

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

Algo interessante acabou de acontecer! Embora a ação da porta $U_f$ nos estados de base padrão deixe o qubit superior/direito sozinho e faça o XOR do valor da função no qubit inferior/mais à esquerda, aqui vemos que o estado do qubit superior/direito mudou (em geral) enquanto o estado do qubit inferior/mais à esquerda permanece o mesmo - especificamente no estado $\vert - \rangle$ antes e depois da execução da porta $U_f$. Esse fenômeno é conhecido como retorno de fase, e teremos mais informações sobre ele em breve.

Com uma simplificação final, que é puxar o fator de $(-1)^{f(0)}$ para fora da soma, obtemos essa expressão do estado $\vert\pi_2\rangle$ :

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

A aplicação da porta Hadamard final ao qubit superior nos deixa com o estado

o que leva ao resultado correto com probabilidade $1$ quando o qubit direito/mais alto é medido.

Observações adicionais sobre o recuo de fase

Antes de prosseguir, vamos examinar a análise acima de um ângulo ligeiramente diferente que pode esclarecer o fenômeno do recuo de fase.

Primeiro, observe que a fórmula a seguir funciona para todas as opções de bits $b,c\in\Sigma.$

Isso pode ser verificado verificando-o para os dois valores possíveis $c = 0$ e $c = 1$ :

Usando essa fórmula, vemos que

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

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

O segredo para que isso funcione é que $X\vert - \rangle = - \vert - \rangle.$ Em termos matemáticos, o vetor $\vert - \rangle$ é um vetor próprio da matriz $X$ com valor próprio $-1.$

Discutiremos os vetores próprios e os valores próprios com mais detalhes na próxima lição sobre Estimativa de fase e fatoração, em que o fenômeno de retrocesso de fase é generalizado para outras operações unitárias.

Tendo em mente que os escalares flutuam livremente por meio de produtos tensoriais, encontramos uma maneira alternativa de raciocinar como a operação $U_f$ transforma $\vert \pi_1\rangle$ em $\vert \pi_2\rangle$ na análise acima:

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 apenas para essa implementação. Para as implementações de outros algoritmos a seguir, realizaremos as importações necessárias separadamente para aumentar a modularidade.

from qiskit import __version__

print(__version__)

Output:

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 uma parte do algoritmo de Deutsch em si; aqui, essencialmente, estamos apenas mostrando uma maneira de preparar a entrada, na forma de uma implementação de 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 ver a aparência de cada circuito usando o método draw . Aqui está o circuito para a função $f_3.$

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

Output:

Em seguida, criaremos o circuito quântico real para o algoritmo de Deutsch, substituindo a porta de consulta por uma implementação de circuito quântico fornecida como argumento. Em breve, conectaremos um dos quatro circuitos definidos pela função deutsch_function que definimos anteriormente. As 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 a aparência do circuito usando o método draw .

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

Output:

Por fim, criaremos uma função que executa o circuito definido anteriormente uma vez e produz o resultado apropriado: "constante" ou "balanceado"

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))

Output:

'balanced'