Algoritmul Deutsch-Jozsa

Pentru acest modul Qiskit în Săli de Clasă, studenții trebuie să aibă un mediu Python funcțional cu următoarele pachete instalate:

• qiskit v2.1.0 sau mai nou
• qiskit-ibm-runtime v0.40.1 sau mai nou
• qiskit-aer v0.17.0 sau mai nou
• qiskit.visualization
• numpy
• pylatexenc

Pentru a configura și instala pachetele de mai sus, consultă ghidul Instalează Qiskit. Pentru a rula joburi pe calculatoare cuantice reale, studenții vor trebui să-și creeze un cont IBM Quantum® urmând pașii din ghidul Configurează-ți contul IBM Cloud.

Acest modul a fost testat și a folosit patru secunde de timp QPU. Aceasta este doar o estimare. Utilizarea ta reală poate varia.

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

Urmărește prezentarea modulului de către Dr. Katie McCormick mai jos sau apasă aici pentru a o urmări pe YouTube.

---

Introducere

La începutul anilor 1980, fizicienii cuantici și informaticienii aveau o vagă intuiție că mecanica cuantică ar putea fi valorificată pentru a efectua calcule mult mai puternice decât cele ale calculatoarelor clasice. Raționamentul lor era acesta: este dificil pentru un calculator clasic să simuleze sisteme cuantice, dar un calculator cuantic ar trebui să o poată face mai eficient. Și dacă un calculator cuantic putea simula sisteme cuantice mai eficient, poate existau și alte sarcini pe care le-ar putea îndeplini mai eficient decât un calculator clasic.

Logica era solidă, dar detaliile rămâneau de elaborat. Totul a început în 1985, când David Deutsch a descris primul „calculator cuantic universal". În același articol, el a oferit primul exemplu de problemă pentru care un calculator cuantic putea rezolva ceva mai eficient decât un calculator clasic. Acest prim exemplu de jucărie este acum cunoscut drept „algoritmul lui Deutsch". Îmbunătățirea adusă de algoritmul lui Deutsch era modestă, dar Deutsch a colaborat cu Richard Jozsa câțiva ani mai târziu pentru a lărgi și mai mult decalajul dintre calculatoarele clasice și cele cuantice.

Acești algoritmi — cel al lui Deutsch și extensia Deutsch-Jozsa — nu sunt deosebit de utili, dar sunt totuși foarte importanți din câteva motive:

1. Din punct de vedere istoric, au fost printre primii algoritmi cuantici demonstrați că depășesc omologii lor clasici. Înțelegerea lor ne poate ajuta să înțelegem cum a evoluat gândirea comunității despre calculul cuantic de-a lungul timpului.
2. Ne pot ajuta să înțelegem unele aspecte ale răspunsului la o întrebare surprinzător de subtilă: Ce conferă putere calculului cuantic? Uneori, calculatoarele cuantice sunt comparate cu procesoare paralele masive, care scalează exponențial. Dar aceasta nu este chiar corect. Deși o parte a răspunsului la această întrebare constă în așa-numitul „paralelism cuantic", extragerea cât mai multor informații posibile într-o singură rulare este o artă subtilă. Algoritmii Deutsch și Deutsch-Jozsa arată cum se poate realiza acest lucru.

În acest modul, vom învăța despre algoritmul lui Deutsch, algoritmul Deutsch-Jozsa și ce ne învață acestea despre puterea calculului cuantic.

Paralelismul cuantic și limitele sale

O parte din puterea calculului cuantic provine din „paralelismul cuantic", care reprezintă, în esență, capacitatea de a efectua operații pe mai multe intrări în același timp, deoarece stările de intrare ale Qubit-urilor pot fi în superpoziție a mai multor stări clasic permise. CU TOATE ACESTEA, deși un Circuit cuantic ar putea evalua mai multe stări de intrare simultan, extragerea tuturor acelor informații dintr-o singură încercare este imposibilă.

Pentru a înțelege ce vreau să spun, să presupunem că avem un bit, $x$, și o funcție aplicată acelui bit, $f(x)$. Există patru funcții binare posibile care duc un singur bit la un alt bit:

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

Am vrea să aflăm care dintre aceste funcții (1-4) este $f(x)$-ul nostru. În mod clasic, ar trebui să rulăm funcția de două ori — o dată pentru $x=0$, o dată pentru $x=1$. Dar să vedem dacă putem face mai bine cu un Circuit cuantic. Putem afla despre funcție folosind următorul Gate:

Aici, Gate-ul $U_f$ calculează $f(x)$, unde $x$ este starea Qubit-ului 0, și o aplică Qubit-ului 1. Astfel, starea rezultată, $|x\rangle|y\oplus f(x)\rangle$, devine pur și simplu $|x\rangle|f(x)\rangle$ când $|y\rangle = |0\rangle$. Aceasta conține toate informațiile de care avem nevoie pentru a cunoaște funcția $f(x)$: Qubit-ul 0 ne spune ce este $x$, iar Qubit-ul 1 ne spune ce este $f(x)$. Deci, dacă inițializăm $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, atunci starea finală a ambelor Qubit-uri va fi: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Dar cum accesăm acele informații?

2.1. Încearcă pe Qiskit:

Folosind Qiskit, vom selecta aleatoriu una dintre cele patru funcții posibile de mai sus și vom rula Circuit-ul. Sarcina ta este să folosești măsurătorile Circuit-ului cuantic pentru a afla funcția în cât mai puține rulări posibil.

În acest prim experiment și pe tot parcursul modulului, vom folosi un cadru pentru calculul cuantic cunoscut sub numele de „Qiskit patterns", care împarte fluxurile de lucru în următorii pași:

• Pasul 1: Maparea intrărilor clasice la o problemă cuantică
• Pasul 2: Optimizarea problemei pentru execuție cuantică
• Pasul 3: Execuție folosind Qiskit Runtime Primitives
• Pasul 4: Post-procesare și analiză clasică

Să începem prin a încărca câteva pachete necesare, inclusiv primitivele Qiskit Runtime. Vom selecta și calculatorul cuantic cel mai puțin ocupat disponibil.

Mai jos există cod pentru salvarea credențialelor la prima utilizare. Asigură-te că ștergi aceste informații din notebook după ce le salvezi în mediul tău, astfel încât credențialele să nu fie accidental distribuite atunci când împarți notebook-ul. Consultă Configurează contul tău IBM Cloud și Inițializează serviciul într-un mediu neîncrezător pentru mai multe îndrumări.

# 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

Celula de mai jos îți va permite să comuti între utilizarea simulatorului și hardware-ul real pe tot parcursul notebook-ului. Recomandăm să o rulezi acum:

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

Acum că am încărcat pachetele necesare, putem continua cu fluxul de lucru Qiskit patterns. În pasul de mapare de mai jos, creăm mai întâi o funcție care selectează dintre cele patru funcții posibile ce iau un singur bit și returnează un alt 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")

În Circuit-ul de mai sus, Gate-ul Hadamard „H" ia Qubit-ul 0, care se află inițial în starea $|0\rangle$, și îl aduce în starea de superpoziție $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Apoi, $U_f$ evaluează funcția $f(x)$ și o aplică Qubit-ului 1.

Urmează să optimizăm și să transpilăm Circuit-ul pentru a fi rulat pe calculatorul cuantic:

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

În final, executăm Circuit-ul nostru transpilat pe calculatorul cuantic și vizualizăm rezultatele:

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

Cel de mai sus este o histogramă a rezultatelor noastre. În funcție de numărul de shots pe care ai ales să rulezi Circuit-ul la pasul 3 de mai sus, poți vedea una sau două bare, reprezentând stările măsurate ale celor doi Qubiți în fiecare shot. Ca întotdeauna cu Qiskit și în acest notebook, folosim notația „little endian", ceea ce înseamnă că stările Qubiților de la 0 la n sunt scrise în ordine crescătoare de la dreapta la stânga, astfel Qubit-ul 0 este întotdeauna cel mai la dreapta.

Astfel, deoarece Qubit-ul 0 se afla în stare de superpoziție, Circuit-ul a evaluat funcția pentru ambele $x=0$ și $x=1$ în același timp — ceva ce calculatoarele clasice nu pot face! Dar capcana apare atunci când vrem să aflăm ceva despre funcția $f(x)$ — când măsurăm Qubiții, le colapsăm starea. Dacă selectezi „shots = 1" pentru a rula Circuit-ul o singură dată, vei vedea o singură bară în histograma de mai sus, iar informațiile tale despre funcție vor fi incomplete.

Check your understanding

Read the question(s) below, think about your answer, then click the triangle to reveal the solution.

De câte ori trebuie să rulăm algoritmul de mai sus pentru a afla funcția $f(x)$? Este asta mai bun decât cazul clasic? Ai prefera un calculator clasic sau cuantic pentru a rezolva această problemă?

Răspuns:

Deoarece măsurătoarea va colapsa superpoziția și va returna o singură valoare, trebuie să rulăm Circuit-ul cel puțin de două ori pentru a obține ambele ieșiri ale funcției $f(0)$ și $f(1)$. În cel mai bun caz, performanța este la egalitate cu cea clasică, unde calculăm atât $f(0)$, cât și $f(1)$ în primele două interogări. Dar există șansa să fie nevoie să-l rulăm de mai mult de două ori, deoarece măsurătoarea finală este probabilistică și ar putea returna aceeași valoare $f(x)$ de două ori la rând. Aș prefera un calculator clasic în acest caz.

Astfel, deși paralelismul cuantic poate fi puternic atunci când este folosit în modul potrivit, nu este corect să spunem că un calculator cuantic funcționează exact ca un procesor paralel clasic masiv. Actul de măsurare colapsează stările cuantice, astfel că putem accesa întotdeauna o singură ieșire a calculului.

Algoritmul lui Deutsch

Deși paralelismul cuantic singur nu ne oferă un avantaj față de calculatoarele clasice, îl putem combina cu un alt fenomen cuantic — interferența — pentru a obține o accelerare. Algoritmul cunoscut acum sub numele de „algoritmul lui Deutsch" este primul exemplu de algoritm care realizează acest lucru.

Problema

Iată care era problema:

Dat un bit de intrare, $x = \{0,1\}$, și o funcție de intrare $f(x) = \{0,1\}$, determină dacă funcția este echilibrată sau constantă. Adică, dacă este echilibrată, atunci ieșirea funcției este 0 jumătate din timp și 1 cealaltă jumătate. Dacă este constantă, atunci ieșirea funcției este fie întotdeauna 0, fie întotdeauna 1. Reamintește-ți tabelul cu cele patru funcții posibile care iau un singur bit și returnează un alt bit:

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

Prima și ultima funcție, $f_1(x)$ și $f_4(x)$, sunt constante, în timp ce cele două funcții din mijloc, $f_2(x)$ și $f_3(x)$, sunt echilibrate.

Algoritmul

Modul în care Deutsch a abordat această problemă a fost prin „modelul de interogare". În modelul de interogare, funcția de intrare ($f_i(x)$ de mai sus) este conținută într-o „cutie neagră" — nu avem acces direct la conținutul ei, dar putem interoga cutia neagră și ne va oferi ieșirea funcției. Uneori spunem că un „oracol" furnizează aceste informații. Consultă Lecția 1: Algoritmi cuantici de interogare din cursul Fundamentele algoritmilor cuantici pentru mai multe detalii despre modelul de interogare.

Pentru a determina dacă un algoritm cuantic este mai eficient decât un algoritm clasic în modelul de interogare, putem compara pur și simplu numărul de interogări pe care trebuie să le facem cutiei negre în fiecare caz. În cazul clasic, pentru a ști dacă funcția conținută în cutia neagră este echilibrată sau constantă, ar trebui să interogăm cutia de două ori pentru a obține atât $f(0)$, cât și $f(1)$.

În algoritmul cuantic al lui Deutsch, însă, el a găsit o modalitate de a obține informația cu o singură interogare! A făcut o singură ajustare la Circuit-ul de „paralelism cuantic" de mai sus, astfel încât a pregătit o stare de superpoziție pe ambii Qubiți, nu doar pe Qubit-ul 0. Apoi, cele două ieșiri ale funcției, $f(0)$ și $f(1)$, au interferat pentru a returna 0 dacă erau ambele 0 sau ambele 1 (funcția era constantă), și au returnat 1 dacă erau diferite (funcția era echilibrată). În acest mod, Deutsch putea diferenția între o funcție constantă și una echilibrată cu o singură interogare.

Iată o diagramă a Circuit-ului algoritmului lui Deutsch:

Pentru a înțelege cum funcționează acest algoritm, să analizăm stările cuantice ale Qubiților în cele trei puncte notate pe diagrama de mai sus. Încearcă să determini singur stările înainte de a da click pentru a vedea răspunsurile:

Verifică-ți înțelegerea

Citește întrebările de mai jos, gândește-te la răspunsuri, apoi apasă pe triunghiuri pentru a vedea soluțiile.

Care este starea $|\pi_1\rangle$?

Răspuns:

Aplicarea unui Hadamard transformă starea $|0\rangle$ în $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ și starea $|1\rangle$ în $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Astfel, starea completă devine: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Care este starea $|\pi_2\rangle$?

Răspuns:

Înainte de a aplica $U_f$, să ne amintim ce face aceasta. Ea va schimba starea Qubitului 1 în funcție de starea Qubitului 0. Prin urmare, are sens să factorizăm starea Qubitului 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Apoi, dacă $f(0)=f(1)$, cele două termene se vor transforma la fel, iar semnul relativ dintre ele rămâne pozitiv; dar dacă $f(0)\neq f(1)$, înseamnă că al doilea termen va dobândi un semn minus față de primul, schimbând starea Qubitului 0 din $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ în $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Deci:

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

Care este starea $|\pi_3\rangle$?

Răspuns:

Acum, starea Qubitului 0 este fie $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, fie $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, în funcție de funcție. Aplicarea Hadamard va produce fie $|0\rangle$, fie $|1\rangle$, respectiv.

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

Analizând răspunsurile tale la întrebările de mai sus, observi că se întâmplă ceva oarecum surprinzător. Deși $U_f$ nu face nimic explicit asupra stării Qubitului 0, deoarece schimbă Qubitul 1 în funcție de starea Qubitului 0, se poate întâmpla ca acest lucru să cauzeze o schimbare de fază în Qubitul 0. Acest fenomen este cunoscut sub numele de „phase-kickback" și este discutat în detaliu în Lecția 1: Algoritmi de interogare cuantică din cursul Fundamentele Algoritmilor Cuantici.

Acum că înțelegem cum funcționează acest algoritm, hai să îl implementăm cu 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
).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

Algoritmul Deutsch-Jozsa

Algoritmul lui Deutsch a fost un prim pas important în demonstrarea modului în care un calculator cuantic ar putea fi mai eficient decât unul clasic, dar a reprezentat doar o îmbunătățire modestă: necesita o singură interogare, față de două în cazul clasic. În 1992, Deutsch și colegul său, Richard Jozsa, au extins algoritmul original de doi Qubiți la mai mulți Qubiți. Problema a rămas aceeași: să se determine dacă o funcție este echilibrată sau constantă. Dar de această dată, funcția mapează $n$ biți la un singur bit. Fie funcția returnează 0 și 1 un număr egal de ori (este echilibrată), fie returnează întotdeauna 1 sau întotdeauna 0 (este constantă).

Iată o diagramă de Circuit a algoritmului:

Acest algoritm funcționează în același mod ca algoritmul lui Deutsch: phase-kickback permite citirea stării Qubitului 0 pentru a determina dacă funcția este constantă sau echilibrată. Este puțin mai dificil de văzut decât în cazul algoritmului lui Deutsch cu doi Qubiți, deoarece stările vor include sume peste cei $n$ Qubiți; prin urmare, calcularea acestor stări va fi lăsată ca exercițiu opțional la sfârșitul modulului. Algoritmul va returna un șir de biți format din toate cifrele 0 dacă funcția este constantă, și un șir de biți ce conține cel puțin un 1 dacă funcția este echilibrată.

Pentru a vedea cum funcționează algoritmul în Qiskit, trebuie mai întâi să generăm oracle-ul nostru: funcția aleatoare care este garantat a fi fie constantă, fie echilibrată. Codul de mai jos va genera o funcție echilibrată în 50% din cazuri și o funcție constantă în celelalte 50%. Nu-ți face griji dacă nu înțelegi în totalitate codul — este complicat și nu este necesar pentru înțelegerea algoritmului cuantic.

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

Acesta este oracle-ul, care este fie echilibrat, fie constant. Poți determina, uitându-te la el, dacă ieșirea de pe ultimul Qubit depinde de valorile introduse pentru primii $n$ Qubiți? Dacă ieșirea de pe ultimul Qubit depinde de primii $n$ Qubiți, poți spune dacă acea ieșire dependentă este echilibrată sau nu?

Putem determina dacă funcția este echilibrată sau constantă uitându-ne la circuitul de mai sus, dar să nu uităm că, în cadrul acestei probleme, tratăm funcția ca pe o „cutie neagră". Nu putem privi înăuntrul cutiei pentru a vedea diagrama Circuit-ului. În schimb, trebuie să interogăm cutia.

Pentru a interoga cutia, folosim algoritmul Deutsch-Jozsa și determinăm dacă funcția este constantă sau echilibrată:

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

Mai sus, primul rând al ieșirii este șirul de biți al rezultatelor măsurătorilor. Al doilea rând afișează dacă șirul de biți implică faptul că funcția a fost echilibrată sau constantă. Dacă șirul de biți conținea numai zerouri, atunci era constantă; dacă nu, era echilibrată. Deci, cu o singură rulare a circuitului cuantic de mai sus, putem determina dacă funcția este constantă sau echilibrată!

Verifică-ți înțelegerea

Citește întrebările de mai jos, gândește-te la răspunsuri, apoi apasă pe triunghiuri pentru a vedea soluțiile.

Câte interogări ar necesita un calculator clasic pentru a determina cu 100% certitudine dacă o funcție este constantă sau echilibrată? Amintește-ți că, în mod clasic, o singură interogare îți permite să aplici funcția doar unui singur șir de biți.

Răspuns:

Există $2^n$ șiruri de biți posibile de verificat, iar în cel mai defavorabil caz ar trebui să testezi $2^n/2+1$ dintre ele. De exemplu, dacă funcția ar fi constantă și ai continua să măsori „1" ca ieșire a funcției, nu ai putea fi sigur că este cu adevărat constantă până nu ai verificat mai mult de jumătate din rezultate. Până atunci, s-ar putea să fi avut pur și simplu ghinion și să fi măsurat mereu „1" pe o funcție echilibrată. Este ca și cum ai arunca o monedă din nou și din nou și ar cădea mereu pe cap. Este puțin probabil, dar nu imposibil.

Cum s-ar schimba răspunsul tău de mai sus dacă ar trebui doar să măsori până când un rezultat (echilibrat sau constant) este mai probabil decât celălalt? Câte interogări ar fi necesare în acest caz?

Răspuns:

În acest caz, ai putea să măsori de doar două ori. Dacă cele două măsurători sunt diferite, știi că funcția este echilibrată. Dacă cele două măsurători sunt aceleași, atunci ar putea fi echilibrată sau ar putea fi constantă. Probabilitatea că este echilibrată cu acest set de măsurători este: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Aceasta este mai mică decât 1/2, deci în acest caz este mai probabil ca funcția să fie constantă.

Astfel, algoritmul Deutsch-Jozsa a demonstrat o accelerare exponențială față de un algoritm clasic determinist (unul care returnează răspunsul cu 100% certitudine), dar nicio accelerare semnificativă față de unul probabilist (unul care returnează un rezultat care este probabil răspunsul corect).

Problema Bernstein - Vazirani

În 1997, Ethan Bernstein și Umesh Vazirani au folosit algoritmul Deutsch-Jozsa pentru a rezolva o problemă mai specifică și mai restricționată față de problema Deutsch-Jozsa. În loc să încerce pur și simplu să distingă între două clase diferite de funcții, ca în cazul D-J, Bernstein și Vazirani au utilizat algoritmul Deutsch-Jozsa pentru a descoperi efectiv un șir codificat într-o funcție. Iată problema:

Funcția $f:\{0,1\}^n \rightarrow \{0,1\}$ primește în continuare un șir de $n$ biți și returnează un singur bit. Dar acum, în loc să promitem că funcția este echilibrată sau constantă, ni se promite că funcția este produsul scalar dintre șirul de intrare $x$ și un șir secret $s$ de $n$ biți, modulo 2. (Acest produs scalar modulo 2 se numește „produsul scalar binar".) Problema constă în a afla care este șirul secret de $n$ biți.

Formulând altfel, ni se dă o funcție cutie neagră $f: {0,1}^n \rightarrow {0,1}$ care satisface $f(x) = s \cdot x$ pentru un șir $s$, și vrem să găsim șirul $s$.

Să vedem cum rezolvă algoritmul D-J această problemă:

1. Mai întâi, un Gate Hadamard este aplicat celor $n$ Qubiți de intrare, iar un Gate NOT plus un Hadamard este aplicat Qubitului de ieșire, obținând starea:

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

Starea Qubiților de la 1 la $n$ poate fi scrisă mai simplu ca o sumă peste toate cele $2^n$ stări de bază ale celor $n$ Qubiți: $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Numim mulțimea acestor stări de bază $\Sigma^n$. (Vezi Fundamentals of Quantum Algorithms pentru mai multe detalii.)

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

2. Urmează aplicarea Gate-ului $U_f$ asupra Qubiților. Acest Gate preia primii $n$ Qubiți ca intrare (care se află acum în o suprapunere egală a tuturor șirurilor posibile de $n$ biți) și aplică funcția $f(x)=s \cdot x$ Qubitului de ieșire, astfel încât acesta se găsește acum în starea: $|- \oplus f(x)\rangle$. Datorită mecanismului de retroacțiune de fază, starea acestui Qubit rămâne neschimbată, dar unii termeni din starea Qubiților de intrare capătă un semn minus:

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

3. Acum, următorul set de Gate-uri Hadamard este aplicat Qubiților de la 0 la $n-1$. Urmărirea semnelor minus în acest caz poate fi dificilă. Este util să știi că aplicarea unui strat de Gate-uri Hadamard la $n$ Qubiți aflați într-o stare de bază standard $|x\rangle$ poate fi scrisă astfel:

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

Astfel, starea devine:

$$|\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. Pasul următor este măsurarea primilor $n$ biți. Dar ce vom măsura? Se dovedește că starea de mai sus se simplifică la: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, deși acest lucru nu este deloc evident. Dacă vrei să urmărești calculele matematice, consulta cursul lui John Watrous Fundamentals of Quantum Algorithms. Ideea esențială este că mecanismul de retroacțiune de fază face ca Qubiții de intrare să se afle în starea $|s\rangle$. Prin urmare, pentru a afla care era șirul secret $s$, trebuie pur și simplu să măsori Qubiții!

Verifică-ți înțelegerea

Citește întrebările de mai jos, gândește-te la răspunsuri, apoi apasă pe triunghiuri pentru a dezvălui soluțiile.

Verifică că starea din Pasul 3 de mai sus este într-adevăr starea $|s\rangle$ pentru cazul special $n=1$.

Răspuns:

Când scrii explicit cele două sume, ar trebui să obții o stare cu patru termeni (omitem starea de ieșire $|-\rangle$ pentru aceasta):

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

Dacă $s=0$, primii doi termeni se adună constructiv, iar ultimii doi termeni se anulează, lăsând $|\Psi\rangle = |0\rangle$. Dacă $s=1$, ultimii doi termeni se adună constructiv, iar primii doi termeni se anulează, lăsând $|\Psi\rangle = |1\rangle$. Deci, în oricare dintre cazuri, $|\Psi\rangle = |s\rangle$. Sperăm că acest caz cel mai simplu îți dă o intuiție despre cum funcționează cazul general cu $n$ Qubiți: toți termenii care nu sunt $|s\rangle$ interferează și dispar, lăsând doar starea $|s\rangle$.

Cum poate același algoritm să rezolve atât problemele Bernstein-Vazirani, cât și Deutsch-Jozsa? Pentru a înțelege acest lucru, gândește-te la funcțiile Bernstein-Vazirani, care au forma $f(x) = s \cdot x$. Sunt acestea și funcții Deutsch-Jozsa? Mai precis, determină dacă funcțiile de această formă satisfac promisiunea problemei Deutsch-Jozsa: că sunt fie constante, fie echilibrate. Cum ne ajută aceasta să înțelegem cum rezolvă același algoritm două probleme diferite?

Răspuns:

Orice funcție Bernstein-Vazirani de forma $f(x) = s \cdot x$ satisface și promisiunea problemei Deutsch-Jozsa: dacă s=00...00, atunci funcția este constantă (returnează întotdeauna 0 pentru orice șir x). Dacă s este orice alt șir, atunci funcția este echilibrată. Prin urmare, aplicarea algoritmului Deutsch-Jozsa uneia dintre aceste funcții rezolvă simultan ambele probleme! Returnează șirul, iar dacă acel șir este 00...00, atunci știm că funcția este constantă; dacă există cel puțin un „1" în șir, știm că funcția este echilibrată.

Putem de asemenea verifica experimental că acest algoritm rezolvă cu succes problema Bernstein-Vazirani. Mai întâi, creăm funcția B-V care se află în interiorul cutiei negre:

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

Astfel, cu o singură interogare, algoritmul Deutsch-Jozsa va returna șirul $s$ folosit în funcție: $f(x)=x \cdot s$ atunci când îl aplicăm la problema Bernstein-Vazirani. Cu un algoritm clasic, ar fi necesare $n$ interogări pentru a rezolva aceeași problemă.

Concluzie

Sperăm că, examinând aceste exemple simple, ți-am oferit o intuiție mai bună despre modul în care calculatoarele cuantice pot valorifica suprapunerea, entanglementul și interferența pentru a obține puterea lor față de calculatoarele clasice.

Algoritmul Deutsch-Jozsa are o importanță istorică uriașă, deoarece a fost primul care a demonstrat orice accelerare față de un algoritm clasic, dar a fost doar o accelerare polinomială. Algoritmul Deutsch-Jozsa este doar începutul poveștii.

După ce au folosit algoritmul pentru a-și rezolva problema, Bernstein și Vazirani l-au folosit ca bază pentru o problemă mai complexă, recursivă, numită problema de eșantionare Fourier recursivă. Soluția lor a oferit o accelerare super-polinomială față de algoritmii clasici. Și chiar înainte de Bernstein și Vazirani, Peter Shor elaborase deja celebrul său algoritm care le permitea calculatoarelor cuantice să factorizeze numere mari exponențial mai rapid decât orice algoritm clasic. Aceste rezultate, colectiv, au arătat promisiunea captivantă a viitoarelor calculatoare cuantice și i-au îndemnat pe fizicieni și ingineri să transforme acest viitor în realitate.

Întrebări

Instructorii pot solicita versiuni ale acestor notebook-uri cu chei de răspuns și ghiduri de plasare în curricule comune completând acest chestionar rapid despre modul în care sunt utilizate notebook-urile.

Concepte esențiale

• Algoritmii Deutsch și Deutsch-Jozsa folosesc paralelismul cuantic combinat cu interferența pentru a găsi un răspuns la o problemă mai rapid decât poate face un calculator clasic.
• Mecanismul de retroacțiune de fază este un fenomen cuantic contraintuitiv care transferă operațiunile efectuate pe un Qubit la faza unui alt Qubit. Algoritmii Deutsch și Deutsch-Jozsa utilizează acest mecanism.
• Algoritmul Deutsch-Jozsa oferă o accelerare polinomială față de orice algoritm clasic determinist.
• Algoritmul Deutsch-Jozsa poate fi aplicat unei probleme diferite, numită problema Bernstein-Vazirani, pentru a găsi un șir ascuns codificat într-o funcție.

Adevărat/fals

1. A/F Algoritmul lui Deutsch este un caz special al algoritmului Deutsch-Jozsa în care intrarea este un singur Qubit.
2. A/F Algoritmii Deutsch și Deutsch-Jozsa folosesc suprapunerea cuantică și interferența pentru a-și atinge eficiența.
3. A/F Algoritmul Deutsch-Jozsa necesită mai multe evaluări ale funcției pentru a determina dacă o funcție este constantă sau echilibrată.
4. A/F „Algoritmul Bernstein-Vazirani" este de fapt același cu algoritmul Deutsch-Jozsa, aplicat unei probleme diferite.
5. A/F Algoritmul Bernstein-Vazirani poate găsi simultan mai multe șiruri secrete.

Răspuns scurt

1. Cât timp ar dura unui algoritm clasic să rezolve problema Deutsch-Jozsa în cel mai defavorabil caz?

2. Cât timp ar dura unui algoritm clasic să rezolve problema Bernstein-Vazirani? Ce accelerare oferă algoritmul DJ în acest caz?

3. Descrie mecanismul de retroacțiune de fază și modul în care funcționează pentru a rezolva problemele Deutsch-Jozsa și Bernstein-Vazirani.

Problemă de provocare

1. Algoritmul Deutsch-Jozsa: Reamintește-ți că mai sus ai avut o întrebare care te ruga să calculezi stările intermediare ale Qubiților $\pi_1$ și $\pi_2$ ale algoritmului lui Deutsch. Fă același lucru pentru stările intermediare ale celor $n+1$ Qubiți, $\pi_1$ și $\pi_2$, ale algoritmului Deutsch-Jozsa, pentru cazul specific $n=2$. Apoi, verifică că $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, din nou, pentru cazul specific $n=2$.