Algoritmo de Grover

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 12 segundos de tempo de QPU. Essa é uma estimativa de boa-fé; 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'

Introdução

O algoritmo de Grover é um algoritmo quântico fundamental que aborda o problema de pesquisa não estruturada : dado um conjunto de $N$ itens e uma maneira de verificar se um determinado item é o que você está procurando, com que rapidez você pode encontrar o item desejado? Na computação clássica, se os dados não estiverem classificados e não houver estrutura a ser explorada, a melhor abordagem é verificar cada item um a um, o que leva a uma complexidade de consulta de $O(N)$ - em média, você precisará verificar cerca de metade dos itens antes de encontrar o destino.

O algoritmo de Grover, apresentado por Lov Grover em 1996, demonstra como um computador quântico pode resolver esse problema com muito mais eficiência, exigindo apenas $O(\sqrt{N})$ etapas para encontrar o item marcado com alta probabilidade. Isso representa uma aceleração quadrática em relação aos métodos clássicos, o que é significativo para grandes conjuntos de dados.

O algoritmo opera no seguinte contexto:

• Configuração do problema: Você tem uma função $f(x)$ que retorna 1 se $x$ for o item desejado e 0 caso contrário. Essa função é frequentemente chamada de oráculo ou caixa preta, pois você só pode saber sobre os dados consultando $f(x)$.
• Utilidade do quantum: Embora os algoritmos clássicos para esse problema exijam, em média, $N/2$ consultas, o algoritmo de Grover pode encontrar a solução em aproximadamente $\pi\sqrt{N}/4$ consultas, o que é muito mais rápido para $N$ grandes.
• Como funciona (em um nível elevado):
  • O computador quântico cria primeiro uma superposição de todos os estados possíveis, representando todos os itens possíveis de uma só vez.
  • Em seguida, ele aplica repetidamente uma sequência de operações quânticas (a iteração de Grover) que amplia a probabilidade da resposta correta e diminui as outras.
  • Após iterações suficientes, a medição do estado quântico produz a resposta correta com alta probabilidade.

Aqui está um diagrama muito básico do algoritmo de Grover que ignora muitas nuances. Para obter um diagrama mais detalhado, consulte este documento.

Alguns aspectos a serem observados sobre o algoritmo de Grover:

• É ideal para pesquisas não estruturadas: nenhum algoritmo quântico pode resolver o problema com menos de $O(\sqrt{N})$ consultas.
• Ele fornece apenas um aumento de velocidade quadrático, não exponencial, ao contrário de alguns outros algoritmos quânticos (por exemplo, o algoritmo de Shor para fatoração).
• Isso tem implicações práticas, como a possível aceleração de ataques de força bruta em sistemas criptográficos, embora a aceleração não seja suficiente para quebrar a maioria das criptografias modernas por si só.

Para alunos de graduação familiarizados com conceitos básicos de computação e modelos de consulta, o algoritmo de Grover oferece uma ilustração clara de como a computação quântica pode superar as abordagens clássicas para determinados problemas, mesmo quando a melhoria é "apenas" quadrática. Ele também serve como uma porta de entrada para a compreensão de algoritmos quânticos mais avançados e do potencial mais amplo da computação quântica.

A amplificação de amplitude é um algoritmo quântico de uso geral, ou sub-rotina, que pode ser usado para obter um aumento de velocidade quadrático em relação a vários algoritmos clássicos. O algoritmo de Grover foi o primeiro a demonstrar esse aumento de velocidade em problemas de pesquisa não estruturados. A formulação de um problema de pesquisa de Grover requer uma função de oráculo que marque um ou mais estados da base computacional como os estados que estamos interessados em encontrar e um circuito de amplificação que aumente a amplitude dos estados marcados, suprimindo, consequentemente, os estados restantes.

Aqui, demonstramos como construir oráculos de Grover e usar o site GroverOperator da biblioteca de circuitos Qiskit para configurar facilmente uma instância de pesquisa de Grover. A primitiva de tempo de execução Sampler permite a execução contínua dos circuitos Grover.

teoria

Suponha que exista uma função $f$ que mapeie strings binárias em uma única variável binária, ou seja

Um exemplo definido em $\Sigma^6$ é

Outro exemplo definido em $\Sigma^{2n}$ é

Você tem a tarefa de encontrar estados quânticos correspondentes aos argumentos $x$ de $f(x)$ que são mapeados para 1. Em outras palavras, encontre todos os $\{x_1\}\in \Sigma^n$ de forma que $f(x_1)=1$ (ou, se não houver solução, informe isso). Nós nos referiríamos às não soluções como $x_0$. É claro que faremos isso em um computador quântico, usando estados quânticos, portanto, é útil expressar essas cadeias binárias como estados:

Usando a notação de estado quântico (Dirac), estamos procurando um ou mais estados especiais $\{|x_1\rangle\}$ em um conjunto de $N=2^n$ estados possíveis, em que $n$ é o número de qubits, e com não soluções denotadas $\{|x_0\rangle\}.$

Podemos pensar na função $f$ como sendo fornecida por um oráculo: uma caixa-preta que podemos consultar para determinar seu efeito em um estado $|x\rangle.$. Na prática, geralmente conhecemos a função, mas sua implementação pode ser muito complicada, o que significa que reduzir o número de consultas ou aplicativos de $f$ pode ser importante. Como alternativa, podemos imaginar um paradigma no qual uma pessoa está consultando um oráculo controlado por outra pessoa, de modo que não conhecemos a função do oráculo, apenas sabemos sua ação em determinados estados a partir da consulta.

Esse é um "problema de pesquisa não estruturada", pois não há nada de especial no site $f$ que nos ajude em nossa pesquisa. As saídas não são classificadas nem as soluções são conhecidas por agrupamento, e assim por diante. Considere o uso de listas telefônicas antigas, de papel, como analogia. Essa pesquisa não estruturada seria como uma varredura em busca de um determinado número, e não como uma pesquisa em uma lista alfabética de nomes.

No caso em que uma única solução é buscada, classicamente, isso requer um número de consultas que é linear em $N$. É claro que você pode encontrar uma solução na primeira tentativa, ou pode não encontrar nenhuma solução nas primeiras $N-1$ tentativas, de modo que seja necessário consultar a entrada $N^{th}$ para ver se há alguma solução. Como as funções não têm estrutura explorável, você precisará de $N/2$ palpites em média. O algoritmo de Grover requer um número de consultas ou cálculos de $f$ que se dimensiona como $\sqrt{N}.$

Esboço dos circuitos no algoritmo de Grover

Um passo a passo matemático completo do algoritmo de Grover pode ser encontrado, por exemplo, em Fundamentals of quantum algorithms, um curso de John Watrous em IBM Quantum Learning. Um tratamento condensado é fornecido em um apêndice no final deste módulo. Mas, por enquanto, analisaremos apenas a estrutura geral do circuito quântico que implementa o algoritmo de Grover.

O algoritmo de Grover pode ser dividido nos seguintes estágios:

• Preparação de uma superposição inicial (aplicação de portas Hadamard a todos os qubits)
• "Marcação" do(s) estado(s) de destino com uma inversão de fase
• Um estágio de "difusão" no qual as portas Hadamard e uma inversão de fase são aplicadas a todos os qubits.
• Possíveis repetições dos estágios de marcação e difusão para maximizar a probabilidade de medir o estado-alvo
• Medição

Em geral, a porta de marcação $Z_f$ e as camadas de difusão que consistem em $H,$ $Z_{\text{OR}},$ e $H$ são coletivamente chamadas de "operador Grover". Nesse diagrama, apenas uma única repetição do operador de Grover é mostrada.

Portas Hadamard $H$ são bem conhecidas e amplamente utilizadas na computação quântica. A porta Hadamard cria estados de superposição. Especificamente, ele é definido por

Sua operação em qualquer outro estado é definida por meio da linearidade. Em particular, uma camada de portas Hadamard nos permite ir do estado inicial com todos os qubits em $|0\rangle$ (denotado $|0\rangle^{\otimes n}$ ) para um estado em que cada qubit tem alguma probabilidade de ser medido em $|0\rangle$ ou $|1\rangle;$. Isso nos permite sondar o espaço de todos os estados possíveis de forma diferente da computação clássica.

Uma importante propriedade corolária da porta Hadamard é que a ação de uma segunda vez pode desfazer esses estados de superposição:

Isso será importante daqui a pouco.

Verifique sua compreensão

A partir da definição da porta de Hadamard, demonstre que uma segunda aplicação da porta de Hadamard desfaz essas superposições, conforme afirmado acima.

• Resposta

  Quando aplicamos X ao estado $|+\rangle$, obtemos o valor e +1 e ao estado $|-\rangle$ obtemos -1, portanto, se tivéssemos uma distribuição 50-50, obteríamos um valor de expectativa de 0.

A porta $Z_\text{OR}$ é menos comum e é definida de acordo com

Por fim, a porta $Z_f$ é definida por

Observe que o efeito disso é que $Z_f$ inverte o sinal em um estado-alvo para o qual $f(x) = 1$ e deixa os outros estados inalterados.

Em um nível muito alto e abstrato, você pode pensar nas etapas do circuito das seguintes maneiras:

• Primeira camada de Hadamard: coloca os qubits em uma superposição de todos os estados possíveis.
• $Z_f$ estado(s) de destino: marque o(s) estado(s) de destino adicionando um sinal "-" na frente. Isso não altera imediatamente as probabilidades de medição, mas muda a forma como o estado-alvo se comportará nas etapas subsequentes.
• Outra camada de Hadamard: O sinal "-" introduzido na etapa anterior mudará o sinal relativo entre alguns termos. Como as portas Hadamard transformam uma mistura de estados computacionais $(|0\rangle+|1\rangle)/\sqrt{2}$ em um estado computacional, $|0\rangle,$, e transformam $(|0\rangle-|1\rangle)/\sqrt{2}$ em $|1\rangle$, essa diferença de sinal relativa pode agora começar a desempenhar um papel em quais estados são medidos.
• Uma camada final de portas Hadamard é aplicada e, em seguida, são feitas as medições. Veremos com mais detalhes como isso funciona na próxima seção.

Exemplo

Para entender melhor como o algoritmo de Grover funciona, vamos trabalhar com um pequeno exemplo de dois qubits. Isso pode ser considerado opcional para aqueles que não se concentram em mecânica quântica e notação de Dirac. Mas para aqueles que esperam trabalhar substancialmente com computadores quânticos, ele é altamente recomendado.

Aqui está o diagrama do circuito com os estados quânticos rotulados em várias posições. Observe que, com apenas dois qubits, há somente quatro estados possíveis que podem ser medidos em qualquer circunstância: $|00\rangle$, $|01\rangle$, $|10\rangle$, e $|11\rangle$.

Vamos supor que o oráculo ( $Z_f$, desconhecido para nós) marque o estado $|01\rangle$. Trabalharemos com as ações de cada conjunto de portas quânticas, incluindo o oráculo, e veremos qual distribuição de estados possíveis aparece no momento da medição. Logo no início, temos

Usando a definição de portas Hadamard, temos

Agora o oráculo marca o estado de destino:

Observe que, nesse estado, todos os quatro resultados possíveis têm a mesma probabilidade de serem medidos. Todos eles têm um peso de magnitude $1/2,$, o que significa que cada um tem uma $|1/2|^2=1/4$ chance de ser medido. Portanto, embora o estado $|01\rangle$ esteja marcado na fase "-", isso ainda não resultou em um aumento da probabilidade de medir esse estado. Continuamos aplicando a próxima camada de portas Hadamard.

Combinando termos semelhantes, encontramos

Agora, $Z_{\text{OR}}$ inverte o sinal em todos os estados, exceto em $|00\rangle$ :

E, por fim, aplicamos a última camada de portas Hadamard:

Vale a pena trabalhar com a combinação desses termos para se convencer de que o resultado é de fato:

Ou seja, a probabilidade de medir $|01\rangle$ é de 100% (na ausência de ruído e erros) e a probabilidade de medir qualquer outro estado é zero.

Esse exemplo de dois qubits foi um caso especialmente limpo; o algoritmo de Grover nem sempre funcionará para produzir 100% de chance de medir o estado-alvo. Em vez disso, ele ampliará a probabilidade de medir o estado-alvo. Além disso, o operador Grover pode precisar ser repetido mais de uma vez.

Na próxima seção, colocaremos esse algoritmo em prática usando computadores quânticos IBM® reais.

A imagem geométrica

O exemplo de dois qubits acima mostrou como a álgebra funciona em um caso simples, mas há uma maneira muito mais intuitiva de compreender o algoritmo de Grover: como uma sequência de reflexões geométricas em um plano bidimensional. A seguir, descrevemos esta imagem. Você também pode consultar o curso de John Watrous, “Fundamentos de Algoritmos Quânticos”, para obter mais detalhes.

Preparando o avião. Podemos decompor o estado de superposição inicial $|\psi\rangle$ em dois componentes. O estado correto — aquele que estamos buscando — chamamos de “ $|A_1\rangle$ ”. Todos os outros estados, agrupados, chamamos de “ $|A_0\rangle$ ”. Por definição, “ $|A_1\rangle$ ” e “ $|A_0\rangle$ ” são ortogonais entre si, de modo que podemos representá-los como eixos perpendiculares em um espaço abstrato bidimensional. Como $|\psi\rangle$ é uma combinação linear desses dois componentes, ele forma um pequeno ângulo $\theta$ em relação ao eixo $|A_0\rangle$ — próximo de $|A_0\rangle$, pois, no início, apenas uma fração minúscula do estado se encontra no componente correto $|A_1\rangle$.

Reflexões. O principal fato matemático de que precisamos é que um operador da forma

reflete qualquer estado em relação ao eixo definido por $|v\rangle.$ Para entender o motivo, considere dois casos: um estado alinhado com $|v\rangle$ permanece inalterado, e um estado perpendicular a $|v\rangle$ tem seu sinal invertido. Qualquer outro estado pode ser decomposto nesses dois componentes, e o operador atua sobre cada um deles de acordo com isso — o que é exatamente uma reflexão sobre um $|v\rangle$ o.

Acontece que tanto a etapa do oráculo quanto a etapa de difusão no algoritmo de Grover podem ser expressas como reflexões nessa representação geométrica.

O oráculo como reflexão. O oráculo inverte o sinal do estado $|A_1\rangle$ e mantém tudo o resto inalterado. Isso equivale a uma reflexão sobre o eixo e $|A_0\rangle$.

A difusão como reflexo. É um pouco mais complicado perceber como o operador de difusão também funciona como uma reflexão. O operador de difusão é

$Z_{\text{OR}}$ por si só é uma reflexão sobre o estado totalmente nulo, uma vez que inverte o sinal de todos os estados que não sejam $|0\rangle^{\otimes n}$. Isso pode ser escrito como $2|0\rangle\langle 0| - I$. As camadas de Hadamard circundantes realizam, na prática, uma mudança de base, transformando o eixo de reflexão. Lembre-se de que $H^{\otimes n}$ mapeia $|0\rangle^{\otimes n}$ para a superposição uniforme $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Como a transformação de Hadamard é seu próprio inverso, a expressão completa torna-se

o que é uma reflexão sobre $|u\rangle$. Como $|u\rangle$ fica muito próximo de $|\psi\rangle$ (ambos estão praticamente na linha de $|A_0\rangle$ ), essa segunda reflexão desvia o estado para um ângulo de $2\theta$ em relação ao ponto de partida.

Rotação de $2\theta$. O efeito combinado dessas duas reflexões resulta em uma rotação de $2\theta$ na direção de $|A_1\rangle$. Cada iteração sucessiva do operador de Grover gira o estado em mais $2\theta.$

Número ideal de iterações. Nosso objetivo é girar o estado o mais próximo possível de $|A_1\rangle$, o que significa girar um total de aproximadamente $\pi/2$ radianos (um quarto de volta). Se cada iteração contribui com $2\theta$, o número ótimo de iterações $t$ satisfaz

Para uma solução única entre os estados de $N$, o ângulo inicial é $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (para $N$ grande). Substituindo,

É daí que vem a famosa aceleração do algoritmo “ $\sqrt{N}$ ”: precisamos apenas de $O(\sqrt{N})$ iterações para chegar ao destino, em vez das $O(N)$ verificações que uma busca clássica exigiria.

De maneira mais geral, se houver $|A_1|$ estados de solução entre $N$ estados totais, o número ideal de iterações é

Observe que, se você aplicar muitas iterações, ultrapassará o ponto de equilíbrio ( $|A_1\rangle$ ) e a probabilidade de encontrar o estado alvo começará a diminuir novamente. É importante determinar o número correto de iterações; no entanto, em hardware quântico sujeito a ruídos, o número experimentalmente ideal pode diferir dessa fórmula ideal.

Por que o algoritmo de Grover é útil?

Neste momento, você deve estar se perguntando: acabamos de criar um oráculo que identifica um estado alvo — mas, para criá-lo, precisávamos conhecer esse estado alvo. Então, o que estamos realmente procurando?

Essa é uma pergunta pertinente, e há várias respostas válidas.

• O modelo de consulta é uma ferramenta teórica. O modelo de computação por consulta nunca foi concebido para ser diretamente prático. Seu objetivo é nos proporcionar uma maneira clara de analisar a complexidade algorítmica, dividindo um problema em duas partes: o oráculo e todo o resto. A pesquisa é muito difícil, considerando que a verificação é gratuita? Como o número de consultas varia de acordo com o tamanho da entrada? Essas são perguntas úteis, mesmo que nenhum sistema real funcione exatamente dessa maneira.

• Você também pode pensar nisso como uma atividade entre duas pessoas : uma delas conhece o estado alvo e constrói o oráculo; a tarefa da outra é encontrar a resposta usando o oráculo como uma caixa preta, sem poder espiar o que há dentro. Na Atividade 2 abaixo, você fará exatamente isso com um colega.

• A amplificação de amplitude é uma sub-rotina amplamente útil. Mesmo que essa primeira demonstração pareça circular, o mecanismo subjacente — chamado de amplificação de amplitude — aparece repetidamente na computação quântica. O que estamos realmente construindo aqui é uma compreensão intuitiva de uma ferramenta que aparece como uma sub-rotina em muitos algoritmos quânticos mais complexos.

• Existem problemas em que é possível criar um oráculo sem saber a resposta. A principal conclusão é que existe toda uma classe de problemas para os quais é muito difícil encontrar uma solução, mas muito fácil verificar se uma determinada solução está correta. O fatoramento é um exemplo: dado o produto de dois grandes números primos, é extremamente difícil determinar quais são esses números primos, mas, uma vez que se os tenha, é possível multiplicá-los facilmente para verificar. (Temos um algoritmo melhor do que o de Grover especificamente para fatoração — veja o algoritmo de Shor —, mas esse está longe de ser o único problema dessa funcionalidade.) O Sudoku, a satisfação de restrições e até mesmo o clássico jogo do Campo Minado são problemas difíceis de resolver, mas fáceis de verificar.

Por que isso é relevante? Isso significa que podemos conhecer todas as condições e requisitos que uma solução deve satisfazer e podemos codificar esses requisitos em um circuito quântico que funciona como o oráculo — mesmo que não conheçamos a solução em si. O algoritmo de Grover vai encontrá-lo para nós.

Com essas ideias em mente, vamos analisar alguns exemplos. Começaremos com um exemplo em que o estado da solução está claramente especificado, para que possamos acompanhar a lógica do algoritmo. Em seguida, passaremos a uma atividade envolvendo duas partes e, por fim, a um exemplo em que o oráculo é construído a partir das restrições do problema, e não a partir do conhecimento da resposta.

Importações gerais e abordagem

Começamos importando vários pacotes necessários.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

Ao longo deste e de outros tutoriais, 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

Em geral, seguiremos essas etapas, embora nem sempre possamos rotulá-las explicitamente.

Atividade 1: Encontre um único estado-alvo determinado

Passo 1: Mapear entradas clássicas para um problema quântico

Precisamos da porta de consulta de fase para colocar uma fase geral (-1) nos estados de solução e deixar os estados sem solução inalterados. Outra forma de dizer isso é que o algoritmo de Grover requer um oráculo que especifique um ou mais estados de base computacional marcados, em que "marcado" significa um estado com uma fase de -1. Isso é feito usando uma porta-Z controlada ou sua generalização multicontrolada em $N$ qubits. Para ver como isso funciona, considere um exemplo específico de uma cadeia de bits {110}. Gostaríamos de ter um circuito que atue em um estado $|\psi\rangle = |q_2,q_1,q_0\rangle$ e aplique uma fase se $|\psi\rangle = |011\rangle$ (onde invertemos a ordem da cadeia binária, devido à notação no Qiskit, que coloca o qubit menos significativo (geralmente 0) à direita).

Portanto, queremos um circuito $Z_f$ que realize

Podemos usar a porta de controle múltiplo de múltiplos alvos (MCMTGate) para aplicar uma porta Z controlada por todos os qubits (inverter a fase se todos os qubits estiverem no estado $|1\rangle$ ). Obviamente, alguns dos qubits em nosso estado desejado podem ser $|0\rangle$. Portanto, para esses qubits, devemos primeiro aplicar uma porta X, depois fazer a porta Z controlada por múltiplos e, em seguida, aplicar outra porta X para desfazer nossa alteração. O site MCMTGate tem a seguinte aparência:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Output:

Observe que muitos qubits podem estar envolvidos no processo de controle (neste caso, três qubits estão), mas nenhum qubit individual é indicado como alvo. Isso ocorre porque o estado inteiro recebe um sinal geral "-" (inversão de fase); a porta afeta todos os qubits de forma equivalente. Isso é diferente de muitas outras portas de múltiplos qubits, como a porta CX , que tem um único qubit de controle e um único qubit de destino.

No código a seguir, definimos uma porta de consulta de fase (ou oráculo) que faz o que acabamos de descrever acima: marca um ou mais estados de base de entrada definidos por meio de sua representação de bitstring. A porta MCMT é usada para implementar a porta Z multicontrolada.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

Agora, escolhemos um estado "marcado" específico para ser nosso alvo e aplicamos a função que acabamos de definir. Vamos ver que tipo de circuito ele criou.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Output:

Se os qubits 1-3 estiverem no estado $|1\rangle$ e o qubit 0 estiver inicialmente no estado $|0\rangle$, o primeiro portão X inverterá o qubit 0 para $|1\rangle$ e todos os qubits estarão em $|1\rangle.$. Isso significa que o portão MCMT aplicará uma mudança geral de sinal ou inversão de fase, conforme desejado. Em qualquer outro caso, os qubits 1-3 estão no estado $|0\rangle$ ou o qubit 0 é invertido para o estado $|0\rangle$, e a inversão de fase não será aplicada. Vemos que esse circuito de fato marca nosso estado desejado $|0111\rangle,$ ou o bitstring {1110}.

O operador Grover completo consiste na porta de consulta de fase (oráculo), nas camadas Hadamard e no operador $Z_\text{OR}$. Podemos usar o site grover_operator para construir isso a partir do oráculo que definimos acima.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Output:

Conforme discutimos na ilustração geométrica acima, talvez seja necessário aplicar o operador de Grover várias vezes. O número ideal de iterações $t$ para maximizar a amplitude do estado alvo na ausência de ruído é

onde $|A_1|$ é o número de estados de solução e $N=2^n$ é o número total de estados. Em computadores quânticos modernos, sujeitos a ruídos, o número ideal de iterações, segundo os resultados experimentais, pode ser diferente — mas, neste caso, calculamos e utilizamos esse número ideal teórico com base no método de otimização de iterações ( $|A_1|=1$ ).

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

Output:

3

Vamos agora construir um circuito que inclua as portas Hadamard iniciais para criar uma superposição de todos os estados possíveis e aplicar o operador Grover o número ideal de vezes.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Output:

Construímos nosso circuito Grover!

Etapa 2: Otimizar o problema para execução em hardware quântico

Definimos nosso circuito quântico abstrato, mas precisamos reescrevê-lo em termos de portas que são nativas do computador quântico que realmente queremos usar. Também precisamos especificar quais qubits do computador quântico devem ser usados. Por esses e outros motivos, agora precisamos transpilar nosso circuito. Primeiro, vamos especificar o computador quântico que queremos usar.

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.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

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

backend = service.least_busy(operational=True, simulator=False)
backend.name

Output:

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Agora, usamos um gerenciador de passagem predefinido para otimizar nosso circuito quântico para o backend que selecionamos.

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

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Vale a pena observar, neste momento, que a profundidade do circuito quântico transpilado é substancial.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

Output:

The total depth is  439
The depth of two-qubit gates is  113

Na verdade, esses números são bastante grandes, mesmo para esse caso simples. Como todas as portas quânticas (e especialmente as portas de dois qubits) apresentam erros e estão sujeitas a ruídos, uma série de mais de 100 portas de dois qubits resultaria em nada além de ruído se os qubits não tivessem um desempenho extremamente alto. Vamos ver o desempenho deles.

Passo 3: Execute usando Qiskit primitives

Queremos fazer muitas medições e ver qual é o estado mais provável. Essa amplificação de amplitude é um problema de amostragem que é adequado para execução com a primitiva Sampler Qiskit Runtime.

Observe que o método run() de Qiskit Runtime SamplerV2 usa um iterável de blocos unificados primitivos (PUBs). Para o Sampler, cada PUB é um iterável no formato (circuit, parameter_values). No entanto, no mínimo, é necessária uma lista de circuitos quânticos.

# To run on a real quantum computer (this was tested on a Heron r2 processor and
# used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Para aproveitar ao máximo essa experiência, recomendamos que você execute seus experimentos nos computadores quânticos reais disponíveis em IBM Quantum. No entanto, se você tiver esgotado seu tempo de QPU, poderá descomentar as linhas abaixo para concluir essa atividade usando um simulador.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Etapa 4: Pós-processamento e retorno do resultado no formato clássico desejado

Agora podemos plotar os resultados da nossa amostragem em um histograma.

plot_distribution(dist)

Output:

Vemos que o algoritmo de Grover retornou o estado desejado com a maior probabilidade de longe, pelo menos uma ordem de magnitude maior do que as outras opções. Na próxima atividade, usaremos o algoritmo de uma forma que seja mais consistente com o fluxo de trabalho de duas partes de um algoritmo de consulta.

Verifique sua compreensão

Acabamos de buscar uma única solução em um conjunto de $2^4=16$ estados possíveis. Determinamos que o número ideal de repetições do operador de Grover é $t=3$. Esse número ideal teria aumentado ou diminuído se tivéssemos procurado (a) qualquer uma das várias soluções ou (b) uma única solução em um espaço de mais estados possíveis?

• Resposta

  Lembre-se de que, desde que o número de soluções seja pequeno em comparação com todo o espaço de soluções, podemos expandir a função seno em torno de ângulos pequenos e usar

  $$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

  (a) Pela expressão acima, vemos que o aumento do número de estados de solução diminuiria o número de iterações. Desde que a fração $\frac{|\mathcal{A}_1|}{N}$ ainda seja pequena, podemos descrever como $t$ diminuiria: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

  (b) À medida que o espaço de soluções possíveis ( $N$ ) aumenta, o número de iterações necessárias aumenta, mas apenas como $t~\sqrt{N}$.

Suponha que pudéssemos aumentar o tamanho da cadeia de bits de destino para que fosse arbitrariamente longa e ainda assim ter o resultado de que o estado de destino tem uma amplitude de probabilidade que é pelo menos uma ordem de magnitude maior do que qualquer outro estado. Isso significa que poderíamos usar o algoritmo de Grover para encontrar o estado de destino de forma confiável?

• Resposta

  Nº Suponha que repetimos a primeira atividade com 20 qubits e executamos o circuito quântico várias vezes num_shots = 10,000. Uma distribuição uniforme de probabilidade significaria que cada estado tem uma probabilidade de $10,000/2^{20}=0.00954$ ser medido uma única vez. Se a probabilidade de medir o estado-alvo fosse 10 vezes maior do que a de não soluções (e a probabilidade de cada não solução fosse correspondentemente ligeiramente reduzida), haveria apenas cerca de 10% de chance de medir o estado-alvo uma única vez. Seria altamente improvável medir o estado-alvo várias vezes, o que o tornaria indistinguível dos muitos estados sem solução obtidos aleatoriamente. A boa notícia é que podemos obter resultados de fidelidade ainda maior usando a supressão e a atenuação de erros.

Atividade 2: Um fluxo de trabalho preciso do algoritmo de consulta

Começaremos esta atividade exatamente como a primeira, exceto que agora você formará uma dupla com outro entusiasta do Qiskit. Você escolherá um bitstring secreto, e seu parceiro escolherá um bitstring (geralmente) diferente. Cada um de vocês gerará um circuito quântico que funciona como um oráculo e os trocará. Em seguida, você usará o algoritmo de Grover com esse oráculo para determinar a cadeia de bits secreta do seu parceiro.

Passo 1: Mapear entradas clássicas para um problema quântico

Usando a função grover_oracle definida acima, construa um circuito de oráculo para um ou mais estados marcados. Não se esqueça de informar ao seu parceiro quantos estados você marcou, para que ele possa aplicar o operador de Grover o número ideal de vezes. Não deixe sua bitstring muito longa. 3-5 bits devem funcionar sem muita dificuldade. As cadeias de bits mais longas resultariam em circuitos profundos que exigiriam técnicas mais avançadas, como a atenuação de erros.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

Agora você criou um circuito quântico que inverte a fase do seu estado-alvo. Você pode salvar esse circuito como my_circuit.qpy usando a sintaxe abaixo.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

Agora, envie esse arquivo ao seu parceiro (por e-mail, serviço de mensagens, um repositório compartilhado etc.). Peça ao seu parceiro que também lhe envie o circuito dele. Certifique-se de salvar o arquivo em algum lugar onde possa encontrá-lo facilmente. Quando você tiver o circuito do seu parceiro, poderá visualizá-lo, mas isso quebra o modelo de consulta. Ou seja, estamos modelando uma situação em que você pode consultar o oráculo (usar o circuito do oráculo), mas não examiná-lo para determinar o estado a que ele se destina.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Pergunte ao seu parceiro quantos estados-alvo foram codificados e digite-os abaixo.

# Update according to your partner's number of target states.
num_marked_states = 1

Isso é usado na próxima expressão para determinar o número ideal de iterações de Grover.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Etapa 2: Otimizar o problema para execução em hardware quântico

Isso ocorre exatamente como antes.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Passo 3: Execute usando Qiskit primitives

Isso também é idêntico ao processo da primeira atividade.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used
# 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Etapa 4: Pós-processamento e retorno do resultado no formato clássico desejado

Agora, exiba um histograma dos resultados da amostragem. Um ou mais estados devem ter uma probabilidade de medição muito maior do que os outros. Informe-os ao seu parceiro e verifique se você determinou corretamente os estados-alvo. Por padrão, o histograma exibido é do mesmo circuito da primeira atividade. Você deve obter resultados diferentes do circuito do seu parceiro.

plot_distribution(dist)

Output:

Verifique sua compreensão

Você deve ter obtido corretamente o(s) estado(s) de destino do seu parceiro. Caso contrário, trabalhe com seu parceiro para identificar o que deu errado. Clique abaixo para ver algumas ideias.

• Sugestões
  • Visualize/desenhe o circuito de seu parceiro e verifique se ele foi carregado corretamente.
  • Compare os circuitos usados e compare o resultado esperado com o que você obteve.
  • Verifique a profundidade dos circuitos usados para garantir que a cadeia de bits não seja muito longa ou que o número de iterações de Grover seja proibitivamente alto.

Se ainda não o fez, desenhe o circuito do oráculo que seu parceiro lhe enviou. Veja se você pode falar sobre o efeito de cada porta e argumentar qual deve ter sido o estado de destino. Isso será muito mais fácil no caso de um único estado marcado do que no caso de vários.

• Sugestões
  • Lembre-se de que o trabalho do oráculo é inverter o sinal no estado de destino.
  • Lembre-se de que o MCMTGate inverte o sinal em um estado se e somente se todos os qubits envolvidos no controle estiverem no estado $|1\rangle$.
  • Se o seu estado de destino já tiver um $|1\rangle$ em um determinado qubit, você não precisará fazer nada com esse qubit. Se o seu alvo tiver um $|0\rangle$ em um determinado qubit e você quiser que o MCMTGate inverta o sinal, será necessário aplicar uma porta X a esse qubit em seu oráculo (e depois desfazer a porta X após o MCMTGate).

Repita o experimento com uma iteração a menos do operador de Grover. Você ainda obtém a resposta correta? Por que ou por que não?

• Orientação

  Provavelmente sim, embora isso possa depender do número de soluções codificadas. Isso destaca uma sutileza: o número "ideal" de iterações de Grover é o número que torna a probabilidade de medir o estado marcado a mais alta possível. Mas menos iterações do que isso ainda podem tornar o estado marcado substancialmente mais provável do que outros estados. Portanto, é possível que você consiga fazer menos iterações do que o número ideal. Isso reduz a profundidade do circuito e, portanto, reduz as taxas de erro.

Por que alguém poderia querer usar menos iterações de Grover do que o "número ideal" identificado aqui?

• Resposta

  O número "ideal" de iterações de Grover é o número que torna a probabilidade de medir o estado marcado a mais alta possível na ausência de ruído. Mas menos iterações do que isso ainda podem tornar o estado marcado substancialmente mais provável do que outros estados. Portanto, talvez você consiga fazer menos iterações do que o número ideal. Isso reduz a profundidade do circuito e, portanto, reduz as taxas de erro.

Atividade 3: Resolver um tabuleiro do Campo Minado com o algoritmo de Grover

Na seção anterior, observamos que o algoritmo de Grover se torna realmente útil quando podemos construir um oráculo a partir das restrições de um problema, em vez de a partir do conhecimento da resposta. O Jogo da Mina é um exemplo perfeito: as casas numeradas indicam quantas minas estão adjacentes, e essas restrições determinam totalmente onde as minas devem estar — mas encontrar a configuração correta requer uma busca.

Foi comprovado que o jogo “Campo Minado” é NP-completo: é difícil de resolver, mas fácil de verificar. Isso faz com que seja um candidato natural para o algoritmo de Grover. É claro que ainda não conseguimos resolver uma grade completa de 9 $\times$ 9 em um computador quântico com ruído — os circuitos seriam complexos demais. Em vez disso, usaremos uma pequena grade como uma demonstração simples de como se abordaria um tabuleiro maior em uma futura máquina tolerante a falhas.

Algumas observações importantes. O algoritmo de Grover proporciona apenas uma aceleração quadrática em relação à busca clássica não estruturada. É quase certo que o Jogo da Mina tenha uma estrutura que possa ser explorada por um algoritmo clássico inteligente. E, no caso de um espaço de pesquisa que cresce exponencialmente, mesmo a melhoria do algoritmo de classificação por relevância ( $\sqrt{N}$ ) tem seus limites. Mas vamos deixar essas preocupações de lado e usar esse problema hipotético para ilustrar como as restrições do problema são codificadas em um oráculo quântico.

A grade

Aqui está o nosso tabuleiro do jogo da mina para crianças:

Cada célula em branco pode ser representada por uma variável binária que indica se contém uma mina. Denominamos essas células como $x_0$, $x_1$ e $x_2$, em que $x_i = 1$ significa que há uma mina nessa célula e $x_i = 0$ significa que não há:

Poderíamos resolver isso mentalmente em cerca de meio segundo, mas estamos usando esse problema simples para ilustrar como um problema muito mais complexo poderia ser abordado com um computador quântico.

Codificar as restrições

Cada célula numerada impõe uma condição às células em branco adjacentes. Precisamos expressar essas condições como expressões booleanas que possam ser codificadas em um circuito quântico.

A célula com o número "1" ao lado de $x_0$ e $x_1$ indica que exatamente um desses sites contém uma mina. Essa é precisamente a operação OR exclusivo (XOR), $\oplus$, que retorna verdadeiro quando exatamente uma de suas entradas é verdadeira:

Da mesma forma, a outra célula com o valor "1" (ao lado de $x_1$ e $x_2$ ) nos dá:

A célula "2" indica que duas das três células em branco devem conter minas. Como o XOR é uma operação de paridade, a expressão $x_0 \oplus x_1 \oplus x_2$ retorna verdadeiro quando um número ímpar de variáveis é verdadeiro. Queremos que um número par (especificamente dois) seja verdadeiro, então negamos com um $\lnot$ o:

Por si só, essa expressão seria satisfeita tanto por zero quanto por dois qubits no estado de $|1\rangle$, uma vez que se trata de uma afirmação sobre a paridade. Mas, quando combinadas com as outras duas cláusulas, cada uma das quais exige pelo menos uma mina, a única solução válida é aquela que contém exatamente duas minas.

Todas as três condições devem ser satisfeitas simultaneamente; por isso, as unimos com os símbolos “e” $\land$ :

Passo 1: Mapear entradas clássicas para um problema quântico

Agora precisamos codificar essa expressão booleana em um circuito quântico que funcione como oráculo. A versão quântica da operação XOR pode ser realizada com portas CX (CNOT): a aplicação de duas portas CX dos qubits de dados a um qubit do espaço de trabalho (ancilla) calcula efetivamente a operação XOR entre eles e armazena o resultado no qubit ancilla.

Apresentamos três qubits do espaço de trabalho — um para cada cláusula. Armazenamos o resultado de cada expressão booleana no qubit do espaço de trabalho correspondente e, em seguida, usamos uma porta Z com controle múltiplo para inverter a fase do estado de três qubits, de modo que todos os três qubits do espaço de trabalho fiquem em estado “ $|1\rangle$ ” (ou seja, todas as cláusulas são satisfeitas simultaneamente).

Na primeira célula de código abaixo, construímos a parte de "cálculo" do oráculo — a parte que avalia cada cláusula e grava o resultado nos qubits da área de trabalho.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

Nesta fase, o resultado de cada cláusula é armazenado no qubit da área de trabalho correspondente. Agora precisamos do estado de dados de três qubits que faça com que todos os três qubits do espaço de trabalho estejam em um estado de $|1\rangle$, de modo a assumirem um sinal negativo. Fazemos isso com uma porta Z multicontrolada (implementada como uma porta MCX entre duas portas de Hadamard no alvo).

Após aplicar a inversão de fase, devemos reverter o cálculo — desfazer todas as etapas de avaliação das cláusulas na ordem inversa — para redefinir os qubits do espaço de trabalho de volta a um $|0\rangle.$ Isso é essencial para que os qubits do espaço de trabalho estejam limpos para as iterações subsequentes do operador de Grover.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Este circuito é o nosso oráculo: ele inverte a fase do estado do qubit de dados que satisfaz todas as três restrições do Jogo da Mina e deixa os qubits da área de trabalho de volta em um $|0\rangle.$

Agora, construímos o operador de Grover completo a partir desse oráculo. xObserve o reflection_qubits argumento: passamos apenas os qubits de dados, pois os qubits do espaço de trabalho não fazem parte do espaço de busca. O trabalho deles está concluído assim que o oráculo for aplicado.

grover_op = grover_operator(qc, reflection_qubits=x)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Com três qubits de dados e um estado de solução, o número ideal de iterações de Grover é $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$; portanto, utilizamos duas iterações. Aplicamos portas de Hadamard aos qubits de dados para criar a superposição inicial, aplicamos o operador de Grover duas vezes e medimos apenas os qubits de dados.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

Etapa 2: Otimizar o problema para execução em hardware quântico

Como antes, compilamos o circuito para o backend de destino.

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

Agora podemos verificar a profundidade do circuito transpilado. Como o oráculo do Campo Minado utiliza qubits de espaço de trabalho e múltiplas portas CX, o circuito transpilado terá mais camadas do que os das atividades anteriores.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

Passo 3: Execute usando Qiskit primitives

# To run on a real quantum computer (this was tested on a Heron r2 processor and
#  used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Etapa 4: Pós-processamento e retorno do resultado no formato clássico desejado

plot_distribution(dist)

O 101 estado deve aparecer com uma probabilidade muito maior do que qualquer outro, indicando que as minas estão localizadas em $x_0$ e $x_2$. Usamos um computador quântico para resolver uma partidinha de Campo Minado!

É claro que os melhores algoritmos clássicos para o jogo da mina são mais eficazes do que uma busca por força bruta em todas as configurações possíveis de minas — eles aproveitam a estrutura do tabuleiro. O algoritmo de Grover só ofereceria uma vantagem em tabuleiros extremamente difíceis, projetados para serem o mais ambíguos possível; e, mesmo assim, o aumento de velocidade quadrático significa que ele não consegue acompanhar o crescimento exponencial indefinidamente. Mas o que realmente importa é a técnica: codificar as restrições de um problema em um oráculo quântico é um padrão poderoso que se aplica à satisfação de restrições, à otimização combinatória e a muitos outros domínios.

Perguntas e conceitos fundamentais:

Conceitos críticos:

Neste módulo, aprendemos alguns dos principais recursos do algoritmo de Grover:

• Enquanto os algoritmos clássicos de pesquisa não estruturada exigem um número de consultas que se dimensiona linearmente no tamanho do espaço, o algoritmo de $N,$ Grover exige um número de consultas que se dimensiona como $\sqrt{N}.$
• O algoritmo de Grover envolve a repetição de uma série de operações (comumente chamada de "operador de Grover") um número de vezes $t,$ escolhido para tornar os estados-alvo com probabilidade ideal de serem medidos.
• O algoritmo de Grover pode ser executado com menos de $t$ iterações e ainda assim ampliar os estados-alvo.
• O algoritmo de Grover se encaixa no modelo de consulta de computação e faz mais sentido quando uma pessoa controla a pesquisa e outra controla/constrói o oráculo. Ele também pode ser útil como uma sub-rotina em outros cálculos quânticos.
• É possível construir um oráculo a partir das restrições do problema, em vez de partir do conhecimento da solução, como demonstrado no exemplo do Jogo da Mina.

Questões verdadeiro/falso:

1. T/F O algoritmo de Grover oferece uma melhoria exponencial em relação aos algoritmos clássicos no número de consultas necessárias para encontrar um único estado marcado em uma pesquisa não estruturada.

2. T/F O algoritmo de Grover funciona aumentando iterativamente a probabilidade de um estado de solução ser medido.

3. T/F Quanto mais vezes você iterar o operador de Grover, maior será a probabilidade de medir um estado de solução.

Perguntas do MC:

1. Selecione a melhor opção para completar a frase. A melhor estratégia para usar com sucesso o algoritmo de Grover em computadores quânticos modernos é iterar o operador de Grover...

• a. Apenas uma vez.
• b. Sempre $t$ vezes, para maximizar a amplitude da probabilidade do(s) estado(s) da solução.
• c. Até $t$ vezes, embora um número menor possa ser suficiente para fazer com que os estados da solução se destaquem.
• d. Não menos que 10 vezes.

2. Aqui é mostrado um circuito de consulta de fase que funciona como um oráculo para marcar um determinado estado com uma inversão de fase. Quais dos seguintes estados são marcados por esse circuito?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Suponha que você queira pesquisar três estados marcados em um conjunto de 128. Qual é o número ideal de iterações do operador de Grover para maximizar as amplitudes dos estados marcados?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Questões para discussão:

1. Que outros problemas você poderia formular como uma pesquisa de Grover? Pense em problemas para os quais é difícil encontrar uma solução, mas fácil verificá-la.

2. Você vê algum problema em escalonar o algoritmo de Grover em computadores quânticos modernos?