Note

Cette page a été générée à partir de tutorials/algorithms/09_textbook_algorithms.ipynb.

Exécuter en mode interactif dans le IBM Quantum lab.

L’algorithme de Shor dans le manuel qiskit

Qiskit contient des implémentations des algorithmes quantiques connus tels que l’algorithme « Deutsch-Jozsa <https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html>` __, l’algorithme » Bernstein-Vazirani <https://qiskit.org/textbook/ch-algorithms/bernstein-vazirani.html>` __ et l’algorithme de Simon <https://qiskit.org/textbook/ch-algorithms/simon.html>` __.

Qiskit dispose également d’une implémentation de l’algorithme de Shor.

Les références précédentes ont des explications détaillées et une construction de circuits tandis que ce bloc-note a des exemples avec les algorithmes préconfigurés de Qiskit que vous pouvez utiliser à des fins d’expérimentation et de formation.

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

Algorithme de Deutsch-Jozsa

Commençons par l’algorithme Deutsch-Jozsa qui peut déterminer si une fonction est 'équilibrée' ou 'constante'. Nous pouvons l’expérimenter dans Qiskit en utilisant un oracle créé à partir d’une table de vérité. Ainsi, par exemple, nous pouvons créer une instance TruthTableOracle comme suit.

bitstr = '11110000'
oracle = TruthTableOracle(bitstr)

Comme indiqué, la table de vérité est spécifiée avec les valeurs bitstr contenant toutes les entrées. La table de vérité a une longueur de \(8\), donc elle correspond à \(3\) bits d’entrée. Nous pouvons bien sûr constater que cette table de vérité représente une fonction 'équilibrée' car la moitié des valeurs sont \(1\) et l’autre moitié \(0\).

Cela pourrait sembler être discutable d’utiliser Deutsch-Jozsa avec une table de vérité puisque les valeurs de la fonction sont littéralement listées dans la table de vérité. L’intention ici est de créer un oracle dont les valeurs de sortie sont facilement disponibles pour nous, mais évidemment pas pour l’algorithme de Deutsch-Jozsa qui ne pourra faire autrement que d’utiliser l’oracle. Dans des situations plus réalistes, le circuit de l’oracle serait fourni comme une boîte noire à l’algorithme.

Comme dit ci-dessus, nous pouvons inspecter le circuit correspondant à la fonction codée dans l’instance de TruthTableOracle.

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

Comme on l’a vu, les \(v_i\) correspondent aux 3 bits d’entrée ; le \(o_0\) est le qubit de sortie de l’oracle ; le \(a_0\) est un qubit ancillaire.

Ensuite nous pouvons simplement créer une instance de DeutschJozsa en utilisant l’oracle, et l’exécuter pour vérifier le résultat.

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.

Nous pouvons bien sûr rapidement rassembler un autre exemple pour une fonction 'constante' comme suit.

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.

Algorithme de Bernstein-Vazirani

Ensuite, l’algorithme de Bernstein-Vazirani qui essaie de trouver une chaîne cachée. Encore une fois, pour les besoins de l’exemple, nous créons une instance de TruthTableOracle.

bitstr = '00111100'
oracle = TruthTableOracle(bitstr)

Comme indiqué, la table de vérité est spécifiée avec les valeurs bitstr contenant toutes les entrées. La table de vérité a une longueur de \(8\), donc elle correspond à \(3\) bits d’entrée. La table de vérité représente la fonction comme suit:

• \(\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\)

Et bien sûr, l’objectif est de trouver le bitstring \(\mathbf{a}\) qui satisfait toutes les équations du produit scalaire.

Revoyons le circuit de l’oracle, qui correspond maintenant à la fonction binaire encodée dans l’instance TruthTableOracle.

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

De nouveau, les \(v_i\) correspondent aux 3 bits d’entrée ; le \(o_0\) est le qubit de sortie de l’oracle ; le \(a_0\) est un qubit ancillaire.

Calculons d’abord la vraie valeur de \(\mathbf{a}\) de façon classique:

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.

Ensuite, nous pouvons créer une instance BernsteinVazirani en utilisant l’oracle, et l’exécuter pour comparer le résultat obtenu avec le résultat attendu.

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.

Algorithme de Simon

L’algorithme de Simon <https://qiskit.org/documentation/stubs/qiskit.aqua.algorithms.Simon.html> __ est utilisé pour résoudre le problème de Simon <https://en.wikipedia.org/wiki/Simon’s_problem> __. Encore une fois, pour l’exemple, nous créons une instance de TruthTableOracle, où la construction présente une forme différente.

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

Comme on l’a montré, la table de vérité est spécifiée avec trois chaînes de caractères de longueur 8 qui contiennent chacune les valeurs de toutes les entrées pour une colonne de sortie particulière dans la table. Chaque chaîne de caractères a une longueur \(8\), donc la table de vérité a \(3\) bits d’entrée; Il y a \(3\) chaînes de caractères, donc la table de vérité a \(3\) bits de sortie.

La fonction \(f\) représentée par la table de vérité est garantie d’être soit 1-à-1 ou 2-à-1. Notre objectif est de déterminer lequel de ces 2 choix est vérifié. Pour le cas de 2-à-1, nous devons également calculer le masque \(\mathbf{s}\), qui satisfait \(\forall \mathbf{x}, mathbf{y}\): \(\mathbf{x} \oplus \mathbf{y} = \mathbf{s}\) si et seulement si \(f(\mathbf{x}) = f(\mathbf{y})\). De façon apparente, si \(f\) est 1-à-1, le masque correspondant est \(\mathbf{s} = \mathbf{0}\).

Calculons d’abord la vraie valeur du masque \(\mathbf{s}\) de façon classique:

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.

Nous pouvons également essayer rapidement une table de vérité qui représente une fonction de 1-à-1 (c’est-à-dire que le masque correspondant est \(\mathbf{0}\)), comme suit.

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.

L’algorithme de factorisation de Shor

L’algorithme de factorisation de Shor est l’un des algorithmes quantiques les plus connus et permet de trouver les facteurs premiers d’un entier \(N\) en temps polynomial. L’implémentation de l’algorithme dans Qiskit n’a besoin que d’un entier cible à factoriser et s’exécute comme suit:

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

Note: cette implémentation de l’algorithme de Shor’s utilise \(4n + 2\) est le nombre de bits représentant l’entier à factoriser lorsqu’il est écrit en binaire. Donc, dans la pratique, pour l’instant, cette implémentation est limitée à la factorisation de petits entiers. Étant donné la valeur ci-dessus de N, nous pouvons calculer \(4n +2\) comme ci-dessous et confirmer le calcul à partir du circuit généré.

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.