Nota

Esta página foi gerada, a partir do tutorials/algorithms/09_textbook_algorithms.ipynb.

Execute interativamente no IBM Quantum lab.

Algoritmos de Shor e de livros didáticos

Qiskit contém implementações dos algoritmos quânticos bem conhecidos da literatura como o algoritmo de Deutsch-Jozsa, o algoritmo de Bernstein-Vazirani e o algoritmo de Simon.

Qiskit tem também uma implementação do algoritmo de Shor.

As referências anteriores têm explicações detalhadas e a construção de circuitos, enquanto este notebook tem exemplos com os algoritmos pré-construídos no Qiskit que você pode usar para fins educativos e de experimentação.

import math
import numpy as np
from qiskit import BasicAer
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import BernsteinVazirani, DeutschJozsa, Simon, Shor
from qiskit.aqua.components.oracles import TruthTableOracle

Algoritmo de Deutsch-Jozsa

Vamos começar com o algoritmo de Deutsch-Jozsa que pode determinar se uma função é 'balanceada' ou 'constante' dada tal função como entrada. Nós podemos experimentar isso no Qiskit usando um oráculo criado a partir de tabelas verdade. Então, por exemplo, podemos criar uma instância TruthTableOracle da seguinte forma.

bitstr = '11110000'
oracle = TruthTableOracle(bitstr)

Como mostrado, a tabela verdade é especificada com a bitstr contendo valores de todas as entradas na tabela. Ela tem tamanho \(8\), então a tabela verdade correspondente é de \(3\) bits de entrada. Claro que podemos ver que esta tabela verdade representa uma função 'balanceada' já que metade dos valores são \(1\) e a outra metade \(0\).

It might seem like a moot point running Deutsch-Jozsa on a truthtable as the function outputs are literally listed as the truthtable’s values. The intention is to create an oracle circuit whose groundtruth information is readily available to us but obviously not to the quantum Deutsch-Jozsa algorithm that is to act upon the oracle circuit. In more realistic situations, the oracle circuit would be provided as a blackbox to the algorithm.

Como mencionado anteriormente, podemos inspecionar o circuito correspondente à função codificada na instância TruthTableOracle.

oracle.circuit.draw(output='mpl')

Como se vê, os \(v_i\)s correspondem aos 3 bits de entrada; o \(o_0\) é o qubit de saída do oráculo; o \(a_0\) é um qubit auxiliar.

Em seguida, podemos simplesmente criar uma instância DeutschJozsa usando o oráculo e executá-la para verificar o resultado.

dj = DeutschJozsa(oracle)
backend = BasicAer.get_backend('qasm_simulator')
result = dj.run(QuantumInstance(backend, shots=1024))
print(f'The truth table {bitstr} represents a \'{result["result"]}\' function.')

The truth table 11110000 represents a 'balanced' function.

Nós podemos, é claro, rapidamente montar outro exemplo para uma função 'constante', da seguinte forma.

bitstr = '1' * 16
oracle = TruthTableOracle(bitstr)
dj = DeutschJozsa(oracle)
backend = BasicAer.get_backend('qasm_simulator')
result = dj.run(QuantumInstance(backend, shots=1024))
print(f'The truth table {bitstr} represents a \'{result["result"]}\' function.')

The truth table 1111111111111111 represents a 'constant' function.

Algoritmo de Bernstein-Vazirani

Em seguida, o algoritmo de Bernstein-Vazirani, que tenta encontrar uma string oculta. Novamente, para o exemplo, criamos uma instância TruthTableOracle.

bitstr = '00111100'
oracle = TruthTableOracle(bitstr)

Como mostrado, a tabela verdade é especificada com a bitstr contendo valores de todas as entradas na tabela. Ela tem tamanho \(8\), então a tabela verdade correspondente é de \(3\) bits de entrada. A tabela verdade representa o mapeamento da função do seguinte modo:

• \(\mathbf{a} \cdot 000 \mod 2 = 0\)

• \(\mathbf{a} \cdot 001 \mod 2 = 0\)

• \(\mathbf{a} \cdot 010 \mod 2 = 1\)

• \(\mathbf{a} \cdot 011 \mod 2 = 1\)

• \(\mathbf{a} \cdot 100 \mod 2 = 1\)

• \(\mathbf{a} \cdot 101 \mod 2 = 1\)

• \(\mathbf{a} \cdot 110 \mod 2 = 0\)

• \(\mathbf{a} \cdot 111 \mod 2 = 0\)

E obviamente o objetivo é encontrar a bitstring \(\mathbf{a}\) que satisfaz todas as equações de produto interno.

Vamos olhar novamente para o circuito do oráculo, que agora corresponde à função binária codificada na instância TruthTableOracle.

oracle.circuit.draw(output='mpl')

Novamente, os \(v_i\)s correspondem aos 3 bits de entrada; o \(o_0\) é o qubit de saída do oráculo; o \(a_0\) é um qubit auxiliar.

Primeiro, vamos calcular a verdade base \(\mathbf{a}\) classicamente:

a_bitstr = ""
num_bits = math.log2(len(bitstr))
for i in reversed(range(3)):
    bit = bitstr[2 ** i]
    a_bitstr += bit
print(f'The groundtruth result bitstring is {a_bitstr}.')

The groundtruth result bitstring is 110.

Em seguida, podemos criar uma instância BernsteinVazirani usando o oráculo e executá-la para verificar o resultado contra a verdade base.

bv = BernsteinVazirani(oracle)
backend = BasicAer.get_backend('qasm_simulator')
result = bv.run(QuantumInstance(backend, shots=1024))
print(f'The result bitstring computed using Bernstein-Vazirani is {result["result"]}.')
assert(result['result'] == a_bitstr)

The result bitstring computed using Bernstein-Vazirani is 110.

Algoritmo de Simon

O algoritmo de Simon é usado para resolver o problema de Simon. Mais uma vez, para o exemplo, criamos uma instância TruthTableOracle, na qual a construção possui uma forma diferente.

bitmaps = [
    '01101001',
    '10011001',
    '01100110'
]
oracle = TruthTableOracle(bitmaps)

Como mostrado, a tabela verdade é especificada com três strings com comprimento de 8 bits, cada uma contendo os valores de todas as entradas para uma coluna específica da saída na tabela. Cada bitstring tem comprimento \(8\), então a tabela verdade tem \(3\) bits de entrada; Há \(3\) bitstrings, então a tabela verdade tem \(3\) bits de saída.

A função \(f\) representada pela tabela verdade é prometida a ser 1 para 1 (injetora) ou 2 para 1. Nosso objetivo é determinar qual. Para o caso de 2 para 1, também precisamos calcular a máscara \(\mathbf{s}\), que satisfaz \(\forall \mathbf{x}, mathbf{y}\): \(\mathbf{x} \oplus \mathbf{y} = \mathbf{s}\) iff \(f(\mathbf{x}) = f(\mathbf{y})\). Aparentemente, se \(f\) for 1 para 1, a máscara correspondente \(\mathbf{s} = \mathbf{0}\).

Primeiro, vamos calcular a máscara de verdade fundamental \(\mathbf{s}\) classicamente:

def compute_mask(input_bitmaps):
    vals = list(zip(*input_bitmaps))[::-1]
    def find_pair():
        for i in range(len(vals)):
            for j in range(i + 1, len(vals)):
                if vals[i] == vals[j]:
                    return i, j
        return 0, 0

    k1, k2 = find_pair()
    return np.binary_repr(k1 ^ k2, int(np.log2(len(input_bitmaps[0]))))

mask = compute_mask(bitmaps)
print(f'The groundtruth mask is {mask}.')

The groundtruth mask is 011.

simon = Simon(oracle)
backend = BasicAer.get_backend('qasm_simulator')
result = simon.run(QuantumInstance(backend, shots=1024))
print(f'The mask computed using Simon is {result["result"]}.')
assert(result['result'] == mask)

The mask computed using Simon is 011.

Também podemos tentar rapidamente uma tabela verdade que representa uma função de 1 para 1 (ou seja, a máscara correspondente é \(\mathbf{0}\)), da seguinte maneira.

bitmaps = [
    '00011110',
    '01100110',
    '10101010'
]
mask = compute_mask(bitmaps)
print(f'The groundtruth mask is {mask}.')

oracle = TruthTableOracle(bitmaps)
simon = Simon(oracle)
result = simon.run(QuantumInstance(backend, shots=1024))
print(f'The mask computed using Simon is {result["result"]}.')
assert(result['result'] == mask)

The groundtruth mask is 000.
The mask computed using Simon is 000.

Algoritmo de Fatoração de Shor

Algoritmo de Fatoração de Shor é um dos algoritmos quânticos mais conhecidos e encontra os fatores primos para o valor inteiro de entrada \(N\) em tempo polinomial. A implementação do algoritmo no Qiskit é simplesmente fornecer um inteiro alvo a ser fatorado e executar, da seguinte forma:

N = 15
shor = Shor(N)
backend = BasicAer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
result = shor.run(quantum_instance)
print(f"The list of factors of {N} as computed by the Shor's algorithm is {result['factors'][0]}.")

The list of factors of 15 as computed by the Shor's algorithm is [3, 5].

Nota: essa implementação do algoritmo de Shor usa \(4n + 2\) qubits, onde \(n\) é o número de bits representando o inteiro em binário. Por conseguinte, na prática, por enquanto, esta implementação limita-se a fatorar inteiros pequenos. Dado o valor acima de N calculamos \(4n +2\) abaixo e confirmamos o tamanho do circuito real.

print(f'Computed of qubits for circuit: {4 * math.ceil(math.log(N, 2)) + 2}')
print(f'Actual number of qubits of circuit: {shor.construct_circuit().num_qubits}')

Computed of qubits for circuit: 18
Actual number of qubits of circuit: 18

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 16:49:50 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.