Nota

Esta página foi gerada, a partir do tutorials/algorithms/06_grover_examples.ipynb.

Grover’s Algorithm and Amplitude Amplification

Grover’s algorithm is one of the most famous quantum algorithms introduced by Lov Grover in 1996 [1]. It has initially been proposed for unstructured search problems, i.e. for finding a marked element in a unstructured database. However, Grover’s algorithm is now a subroutine to several other algorithms, such as Grover Adaptive Search [2]. For the details of Grover’s algorithm, please see Grover’s Algorithm in the Qiskit textbook.

Qiskit implements Grover’s algorithm in the Grover class. This class also includes the generalized version, Amplitude Amplification [3], and allows setting individual iterations and other meta-settings to Grover’s algorithm.

Referências:

[1]: L. K. Grover, A fast quantum mechanical algorithm for database search. Proceedings 28th Annual Symposium on the Theory of Computing (STOC) 1996, pp. 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

Grover’s algorithm

Grover’s algorithm uses the Grover operator \(\mathcal{Q}\) to amplify the amplitudes of the good states:

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

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

\[\begin{split}|x\rangle \mapsto \begin{cases} -|x\rangle, &x \neq 0 \\ |x\rangle, &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 bom estado e 0 caso contrário.

In a nutshell, Grover’s algorithm applies different powers of \(\mathcal{Q}\) and after each execution checks whether a good solution has been found.

Running Grover’s algorithm

To run Grover’s algorithm with the Grover class, firstly, we need to specify an oracle for the circuit of Grover’s algorithm. In the following example, we use QuantumCircuit as the oracle of Grover’s algorithm. However, there are several other class that we can use as the oracle of Grover’s algorithm. We talk about them later in this tutorial.

Note that the oracle for Grover must be a phase-flip oracle. That is, it multiplies the amplitudes of the of «good states» by a factor of \(-1\). We explain later how to convert a bit-flip oracle to a phase-flip oracle.

from qiskit import QuantumCircuit
from qiskit.algorithms import AmplificationProblem

# 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
problem = AmplificationProblem(oracle, is_good_state=good_state)

# now we can have a look at the Grover operator that is used in running the algorithm
# (Algorithm circuits are wrapped in a gate to appear in composition as a block
# so we have to decompose() the op to see it expanded into its component gates.)
problem.grover_operator.decompose().draw(output='mpl')

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.

If the search was successful, the oracle_evaluation attribute of the result will be True. In this case, the most sampled measurement, top_measurement, is one of the «good states». Otherwise, oracle_evaluation will be False.

from qiskit.algorithms import Grover
from qiskit.primitives import Sampler


grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

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

Success!
Top measurement: 11

In the example, the result of top_measurement is 11 which is one of «good state». Thus, we succeeded to find the answer by using Grover.

Utilizando diferentes tipos de classes como oráculo de Grover

In the above example, we used QuantumCircuit as the oracle of Grover. However, we can also use qiskit.quantum_info.Statevector as oracle. All the following examples are when \(|11\rangle\) is «good state»

from qiskit.quantum_info import Statevector
oracle = Statevector.from_label('11')
problem = AmplificationProblem(oracle, is_good_state=['11'])

grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

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

Success!
Top measurement: 11

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

problem.grover_operator.oracle.decompose().draw(output='mpl')

O Qiskit permite uma construção fácil de oráculos mais complexos: * ` ` PhaseOracle ` `: para análise de expressões lógicas tais como ` ` “~ a | b” ` `. Isto é especialmente útil para solução de problemas de 3-SAT e é mostrado no tutorial ` Grover Exemplos <07_grover_examples.ipynb> ` __.

Here we’ll use the PhaseOracle for the simple example of finding the state \(|11\rangle\), which corresponds to 'a & b'.

from qiskit.circuit.library.phase_oracle import PhaseOracle
from qiskit.exceptions import MissingOptionalLibraryError

# `Oracle` (`PhaseOracle`) as the `oracle` argument
expression = '(a & b)'
try:
    oracle = PhaseOracle(expression)
    problem = AmplificationProblem(oracle)
    display(problem.grover_operator.oracle.decompose().draw(output='mpl'))
except MissingOptionalLibraryError as ex:
    print(ex)

Que observamos que este oráculo implementa uma inversão de fase quando o estado é \(|11\rangle\)

As mentioned above, Grover’s algorithm requires a phase-flip oracle. A bit-flip oracle flips the state of an auxiliary qubit if the other qubits satisfy the condition. To use these types of oracles with Grover’s we need to convert the bit-flip oracle to a phase-flip oracle by sandwiching the auxiliary qubit of the bit-flip oracle by \(X\) and \(H\) gates.

Nota: Esta transformação de um bit-flip para um oráculo phase-flip geralmente se mantém e você pode usar isso para converter seu oráculo para a representação correta.

Amplificação de amplitude

Grover’s algorithm uses Hadamard gates to create the uniform superposition of all the states at the beginning of the Grover operator \(\mathcal{Q}\). If some information on the good states is available, it might be useful to not start in a uniform superposition but only initialize specific states. This, generalized, version of Grover’s algorithm is referred to Amplitude Amplification.

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.ccz(0, 1, 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
problem = AmplificationProblem(oracle, state_preparation=state_preparation, is_good_state=['110', '111'])

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

state preparation circuit:

grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
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 zero, oracle e preparação de estado.

O qiskit.circuit.library.GroverOperator pode ser um bom ponto de partida e oferece mais opções para uma construção automatizada do operador de Grover. Você pode, por exemplo, * definir o mcx_mode *, ignorar qubits na reflexão zero definindo o reflection_qubits, * explicitamente trocar as operações \(\mathcal{S_f}, \mathcal{S_0}\) e \(\mathcal{A}\) usando os argumentos oracle, zero_reflection e state_preparation

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

oracle = QuantumCircuit(5)
oracle.ccz(0, 1, 2)
oracle.draw(output='mpl')

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

from qiskit.circuit.library import GroverOperator
grover_op = GroverOperator(oracle, insert_barriers=True)
grover_op.decompose().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.decompose().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.

Especificar 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']
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

# a list of integer good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = [0, 1]
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.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')
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.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)
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

O número de iterations

The number of repetition of applying the Grover operator is important to obtain the correct result with Grover’s algorithm. The number of iteration can be set by the iteration argument of Grover. The following inputs are supported: * an integer to specify a single power of the Grover operator that’s applied * or a list of integers, in which all these different powers of the Grover operator are run consecutively and after each time we check if a correct solution has been found

Additionally there is the sample_from_iterations argument. When it is True, instead of the specific power in iterations, a random integer between 0 and the value in iteration is used as the power Grover’s operator. This approach is useful when we don’t even know the number of solution.

Para obter 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)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=1)

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

# using sample_from_iterations
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(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 de saída são um valor aproximado. Quando o número de qubits é pequeno, as iterações de saída podem não ser ótimas.

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

12

Aplicando post_processing

We can apply an optional post processing to the top measurement for ease of readability. It can be used e.g. to convert from the bit-representation of the measurement [1, 0, 1] to a DIMACS CNF format [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)
problem = AmplificationProblem(oracle, is_good_state=['11'], post_processing=to_DIAMACS_CNF_format)
problem.post_processing([1, 0, 1])

[1, -2, 3]

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
qiskit-terra	0.23.0.dev0+0f6c75e
qiskit-aer	0.11.1
qiskit-optimization	0.5.0
System information
Python version	3.9.10
Python compiler	Clang 13.1.6 (clang-1316.0.21.2.5)
Python build	main, Aug 9 2022 18:26:17
OS	Darwin
CPUs	10
Memory (Gb)	64.0
Fri Nov 25 21:25:09 2022 JST

This code is a part of Qiskit

© Copyright IBM 2017, 2022.

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.