L'algorithme Deutsch-Jozsa

Pour ce module Qiskit en classe, les étudiants doivent disposer d'un environnement Python fonctionnel avec les paquets suivants installés :

qiskit v2.1.0 ou plus récent
qiskit-ibm-runtime v0.40.1 ou plus récent
qiskit-aer v0.17.0 ou plus récent
qiskit.visualization
numpy
pylatexenc

Pour configurer et installer les paquets ci-dessus, voir le guide d' installation de Qiskit. Afin d'exécuter des tâches sur de véritables ordinateurs quantiques, les étudiants devront créer un compte sur IBM Quantum® en suivant les étapes du guide Configurer votre compte IBM Cloud.

Ce module a été testé et a utilisé quatre secondes de temps QPU. Il s'agit uniquement d'une estimation. L'utilisation réelle peut varier.

# 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'

Regardez la présentation du module par le Dr. Katie McCormick ci-dessous, ou cliquez ici pour la regarder sur YouTube.

Introduction

Au début des années 1980, les physiciens quantiques et les informaticiens avaient une vague idée que la mécanique quantique pouvait être exploitée pour effectuer des calculs bien plus puissants que ceux des ordinateurs classiques. Leur raisonnement est le suivant : il est difficile pour un ordinateur classique de simuler des systèmes quantiques, mais un ordinateur quantique devrait pouvoir le faire plus efficacement. Et si un ordinateur quantique peut simuler des systèmes quantiques plus efficacement, il peut peut-être accomplir d'autres tâches plus efficacement qu'un ordinateur classique.

La logique était bonne, mais les détails restaient à régler. Cela a commencé en 1985, lorsque David Deutsch a décrit le premier "ordinateur quantique universel" Dans ce même article, il a fourni le premier exemple de problème pour lequel un ordinateur quantique pourrait résoudre quelque chose plus efficacement qu'un ordinateur classique. Ce premier exemple de jouet est aujourd'hui connu sous le nom d'"algorithme de Deutsch" L'amélioration de l'algorithme de Deutsch était modeste, mais Deutsch a travaillé avec Richard Jozsa quelques années plus tard pour creuser davantage l'écart entre les ordinateurs classiques et les ordinateurs quantiques.

Ces algorithmes - celui de Deutsch et l'extension Deutsch-Jozsa - ne sont pas particulièrement utiles, mais ils restent très importants pour plusieurs raisons :

Historiquement, ils ont été parmi les premiers algorithmes quantiques dont il a été démontré qu'ils surpassaient leurs homologues classiques. Les comprendre peut nous aider à comprendre comment la pensée de la communauté sur l'informatique quantique a évolué au fil du temps.
Ils peuvent nous aider à comprendre certains aspects de la réponse à une question étonnamment subtile : Qu'est-ce qui donne à l'informatique quantique sa puissance? Les ordinateurs quantiques sont parfois comparés à des processeurs parallèles géants à échelle exponentielle. Mais ce n'est pas tout à fait exact. Si une partie de la réponse à cette question réside dans ce que l'on appelle le "parallélisme quantique", l'extraction d'un maximum d'informations en une seule fois est un art subtil. Les algorithmes de Deutsch et de Deutsch-Jozsa montrent comment cela est possible.

Dans ce module, nous découvrirons l'algorithme de Deutsch, l'algorithme de Deutsch-Jozsa et ce qu'ils nous apprennent sur la puissance de l'informatique quantique.

Le parallélisme quantique et ses limites

Une partie de la puissance de l'informatique quantique provient du "parallélisme quantique" qui est essentiellement la capacité d'effectuer des opérations sur plusieurs entrées en même temps, puisque les états d'entrée des qubits peuvent être dans une superposition de plusieurs états classiquement autorisés. CEPENDANT, bien qu'un circuit quantique puisse être capable d'évaluer plusieurs états d'entrée à la fois, il est impossible d'extraire toutes ces informations en une seule fois.

Pour comprendre ce que je veux dire, disons que nous avons un bit, $x$ et une fonction appliquée à ce bit, $f(x)$ . Il existe quatre fonctions binaires possibles qui transforment un bit unique en un autre bit unique :

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Nous aimerions savoir laquelle de ces fonctions (1-4) est notre $f(x)$ . Classiquement, nous devrions exécuter la fonction deux fois - une fois pour $x=0$ , une fois pour $x=1$ . Mais voyons si nous pouvons faire mieux avec un circuit quantique. Nous pouvons apprendre à connaître la fonction à l'aide de la porte suivante :

Ici, la porte $U_f$ calcule $f(x)$ , où $x$ est l'état du qubit 0, et l'applique au qubit 1. Ainsi, l'état résultant, $|x\rangle|y\oplus f(x)\rangle$ , devient simplement $|x\rangle|f(x)\rangle$ lorsque $|y\rangle = |0\rangle$ . Ceci contient toutes les informations dont nous avons besoin pour connaître la fonction $f(x)$ : le qubit 0 nous dit ce qu'est $x$ , et le qubit 1 nous dit ce qu'est $f(x)$ . Ainsi, si nous initialisons $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ , l'état final des deux qubits sera : $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$ . Mais comment accéder à cette information?

2.1. Essayez-le sur Qiskit :

À l'aide de Qiskit, nous sélectionnons au hasard l'une des quatre fonctions possibles ci-dessus et nous exécutons le circuit. Votre tâche consiste alors à utiliser les mesures du circuit quantique pour apprendre la fonction en un minimum d'essais.

Dans cette première expérience et tout au long du module, nous utiliserons un cadre pour l'informatique quantique connu sous le nom de "modèles Qiskit", qui décompose les flux de travail en plusieurs étapes :

Etape 1 : Tracer un problème quantique à partir d'entrées classiques
Étape 2 : Optimisation du problème pour l'exécution quantique
Étape 3 : Exécution à l'aide des primitives « IBM Quantum »
Étape 4 : Post-traitement et analyse classique

Commençons par installer quelques paquets indispensables, notamment les primitives de l' IBM Quantum. Nous choisirons également l'ordinateur quantique le moins sollicité parmi ceux dont nous disposons.

Le code ci-dessous vous permet de sauvegarder vos données d'identification lors de la première utilisation. Veillez à supprimer ces informations du bloc-notes après l'avoir enregistré dans votre environnement, afin que vos informations d'identification ne soient pas accidentellement partagées lorsque vous partagez le bloc-notes. Voir Configurer votre compte IBM Cloud et Initialiser le service dans un environnement non fiable pour plus d'informations.

# Load IBM Quantum Compute Service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

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

# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)


sampler = Sampler(mode=backend)

Output:

ibm_brisbane

La cellule ci-dessous vous permettra de basculer entre l'utilisation du simulateur ou du matériel réel tout au long du carnet. Nous vous recommandons de l'exécuter maintenant :

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

# Alternatively, load a fake backend with generic properties and define a simulator.


noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)

Maintenant que nous avons chargé les paquets nécessaires, nous pouvons procéder à la mise en œuvre des modèles Qiskit. Dans l'étape de mise en correspondance ci-dessous, nous créons d'abord une fonction qui sélectionne parmi les quatre fonctions possibles qui transforment un bit unique en un autre bit unique.

# Step 1: Map

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)


def twobit_function(case: int):
    """
    Generate a valid two-bit function as a `QuantumCircuit`.
    """
    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f


# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the
# circuit is too large to display

# you may edit the number inside "twobit_function()" to select among the four valid functions:
# blackbox = twobit_function(2).to_gate()

# blackbox.label = "$U_f$"

qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()


qc.draw("mpl")

Output:

Dans le circuit ci-dessus, la porte de Hadamard "H" fait passer le qubit 0, qui est initialement dans l'état $|0\rangle$ , à l'état de superposition $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ . Ensuite, $U_f$ évalue la fonction $f(x)$ et l'applique au qubit 1.

Ensuite, nous devons optimiser et transpiler le circuit pour l'exécuter sur l'ordinateur quantique :

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

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

qc_isa = pm.run(qc)

Enfin, nous exécutons notre circuit transpilé sur l'ordinateur quantique et visualisons nos résultats :

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()

# Step 4: Visualize and analyze results

## Analysis
from qiskit.visualization import plot_histogram

plot_histogram(counts)

Output:

L'histogramme ci-dessus représente nos résultats. Selon le nombre de tirs que vous avez choisi pour exécuter le circuit à l'étape 3 ci-dessus, vous pouvez voir une ou deux barres, représentant les états mesurés des deux qubits à chaque tir. Comme toujours avec Qiskit et dans ce carnet, nous utilisons la notation "little endian", ce qui signifie que les états des qubits 0 à n sont écrits dans l'ordre croissant de droite à gauche, de sorte que le qubit 0 est toujours le plus à droite.

Ainsi, comme le qubit 0 était dans un état de superposition, le circuit a évalué la fonction pour $x=0$ et $x=1$ en même temps — quelque chose que les ordinateurs classiques ne peuvent pas faire! Mais le problème se pose lorsque nous voulons en savoir plus sur la fonction $f(x)$ - lorsque nous mesurons les qubits, leur état s'effondre. Si vous sélectionnez "shots = 1" pour n'exécuter le circuit qu'une seule fois, vous ne verrez qu'une seule barre dans l'histogramme ci-dessus et vos informations sur la fonction seront incomplètes.

Vérifiez votre compréhension

Combien de fois devons-nous exécuter l'algorithme ci-dessus pour apprendre la fonction $f(x)$ ? Cette méthode est-elle meilleure que la méthode classique? Préféreriez-vous un ordinateur classique ou quantique pour résoudre ce problème?

Étant donné que la mesure effondrera la superposition et ne renverra qu'une seule valeur, nous devons exécuter le circuit au moins deux fois pour renvoyer les deux sorties de la fonction $f(0)$ et $f(1)$ . Dans le meilleur des cas, les résultats sont aussi bons que dans le cas classique, où nous calculons à la fois $f(0)$ et $f(1)$ dans les deux premières requêtes. Mais il est possible que nous devions l'exécuter plus de deux fois, car la mesure finale est probabiliste et peut renvoyer la même valeur $f(x)$ les deux premières fois. Dans ce cas, je préférerais un ordinateur classique.

Ainsi, si le parallélisme quantique peut être puissant lorsqu'il est utilisé à bon escient, il n'est pas correct de dire qu'un ordinateur quantique fonctionne comme un processeur parallèle classique massif. L'acte de mesure effondre les états quantiques, de sorte que nous ne pouvons jamais accéder qu'à un seul résultat du calcul.

Algorithme de Deutsch

Bien que le parallélisme quantique ne nous donne pas à lui seul un avantage sur les ordinateurs classiques, nous pouvons l'associer à un autre phénomène quantique, l'interférence, pour obtenir une accélération. L'algorithme connu aujourd'hui sous le nom d'"algorithme de Deutsch" est le premier exemple d'algorithme permettant d'atteindre cet objectif.

Le problème

C'est là que le bât blesse :

Étant donné un bit d'entrée, $x = \{0,1\}$ , et une fonction d'entrée $f(x) = \{0,1\}$ , déterminez si la fonction est équilibrée ou constante. En d'autres termes, si elle est équilibrée, la sortie de la fonction est 0 la moitié du temps et 1 l'autre moitié du temps. S'il est constant, la sortie de la fonction est soit toujours 0, soit toujours 1. Rappelons le tableau des quatre fonctions possibles prenant un bit unique pour un autre bit unique :

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

La première et la dernière fonction, $f_1(x)$ et $f_4(x)$ , sont constantes, tandis que les deux fonctions intermédiaires, $f_2(x)$ et $f_3(x)$ , sont équilibrées.

L'algorithme

Deutsch a abordé ce problème par le biais du "modèle de requête" Dans le modèle d'interrogation, la fonction d'entrée ( $f_i(x)$ ci-dessus) est contenue dans une "boîte noire" - nous n'avons pas d'accès direct à son contenu, mais nous pouvons interroger la boîte noire et elle nous donnera la sortie de la fonction. On dit parfois qu'un "oracle" fournit ces informations. Voir la leçon 1 : Algorithmes de requête quantique du cours Fondamentaux de l'algorithmique quantique pour en savoir plus sur le modèle de requête.

Pour déterminer si un algorithme quantique est plus efficace qu'un algorithme classique dans le modèle d'interrogation, il suffit de comparer le nombre d'interrogations de la boîte noire dans chaque cas. Dans le cas classique, pour savoir si la fonction contenue dans la boîte noire est équilibrée ou constante, il faudrait interroger la boîte deux fois pour obtenir $f(0)$ et $f(1)$ .

Dans l'algorithme quantique de Deutsch, il a trouvé un moyen d'obtenir l'information avec une seule requête! Il a apporté une modification au circuit de "parallélisme quantique" ci-dessus, afin de préparer un état de superposition sur les deux qubits, au lieu du seul qubit 0. Ensuite, les deux sorties de la fonction, $f(0)$ et $f(1)$ , ont interféré pour renvoyer 0 si elles étaient toutes les deux 0 ou toutes les deux 1 (la fonction était constante), et ont renvoyé 1 si elles étaient différentes (la fonction était équilibrée). Deutsch pouvait ainsi faire la différence entre une fonction constante et une fonction équilibrée à l'aide d'une seule requête.

Voici un schéma de l'algorithme de Deutsch :

Pour comprendre le fonctionnement de cet algorithme, examinons les états quantiques des qubits aux trois points notés sur le diagramme ci-dessus. Essayez de trouver les états par vous-même avant de cliquer pour voir les réponses :

Vérifiez votre compréhension

Quel est l'état $|\pi_1\rangle$ ?

L'application d'une transformation de Hadamard transforme l'état $|0\rangle$ en $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ et l'état $|1\rangle$ en $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ . L'état complet devient donc $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Quel est l'état $|\pi_2\rangle$ ?

Avant d'appliquer $U_f$ , rappelez-vous ce qu'il fait. Il modifiera l'état du qubit 1 en fonction de l'état du qubit 0. Il est donc logique de factoriser l'état du qubit 0 : $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$ . Ensuite, si $f(0)=f(1)$ , les deux termes se transformeront de la même manière et le signe relatif entre les deux termes restera positif, mais si $f(0)\neq f(1)$ , cela signifie que le deuxième terme prendra un signe négatif par rapport au premier terme, changeant l'état du qubit 0 de $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ à $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ . Donc :
$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{if} & f(0) \neq f(1) \\ \end{cases}$

Quel est l'état $|\pi_3\rangle$ ?

Maintenant, l'état du qubit 0 est soit $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ soit $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ , selon la fonction. L'application de la méthode de Hadamard permet d'obtenir $|0\rangle$ ou $|1\rangle$ , respectivement.
$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$

En examinant vos réponses aux questions ci-dessus, vous constaterez qu'il se passe quelque chose d'un peu surprenant. Bien que $U_f$ ne fasse rien explicitement à l'état du qubit 0, parce qu'il modifie le qubit 1 en fonction de l'état du qubit 0, il peut arriver que cela provoque un déphasage dans le qubit 0. Ce phénomène est connu sous le nom de "phase-kickback" et est discuté plus en détail dans la leçon 1 : Algorithmes d'interrogation quantique du cours Fondamentaux de l'algorithmique quantique.

Maintenant que nous comprenons le fonctionnement de cet algorithme, mettons-le en œuvre avec Qiskit.

## Deutsch's algorithm:

## Step 1: Map the problem

# first, convert oracle circuit (above) to a single gate for drawing purposes.
# otherwise, the circuit is too large to display
blackbox = twobit_function(
    3
    # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
).to_gate()
blackbox.label = "$U_f$"


qc_deutsch = QuantumCircuit(2, 1)

qc_deutsch.x(1)
qc_deutsch.h(range(2))

qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()

qc_deutsch.h(0)
qc_deutsch.measure(0, 0)

qc_deutsch.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

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

qc_isa = pm.run(qc_deutsch)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)
if "1" in counts:
    print("balanced")
else:
    print("constant")

Output:

{'1': 1}
balanced

L'algorithme Deutsch-Jozsa

L'algorithme de Deutsch a constitué une première étape importante dans la démonstration de la manière dont un ordinateur quantique pourrait être plus efficace qu'un ordinateur classique, mais il ne s'agissait que d'une amélioration modeste : il ne nécessitait qu'une seule requête, contre deux dans le cas classique. En 1992, Deutsch et son collègue Richard Jozsa ont étendu l'algorithme original à deux qubits à un plus grand nombre de qubits. Le problème reste le même : déterminer si une fonction est équilibrée ou constante. Mais cette fois, la fonction passe de $n$ bits à un seul bit. Soit la fonction renvoie 0 et 1 un nombre égal de fois (elle est équilibrée ), soit la fonction renvoie toujours 1 ou toujours 0 (elle est constante ).

Voici un schéma de l'algorithme :

Cet algorithme fonctionne de la même manière que l'algorithme de Deutsch : le rebond de phase permet de lire l'état du qubit 0 pour déterminer si la fonction est constante ou équilibrée. C'est un peu plus difficile à voir que dans le cas de l'algorithme de Deutsch à deux qubits, puisque les états incluront des sommes sur les qubits $n$ , et donc le calcul de ces états sera laissé comme un exercice optionnel pour vous à la fin du module. L'algorithme renvoie une chaîne de bits contenant tous les 0 si la fonction est constante, et une chaîne de bits contenant au moins un 1 si la fonction est équilibrée.

Pour voir comment l'algorithme fonctionne dans Qiskit, nous devons d'abord générer notre oracle : la fonction aléatoire qui est garantie comme étant soit constante, soit équilibrée. Le code ci-dessous génère une fonction équilibrée dans 50 % des cas et une fonction constante dans 50 % des cas. Ne vous inquiétez pas si vous ne suivez pas entièrement le code - il est compliqué et n'est pas nécessaire à notre compréhension de l'algorithme quantique.

from qiskit import QuantumCircuit
import numpy as np


def dj_function(num_qubits):
    """
    Create a random Deutsch-Jozsa function.
    """

    qc_dj = QuantumCircuit(num_qubits + 1)
    if np.random.randint(0, 2):
        # Flip output qubits with 50% chance
        qc_dj.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance.
        return qc_dj

    # If the "if" statement above was "TRUE" then we've returned the constant
    # function and the function is complete. If not, we proceed in creating our
    # balanced function. Everything below is to produce the balanced function:

    # select half of all possible states at random:
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc_dj, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc_dj.x(qubit)
        return qc_dj

    for state in on_states:
        # qc_dj.barrier()  # Barriers are added to help visualize how the functions are created.
        # They can safely be removed.
        qc_dj = add_cx(qc_dj, f"{state:0b}")
        qc_dj.mcx(list(range(num_qubits)), num_qubits)
        qc_dj = add_cx(qc_dj, f"{state:0b}")

    # qc_dj.barrier()

    return qc_dj


n = 3  # number of input qubits

oracle = dj_function(n)

display(oracle.draw("mpl"))

Output:

Il s'agit de la fonction oracle, qui est soit équilibrée, soit constante. Pouvez-vous voir en l'observant si la sortie du dernier qubit dépend des valeurs introduites pour les premiers $n$ qubits? Si la sortie du dernier qubit dépend des premiers $n$ qubits, pouvez-vous dire si cette sortie dépendante est équilibrée ou non?

Nous pouvons dire si la fonction est équilibrée ou constante en regardant le circuit ci-dessus, mais n'oubliez pas que pour ce problème, nous considérons cette fonction comme une "boîte noire" Nous ne pouvons pas jeter un coup d'œil dans la boîte pour voir le schéma du circuit. Au lieu de cela, nous devons interroger la boîte.

Pour interroger la boîte, nous utilisons l'algorithme de Deutsch-Jozsa et déterminons si la fonction est constante ou équilibrée :

blackbox = oracle.to_gate()
blackbox.label = "$U_f$"


qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()


qc_dj.draw("mpl")

Output:

# Step 1: Map the problem

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()


qc_dj.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

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

qc_isa = pm.run(qc_dj)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

if (
    "0" * n in counts
):  # The D-J algorithm returns all zeroes if the function was constant
    print("constant")
else:
    print("balanced")  # anything other than all zeroes means the function is balanced.

Output:

{'110': 1}
balanced

Ci-dessus, la première ligne de la sortie est la chaîne de bits des résultats des mesures. La deuxième ligne indique si la chaîne de bits implique que la fonction était équilibrée ou constante. Si la chaîne de bits contient tous les zéros, elle est constante; sinon, elle est équilibrée. Ainsi, en exécutant une seule fois le circuit quantique ci-dessus, nous pouvons déterminer si la fonction est constante ou équilibrée!

Vérifiez votre compréhension

Combien de requêtes faudrait-il à un ordinateur classique pour déterminer avec une certitude de 100 % si une fonction est constante ou équilibrée? Rappelez-vous que, classiquement, une requête unique ne vous permet d'appliquer la fonction qu'à une seule chaîne de bits.

Il existe $2^n$ chaînes de bits possibles à vérifier et, dans le pire des cas, vous devrez tester $2^n/2+1$ d'entre elles. Par exemple, si la fonction est constante et que vous continuez à mesurer "1" comme sortie de la fonction, vous ne pouvez pas être certain qu'elle est vraiment constante avant d'avoir vérifié plus de la moitié des résultats. Auparavant, il fallait être très malchanceux pour continuer à mesurer "1" sur une fonction équilibrée. C'est comme si l'on jouait à pile ou face et que l'on tombait à chaque fois sur pile. C'est peu probable, mais pas impossible.

Comment votre réponse ci-dessus changerait-elle si vous deviez simplement mesurer jusqu'à ce qu'un résultat (équilibré ou constant) soit plus probable que l'autre? Combien de requêtes faut-il dans ce cas?

Dans ce cas, il suffit de mesurer deux fois. Si les deux mesures sont différentes, vous savez que la fonction est équilibrée. Si les deux mesures sont identiques, il peut s'agir d'un équilibre ou d'une constance. La probabilité qu'il soit équilibré avec cet ensemble de mesures est : $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$ . Cette probabilité est inférieure à 1/2, il est donc plus probable que la fonction soit constante dans ce cas.

Ainsi, l'algorithme de Deutsch-Jozsa a démontré une accélération exponentielle par rapport à un algorithme classique déterministe (qui renvoie la réponse avec une certitude de 100 %), mais aucune accélération significative par rapport à un algorithme probabiliste (qui renvoie un résultat susceptible d' être la bonne réponse).

Le problème de Bernstein-Vazirani

En 1997, Ethan Bernstein et Umesh Vazirani ont utilisé l'algorithme de Deutsch-Jozsa pour résoudre un problème plus spécifique et plus restreint que le problème de Deutsch-Jozsa. Plutôt que d'essayer simplement de faire la distinction entre deux classes différentes de fonctions, comme dans le cas D-J, Bernstein et Vazirani ont utilisé l'algorithme Deutsch-Jozsa pour apprendre une chaîne de caractères codée dans une fonction. Voici le problème :

La fonction $f:\{0,1\}^n \rightarrow \{0,1\}$ prend toujours une chaîne de $n$ bits et produit un seul bit. Mais maintenant, au lieu de promettre que la fonction est équilibrée ou constante, on nous promet que la fonction est le produit de points entre la chaîne d'entrée $x$ et une chaîne secrète $n$ -bit $s$ , modulo 2. (Ce produit de points modulo 2 est appelé "produit de points binaires") Le problème est de découvrir ce qu'est la chaîne secrète, $n$ -bit.

En d'autres termes, on nous donne une fonction de boîte noire $f: {0,1}^n \rightarrow {0,1}$ qui satisfait $f(x) = s \cdot x$ pour une certaine chaîne $s$ , et nous voulons apprendre la chaîne $s$ .

Voyons comment l'algorithme D-J résout ce problème :

Tout d'abord, une porte de Hadamard est appliquée aux qubits d'entrée $n$ , et une porte NOT plus une porte de Hadamard sont appliquées au qubit de sortie, ce qui crée l'état :

|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0

L'état des qubits 1 à $n$ peut être écrit plus simplement comme une somme sur tous $2^n$ les états de base des qubits $n$ $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$ . Nous appelons l'ensemble de ces états de base $\Sigma^n$ . (Voir Fundamentals of Quantum Algorithms pour plus de détails)

|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}

Ensuite, la porte $U_f$ est appliquée aux qubits. Cette porte prend les n premiers qubits en entrée (qui sont maintenant dans une superposition égale de toutes les chaînes de n bits possibles) et applique la fonction $f(x)=s \cdot x$ au qubit de sortie, de sorte que ce qubit est maintenant dans l'état : $|- \oplus f(x)\rangle$ . Grâce au mécanisme de rebond de phase, l'état de ce qubit reste inchangé, mais certains des termes de l'état du qubit d'entrée prennent un signe moins :

|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}

La série suivante de Hadamards est appliquée aux qubits 0 à $n-1$ . Dans ce cas, il peut s'avérer difficile de garder la trace des signes moins. Il est utile de savoir que l'application d'une couche de Hadamards à $n$ qubits dans un état de base standard $|x\rangle$ peut s'écrire comme suit :

H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}}\sum\limits_{y \in \Sigma^n}{(-1)^{x \cdot y}|y\rangle}

L'état devient donc :

|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}

L'étape suivante consiste à mesurer les premiers $n$ bits. Mais qu'allons-nous mesurer? Il s'avère que l'état ci-dessus se simplifie en : $|\Psi\rangle = |-\rangle \otimes |s\rangle$ mais c'est loin d'être évident. Si vous souhaitez vous familiariser avec les mathématiques, consultez le cours Fundamentals of Quantum Algorithms de John Watrous. Le fait est que le mécanisme de rebond de phase conduit à ce que les qubits d'entrée soient dans l'état $|s\rangle$ . Ainsi, pour découvrir quelle était la chaîne secrète $s$ , il suffit de mesurer les qubits!

Vérifiez votre compréhension

Vérifier que l'état de l'étape 3 ci-dessus est bien l'état $|s\rangle$ pour le cas particulier de $n=1$ .

Lorsque vous écrivez explicitement les deux sommations, vous devriez obtenir un état à quatre termes (omettons pour cela l'état de sortie $|-\rangle$ ) :
$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$
Si $s=0$ , les deux premiers termes s'additionnent de manière constructive et les deux derniers s'annulent, ce qui nous donne $|\Psi\rangle = |0\rangle$ . Si $s=1$ , les deux derniers termes s'additionnent de manière constructive et les deux premiers s'annulent, ce qui nous donne $|\Psi\rangle = |1\rangle$ . Donc, dans les deux cas, $|\Psi\rangle = |s\rangle$ . Nous espérons que ce cas le plus simple vous donne une idée de la manière dont fonctionne le cas général avec $n$ qubits : tous les termes qui ne sont pas $|s\rangle$ interfèrent, laissant seulement l'état $|s\rangle$ .

Comment le même algorithme peut-il résoudre les problèmes de Bernstein-Vazirani et de Deutsch-Jozsa? Pour comprendre cela, pensez aux fonctions de Bernstein-Vazirani, qui sont de la forme $f(x) = s \cdot x$ . Ces fonctions sont-elles également des fonctions de Deutsch-Jozsa? Il s'agit de déterminer si les fonctions de cette forme satisfont à la promesse du problème de Deutsch-Jozsa, à savoir qu'elles sont soit constantes, soit équilibrées. Comment cela nous aide-t-il à comprendre comment un même algorithme résout deux problèmes différents?

Toute fonction de Bernstein-Vazirani de la forme $f(x) = s \cdot x$ satisfait également la promesse du problème de Deutsch-Jozsa : si s=00...00, alors la fonction est constante (elle renvoie toujours 0 pour chaque chaîne de caractères x). Si s est une autre chaîne, la fonction est équilibrée. Ainsi, l'application de l'algorithme de Deutsch-Jozsa à l'une de ces fonctions résout simultanément les deux problèmes! Il renvoie la chaîne, et si cette chaîne est 00...00, nous savons qu'elle est constante; s'il y a au moins un "1" dans la chaîne, nous savons qu'elle est équilibrée.

Nous pouvons également vérifier que cet algorithme résout avec succès le problème de Bernstein-Vazirani en le testant expérimentalement. Tout d'abord, nous créons la fonction B-V qui vit à l'intérieur de la boîte noire :

# Step 1: Map the problem


def bv_function(s):
    """
    Create a Bernstein-Vazirani function from a string of 1s and 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc


display(bv_function("1000").draw("mpl"))

Output:

string = "1000"  # secret string that we'll pretend we don't know or have access to
n = len(string)

qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))

qc.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

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

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

Output:

{'0000': 1}

Ainsi, avec une seule requête, l'algorithme de Deutsch-Jozsa renverra la chaîne $s$ utilisée dans la fonction : $f(x)=x \cdot s$ lorsque nous l'appliquerons au problème de Bernstein-Vazirani. Avec un algorithme classique, il faudrait $n$ requêtes pour résoudre le même problème.

Conclusion

Nous espérons qu'en examinant ces exemples simples, nous vous avons donné une meilleure idée de la manière dont les ordinateurs quantiques sont capables d'exploiter la superposition, l'intrication et l'interférence pour atteindre leur puissance par rapport aux ordinateurs classiques.

L'algorithme de Deutsch-Jozsa revêt une importance historique considérable, car il a été le premier à démontrer une accélération par rapport à un algorithme classique, mais il ne s'agissait que d'une accélération polynomiale. L'algorithme Deutsch-Jozsa n'est que le début de l'histoire.

Après avoir utilisé l'algorithme pour résoudre leur problème, Bernstein et Vazirani s'en sont servis comme base pour un problème récursif plus compliqué, appelé problème récursif d'échantillonnage de Fourier. Leur solution offre une accélération super-polynomiale par rapport aux algorithmes classiques. Avant même Bernstein et Vazirani, Peter Shor avait déjà mis au point son célèbre algorithme qui permettait aux ordinateurs quantiques de factoriser de grands nombres exponentiellement plus vite que n'importe quel algorithme classique. Ces résultats, pris dans leur ensemble, ont montré la promesse excitante d'un futur ordinateur quantique et ont incité les physiciens et les ingénieurs à faire de cet avenir une réalité.

Questions

Les enseignants peuvent demander des versions de ces cahiers avec les corrigés et des conseils sur le placement dans les programmes d'études communs en répondant à cette enquête rapide sur la façon dont les cahiers sont utilisés.

Concepts essentiels

les algorithmes Deutsch et Deutsch-Jozsa utilisent le parallélisme quantique combiné à l'interférence pour trouver une réponse à un problème plus rapidement qu'un ordinateur classique.
le mécanisme de rebond de phase est un phénomène quantique contre-intuitif qui transfère des opérations sur un qubit à la phase d'un autre qubit. Les algorithmes de Deutsch et de Deutsch-Jozsa utilisent ce mécanisme.
L'algorithme de Deutsch-Jozsa offre une accélération polynomiale par rapport à n'importe quel algorithme classique déterministe.
L'algorithme de Deutsch-Jozsa peut être appliqué à un autre problème, appelé problème de Bernstein-Vazirani, qui consiste à trouver une chaîne cachée codée dans une fonction.

true/false

T/F L'algorithme de Deutsch est un cas particulier de l'algorithme de Deutsch-Jozsa où l'entrée est un seul qubit.
T/F Les algorithmes de Deutsch et de Deutsch-Jozsa utilisent la superposition et l'interférence quantiques pour atteindre leur efficacité.
T/F L'algorithme de Deutsch-Jozsa nécessite plusieurs évaluations de fonctions pour déterminer si une fonction est constante ou équilibrée.
T/F L'"algorithme de Bernstein-Vazirani" est en fait le même que l'algorithme de Deutsch-Jozsa, appliqué à un problème différent.
T/F L'algorithme de Bernstein-Vazirani peut trouver plusieurs chaînes secrètes simultanément.

Réponse courte

Combien de temps faudrait-il à un algorithme classique pour résoudre le problème Deutsch-Jozsa dans le pire des cas?
Combien de temps faudrait-il à un algorithme classique pour résoudre le problème de Bernstein-Vazirani? Quel est le gain de vitesse offert par l'algorithme DJ dans ce cas?
Décrire le mécanisme de rétroaction en phase et son fonctionnement pour résoudre les problèmes de Deutsch-Jozsa et de Bernstein-Vazirani.

Problème difficile

L'algorithme de Deutsch-Jozsa : Rappelez-vous que vous aviez une question ci-dessus vous demandant de calculer les états intermédiaires des qubits $\pi_1$ , et $\pi_2$ de l'algorithme de Deutsch. Faites de même pour les états intermédiaires $n+1$ -qubit $\pi_1$ , et $\pi_2$ de l'algorithme de Deutsch-Jozsa, pour le cas spécifique où $n=2$ . Ensuite, vérifiez que $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$ , à nouveau, pour le cas spécifique où $n=2$ .

Cette page a-t-elle été utile ?

Signaler un bogue, une coquille ou proposer du contenu sur GitHub.