Algoritmus Deutsch-Jozsa

Pro tento modul Qiskit in Classrooms musí mít studenti funkční prostředí Python s nainstalovanými následujícími balíčky:

• qiskit v2.1.0 nebo novější
• qiskit-ibm-runtime v0.40.1 nebo novější
• qiskit-aer v0.17.0 nebo novější
• qiskit.visualization
• numpy
• pylatexenc

Pokyny k nastavení a instalaci výše uvedených balíčků najdeš v průvodci Instalace Qiskit. Pokud chceš spouštět úlohy na skutečných kvantových počítačích, budeš si muset vytvořit účet u IBM Quantum® podle kroků v průvodci Nastavení účtu IBM Cloud.

Tento modul byl otestován a spotřeboval čtyři sekundy času QPU. Jde pouze o odhad. Tvoje skutečná spotřeba se může lišit.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

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

Níže se můžeš podívat na průvodní video modulu od Dr. Katie McCormick, nebo klikni sem a sleduj ho na YouTube.

---

Úvod

Na počátku 80. let 20. století měli kvantový fyzici a informatici mlhavou představu, že kvantovou mechaniku lze využít k výpočtům, jež by daleko předčily možnosti klasických počítačů. Jejich úvaha zněla takto: pro klasický počítač je obtížné simulovat kvantové systémy, ale kvantový počítač by to měl zvládnout efektivněji. A pokud by kvantový počítač dokázal simulovat kvantové systémy efektivněji, možná by existovaly i další úlohy, které by zvládl efektivněji než klasický počítač.

Logika byla správná, ale podrobnosti bylo teprve třeba propracovat. To začalo v roce 1985, kdy David Deutsch popsal první „universální kvantový počítač". Ve stejném článku také uvedl první příklad problému, který kvantový počítač dokáže vyřešit efektivněji než klasický. Tento první ilustrativní příklad je dnes znám jako „Deutschův algoritmus." Zlepšení v Deutschově algoritmu bylo skromné, ale Deutsch o několik let později spolupracoval s Richardem Jozsou a propast mezi klasickými a kvantovými počítači ještě prohloubili.

Tyto algoritmy — Deutschův a jeho rozšíření na Deutsch-Jozsa — nejsou zvláště prakticky užitečné, přesto jsou stále velmi důležité z několika důvodů:

1. Z historického hlediska patří k prvním kvantovým algoritmům, u nichž bylo prokázáno, že překonávají svůj klasický protějšek. Jejich pochopení nám pomáhá pochopit, jak se pohled komunity na kvantové výpočty vyvíjel v čase.
2. Pomáhají nám pochopit některé aspekty odpovědi na překvapivě jemnou otázku: Co dává kvantovým výpočtům jejich sílu? Kvantové počítače jsou někdy přirovnávány k obrovským, exponenciálně škálovatelným paralelním procesorům. To ale není úplně přesné. Přestože část odpovědi na tuto otázku spočívá v takzvaném „kvantovém paralelismu", vytěžit co nejvíce informací v jediném běhu je subtilní umění. Deutschův algoritmus a algoritmus Deutsch-Jozsa ukazují, jak toho lze dosáhnout.

V tomto modulu se seznámíme s Deutschovým algoritmem, algoritmem Deutsch-Jozsa a s tím, co nás učí o síle kvantových výpočtů.

Kvantový paralelismus a jeho hranice

Část síly kvantových výpočtů pramení z „kvantového paralelismu", tedy schopnosti provádět operace na více vstupech současně, protože vstupní stavy Qubitů mohou být v superpozici více klasicky povolených stavů. Kvantový Circuit však sice může vyhodnocovat více vstupních stavů naráz, ale získat veškeré tyto informace najednou je nemožné.

Abychom si to přiblížili, předpokládejme, že máme bit $x$ a nějakou funkci aplikovanou na tento bit, $f(x)$. Existují čtyři možné binární funkce zobrazující jeden bit na jeden bit:

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

Chceme zjistit, která z těchto funkcí (1–4) naše $f(x)$ je. Klasicky bychom museli funkci spustit dvakrát — jednou pro $x=0$, jednou pro $x=1$. Podívejme se ale, zda s kvantovým Circuitem dokážeme udělat lépe. O funkci se můžeme dozvědět pomocí následujícího Gate:

Gate $U_f$ počítá $f(x)$, kde $x$ je stav Qubitu 0, a výsledek aplikuje na Qubit 1. Výsledný stav $|x\rangle|y\oplus f(x)\rangle$ se tak při $|y\rangle = |0\rangle$ jednoduše stane $|x\rangle|f(x)\rangle$. Tento stav obsahuje veškeré informace potřebné ke zjištění funkce $f(x)$: Qubit 0 říká, jaké je $x$, a Qubit 1 říká, jaké je $f(x)$. Pokud tedy inicializujeme $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, bude výsledný stav obou Qubitů: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Jak ale k těmto informacím přistoupit?

2.1. Vyzkoušej to na Qiskit:

Pomocí Qiskitu náhodně vybereme jednu ze čtyř výše uvedených funkcí a spustíme Circuit. Tvojím úkolem pak bude využít měření kvantového Circuitu k tomu, abys funkci zjistil(a) v co nejmenším počtu běhů.

V tomto prvním experimentu a v celém modulu budeme používat rámec pro kvantové výpočty nazvaný „Qiskit patterns", který rozděluje pracovní postupy do následujících kroků:

• Krok 1: Mapování klasických vstupů na kvantový problém
• Krok 2: Optimalizace problému pro kvantové spuštění
• Krok 3: Spuštění pomocí primitiv Qiskit Runtime
• Krok 4: Postprocesing a klasická analýza

Začneme načtením potřebných balíčků, včetně primitiv Qiskit Runtime. Také vybereme nejméně vytížený dostupný kvantový počítač.

Níže je kód pro uložení přihlašovacích údajů při prvním použití. Po uložení do svého prostředí tyto informace ze zápisníku smaž, aby nedošlo k náhodnému sdílení přihlašovacích údajů při sdílení zápisníku. Více informací najdeš v průvodci Nastavení účtu IBM Cloud a Inicializace služby v nedůvěryhodném prostředí.

# Load the Qiskit Runtime 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)

ibm_brisbane

Níže uvedená buňka ti umožní přepínat mezi simulátorem a skutečným hardwarem v průběhu celého zápisníku. Doporučujeme ji spustit nyní:

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

Nyní, když jsme načetli potřebné balíčky, můžeme pokračovat pracovním postupem Qiskit patterns. V kroku mapování níže nejprve vytvoříme funkci, která vybírá z čtyř možných funkcí zobrazujících jeden bit na jeden bit.

# 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
# blackbox = twobit_function(2).to_gate()  # you may edit the number inside "twobit_function()" to select among the four valid functions
# blackbox.label = "$U_f$"

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

qc.draw("mpl")

Ve výše uvedeném Circuitu Gate Hadamard „H" převede Qubit 0, který je zpočátku ve stavu $|0\rangle$, do superpozičního stavu $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Poté $U_f$ vyhodnotí funkci $f(x)$ a výsledek aplikuje na Qubit 1.

Dále musíme Circuit optimalizovat a transpilovat pro spuštění na kvantovém počítači:

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

Nakonec spustíme transpilovaný Circuit na kvantovém počítači a vizualizujeme výsledky:

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

Výše je histogram našich výsledků. Podle počtu „shots", které jsi zvolil(a) ke spuštění Circuitu ve 3. kroku, může histogram obsahovat jeden nebo dva sloupce znázorňující naměřené stavy obou Qubitů v každém výstřelu. Jak je u Qiskitu a v tomto zápisníku zvykem, používáme notaci „little endian", to znamená, že stavy Qubitů 0 až n jsou zapsány vzestupně zprava doleva, takže Qubit 0 je vždy nejdále vpravo.

Protože byl Qubit 0 v superpozičním stavu, Circuit vyhodnotil funkci současně pro $x=0$ i $x=1$ — něco, co klasické počítače neumějí! Háček ale nastane, když chceme zjistit informace o funkci $f(x)$ — při měření Qubitů dochází k zániku jejich stavu. Pokud zvolíš „shots = 1" a Circuit spustíš jen jednou, uvidíš v histogramu pouze jeden sloupec a informace o funkci budou neúplné.

Ověř si porozumění

Přečti si otázku (otázky) níže, zamysli se nad odpovědí, pak klikni na trojúhelník a odhal řešení.

Kolikrát musíme výše uvedený algoritmus spustit, abychom zjistili funkci $f(x)$? Je to nějak lepší než klasický případ? Dřál(a) bys raději klasický nebo kvantový počítač k řešení tohoto problému?

Odpověď:

Protože měření zanese superpozici a vrátí pouze jednu hodnotu, musíme Circuit spustit alespoň dvakrát, abychom získali oba výstupy funkce $f(0)$ a $f(1)$. V nejlepším případě si povedeme stejně jako v klasickém případě, kdy oba výsledky $f(0)$ a $f(1)$ zjistíme při prvních dvou dotazech. Existuje však šance, že bude potřeba Circuit spustit více než dvakrát, protože výsledné měření je pravděpodobnostní a při prvních dvou bězích může vrátit stejnou hodnotu $f(x)$. V tomto případě bych raději zvolil(a) klasický počítač.

I když tedy kvantový paralelismus může být při správném použití mocný nástroj, nelze říci, že kvantový počítač funguje jako obrovský klasický paralelní procesor. Akt měření zanese kvantové stavy, takže vždy máme přístup pouze k jedinému výstupu výpočtu.

Deutschův algoritmus

Samotný kvantový paralelismus nám neposkytuje výhodu oproti klasickým počítačům, ale můžeme ho zkombinovat s jiným kvantovým jevem — interferencí — a dosáhnout tak zrychlení. Algoritmus dnes známý jako „Deutschův algoritmus" je prvním příkladem algoritmu, který toho dosahuje.

Problém

Problém byl následující:

Je dán vstupní bit $x = \{0,1\}$ a vstupní funkce $f(x) = \{0,1\}$. Urči, zda je funkce vyvážená nebo konstantní. To znamená: je-li vyvážená, výstup funkce je 0 v polovině případů a 1 ve druhé polovině. Je-li konstantní, výstup funkce je vždy 0 nebo vždy 1. Připomeň si tabulku čtyř možných funkcí zobrazujících jeden bit na jeden bit:

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

První a poslední funkce, $f_1(x)$ a $f_4(x)$, jsou konstantní, zatímco prostřední dvě funkce, $f_2(x)$ a $f_3(x)$, jsou vyvážené.

Algoritmus

Deutsch k tomuto problému přistoupil prostřednictvím „dotazovacího modelu." V dotazovacím modelu je vstupní funkce ($f_i(x)$ výše) uložena v „černé skříňce" — nemáme přímý přístup k jejímu obsahu, ale můžeme se jí dotazovat a ona nám vrátí výstup funkce. Někdy říkáme, že tuto informaci poskytuje „orákulum." Více o dotazovacím modelu najdeš v Lekci 1: Kvantové dotazovací algoritmy kurzu Základy kvantových algoritmů.

Abychom zjistili, zda je kvantový algoritmus efektivnější než klasický v dotazovacím modelu, stačí porovnat počet dotazů, které musíme na černou skříňku vznést v každém případě. V klasickém případě bychom potřebovali skříňku dotázat dvakrát, abychom získali $f(0)$ i $f(1)$ a zjistili, zda je funkce vyvážená nebo konstantní.

V Deutschově kvantovém algoritmu však Deutsch našel způsob, jak získat informaci jediným dotazem! Provedl jednu úpravu výše uvedeného obvodu „kvantového paralelismu" — připravil superpozici na obou qubitech místo jen na qubitu 0. Poté oba výstupy funkce, $f(0)$ a $f(1)$, interferovaly: vrátily 0, pokud byly oba 0 nebo oba 1 (funkce byla konstantní), a vrátily 1, pokud se lišily (funkce byla vyvážená). Deutschovi tak stačil jediný dotaz k rozlišení konstantní a vyvážené funkce.

Zde je schéma obvodu Deutschova algoritmu:

Abys pochopil/a, jak tento algoritmus funguje, podíváme se na kvantové stavy qubitů ve třech bodech vyznačených v diagramu výše. Zkus si stavy odvodit sám/sama, než klikneš pro zobrazení odpovědí:

Ověř si porozumění

Přečti si otázky níže, zamysli se nad odpověďmi a pak klikni na trojúhelníky pro odhalení řešení.

Jaký je stav $|\pi_1\rangle$?

Odpověď:

Aplikace Hadamardovy brány transformuje stav $|0\rangle$ na $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ a stav $|1\rangle$ na $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Celkový stav se tedy stane: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Jaký je stav $|\pi_2\rangle$?

Odpověď:

Než aplikujeme $U_f$, připomeňme, co dělá. Změní stav qubitu 1 na základě stavu qubitu 0. Má tedy smysl vytknout stav qubitu 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Pokud $f(0)=f(1)$, oba členy se transformují stejně a relativní znaménko mezi nimi zůstane kladné. Pokud však $f(0)\neq f(1)$, druhý člen získá záporné znaménko vůči prvnímu, čímž se stav qubitu 0 změní z $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ na $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Tedy:

$$|\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}$$

Jaký je stav $|\pi_3\rangle$?

Odpověď:

Stav qubitu 0 je nyní buď $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, nebo $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, v závislosti na funkci. Aplikace Hadamardovy brány vrátí buď $|0\rangle$, nebo $|1\rangle$.

$$|\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}$$

Při procházení svých odpovědí si všimni, že se děje něco poněkud překvapivého. Přestože $U_f$ explicitně nic nedělá se stavem qubitu 0, protože mění qubit 1 na základě stavu qubitu 0, může dojít k fázovému posunu qubitu 0. Tento jev se nazývá „phase kickback" a podrobněji je probírán v Lekci 1: Kvantové dotazovací algoritmy kurzu Základy kvantových algoritmů.

Teď, když rozumíme fungování tohoto algoritmu, implementujme ho pomocí Qiskitu.

## 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
).to_gate()  # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
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")

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

{'1': 1}
balanced

Algoritmus Deutscha a Jozsy

Deutschův algoritmus byl důležitým prvním krokem při demonstraci toho, jak by kvantový počítač mohl být efektivnější než klasický, ale byl to jen skromný pokrok: vyžadoval pouze jeden dotaz, zatímco v klasickém případě dva. V roce 1992 Deutsch a jeho kolega Richard Jozsa rozšířili původní dvouqubitový algoritmus na více qubitů. Problém zůstal stejný: určit, zda je funkce vyvážená, nebo konstantní. Tentokrát ale funkce zobrazuje $n$ bitů na jediný bit. Buď funkce vrací 0 a 1 stejný počet krát (je vyvážená), nebo funkce vrací vždy 1 nebo vždy 0 (je konstantní).

Zde je schéma obvodu algoritmu:

Tento algoritmus funguje stejně jako Deutschův algoritmus: phase kickback umožňuje přečíst stav qubitu 0 a určit, zda je funkce konstantní nebo vyvážená. Je to o něco složitější než v případě dvouqubitového Deutschova algoritmu, protože stavy budou zahrnovat součty přes $n$ qubitů, takže výpočet těchto stavů nechám jako volitelné cvičení pro tebe na konci tohoto modulu. Algoritmus vrátí bitový řetězec samých 0, pokud je funkce konstantní, a bitový řetězec obsahující alespoň jednu 1, pokud je funkce vyvážená.

Abychom viděli, jak algoritmus funguje v Qiskitu, nejprve potřebujeme vygenerovat náš orákul: náhodnou funkci, která je zaručeně buď konstantní, nebo vyvážená. Níže uvedený kód vygeneruje vyváženou funkci v 50 % případů a konstantní funkci v 50 % případů. Nezalekni se, pokud kódu úplně nerozumíš — je složitý a pro pochopení kvantového algoritmu není nutný.

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"))

Toto je orákulová funkce, která je buď vyvážená, nebo konstantní. Dokážeš pohledem na ni určit, zda výstup na posledním qubitu závisí na hodnotách vložených pro prvních $n$ qubitů? Pokud výstup pro poslední qubit závisí na prvních $n$ qubitech, dokážeš říct, jestli je tento závislý výstup vyvážený?

Zda je funkce vyvážená nebo konstantní, lze určit pohledem na výše uvedený obvod, ale vzpomeň si, že pro účely tohoto problému si tuto funkci představujeme jako „černou skříňku". Nemůžeme nahlédnout do skříňky a prohlédnout si schéma obvodu. Místo toho musíme skříňku dotazovat.

K dotazování skříňky použijeme algoritmus Deutscha a Jozsy a určíme, zda je funkce konstantní nebo vyvážená:

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")

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

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

{'110': 1}
balanced

Výše je na prvním řádku výstupu bitový řetězec výsledků měření. Na druhém řádku je uvedeno, zda bitový řetězec naznačuje, že funkce byla vyvážená nebo konstantní. Pokud by bitový řetězec obsahoval samé nuly, pak byla konstantní; pokud ne, byla vyvážená. Takže jediným spuštěním výše uvedeného kvantového obvodu dokážeme určit, zda je funkce konstantní nebo vyvážená!

Ověř si své znalosti

Přečti si níže uvedené otázky, zamysli se nad svými odpověďmi a poté klikni na trojúhelníky pro odkrytí řešení.

Kolik dotazů by klasický počítač potřeboval k tomu, aby se stoprocentní jistotou určil, zda je funkce konstantní nebo vyvážená? Vzpomeň si, že klasicky jediný dotaz umožňuje aplikovat funkci pouze na jeden bitový řetězec.

Odpověď:

Existuje $2^n$ možných bitových řetězců ke kontrole a v nejhorším případě bys musel otestovat $2^n/2+1$ z nich. Například pokud by funkce byla konstantní a ty bys stále měřil „1" jako výstup funkce, nemohl bys si být jistý, že je skutečně konstantní, dokud bys nezkontroloval více než polovinu výsledků. Do té doby by ses mohl jen smůlou stále trefovat na „1" u vyvážené funkce. Je to jako házet mincí znovu a znovu a pokaždé padnout na hlavu. Je to nepravděpodobné, ale ne nemožné.

Jak by se tvoje výše uvedená odpověď změnila, kdybys musel měřit jen do té doby, dokud jeden výsledek (vyvážený nebo konstantní) nebude pravděpodobnější než druhý? Kolik dotazů by to v tomto případě vyžadovalo?

Odpověď:

V tomto případě bys mohl jednoduše měřit dvakrát. Pokud jsou dvě měření různá, víš, že funkce je vyvážená. Pokud jsou dvě měření stejná, mohla by být vyvážená nebo konstantní. Pravděpodobnost, že je vyvážená při této sadě měření, je: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. To je méně než 1/2, takže je v tomto případě pravděpodobnější, že je funkce konstantní.

Algoritmus Deutscha a Jozsy tedy prokázal exponenciální zrychlení oproti deterministickému klasickému algoritmu (který vrací odpověď se stoprocentní jistotou), ale žádné výrazné zrychlení oproti pravděpodobnostnímu (který vrací výsledek, který je pravděpodobně správnou odpovědí).

Problém Bernsteina a Vazirani

V roce 1997 použili Ethan Bernstein a Umesh Vazirani algoritmus Deutscha a Jozsy k řešení konkrétnějšího, omezenějšího problému ve srovnání s problémem D-J. Místo pouhého rozlišování mezi dvěma různými třídami funkcí, jako v případě D-J, použili Bernstein a Vazirani algoritmus Deutscha a Jozsy k faktickému zjištění řetězce zakódovaného ve funkci. Zde je ten problém:

Funkce $f:\{0,1\}^n \rightarrow \{0,1\}$ stále bere $n$-bitový řetězec a vydává jediný bit. Ale nyní, namísto slibu, že funkce je vyvážená nebo konstantní, je nám slíbeno, že funkce je skalárním součinem vstupního řetězce $x$ a nějakého tajného $n$-bitového řetězce $s$, modulo 2. (Tento skalární součin modulo 2 se nazývá „binární skalární součin".) Problémem je zjistit, jaký je tajný $n$-bitový řetězec.

Jinak řečeno, dostaneme funkci černé skříňky $f: {0,1}^n \rightarrow {0,1}$, která splňuje $f(x) = s \cdot x$ pro nějaký řetězec $s$, a chceme tento řetězec $s$ zjistit.

Podívejme se na to, jak algoritmus D-J tento problém řeší:

1. Nejprve je Hadamardova hradla aplikována na $n$ vstupních qubitů a hradlo NOT plus Hadamard je aplikováno na výstupní qubit, čímž vznikne stav:

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

Stav qubitů 1 až $n$ lze zapsat jednodušeji jako součet přes všechny $2^n$ $n$-qubitových bázových stavů $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Sadu těchto bázových stavů nazýváme $\Sigma^n$. (Více podrobností najdeš v kurzu Fundamentals of Quantum Algorithms.)

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

2. Dále je na qubity aplikována hradla $U_f$. Tato hradla vezmou prvních n qubitů jako vstup (které jsou nyní v rovnoměrné superpozici všech možných n-bitových řetězců) a aplikují funkci $f(x)=s \cdot x$ na výstupní qubit, takže tento qubit je nyní ve stavu: $|- \oplus f(x)\rangle$. Díky mechanismu phase kickback zůstane stav tohoto qubitu nezměněn, ale některé členy ve stavu vstupního qubitu získají záporné znaménko:

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

3. Nyní jsou na qubity 0 až $n-1$ aplikována další Hadamardova hradla. Sledovat záporná znaménka v tomto případě může být složité. Je užitečné vědět, že aplikace vrstvy Hadamardů na $n$ qubitů ve standardním bázovém stavu $|x\rangle$ lze zapsat jako:

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

Stav se tedy stane:

$$|\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}$$

4. Dalším krokem je měření prvních $n$ bitů. Co ale změříme? Ukazuje se, že výše uvedený stav se zjednodušuje na: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, ale to vůbec není zřejmé. Pokud chceš projít matematiku, viz kurz Johna Watrouse Fundamentals of Quantum Algorithms. Podstatné je, že mechanismus phase kickback vede k tomu, že vstupní qubity jsou ve stavu $|s\rangle$. Abys zjistil, jaký byl tajný řetězec $s$, stačí tedy qubity změřit!

Ověř si své znalosti

Přečti si níže uvedené otázky, zamysli se nad svými odpověďmi a poté klikni na trojúhelníky pro odkrytí řešení.

Ověř, že stav z kroku 3 výše je skutečně stavem $|s\rangle$ pro speciální případ $n=1$.

Odpověď:

Když explicitně vypíšeš oba součty, měl bys dostat stav se čtyřmi členy (vynechme výstupní stav $|-\rangle$):

$$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

Pokud $s=0$, pak se první dva členy sčítají konstruktivně a poslední dva se ruší, čímž dostaneme $|\Psi\rangle = |0\rangle$. Pokud $s=1$, pak se poslední dva členy sčítají konstruktivně a první dva se ruší, čímž dostaneme $|\Psi\rangle = |1\rangle$. Takže v obou případech $|\Psi\rangle = |s\rangle$. Doufejme, že tento nejjednodušší případ ti dá pocit, jak funguje obecný případ s $n$ qubity: všechny členy, které nejsou $|s\rangle$, se navzájem ruší interferencí a zůstane pouze stav $|s\rangle$.

Jak může stejný algoritmus řešit jak problém Bernsteina a Vazirani, tak problém Deutscha a Jozsy? Aby to dávalo smysl, zamysli se nad funkcemi Bernsteina a Vazirani, které mají tvar $f(x) = s \cdot x$. Jsou tyto funkce také funkcemi Deutscha a Jozsy? Tedy urči, zda funkce tohoto tvaru splňují příslib problému Deutscha a Jozsy: že jsou buď konstantní, nebo vyvážené. Jak nám to pomáhá pochopit, jak stejný algoritmus řeší dva různé problémy?

Odpověď:

Každá funkce Bernsteina a Vazirani tvaru $f(x) = s \cdot x$ také splňuje příslib problému Deutscha a Jozsy: pokud s=00...00, pak je funkce konstantní (pro každý řetězec x vždy vrací 0). Pokud je s jakýkoli jiný řetězec, pak je funkce vyvážená. Aplikace algoritmu Deutscha a Jozsy na jednu z těchto funkcí tedy simultánně řeší oba problémy! Vrátí řetězec, a pokud je tento řetězec 00...00, víme, že je konstantní; pokud je v řetězci alespoň jedna „1", víme, že je vyvážená.

Také můžeme ověřit, že tento algoritmus úspěšně řeší problém Bernsteina a Vazirani jeho experimentálním otestováním. Nejprve vytvoříme funkci B-V, která žije uvnitř černé skříňky:

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

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")

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

{'0000': 1}

Takže jediným dotazem algoritmus Deutscha a Jozsy vrátí řetězec $s$ použitý ve funkci: $f(x)=x \cdot s$, když jej aplikujeme na problém Bernsteina a Vazirani. Klasickým algoritmem by bylo k řešení stejného problému potřeba $n$ dotazů.

Závěr

Doufáme, že zkoumáním těchto jednoduchých příkladů jsme ti dali lepší intuici pro to, jak jsou kvantové počítače schopny využít superpozici, provázanost a interferenci k dosažení své převahy nad klasickými počítači.

Algoritmus Deutscha a Jozsy má obrovský historický význam, protože byl prvním, který prokázal jakékoli zrychlení oproti klasickému algoritmu, ale bylo to pouze polynomiální zrychlení. Algoritmus Deutscha a Jozsy je jen začátkem tohoto příběhu.

Poté, co Bernstein a Vazirani použili algoritmus k řešení svého problému, použili jej jako základ pro složitější, rekurzivní problém nazvaný rekurzivní problém vzorkování Fourierovy transformace. Jejich řešení nabídlo super-polynomiální zrychlení oproti klasickým algoritmům. A ještě před Bernsteinem a Vazirani přišel Peter Shor se svým slavným algoritmem, který umožnil kvantovým počítačům faktorizovat velká čísla exponenciálně rychleji, než by mohl jakýkoli klasický algoritmus. Tyto výsledky společně ukázaly vzrušující příslib budoucích kvantových počítačů a podnítily fyziky a inženýry k tomu, aby tuto budoucnost proměnili v realitu.

Otázky

Instruktoři mohou požádat o verze těchto notebooků s odpověďovými klíči a pokyny pro zařazení do běžných učebních osnov vyplněním tohoto krátkého dotazníku o tom, jak jsou notebooky používány.

Klíčové pojmy

• algoritmy Deutscha a Deutscha-Jozsy používají kvantový paralelismus kombinovaný s interferencí k nalezení odpovědi na problém rychleji, než to dokáže klasický počítač.
• mechanismus phase kickback je protiintuitivní kvantový jev, který přenáší operace na jednom qubitu do fáze jiného qubitu. Algoritmy Deutscha a Deutscha-Jozsy tento mechanismus využívají.
• Algoritmus Deutscha a Jozsy nabízí polynomiální zrychlení oproti jakémukoli deterministickému klasickému algoritmu.
• Algoritmus Deutscha a Jozsy lze aplikovat na jiný problém, nazvaný problém Bernsteina a Vazirani, k nalezení skrytého řetězce zakódovaného ve funkci.

Pravda/nepravda

1. P/N Deutschův algoritmus je speciálním případem algoritmu Deutscha a Jozsy, kde je vstupem jediný qubit.
2. P/N Algoritmy Deutscha a Deutscha-Jozsy používají kvantovou superpozici a interferenci k dosažení své efektivity.
3. P/N Algoritmus Deutscha a Jozsy vyžaduje více vyhodnocení funkce k určení, zda je funkce konstantní nebo vyvážená.
4. P/N „Algoritmus Bernsteina a Vazirani" je ve skutečnosti stejný jako algoritmus Deutscha a Jozsy, aplikovaný na jiný problém.
5. P/N Algoritmus Bernsteina a Vazirani dokáže simultánně nalézt více tajných řetězců.

Krátké odpovědi

1. Jak dlouho by trvalo klasickému algoritmu řešit problém Deutscha a Jozsy v nejhorším případě?

2. Jak dlouho by trvalo klasickému algoritmu řešit problém Bernsteina a Vazirani? Jaké zrychlení nabízí algoritmus DJ v tomto případě?

3. Popiš mechanismus phase kickback a jak funguje při řešení problémů Deutscha-Jozsy a Bernsteina-Vazirani.

Výzva

1. Algoritmus Deutscha a Jozsy: Vzpomeň si, že výše jsi měl otázku, ve které jsi měl vypracovat mezilehlé qubitové stavy $\pi_1$ a $\pi_2$ Deutschova algoritmu. Udělej totéž pro mezilehlé $(n+1)$-qubitové stavy $\pi_1$ a $\pi_2$ algoritmu Deutscha a Jozsy, pro specifický případ $n=2$. Poté ověř, že $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, opět pro specifický případ $n=2$.