O algoritmo de Deutsch-Jozsa

Para este módulo do Qiskit in Classrooms, os estudantes precisam ter um ambiente Python funcional com os seguintes pacotes instalados:

• qiskit v2.1.0 ou mais recente
• qiskit-ibm-runtime v0.40.1 ou mais recente
• qiskit-aer v0.17.0 ou mais recente
• qiskit.visualization
• numpy
• pylatexenc

Para configurar e instalar os pacotes acima, consulte o guia Instalar o Qiskit. Para executar jobs em computadores quânticos reais, os estudantes precisarão criar uma conta no IBM Quantum® seguindo os passos descritos no guia Configure sua conta IBM Cloud.

Este módulo foi testado e utilizou quatro segundos de tempo de QPU. Isso é apenas uma estimativa. Seu uso real pode variar.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Assista ao guia do módulo com a Dra. Katie McCormick abaixo, ou clique aqui para assisti-lo no YouTube.

---

Introdução

No início dos anos 1980, físicos quânticos e cientistas da computação tinham uma noção vaga de que a mecânica quântica poderia ser aproveitada para realizar computações muito mais poderosas do que os computadores clássicos conseguem fazer. O raciocínio deles era o seguinte: é difícil para um computador clássico simular sistemas quânticos, mas um computador quântico deveria conseguir fazer isso de forma mais eficiente. E se um computador quântico pudesse simular sistemas quânticos com mais eficiência, talvez houvesse outras tarefas que ele pudesse executar de forma mais eficiente do que um computador clássico.

A lógica era sólida, mas os detalhes ainda precisavam ser elaborados. Isso começou em 1985, quando David Deutsch descreveu o primeiro "computador quântico universal." Nesse mesmo artigo, ele forneceu o primeiro exemplo de problema para o qual um computador quântico poderia resolver algo de forma mais eficiente do que um computador clássico. Esse primeiro exemplo lúdico é hoje conhecido como "algoritmo de Deutsch." A melhoria no algoritmo de Deutsch foi modesta, mas Deutsch trabalhou com Richard Jozsa alguns anos depois para ampliar ainda mais a diferença entre computadores clássicos e quânticos.

Esses algoritmos — o de Deutsch e a extensão Deutsch-Jozsa — não são particularmente úteis, mas ainda são muito importantes por algumas razões:

1. Historicamente, foram alguns dos primeiros algoritmos quânticos demonstrados a superar seus equivalentes clássicos. Compreendê-los pode nos ajudar a entender como o pensamento da comunidade sobre computação quântica evoluiu ao longo do tempo.
2. Eles podem nos ajudar a entender alguns aspectos da resposta a uma pergunta surpreendentemente sutil: O que dá poder à computação quântica? Às vezes, computadores quânticos são comparados a processadores paralelos gigantes com escala exponencial. Mas isso não está totalmente correto. Embora parte da resposta a essa pergunta esteja no chamado "paralelismo quântico," extrair o máximo de informação possível em uma única execução é uma arte sutil. Os algoritmos de Deutsch e Deutsch-Jozsa mostram como isso pode ser feito.

Neste módulo, aprenderemos sobre o algoritmo de Deutsch, o algoritmo de Deutsch-Jozsa e o que eles nos ensinam sobre o poder da computação quântica.

Paralelismo quântico e seus limites

Parte do poder da computação quântica vem do "paralelismo quântico," que é essencialmente a capacidade de realizar operações em múltiplas entradas ao mesmo tempo, já que os estados de entrada dos qubits podem estar em uma superposição de múltiplos estados classicamente permitidos. PORÉM, embora um circuito quântico possa ser capaz de avaliar múltiplos estados de entrada ao mesmo tempo, extrair toda essa informação de uma só vez é impossível.

Para entender o que quero dizer aqui, digamos que temos um bit, $x$, e alguma função aplicada a esse bit, $f(x)$. Existem quatro possíveis funções binárias que mapeiam um único bit em outro único bit:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Gostaríamos de descobrir qual dessas funções (1 a 4) é a nossa $f(x)$. Classicamente, precisaríamos executar a função duas vezes — uma para $x=0$ e outra para $x=1$. Mas vamos ver se conseguimos fazer melhor com um circuito quântico. Podemos aprender sobre a função com a seguinte porta:

Aqui, a porta $U_f$ calcula $f(x)$, onde $x$ é o estado do qubit 0, e aplica isso ao qubit 1. Portanto, o estado resultante, $|x\rangle|y\oplus f(x)\rangle$, simplesmente se torna $|x\rangle|f(x)\rangle$ quando $|y\rangle = |0\rangle$. Isso contém toda a informação que precisamos para conhecer a função $f(x)$: o qubit 0 nos diz qual é $x$, e o qubit 1 nos diz qual é $f(x)$. Então, se inicializarmos $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, o estado final de ambos os qubits será: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Mas como acessamos essa informação?

2.1. Experimente no Qiskit:

Usando o Qiskit, vamos selecionar aleatoriamente uma das quatro funções possíveis acima e executar o circuito. Em seguida, sua tarefa é usar as medições do circuito quântico para aprender a função no menor número possível de execuções.

Neste primeiro experimento e ao longo de todo o módulo, usaremos um framework para computação quântica conhecido como "padrões Qiskit" (Qiskit patterns), que divide os fluxos de trabalho nas seguintes etapas:

• Etapa 1: Mapear entradas clássicas para um problema quântico
• Etapa 2: Otimizar o problema para execução quântica
• Etapa 3: Executar usando os Primitivos do Qiskit Runtime
• Etapa 4: Pós-processamento e análise clássica

Vamos começar carregando alguns pacotes necessários, incluindo os primitivos do Qiskit Runtime. Também selecionaremos o computador quântico menos ocupado disponível para nós.

Há um código abaixo para salvar suas credenciais no primeiro uso. Certifique-se de excluir essas informações do notebook após salvá-las no seu ambiente, para que suas credenciais não sejam compartilhadas acidentalmente quando você compartilhar o notebook. Consulte Configure sua conta IBM Cloud e Inicialize o serviço em um ambiente não confiável para mais orientações.

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)

sampler = Sampler(mode=backend)

ibm_brisbane

A célula abaixo permitirá que você alterne entre o uso do simulador ou hardware real ao longo do notebook. Recomendamos executá-la agora:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

# Alternatively, load a fake backend with generic properties and define a simulator.

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)

Agora que carregamos os pacotes necessários, podemos prosseguir com o fluxo de trabalho dos padrões Qiskit. Na etapa de mapeamento abaixo, primeiro criamos uma função que seleciona entre as quatro possíveis funções que mapeiam um único bit em outro único bit.

# Step 1: Map

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)

def twobit_function(case: int):
    """
    Generate a valid two-bit function as a `QuantumCircuit`.
    """
    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

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
# blackbox = twobit_function(2).to_gate()  # you may edit the number inside "twobit_function()" to select among the four valid functions
# blackbox.label = "$U_f$"

qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()

qc.draw("mpl")

No circuito acima, a porta Hadamard "H" leva o qubit 0, que está inicialmente no estado $|0\rangle$, para o estado de superposição $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Em seguida, $U_f$ avalia a função $f(x)$ e aplica isso ao qubit 1.

Em seguida, precisamos otimizar e transpilar o circuito para ser executado no computador quântico:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

Por fim, executamos nosso circuito transpilado no computador quântico e visualizamos os resultados:

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()

# Step 4: Visualize and analyze results

## Analysis
from qiskit.visualization import plot_histogram

plot_histogram(counts)

O acima é um histograma dos nossos resultados. Dependendo do número de shots que você escolheu para executar o circuito na etapa 3 acima, você pode ver uma ou duas barras, representando os estados medidos dos dois qubits em cada shot. Como sempre no Qiskit e neste notebook, usamos a notação "little endian", o que significa que os estados dos qubits 0 a n são escritos em ordem crescente da direita para a esquerda, portanto o qubit 0 está sempre mais à direita.

Assim, como o qubit 0 estava em um estado de superposição, o circuito avaliou a função para ambos $x=0$ e $x=1$ ao mesmo tempo — algo que os computadores clássicos não conseguem fazer! Mas o problema surge quando queremos aprender sobre a função $f(x)$ — quando medimos os qubits, colapsamos seu estado. Se você selecionar "shots = 1" para executar o circuito apenas uma vez, verá apenas uma barra no histograma acima, e suas informações sobre a função estarão incompletas.

Verifique seu entendimento

Leia as perguntas abaixo, pense nas suas respostas e clique no triângulo para revelar as soluções.

Quantas vezes devemos executar o algoritmo acima para aprender a função $f(x)$? Isso é melhor do que o caso clássico? Você preferiria ter um computador clássico ou quântico para resolver esse problema?

Resposta:

Como a medição colapsará a superposição e retornará apenas um valor, precisamos executar o circuito pelo menos duas vezes para obter as duas saídas da função $f(0)$ e $f(1)$. No melhor caso, isso tem o mesmo desempenho que o caso clássico, onde calculamos $f(0)$ e $f(1)$ nas duas primeiras consultas. Mas há uma chance de precisarmos executá-lo mais de duas vezes, já que a medição final é probabilística e pode retornar o mesmo valor $f(x)$ nas duas primeiras vezes. Eu preferiria ter um computador clássico nesse caso.

Portanto, embora o paralelismo quântico possa ser poderoso quando usado da forma certa, não é correto dizer que um computador quântico funciona exatamente como um processador paralelo clássico massivo. O ato de medir colapsa os estados quânticos, então só podemos acessar uma única saída do cálculo por vez.

O algoritmo de Deutsch

Embora o paralelismo quântico por si só não nos dê vantagem sobre os computadores clássicos, podemos combiná-lo com outro fenômeno quântico, a interferência, para obter uma aceleração. O algoritmo hoje conhecido como "algoritmo de Deutsch" é o primeiro exemplo de um algoritmo que consegue isso.

O problema

Eis o problema:

Dado um bit de entrada, $x = \{0,1\}$, e uma função de entrada $f(x) = \{0,1\}$, determine se a função é balanceada ou constante. Ou seja, se for balanceada, a saída da função é 0 metade do tempo e 1 na outra metade. Se for constante, a saída da função é sempre 0 ou sempre 1. Lembre-se da tabela das quatro funções possíveis que mapeiam um único bit em outro único bit:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

A primeira e a última funções, $f_1(x)$ e $f_4(x)$, são constantes, enquanto as duas funções do meio, $f_2(x)$ e $f_3(x)$, são balanceadas.

O algoritmo

A forma como Deutsch abordou esse problema foi através do "modelo de consulta" (query model). No modelo de consulta, a função de entrada ($f_i(x)$ acima) está contida em uma "caixa preta" — não temos acesso direto ao seu conteúdo, mas podemos consultar a caixa preta e ela nos dará a saída da função. Às vezes dizemos que um "oráculo" fornece essa informação. Consulte Lição 1: Algoritmos de Consulta Quântica do curso Fundamentos de Algoritmos Quânticos para mais informações sobre o modelo de consulta.

Para determinar se um algoritmo quântico é mais eficiente do que um algoritmo clássico no modelo de consulta, podemos simplesmente comparar o número de consultas que precisamos fazer à caixa preta em cada caso. No caso clássico, para saber se a função contida na caixa preta é balanceada ou constante, precisaríamos consultar a caixa duas vezes para obter $f(0)$ e $f(1)$.

No algoritmo quântico de Deutsch, porém, ele encontrou uma forma de obter a informação com apenas uma consulta! Ele fez um ajuste no circuito de "paralelismo quântico" acima, de modo a preparar um estado de superposição em ambos os qubits, em vez de apenas no qubit 0. Então, as duas saídas da função, $f(0)$ e $f(1)$, interferiram para retornar 0 se ambas fossem 0 ou ambas fossem 1 (a função era constante), e retornaram 1 se fossem diferentes (a função era balanceada). Dessa forma, Deutsch poderia diferenciar entre uma função constante e uma balanceada com uma única consulta.

Aqui está um diagrama de circuito do algoritmo de Deutsch:

Para entender como esse algoritmo funciona, vamos analisar os estados quânticos dos qubits nos três pontos indicados no diagrama acima. Tente calcular os estados por conta própria antes de clicar para ver as respostas:

Verifique seu entendimento

Leia as perguntas abaixo, pense nas suas respostas e clique nos triângulos para revelar as soluções.

Qual é o estado $|\pi_1\rangle$?

Resposta:

Aplicar uma Hadamard transforma o estado $|0\rangle$ em $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ e o estado $|1\rangle$ em $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Portanto, o estado completo se torna: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Qual é o estado $|\pi_2\rangle$?

Resposta:

Antes de aplicar $U_f$, lembre-se do que ela faz. Ela mudará o estado do qubit 1 com base no estado do qubit 0. Portanto, faz sentido fatorar o estado do qubit 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Então, se $f(0)=f(1)$, os dois termos se transformarão da mesma forma e o sinal relativo entre os dois termos permanece positivo, mas se $f(0)\neq f(1)$, então o segundo termo adquirirá um sinal negativo em relação ao primeiro termo, mudando o estado do qubit 0 de $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ para $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Portanto:

$$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Qual é o estado $|\pi_3\rangle$?

Resposta:

Agora, o estado do qubit 0 é $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ ou $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, dependendo da função. Aplicar a Hadamard resultará em $|0\rangle$ ou $|1\rangle$, respectivamente.

$$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Analisando suas respostas para as perguntas acima, observe que algo um tanto surpreendente acontece. Embora $U_f$ não faça nada explicitamente no estado do qubit 0, porque ela muda o qubit 1 com base no estado do qubit 0, pode acontecer que isso cause uma mudança de fase no qubit 0. Isso é conhecido como o fenômeno de "phase-kickback" (retrocesso de fase), e é discutido com mais detalhes em Lição 1: Algoritmos de Consulta Quântica do curso Fundamentos de Algoritmos Quânticos.

Agora que entendemos como esse algoritmo funciona, vamos implementá-lo com o Qiskit.

## Deutsch's algorithm:

## Step 1: Map the problem

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
blackbox = twobit_function(
    3
).to_gate()  # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
blackbox.label = "$U_f$"

qc_deutsch = QuantumCircuit(2, 1)

qc_deutsch.x(1)
qc_deutsch.h(range(2))

qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()

qc_deutsch.h(0)
qc_deutsch.measure(0, 0)

qc_deutsch.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_deutsch)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)
if "1" in counts:
    print("balanced")
else:
    print("constant")

{'1': 1}
balanced

O algoritmo de Deutsch-Jozsa

O algoritmo de Deutsch foi um primeiro passo importante para demonstrar como um computador quântico pode ser mais eficiente do que um computador clássico, mas representou apenas uma melhora modesta: ele exigia apenas uma consulta, em comparação com duas no caso clássico. Em 1992, Deutsch e seu colega Richard Jozsa estenderam o algoritmo original de dois qubits para mais qubits. O problema permaneceu o mesmo: determinar se uma função é balanceada ou constante. Mas desta vez, a função vai de $n$ bits para um único bit. Ou a função retorna 0 e 1 um número igual de vezes (ela é balanceada), ou sempre retorna 1 ou sempre retorna 0 (ela é constante).

Aqui está um diagrama de circuito do algoritmo:

Este algoritmo funciona da mesma forma que o algoritmo de Deutsch: o phase-kickback permite ler o estado do qubit 0 para determinar se a função é constante ou balanceada. É um pouco mais difícil de visualizar do que no caso do algoritmo de Deutsch com dois qubits, pois os estados incluirão somas sobre os $n$ qubits — portanto, a resolução desses estados será deixada como exercício opcional para você ao final do módulo. O algoritmo retornará uma sequência de bits com todos os dígitos iguais a 0 se a função for constante, e uma sequência contendo pelo menos um 1 se a função for balanceada.

Para entender como o algoritmo funciona no Qiskit, primeiro precisamos gerar nosso oráculo: a função aleatória que tem a garantia de ser constante ou balanceada. O código abaixo gerará uma função balanceada em 50% das vezes e uma função constante nos outros 50%. Não se preocupe se você não entender completamente o código — ele é complexo e não é necessário para compreender o algoritmo quântico.

from qiskit import QuantumCircuit
import numpy as np

def dj_function(num_qubits):
    """
    Create a random Deutsch-Jozsa function.
    """

    qc_dj = QuantumCircuit(num_qubits + 1)
    if np.random.randint(0, 2):
        # Flip output qubits with 50% chance
        qc_dj.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance.
        return qc_dj

    # If the "if" statement above was "TRUE" then we've returned the constant
    # function and the function is complete. If not, we proceed in creating our
    # balanced function. Everything below is to produce the balanced function:

    # select half of all possible states at random:
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc_dj, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc_dj.x(qubit)
        return qc_dj

    for state in on_states:
        # qc_dj.barrier()  # Barriers are added to help visualize how the functions are created. They can safely be removed.
        qc_dj = add_cx(qc_dj, f"{state:0b}")
        qc_dj.mcx(list(range(num_qubits)), num_qubits)
        qc_dj = add_cx(qc_dj, f"{state:0b}")

    # qc_dj.barrier()

    return qc_dj

n = 3  # number of input qubits

oracle = dj_function(n)

display(oracle.draw("mpl"))

Esta é a função oráculo, que pode ser balanceada ou constante. Você consegue identificar, apenas olhando para o circuito, se a saída do último qubit depende dos valores inseridos nos primeiros $n$ qubits? Se a saída do último qubit depender dos primeiros $n$ qubits, você consegue dizer se essa saída dependente é balanceada ou não?

Podemos determinar se a função é balanceada ou constante observando o circuito acima, mas lembre-se: para os propósitos deste problema, tratamos essa função como uma "caixa preta". Não podemos olhar dentro da caixa para ver o diagrama do circuito. Em vez disso, precisamos consultar a caixa.

Para consultar a caixa, usamos o algoritmo de Deutsch-Jozsa e determinamos se a função é constante ou balanceada:

blackbox = oracle.to_gate()
blackbox.label = "$U_f$"

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 1: Map the problem

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_dj)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

if (
    "0" * n in counts
):  # The D-J algorithm returns all zeroes if the function was constant
    print("constant")
else:
    print("balanced")  # anything other than all zeroes means the function is balanced.

{'110': 1}
balanced

Acima, a primeira linha da saída é a sequência de bits dos resultados das medições. A segunda linha indica se a sequência de bits implica que a função foi balanceada ou constante. Se a sequência contivesse apenas zeros, a função seria constante; caso contrário, seria balanceada. Assim, com apenas uma única execução do circuito quântico acima, podemos determinar se a função é constante ou balanceada!

Verifique sua compreensão

Leia as perguntas abaixo, pense nas suas respostas e clique nos triângulos para revelar as soluções.

Quantas consultas um computador clássico precisaria para determinar com 100% de certeza se uma função é constante ou balanceada? Lembre-se: classicamente, uma única consulta permite aplicar a função a apenas uma sequência de bits.

Resposta:

Existem $2^n$ possíveis sequências de bits para verificar e, no pior caso, você precisaria testar $2^n/2+1$ delas. Por exemplo, se a função fosse constante e você continuasse medindo "1" como saída da função, não poderia ter certeza de que ela é verdadeiramente constante até verificar mais da metade dos resultados. Antes disso, você poderia simplesmente ter tido muito azar ao continuar medindo "1" em uma função balanceada. É como lançar uma moeda repetidamente e ela cair cara sempre. É improvável, mas não impossível.

Como sua resposta acima mudaria se você precisasse apenas medir até que um resultado (balanceado ou constante) fosse mais provável do que o outro? Quantas consultas seriam necessárias nesse caso?

Resposta:

Nesse caso, você poderia simplesmente medir duas vezes. Se as duas medições forem diferentes, você sabe que a função é balanceada. Se as duas medições forem iguais, ela pode ser balanceada ou constante. A probabilidade de ser balanceada com esse conjunto de medições é: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Isso é menor que 1/2, portanto é mais provável que a função seja constante nesse caso.

Portanto, o algoritmo de Deutsch-Jozsa demonstrou uma aceleração exponencial em relação a um algoritmo clássico determinístico (aquele que retorna a resposta com 100% de certeza), mas nenhuma aceleração significativa em relação a um probabilístico (aquele que retorna um resultado que provavelmente está correto).

O problema de Bernstein-Vazirani

Em 1997, Ethan Bernstein e Umesh Vazirani usaram o algoritmo de Deutsch-Jozsa para resolver um problema mais específico e restrito em comparação ao problema de Deutsch-Jozsa. Em vez de simplesmente tentar distinguir entre duas classes diferentes de funções, como no caso D-J, Bernstein e Vazirani usaram o algoritmo de Deutsch-Jozsa para realmente aprender uma sequência codificada em uma função. Aqui está o problema:

A função $f:\{0,1\}^n \rightarrow \{0,1\}$ ainda recebe uma sequência de $n$ bits e produz um único bit. Mas agora, em vez de garantir que a função é balanceada ou constante, temos a garantia de que a função é o produto escalar entre a sequência de entrada $x$ e alguma sequência secreta de $n$ bits $s$, módulo 2. (Esse produto escalar módulo 2 é chamado de "produto escalar binário".) O problema é descobrir qual é a sequência secreta de $n$ bits.

Dito de outra forma, temos uma função de caixa preta $f: {0,1}^n \rightarrow {0,1}$ que satisfaz $f(x) = s \cdot x$ para alguma sequência $s$, e queremos aprender a sequência $s$.

Vamos ver como o algoritmo D-J resolve esse problema:

1. Primeiro, uma porta Hadamard é aplicada aos $n$ qubits de entrada, e uma porta NOT seguida de uma Hadamard é aplicada ao qubit de saída, produzindo o estado:

$$|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0$$

O estado dos qubits 1 a $n$ pode ser escrito de forma mais simples como uma soma sobre todos os $2^n$ estados de base de $n$ qubits $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Chamamos o conjunto desses estados de base de $\Sigma^n$. (Veja Fundamentals of Quantum Algorithms para mais detalhes.)

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}$$

2. Em seguida, a porta $U_f$ é aplicada aos qubits. Essa porta recebe os primeiros n qubits como entrada (que agora estão em uma superposição igual de todas as possíveis sequências de n bits) e aplica a função $f(x)=s \cdot x$ ao qubit de saída, de modo que esse qubit passa ao estado: $|- \oplus f(x)\rangle$. Graças ao mecanismo de phase-kickback, o estado desse qubit permanece inalterado, mas alguns dos termos no estado do qubit de entrada adquirem um sinal negativo:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}$$

3. Agora, o próximo conjunto de portas Hadamard é aplicado aos qubits 0 a $n-1$. Acompanhar os sinais negativos nesse caso pode ser complicado. É útil saber que aplicar uma camada de Hadamards a $n$ qubits em um estado de base padrão $|x\rangle$ pode ser escrito como:

$$H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}}\sum\limits_{y \in \Sigma^n}{(-1)^{x \cdot y}|y\rangle}$$

Então o estado se torna:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}$$

4. O próximo passo é medir os primeiros $n$ bits. Mas o que vamos medir? Acontece que o estado acima se simplifica para: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, mas isso está longe de ser óbvio. Se você quiser acompanhar a matemática, consulte o curso Fundamentals of Quantum Algorithms de John Watrous. O ponto crucial, porém, é que o mecanismo de phase-kickback faz com que os qubits de entrada estejam no estado $|s\rangle$. Portanto, para descobrir qual era a sequência secreta $s$, você simplesmente precisa medir os qubits!

Verifique sua compreensão

Leia as perguntas abaixo, pense nas suas respostas e clique nos triângulos para revelar as soluções.

Verifique que o estado da Etapa 3 acima é de fato o estado $|s\rangle$ para o caso especial de $n=1$.

Resposta:

Ao escrever explicitamente as duas somatórias, você deve obter um estado com quatro termos (omitindo o estado de saída $|-\rangle$ por ora):

$$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

Se $s=0$, os dois primeiros termos se somam construtivamente e os dois últimos se cancelam, deixando $|\Psi\rangle = |0\rangle$. Se $s=1$, os dois últimos termos se somam construtivamente e os dois primeiros se cancelam, deixando $|\Psi\rangle = |1\rangle$. Portanto, em ambos os casos, $|\Psi\rangle = |s\rangle$. Esperamos que esse caso mais simples dê uma ideia de como o caso geral com $n$ qubits funciona: todos os termos que não são $|s\rangle$ interferem entre si e se cancelam, deixando apenas o estado $|s\rangle$.

Como o mesmo algoritmo pode resolver tanto o problema de Bernstein-Vazirani quanto o de Deutsch-Jozsa? Para entender isso, pense nas funções de Bernstein-Vazirani, que têm a forma $f(x) = s \cdot x$. Essas funções também são funções de Deutsch-Jozsa? Ou seja, determine se funções dessa forma satisfazem a promessa do problema de Deutsch-Jozsa: que são constantes ou balanceadas. Como isso nos ajuda a entender como o mesmo algoritmo resolve dois problemas diferentes?

Resposta:

Toda função de Bernstein-Vazirani da forma $f(x) = s \cdot x$ também satisfaz a promessa do problema de Deutsch-Jozsa: se s=00...00, então a função é constante (sempre retorna 0 para qualquer sequência x). Se s for qualquer outra sequência, a função é balanceada. Portanto, aplicar o algoritmo de Deutsch-Jozsa a uma dessas funções resolve ambos os problemas simultaneamente! Ele retorna a sequência e, se essa sequência for 00...00, sabemos que é constante; se houver pelo menos um "1" na sequência, sabemos que é balanceada.

Podemos também verificar que esse algoritmo resolve com sucesso o problema de Bernstein-Vazirani testando-o experimentalmente. Primeiro, criamos a função B-V que está dentro da caixa preta:

# Step 1: Map the problem

def bv_function(s):
    """
    Create a Bernstein-Vazirani function from a string of 1s and 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_function("1000").draw("mpl"))

string = "1000"  # secret string that we'll pretend we don't know or have access to
n = len(string)

qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))

qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

{'0000': 1}

Assim, com apenas uma única consulta, o algoritmo de Deutsch-Jozsa retornará a sequência $s$ usada na função: $f(x)=x \cdot s$, quando o aplicamos ao problema de Bernstein-Vazirani. Com um algoritmo clássico, seriam necessárias $n$ consultas para resolver o mesmo problema.

Conclusão

Esperamos que, ao examinar esses exemplos simples, tenhamos dado a você uma intuição melhor sobre como os computadores quânticos conseguem aproveitar a superposição, o entrelaçamento e a interferência para alcançar sua vantagem sobre os computadores clássicos.

O algoritmo de Deutsch-Jozsa tem enorme importância histórica por ter sido o primeiro a demonstrar qualquer aceleração em relação a um algoritmo clássico, embora tenha sido apenas uma aceleração polinomial. O algoritmo de Deutsch-Jozsa é apenas o começo da história.

Depois de usarem o algoritmo para resolver seu problema, Bernstein e Vazirani o utilizaram como base para um problema mais complexo e recursivo chamado problema de amostragem de Fourier recursiva. Sua solução ofereceu uma aceleração super-polinomial em relação aos algoritmos clássicos. E mesmo antes de Bernstein e Vazirani, Peter Shor já havia desenvolvido seu famoso algoritmo que permitia aos computadores quânticos fatorar números grandes exponencialmente mais rápido do que qualquer algoritmo clássico conseguia. Esses resultados, em conjunto, demonstraram a promessa empolgante dos futuros computadores quânticos e incentivaram físicos e engenheiros a tornar esse futuro uma realidade.

Questões

Instrutores podem solicitar versões desses cadernos com gabaritos e orientações sobre como inseri-los em currículos comuns preenchendo esta pesquisa rápida sobre como os cadernos estão sendo usados.

Conceitos fundamentais

• os algoritmos de Deutsch e Deutsch-Jozsa usam paralelismo quântico combinado com interferência para encontrar a resposta para um problema mais rapidamente do que um computador clássico consegue.
• o mecanismo de phase-kickback é um fenômeno quântico contraintuitivo que transfere operações em um qubit para a fase de outro qubit. Os algoritmos de Deutsch e Deutsch-Jozsa utilizam esse mecanismo.
• O algoritmo de Deutsch-Jozsa oferece uma aceleração polinomial em relação a qualquer algoritmo clássico determinístico.
• O algoritmo de Deutsch-Jozsa pode ser aplicado a um problema diferente, chamado de problema de Bernstein-Vazirani, para encontrar uma sequência oculta codificada em uma função.

Verdadeiro/Falso

1. V/F O algoritmo de Deutsch é um caso especial do algoritmo de Deutsch-Jozsa em que a entrada é um único qubit.
2. V/F Os algoritmos de Deutsch e Deutsch-Jozsa usam superposição e interferência quântica para alcançar sua eficiência.
3. V/F O algoritmo de Deutsch-Jozsa requer múltiplas avaliações da função para determinar se ela é constante ou balanceada.
4. V/F O "algoritmo de Bernstein-Vazirani" é na verdade o mesmo que o algoritmo de Deutsch-Jozsa, aplicado a um problema diferente.
5. V/F O algoritmo de Bernstein-Vazirani pode encontrar múltiplas sequências secretas simultaneamente.

Resposta curta

1. Quanto tempo levaria um algoritmo clássico para resolver o problema de Deutsch-Jozsa no pior caso?

2. Quanto tempo levaria um algoritmo clássico para resolver o problema de Bernstein-Vazirani? Qual aceleração o algoritmo DJ oferece nesse caso?

3. Descreva o mecanismo de phase-kickback e como ele funciona para resolver os problemas de Deutsch-Jozsa e Bernstein-Vazirani.

Problema desafio

1. O algoritmo de Deutsch-Jozsa: Lembre-se de que havia uma pergunta acima pedindo para você calcular os estados intermediários dos qubits $\pi_1$ e $\pi_2$ do algoritmo de Deutsch. Faça o mesmo para os estados intermediários de $n+1$ qubits $\pi_1$ e $\pi_2$ do algoritmo de Deutsch-Jozsa, para o caso específico de $n=2$. Em seguida, verifique que $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, novamente para o caso específico de $n=2$.