Nota

Esta página foi gerada, a partir do tutorials/algorithms/07_grover.ipynb.

Execute interativamente no IBM Quantum lab.

Algoritmo de Grover e Amplificação De Amplitude

O algoritmo de Grover é um dos algoritmos quânticos mais famosos apresentado por Lov Grover em 1996 [1]. Inicialmente foi proposto para problemas de busca não estruturada, ou seja, para encontrar um elemento marcado em um banco de dados não estruturado. No entanto, o algoritmo de Grover é agora uma subrotina para vários outros algoritmos, como a Busca Adaptativa de Grover [2]. Para detalhes do algoritmo de Grover, por favor, consulte Algoritmo de Grover no Qiskit textbook.

Qiskit implementa o algoritmo de Grover na classe Grover. Esta classe também inclui a versão generalizada, a Amplificação de Amplitude [3], e permite a configuração de iterações individuais e outras meta-configurações do algoritmo de Grover.

Referências:

[1]: L. K. Grover, Um algoritmo quântico mecânico rápido para pesquisa em banco de dados. Processos do 28° Simpósio Anual em Teoria da Computação (STOC) 1996, págs. 212-219. https://arxiv.org/abs/quant-ph/9605043

[2]: A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization. https://arxiv.org/abs/1912.04088

[3]: Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Quantum Amplitude Amplification and Estimation. http://arxiv.org/abs/quant-ph/0005055

Algoritmo de Grover

O algoritmo de Grover usa o operador de Grover :math:` mathcal{Q}` para amplificar as amplitudes dos estados:

\[\mathcal{Q} = \mathcal{A}\mathcal{S_0}\mathcal{A}^\dagger \mathcal{S_f}\]

Aqui, * \(\mathcal{A}\) é o estado de busca inicial para o algoritmo, que é apenas Hadamards, \(H^{\otimes n}\) no documento de Busca de Grover, mas pode ser mais elaborado para Amplificação de Amplitude * \(\mathcal{S_0}\) é a reflexão sobre o estado só de 0s

\[\begin{split}|x\rangle \mapsto \begin{cases} -|x\rângulo, &x \neq 0 \\ |x\rângulo, &x = 0 \end{cases}\end{split}\]

* \(\mathcal{S_f}\) é o oráculo que aplica

\[|x\rangle \mapsto (-1) ^ {f (x)} |x\rangle\]

onde \(f(x)\) é 1 se \(x\) é um estado e 0 caso contrário.

Em poucas palavras, o algoritmo de Grover aplica diferentes potências de \(\mathcal{Q}\) e depois de cada execução verifica se uma boa solução foi encontrada.

Executando o algoritmo de Grover

Para executar o algoritmo de Grover com a classe Grover, primeiramente precisamos especificar um oráculo para o circuito do algoritmo de Grover. No exemplo a seguir, utilizamos QuantumCircuit como o oráculo do algoritmo de Grover. No entanto, existem diversas outras classe que podemos usar como oráculo do algoritmo de Grover. Falamos sobre eles mais tarde neste tutorial.

Observe que o oráculo para Grover precisa ser um oráculo de inversão de fase. Ou seja, ele multiplica as amplitudes dos “estados bons” por um fator de \(-1\). Explicamos mais tarde como converter um oráculo de inversão de bit para um oráculo de inversão de fase.

from qiskit import QuantumCircuit
from qiskit.aqua.algorithms import Grover

# the state we desire to find is '11'
good_state = ['11']

# specify the oracle that marks the state '11' as a good solution
oracle = QuantumCircuit(2)
oracle.cz(0, 1)

# define Grover's algorithm
grover = Grover(oracle=oracle, good_state=good_state)

# now we can have a look at the Grover operator that is used in running the algorithm
grover.grover_operator.draw(output='mpl')

<matplotlib.figure.Figure at 0x7f359572eba8>

Em seguida, especificamos um backend e chamamos o método run de Grover com um backend para executar os circuitos. O tipo de resultado retornado é um GroverResult.

Se a busca foi bem-sucedida, o resultado do atributo oracle_evaluation será True. Neste caso, a medição mais amostrada, top_measurement, é um dos “estados bons”. Caso contrário, oracle_evaluation será False.

from qiskit import Aer
from qiskit.aqua import QuantumInstance

qasm_simulator = Aer.get_backend('qasm_simulator')
result = grover.run(quantum_instance=qasm_simulator)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.aqua.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

No exemplo, o resultado de top_measurement é 11 que é um “estado bom”. Assim, nós tivemos sucesso em encontrar a resposta utilizando Grover.

Utilizando os diferentes tipos de classes como oráculo de Grover

No exemplo acima, utilizamos QuantumCircuit como o oráculo de Grover. No entanto, podemos também utilizar qiskit.aqua.components.oracles.Oracle, e qiskit.quantum_info.Statevector como oráculos. Todos os exemplos a seguir são quando \(|11\rangle\) é um “estado bom”

from qiskit.quantum_info import Statevector
oracle = Statevector.from_label('11')
grover = Grover(oracle=oracle, good_state=['11'])

result = grover.run(quantum_instance=qasm_simulator)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.aqua.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

Internamente, o vetor de estados é mapeado para um circuito quântico:

grover.grover_operator.oracle.draw(output='mpl')

Os componentes Oracle no Qiskit Aqua permitem uma construção fácil de oráculos mais complexos. O tipo Oracle tem as interessantes subclasses: * LogicalExpressionOracle: para a interpretação de expressões lógicas tais como '~a | b'. Isto é especialmente útil para a solução de problemas de 3-SAT e é mostrada no tutorial que acompanha esse Exemplos de Grover. * TrutheTableOracle: para a conversão de tabelas verdade binárias em circuitos

Aqui vamos usar o LogicalExpressionOracle para o exemplo simples de encontrar o estado \(|11\rangle\), que corresponde a 'a & b'.

from qiskit.aqua.components.oracles import LogicalExpressionOracle

# `Oracle` (`LogicalExpressionOracle`) as the `oracle` argument
expression = '(a & b)'
oracle = LogicalExpressionOracle(expression)
grover = Grover(oracle=oracle)
grover.grover_operator.oracle.draw(output='mpl')

Podem observar que este oráculo é efetivamente implementado com três qubits em vez de dois!

Isso porque o LogicalExpressionOracle não é um oráculo inversor de fase (que inverte a fase do estado bom) mas um oráculo inversor de bit. Isso significa que ele inverte o estado de um qubit auxiliar se os outros qubits satisfazem a condição. Para o algoritmo de Grover, no entanto, exigimos um oráculo de inversão de fase. Para converter o oráculo de inversão de bits para um oráculo de inversão de fase nós envolvemos o NOT-controlado por portas \(X\) e \(H\), como você pode ver no circuito acima.

Nota: Esta transformação de um oráculo de inversão de bit para um de inversão de fase é geral e você pode usar isso para converter seu oráculo para a representação correta.

Amplificação de amplitude

O algoritmo de Grover usa portas Hadamard para criar a superposição uniforme de todos os estados no início do operador de Grover \(\mathcal{Q}\). Se alguma informação sobre os estados bons estiver disponível, poderá ser útil não começar com uma superposição uniforme, mas apenas inicializar os estados específicos. Esta versão generalizada do algoritmo de Grover se refere à Amplificação de Amplitude.

No Qiskit, o estado inicial de superposição pode facilmente ser ajustado definindo o argumento state_preparation.

Preparação do Estado

A state_preparation argument is used to specify a quantum circuit that prepares a quantum state for the start point of the amplitude amplification. By default, a circuit with \(H^{\otimes n}\) is used to prepare uniform superposition (so it will be Grover’s search). The diffusion circuit of the amplitude amplification reflects state_preparation automatically.

import numpy as np

# Specifying `state_preparation`
# to prepare a superposition of |01>, |10>, and |11>
oracle = QuantumCircuit(3)
oracle.h(2)
oracle.ccx(0,1,2)
oracle.h(2)

theta = 2 * np.arccos(1 / np.sqrt(3))
state_preparation = QuantumCircuit(3)
state_preparation.ry(theta, 0)
state_preparation.ch(0,1)
state_preparation.x(1)
state_preparation.h(2)

# we only care about the first two bits being in state 1, thus add both possibilities for the last qubit
grover = Grover(oracle=oracle, state_preparation=state_preparation, good_state=['110', '111'])

# state_preparation
print('state preparation circuit:')
grover.grover_operator.state_preparation.draw(output='mpl')

state preparation circuit:

result = grover.run(quantum_instance=qasm_simulator)
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Success!
Top measurement: 111

Flexibilidade total

Para uso mais avançado, também é possível especificar o operador de Grover inteiro, configurando o argumento grover_operator. Isso pode ser útil se você souber uma implementação mais eficiente para :math:` mathcal{Q}` do que a construção padrão via reflexão em zero, oráculo e preparação de estado.

The qiskit.circuit.library.GroverOperator can be a good starting point and offers more options for an automated construction of the Grover operator. You can for instance

• set the mcx_mode

• ignore qubits in the zero reflection by setting reflection_qubits

• explicitly exchange the \(\mathcal{S_f}, \mathcal{S_0}\) and \(\mathcal{A}\) operations using the oracle, zero_reflection and state_preparation arguments

Por exemplo, imagine que o estado bom é um estado de três qubit \(|111\rangle\) mas utilizamos 2 qubits adicionais como qubits auxiliares.

from qiskit.circuit.library import GroverOperator, ZGate

oracle = QuantumCircuit(5)
oracle.append(ZGate().control(2), [0, 1, 2])
oracle.draw(output='mpl')

Em seguida, por padrão, o operador de Grover implementa a reflexão sobre zero em todos os cinco qubits.

grover_op = GroverOperator(oracle, insert_barriers=True)
grover_op.draw(output='mpl')

Mas sabemos que só precisamos considerar os três primeiros:

grover_op = GroverOperator(oracle, reflection_qubits=[0, 1, 2], insert_barriers=True)
grover_op.draw(output='mpl')

Mergulhando em outros argumentos de Grover

Grover tem outros argumentos além de oracle e state_preparation. Explicaremos eles nesta seção.

Especificando good_state

good_state é usado para verificar se o resultado da medição está correto ou não internamente. Ele pode ser uma lista de strings binárias, uma lista de inteiros, Statevector e Callable. Se o input for uma lista de bitstrings, cada bitstring na lista representa um estado bom. Se a entrada for uma lista de inteiros, cada inteiro representa o índice do estado bom como \(|1\rangle\). Se for um Statevector, representa uma superposição de todos os estados bons.

# a list of binary strings good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = ['11', '00']
grover = Grover(oracle=oracle, good_state=good_state)
print(grover.is_good_state('11'))

True

# a list of integer good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = [0, 1]
grover = Grover(oracle=oracle, good_state=good_state)
print(grover.is_good_state('11'))

True

from qiskit.quantum_info import Statevector

# `Statevector` good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = Statevector.from_label('11')
grover = Grover(oracle=oracle, good_state=good_state)
print(grover.is_good_state('11'))

True

# Callable good state
def callable_good_state(bitstr):
    if bitstr == "11":
        return True
    return False

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=callable_good_state)
print(grover.is_good_state('11'))

True

O número de iterações

O número de repetições da aplicação do operador de Grover é importante para obter o resultado correto com o algoritmo de Grover. O número de iterações pode ser configurado pelo argumento iteration do Grover. As entradas a seguir são suportadas: * um inteiro para especificar uma única potência do operador de Grover que é aplicada * ou uma lista de inteiros, na qual todas estas diferentes potências do operador de Grover são executadas consecutivamente e depois de cada vez verificamos se uma solução correta foi encontrada

Adicionalmente há o argumento sample_from_iterations. Quando ele for True, em vez de uma potência específica em iterations, um inteiro aleatório entre 0 e o valor em iteration é usado como operador de potência de Grover. Essa abordagem é útil quando nem sequer conhecemos o número de soluções.

Para mais detalhes do algoritmo usando sample_from_iterations, consulte [4].

Referências:

[4]: Boyer et al., Tight bounds on quantum searching arxiv:quant-ph/9605034

# integer iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=['11'], iterations=1)

# list iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=['11'], iterations=[1, 2, 3])

# using sample_from_iterations
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=['11'], iterations=[1, 2, 3], sample_from_iterations=True)

Quando o número de soluções é conhecido, podemos também utilizar um método estático optimal_num_iterations para encontrar o número ideal de iterações. Observe que as iterações da saída são um valor aproximado. Quando o número de qubits é pequeno, as iterações da saída podem não ser ótimas.

iterations = Grover.optimal_num_iterations(num_solutions=1, num_qubits=8)
iterations

12

Aplicando post_processing

Podemos aplicar um processamento posterior opcional para a melhor medição para facilitar a legibilidade. Pode ser utilizado, por exemplo, para converter da representação em bits da medição [1, 0, 1] para um formato de DIMACS CNF [1, -2, 3].

def to_DIAMACS_CNF_format(bit_rep):
    return [index+1 if val==1 else -1 * (index + 1) for index, val in enumerate(bit_rep)]

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=['11'],post_processing=to_DIAMACS_CNF_format)
grover.post_processing([1, 0, 1])

[1, -2, 3]

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.23.0
Terra	0.16.0
Aer	0.7.0
Ignis	0.5.0
Aqua	0.8.0
IBM Q Provider	0.11.0
System information
Python	3.6.1 |Continuum Analytics, Inc.| (default, May 11 2017, 13:09:58) [GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]
OS	Linux
CPUs	1
Memory (Gb)	5.827335357666016
Sun Nov 08 17:30:57 2020 EST

This code is a part of Qiskit

© Copyright IBM 2017, 2020.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.