O algoritmo de Deutsch-Jozsa

Para este módulo do Qiskit in Classrooms, os alunos devem ter um ambiente Python em funcionamento 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 trabalhos em computadores quânticos reais, os alunos precisarão configurar uma conta no IBM Quantum® seguindo as etapas do guia Configurar sua conta IBM Cloud.

Esse módulo foi testado e usou quatro segundos de tempo de QPU. Essa é apenas uma estimativa. Seu uso real pode variar.

# 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 passo a passo do módulo pela Dra. Katie McCormick abaixo, ou clique aqui para assisti-lo em YouTube.

Introdução

No início da década de 1980, os físicos quânticos e os cientistas da computação tinham uma vaga noção de que a mecânica quântica poderia ser aproveitada para fazer cálculos muito mais avançados do que os computadores clássicos. O raciocínio deles foi o seguinte: é difícil para um computador clássico simular sistemas quânticos, mas um computador quântico deve ser capaz de fazer isso com mais eficiência. E se um computador quântico pudesse simular sistemas quânticos com mais eficiência, talvez houvesse outras tarefas que ele pudesse realizar com mais eficiência do que um computador clássico.

A lógica era sólida, mas os detalhes ainda precisavam ser trabalhados. 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 com mais eficiência do que um computador clássico. Esse primeiro exemplo de brinquedo é hoje conhecido como "algoritmo de Deutsch" O aprimoramento do algoritmo de Deutsch foi modesto, mas Deutsch trabalhou com Richard Jozsa alguns anos depois para aumentar ainda mais a distância entre os 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 alguns motivos:

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

Neste módulo, aprenderemos sobre o algoritmo de Deutsch, o algoritmo 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 é derivada do "paralelismo quântico" que é essencialmente a capacidade de realizar operações em várias entradas ao mesmo tempo, já que os estados de entrada do qubit podem estar em uma superposição de vários estados classicamente permitidos. NO ENTANTO, embora um circuito quântico possa ser capaz de avaliar vários estados de entrada de uma só vez, é impossível extrair todas essas informações de uma só vez.

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

Gostaríamos de descobrir qual dessas funções (1-4) é a nossa $f(x)$. Classicamente, precisaríamos executar a função duas vezes - uma para $x=0$, 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)$, em que $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 todas as informações de que precisamos para conhecer a função $f(x)$ : o qubit 0 nos diz o que é $x$ e o qubit 1 nos diz o que é $f(x)$. Portanto, 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 essas informações?

2.1. Experimente no Qiskit:

Usando o Qiskit, selecionaremos aleatoriamente uma das quatro funções possíveis acima e executaremos 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 em todo o módulo, usaremos uma estrutura para computação quântica conhecida como "padrões Qiskit", 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 a execução quântica
• Etapa 3: Executar usando Qiskit Runtime Primitives
• Etapa 4: Pós-processamento e análise clássica

Vamos começar carregando alguns pacotes necessários, incluindo as primitivas 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 na primeira utilização. Certifique-se de excluir essas informações do notebook depois de salvá-lo em seu ambiente, para que suas credenciais não sejam compartilhadas acidentalmente quando você compartilhar o notebook. Consulte Configurar sua conta IBM Cloud e Inicializar o serviço em um ambiente não confiável para obter 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)

Output:

ibm_brisbane

A célula abaixo permitirá que você alterne entre usar o simulador ou o hardware real em todo o notebook. Recomendamos executá-lo 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 do Qiskit. Na etapa de mapeamento abaixo, primeiro criamos uma função que seleciona entre as quatro funções possíveis que levam um único bit a 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

# you may edit the number inside "twobit_function()" to select among the four valid functions:
# blackbox = twobit_function(2).to_gate()

# blackbox.label = "$U_f$"

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


qc.draw("mpl")

Output:

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 a aplica 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 nossos 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)

Output:

Acima está um histograma de nossos resultados. Dependendo do número de disparos que você escolheu para executar o circuito na etapa 3 acima, você poderá ver uma ou duas barras, representando os estados medidos dos dois qubits em cada disparo. Como sempre acontece com o 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, de modo que o qubit 0 é sempre o mais à direita.

Então, como o qubit 0 estava em um estado de superposição, o circuito avaliou a função para $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 "disparos = 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 sua compreensão

Quantas vezes devemos executar o algoritmo acima para aprender a função $f(x)$? Isso é melhor do que o caso clássico? Você prefere 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 retornar ambas as saídas da função $f(0)$ e $f(1)$. Na melhor das hipóteses, o desempenho é tão bom quanto o do caso clássico, em que calculamos $f(0)$ e $f(1)$ nas duas primeiras consultas. Mas há uma chance de precisarmos executá-lo mais de duas vezes, pois a medição final é probabilística e pode retornar o mesmo valor $f(x)$ nas duas primeiras vezes. Nesse caso, eu preferiria ter um computador clássico.

Portanto, embora o paralelismo quântico possa ser poderoso quando usado da maneira correta, não é correto dizer que um computador quântico funciona exatamente como um processador paralelo clássico maciço. O ato da medição colapsa os estados quânticos, de modo que só podemos acessar um único resultado da computação.

Algoritmo de Deutsch

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

O problema

Aqui estava 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 equilibrado, a saída da função será 0 na metade do tempo e 1 na outra metade do tempo. Se for constante, o resultado da função será sempre 0 ou sempre 1. Lembre-se da tabela de quatro funções possíveis que transformam um bit único em outro bit único:

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 maneira como Deutsch abordou esse problema foi por meio do "modelo de consulta" 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 fornecerá a saída da função. Às vezes, dizemos que um "oráculo" fornece essas informações. Consulte a Lição 1: Algoritmos de consulta quântica do curso Fundamentos de Algoritmos Quânticos para saber mais 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 era equilibrada 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 maneira de obter as informações com apenas uma consulta! Ele fez um ajuste no circuito de "paralelismo quântico" acima, de modo que preparou um estado de superposição em ambos os qubits, em vez de apenas no qubit 0. Em seguida, as duas saídas da função, $f(0)$ e $f(1)$, interferiram para retornar 0 se ambas fossem 0 ou 1 (a função era constante), e retornaram 1 se fossem diferentes (a função era equilibrada). Dessa forma, Deutsch poderia diferenciar entre uma função constante e uma função equilibrada com uma única consulta.

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

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

Verifique sua compreensão

O que é o estado $|\pi_1\rangle$?

• Resposta

  A aplicação de uma transformação 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}}]$

O que é o estado $|\pi_2\rangle$?

• Resposta

  Antes de aplicarmos o $U_f$, lembre-se do que ele faz. Ele 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 permanecerá positivo, mas se $f(0)\neq f(1)$, isso significa que o segundo termo receberá um sinal de menos em relação ao primeiro termo, alterando o estado do qubit 0 de $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ para $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ :

  $$|\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}$$

O que é 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. A aplicação do Hadamard produzirá $|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}$$

Ao analisar suas respostas para as perguntas acima, observe que algo surpreendente acontece. Embora o site $U_f$ não faça nada explicitamente ao estado do qubit 0, porque ele altera 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 "phase-kickback" e é discutido em mais detalhes na Lição 1: Algoritmos de consulta quântica do curso Fundamentals of Quantum Algorithms (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
    # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
).to_gate()
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")

Output:

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

Output:

{'1': 1}
balanced

O algoritmo de Deutsch-Jozsa

O algoritmo de Deutsch foi uma primeira etapa importante na demonstração de como um computador quântico pode ser mais eficiente do que um computador clássico, mas foi apenas uma melhoria modesta: exigiu apenas uma consulta, em comparação com duas no caso clássico. Em 1992, Deutsch e seu colega, Richard Jozsa, ampliaram o algoritmo original de dois qubits para mais qubits. O problema continua 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 (é equilibrada ) ou a função retorna sempre 1 ou sempre 0 (é constante ).

Aqui está um diagrama de circuito do algoritmo:

Esse algoritmo funciona da mesma forma que o algoritmo de Deutsch: o recuo de fase permite ler o estado do qubit 0 para determinar se a função é constante ou equilibrada. É um pouco mais complicado de ver do que no caso do algoritmo de Deutsch de dois qubits, já que os estados incluirão somas sobre os $n$ qubits e, portanto, o cálculo desses estados será deixado como um exercício opcional para você no final do módulo. O algoritmo retornará uma cadeia de bits com todos os 0s se a função for constante e uma cadeia de bits com pelo menos um 1 se a função for equilibrada.

Para ver 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 equilibrada. O código abaixo gerará uma função equilibrada 50% do tempo e uma função constante 50% do tempo. Não se preocupe se você não seguir totalmente o código - ele é complicado e não é necessário para nossa compreensão do 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"))

Output:

Essa é a função do oráculo, que é equilibrada ou constante. Você consegue ver se a saída no último qubit depende dos valores inseridos nos primeiros $n$ qubits? Se a saída do último qubit depender dos primeiros $n$ qubits, você pode dizer se essa saída dependente é equilibrada ou não?

Podemos dizer se a função é equilibrada ou constante observando o circuito acima, mas lembre-se de que, para este problema, pensaremos nessa função como uma "caixa preta" Não podemos entrar na caixa para ver o diagrama do circuito. Em vez disso, precisamos consultar a caixa.

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

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

Output:

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

Output:

# 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.

Output:

{'110': 1}
balanced

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

Verifique sua compreensão

Quantas consultas seriam necessárias para um computador clássico determinar com 100% de certeza se uma função é constante ou equilibrada? Lembre-se de que, classicamente, uma única consulta só permite que você aplique a função a uma única bitstring.

• Resposta

  Há $2^n$ cadeias de bits possíveis para verificar e, na pior das hipóteses, você precisaria testar $2^n/2+1$ delas. Por exemplo, se a função fosse constante e você continuasse medindo "1" como o resultado da função, não poderia ter certeza de que ela era realmente constante até verificar mais da metade dos resultados. Antes disso, você poderia ter tido muito azar de continuar medindo "1" em uma função equilibrada. É como jogar uma moeda repetidamente e ela sempre dar cara. É improvável, mas não impossível.

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

• Resposta

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

Portanto, o algoritmo Deutsch-Jozsa demonstrou um aumento exponencial de velocidade em relação a um algoritmo clássico determinístico (que retorna a resposta com 100% de certeza), mas nenhum aumento significativo de velocidade em relação a um algoritmo probabilístico (que retorna um resultado que provavelmente é a resposta correta).

O problema de Bernstein-Vazirani

Em 1997, Ethan Bernstein e Umesh Vazirani usaram o algoritmo Deutsch-Jozsa para resolver um problema mais específico e restrito em comparação com o problema 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 Deutsch-Jozsa para realmente aprender uma string codificada em uma função. O problema é o seguinte:

A função $f:\{0,1\}^n \rightarrow \{0,1\}$ ainda recebe uma cadeia de caracteres de $n$ bits e gera um único bit. Mas agora, em vez de prometer que a função é equilibrada ou constante, prometemos que a função é o produto escalar entre a string de entrada $x$ e alguma string 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 cadeia secreta de $n$ bits.

Em outras palavras, recebemos uma função de caixa preta $f: {0,1}^n \rightarrow {0,1}$ que satisfaz $f(x) = s \cdot x$ para alguma string $s$, e queremos aprender a string $s$.

Vamos dar uma olhada em como o algoritmo D-J resolve esse problema:

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

O estado dos qubits 1 a $n$ pode ser escrito de forma mais simples como uma soma de todos os $2^n$ estados da base do $n$ -qubit $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Chamamos o conjunto desses estados de base de $\Sigma^n$. (Consulte Fundamentos de Algoritmos Quânticos para obter mais detalhes)

2. Em seguida, a porta $U_f$ é aplicada aos qubits. Essa porta receberá 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 aplicará a função $f(x)=s \cdot x$ ao qubit de saída, de modo que esse qubit esteja agora no estado: $|- \oplus f(x)\rangle$. Graças ao mecanismo de retrocesso de fase, o estado desse qubit permanece inalterado, mas alguns dos termos no estado do qubit de entrada recebem um sinal de menos:

3. Agora, o próximo conjunto de Hadamards é aplicado aos qubits 0 a $n-1$. Manter o controle dos sinais de menos nesse caso pode ser complicado. É útil saber que a aplicação de uma camada de Hadamards a $n$ qubits em um estado de base padrão $|x\rangle$ pode ser escrita como:

Assim, o estado se torna:

4. A próxima etapa é medir os primeiros $n$ bits. Mas o que vamos medir? Acontece que o estado acima 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 (Fundamentos de Algoritmos Quânticos ) de John Watrous. A questão, porém, é que o mecanismo de retrocesso de fase faz com que os qubits de entrada estejam no estado $|s\rangle$. Portanto, para descobrir qual era a string secreta $s$, basta medir os qubits!

Verifique sua compreensão

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

• Resposta

  Quando você escreve explicitamente as duas somas, deve obter um estado com quatro termos (vamos omitir o estado de saída $|-\rangle$ para isso):

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

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

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

• Resposta

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

Também podemos verificar se esse algoritmo resolve com sucesso o problema de Bernstein-Vazirani testando-o experimentalmente. Primeiro, criamos a função B-V que fica 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"))

Output:

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

Output:

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

Output:

{'0000': 1}

Portanto, com uma única consulta, o algoritmo Deutsch-Jozsa retornará a string $s$ usada na função: $f(x)=x \cdot s$ quando a aplicarmos ao problema 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 lhe dado uma melhor intuição de como os computadores quânticos são capazes de aproveitar a superposição, o emaranhamento e a interferência para alcançar seu poder sobre os computadores clássicos.

O algoritmo Deutsch-Jozsa tem grande importância histórica porque foi o primeiro a demonstrar qualquer aumento de velocidade em relação a um algoritmo clássico, mas foi apenas um aumento de velocidade polinomial. O algoritmo Deutsch-Jozsa é apenas o começo da história.

Depois de usar o algoritmo para resolver seu problema, Bernstein e Vazirani usaram-no como base para um problema recursivo mais complicado, chamado de problema de amostragem recursiva de Fourier. Sua solução ofereceu uma velocidade superpolinomial em relação aos algoritmos clássicos. E mesmo antes de Bernstein e Vazirani, Peter Shor já havia criado seu famoso algoritmo que permitiu aos computadores quânticos fatorar grandes números exponencialmente mais rápido do que qualquer algoritmo clássico. Esses resultados, em conjunto, mostraram a empolgante promessa do futuro computador quântico e estimularam físicos e engenheiros a tornar esse futuro uma realidade.

Perguntas

Os instrutores podem solicitar versões desses cadernos com chaves de resposta e orientação sobre a colocação em currículos comuns preenchendo esta pesquisa rápida sobre como os cadernos estão sendo usados.

Conceitos críticos

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

True/false

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

Resposta curta

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

2. Quanto tempo um algoritmo clássico levaria para resolver o problema de Bernstein-Vazirani? Qual é o aumento de velocidade que o algoritmo DJ oferece nesse caso?

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

Problema desafiador

1. O algoritmo Deutsch-Jozsa: Lembre-se de que você fez uma pergunta acima pedindo para 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 do $n+1$ -qubit $\pi_1$, e $\pi_2$ do algoritmo Deutsch-Jozsa, para o caso específico de $n=2$. Em seguida, verifique se $\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$.