Problema de Deutsch — Teoria

Sobre o problema de Deutsch, já foi feita uma simulação no Qiskit e até uma menção no filme Vingadores: Ultimato. Só faltou a teoria, que será detalhada a seguir.

O circuito tem a finalidade de descobrir se uma função desconhecida é constante ou balanceada, com uma chamada à caixa-preta (Uf).

Vamos descrever as fórmulas do modelo, e mostrar como a interferência age para chegar ao resultado.

As duas entradas recebem, respectivamente, |0> e |1>, e é aplicada uma porta Hadamard em cada:

|0> -> (Hadamard) -> (|0> + |1>) / sqrt(2) |1> -> (Hadamard) -> (|0> - |1>) / sqrt(2)

Lembrando que a matriz de estados da porta Hadamard é:

Portanto, logo antes de entrar na caixa-preta Uf, os qubits estão no estado sobreposto:

Lembrando que a caixa-preta vai fazer a operação |x, (f(x) + y) mod 2>.

A caixa-preta pode ter 4 funções possíveis, após a operação da caixa-preta:

Caso 1. Se f(x) = 0, resulta em:

Caso 2. Se f(0) = 0 e f(1) = 1, resulta em:

Caso 3. Se f(0) = 1 e f(1) = 0, resulta em:

Caso 4. Se f(x) = 1, resulta em:

A seguir, logo depois da caixa-preta, deve-se aplicar a porta Hadamard só no primeiro qubit. Ou seja, H produto direto I

Se H = [[1 1], [1 -1]] /sqrt(2) e I = [[1 0],[0, 1]], o produto direto é:

Caso 1. (|00> - |01> + |10> - |11>) / 2 é equivalente a [1 -1 1 -1]/2

Vezes a matriz de estados acima, resulta em [1 -1 0 0] /sqrt(2)

Ou seja, (|00> - |01>) / sqrt(2)

Portanto, o primeiro qubit sempre será zero.

Caso 2. (|00> - |01> + |11> - |10>) / 2 é equivalente a [1 -1 -1 1]/2

Vezes a matriz de estados acima, resulta em [0 0 1 -1] /sqrt(2)

Ou seja, (|10> - |11>) / sqrt(2)

Portanto, o primeiro qubit sempre será um.

Caso 3. (|01> - |00> + |10> - |11>) / 2 é equivalente a [-1 1 1 -1]/2

Vezes a matriz de estados acima, resulta em [0 0 -1 1] /sqrt(2)

Ou seja, (-|10> + |11>) / sqrt(2)

Portanto, o primeiro qubit sempre será um.

Caso 4. (|01> - |00> + |11> - |10>) / 2 é equivalente a [-1 1 -1 1]/2

Vezes a matriz de estados acima, resulta em [-1 1 0 0] /sqrt(2)

Ou seja, (-|00> + |01>) / sqrt(2)

Portanto, o primeiro qubit sempre será zero.

Se a função é constante, o primeiro qubit será zero. Se a função é balanceada, o primeiro qubit será 1. Isto conversa com os resultados do experimento no qiskit.

Porém, é muita conta e pouca interpretação. Vamos tentar visualizar o que acontece, fazendo superposições.

Se eu entro |0> numa porta Hadamard, o resultado é (|0> + |1>) / sqrt(2), como já apontado anteriormente. Podemos representar graficamente:

Se eu entro |1> numa porta Hadamard, o resultado é (|0> — |1>) / sqrt(2). Podemos representar graficamente:

Vamos utilizar esta notação para analisar o caso 1.

(|00> — |01> + |10> — |11>) / 2 é equivalente a [1 -1 1 -1]/2

Podemos interpretar como a soma de cada componente:

Se aplicarmos a porta Hadamard no primeiro qubit de cada, temos o mapa a seguir. Note que agora são dois qubits. A regra é aplicar o Hadamard no primeiro, e deixar o segundo inalterado.

Note que, para |00> e |01>, ocorreu uma interferência positiva. Para os demais, os valores se anularam, interferência negativa.

Note também que o diagrama mostra as amplitudes, não a probabilidade. Para achar a probabilidade do resultado, aplicar a regra de Born (elevar ao quadrado).

Outro detalhe. Em geral, os qubits são números complexos, o que necessitaria da esfera de Bloch para representação. Porém, como aqui só temos situações simples, é mais fácil enxergar resultados deste modo.

Resultado para o caso 1:

Analogamente, caso 2:

Caso 3:

Caso 4:

Conclusão: o problema de Deutsch é o mais simples algoritmo quântico. Este não tem utilidade prática alguma, e sequer apresenta uma “vantagem quântica”, por ser simulável classicamente. Porém, mesmo assim, a resolução deste introduz uma série de conceitos interessantes, que serão utilizados em algoritmos mais avançados.

Veja também:

Originally published at http://informacaoquantica.wordpress.com on April 28, 2020.

Project Manager on Analytics and Innovation. “Samurai of Analytics”. Passionate about Combinatorial Optimization, Philosophy and Quantum Computing.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store