Ang Deutsch-Jozsa algorithm

Para sa Qiskit in Classrooms module na ito, kailangang may gumaganang Python environment ang mga estudyante na may mga sumusunod na naka-install na package:

• qiskit v2.1.0 o mas bago
• qiskit-ibm-runtime v0.40.1 o mas bago
• qiskit-aer v0.17.0 o mas bago
• qiskit.visualization
• numpy
• pylatexenc

Para i-set up at i-install ang mga package sa itaas, tingnan ang gabay na I-install ang Qiskit. Para makapag-run ng mga job sa tunay na quantum computer, kailangang mag-set up ng account sa IBM Quantum® ang mga estudyante sa pamamagitan ng pagsunod sa mga hakbang sa gabay na I-set up ang iyong IBM Cloud account.

Ang module na ito ay nasubok at gumamit ng apat na segundo ng QPU time. Tantiya lang ito. Maaaring mag-iba ang iyong aktwal na paggamit.

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

Panoorin ang walkthrough ng module ni Dr. Katie McCormick sa ibaba, o i-click ang dito para panoorin ito sa YouTube.

---

Panimula

Noong unang bahagi ng 1980's, may malabo na ideya ang mga quantum physicist at computer scientist na maaaring gamitin ang quantum mechanics para gumawa ng mga kalkulasyon na mas makapangyarihan kaysa sa klasikal na mga computer. Ganito ang kanilang pangangatwiran: mahirap para sa isang klasikal na computer na i-simulate ang mga quantum system, ngunit ang isang quantum computer ay dapat na makayanang gawin ito nang mas mahusay. At kung kaya ng isang quantum computer na i-simulate ang mga quantum system nang mas mahusay, marahil ay mayroon pang ibang mga gawain na mas mahusay nitong magagawa kaysa sa klasikal na computer.

Makatuwiran ang lohika, ngunit ang mga detalye ay kailangang linawin pa. Nagsimula ito noong 1985, nang ilarawan ni David Deutsch ang unang "universal quantum computer." Sa parehong papel na iyon, nagbigay siya ng unang halimbawang problema kung saan mas mahusay na malulutas ng isang quantum computer kaysa sa isang klasikal na computer. Ang unang halimbawang ito ay kilala na ngayon bilang "Deutsch's algorithm." Katamtaman lang ang pagpapabuti sa Deutsch's algorithm, ngunit nakipagtulungan si Deutsch kay Richard Jozsa ilang taon pagkatapos para higit na palawakin ang agwat sa pagitan ng klasikal at quantum na mga computer.

Ang mga algorithm na ito — ang kay Deutsch, at ang Deutsch-Jozsa extension — ay hindi partikular na kapaki-pakinabang, ngunit mahalaga pa rin ang mga ito sa ilang dahilan:

1. Sa kasaysayan, ilan sila sa mga unang quantum algorithm na naipakitang mas mahusay kaysa sa kanilang mga katumbas na klasikal. Ang pag-unawa sa mga ito ay makakatulong sa atin na maunawaan kung paano naging-iba ang pag-iisip ng komunidad sa quantum computing sa paglipas ng panahon.
2. Makakatulong ang mga ito sa atin na maunawaan ang ilang aspeto ng sagot sa isang sorpresibong maselan na tanong: Ano ang nagbibigay ng kapangyarihan sa quantum computing? Minsan, ang mga quantum computer ay inihahambing sa mga napakalaking, exponentially-scaling na parallel processor. Ngunit hindi ito tama. Kahit ang bahagi ng sagot sa tanong na ito ay nasa tinatawag na "quantum parallelism," ang pag-extract ng pinakamaraming impormasyon hangga't maaari sa iisang takbo ay isang malikhaing sining. Ang Deutsch at Deutsch-Jozsa algorithm ay nagpapakita kung paano ito maaaring gawin.

Sa module na ito, matututunan natin ang Deutsch's algorithm, ang Deutsch-Jozsa algorithm, at kung ano ang itinuturo nila sa atin tungkol sa kapangyarihan ng quantum computing.

Quantum parallelism at ang mga limitasyon nito

Bahagi ng kapangyarihan ng quantum computing ay nagmumula sa "quantum parallelism," na sa esensya ay ang kakayahang magsagawa ng mga operasyon sa maraming input nang sabay-sabay, dahil ang mga qubit input state ay maaaring nasa superposition ng maraming klasikal na pinapayagang estado. GAYUNPAMAN, kahit na maaaring masuri ng isang quantum Circuit ang maraming input state nang sabay-sabay, imposible ang pag-extract ng lahat ng impormasyong iyon sa iisang pagkakataon.

Para maunawaan ang ibig kong sabihin dito, sabihin nating mayroon tayong isang bit, $x$ at ilang function na inilapat sa bit na iyon, $f(x)$. May apat na posibleng binary function na kumukuha ng iisang bit at nagbibigay ng iisang bit:

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

Gusto naming malaman kung alin sa mga function na ito (1-4) ang ating $f(x)$. Klasikal na, kailangan nating patakbuhin ang function nang dalawang beses — isang beses para sa $x=0$, isang beses para sa $x=1$. Ngunit tingnan natin kung kaya nating gumawa ng mas mahusay gamit ang isang quantum Circuit. Maaari tayong matuto tungkol sa function gamit ang sumusunod na Gate:

Dito, ang $U_f$ Gate ay nagkukwenta ng $f(x)$, kung saan ang $x$ ay ang estado ng qubit 0, at inilalapat iyon sa qubit 1. Kaya, ang resultang estado, $|x\rangle|y\oplus f(x)\rangle$, ay magiging simpleng $|x\rangle|f(x)\rangle$ kapag $|y\rangle = |0\rangle$. Naglalaman ito ng lahat ng impormasyong kailangan natin para malaman ang function $f(x)$: sinasabi sa atin ng qubit 0 kung ano ang $x$, at sinasabi sa atin ng qubit 1 kung ano ang $f(x)$. Kaya, kung i-initialize natin ang $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, ang panghuling estado ng parehong qubit ay magiging: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Ngunit paano natin maa-access ang impormasyong iyon?

2.1. Subukan sa Qiskit:

Gamit ang Qiskit, random naming pipiliin ang isa sa apat na posibleng function sa itaas at patakbuhin ang Circuit. Pagkatapos, ang iyong gawain ay gamitin ang mga sukat ng quantum Circuit para malaman ang function sa pinakamaliit na bilang ng mga takbo.

Sa unang eksperimentong ito at sa buong module, gagamit tayo ng balangkas para sa quantum computing na kilala bilang "Qiskit patterns," na binabasag ang mga workflow sa mga sumusunod na hakbang:

• Hakbang 1: I-map ang mga klasikal na input sa isang quantum na problema
• Hakbang 2: I-optimize ang problema para sa quantum na pagpapatupad
• Hakbang 3: Isagawa gamit ang Qiskit Runtime Primitives
• Hakbang 4: Post-processing at klasikal na pagsusuri

Magsimula tayo sa pag-load ng ilang kinakailangang package, kabilang ang mga Qiskit Runtime primitive. Pipili rin tayo ng pinaka-hindi abala na quantum computer na available sa atin.

Mayroong code sa ibaba para sa pag-save ng iyong mga kredensyal sa unang paggamit. Tiyaking burahin ang impormasyong ito mula sa notebook pagkatapos itong i-save sa iyong environment, para hindi aksidenteng mabahagi ang iyong mga kredensyal kapag ibinabahagi mo ang notebook. Tingnan ang I-set up ang iyong IBM Cloud account at I-initialize ang serbisyo sa isang hindi pinagkakatiwalaang environment para sa karagdagang gabay.

# 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

Ang cell sa ibaba ay magbibigay-daan sa iyo na lumipat sa pagitan ng paggamit ng simulator o tunay na hardware sa buong notebook. Inirerekomenda naming patakbuhin ito ngayon:

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

Ngayon na na-load na natin ang mga kinakailangang package, maaari na tayong magpatuloy sa Qiskit patterns workflow. Sa hakbang ng mapping sa ibaba, gumagawa muna tayo ng function na pumipili sa apat na posibleng function na kumukuha ng iisang bit at nagbibigay ng iisang 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")

Sa Circuit sa itaas, ang Hadamard Gate na "H" ay kumukuha ng qubit 0, na nasa estado $|0\rangle$ sa simula, at dinadala ito sa superposition state na $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Pagkatapos, sinusuri ng $U_f$ ang function $f(x)$ at inilalapat iyon sa qubit 1.

Susunod, kailangan nating i-optimize at i-transpile ang Circuit para mapatakbo sa quantum computer:

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

Sa wakas, pinapatakbo natin ang ating na-transpile na Circuit sa quantum computer at binibiswal ang ating mga resulta:

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

Ang nasa itaas ay isang histogram ng ating mga resulta. Depende sa bilang ng shots na pinili mong patakbuhin sa Circuit sa hakbang 3 sa itaas, maaari kang makakita ng isa o dalawang bar, na kumakatawan sa mga sinusukat na estado ng dalawang qubit sa bawat shot. Tulad ng lagi sa Qiskit at sa notebook na ito, gumagamit tayo ng notasyong "little endian," ibig sabihin ang mga estado ng qubit 0 hanggang n ay nakasulat sa pataas na pagkakasunod-sunod mula kanan hanggang kaliwa, kaya ang qubit 0 ay laging pinakamalayo sa kanan.

Kaya, dahil nasa superposition state ang qubit 0, sinuri ng Circuit ang function para sa parehong $x=0$ at $x=1$ nang sabay-sabay — isang bagay na hindi kaya ng mga klasikal na computer! Ngunit ang problema ay darating kapag gusto nating malaman ang function $f(x)$ — kapag sinusukat natin ang mga qubit, nag-co-collapse ang kanilang estado. Kung pipili ka ng "shots = 1" para patakbuhin lang ang Circuit nang isang beses, isang bar lang ang makikita mo sa histogram sa itaas, at ang iyong impormasyon tungkol sa function ay magiging hindi kumpleto.

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong sagot, pagkatapos i-click ang tatsulok para makita ang solusyon.

Ilang beses kailangang patakbuhin ang algorithm sa itaas para malaman ang function $f(x)$? Mas magaling ba ito kaysa sa klasikal na kaso? Mas gusto mo bang gumamit ng klasikal o quantum na computer para malutas ang problemang ito?

Sagot:

Dahil mag-co-collapse ang superposition kapag sinusukat at ibabalik lang ang isang halaga, kailangan nating patakbuhin ang Circuit nang hindi bababa sa dalawang beses para maibalik ang parehong output ng function na $f(0)$ at $f(1)$. Sa pinakamainam, magiging katumbas ito ng klasikal na kaso, kung saan kinukwenta natin ang $f(0)$ at $f(1)$ sa unang dalawang query. Ngunit may posibilidad na kailangan nating patakbuhin ito nang higit sa dalawang beses, dahil ang huling sukat ay probabilistiko at maaaring makabalik ng parehong $f(x)$ na halaga sa unang dalawang beses. Sa kasong ito, mas pipiliin ko ang klasikal na computer.

Kaya, habang maaaring maging makapangyarihan ang quantum parallelism kapag ginamit nang tama, hindi tama na sabihing gumagana ang isang quantum computer tulad ng isang napakalaking, klasikal na parallel processor. Ang pagsukat ay nagko-collapse ng mga quantum state, kaya isang output lang ng kalkulasyon ang maaari nating ma-access sa bawat pagkakataon.

Ang Deutsch's algorithm

Habang ang quantum parallelism lamang ay hindi nagbibigay sa atin ng kalamangan sa mga klasikal na computer, maaari nating ipares ito sa isa pang quantum na penomenon, ang interference, para makamit ang speed-up. Ang algorithm na kilala ngayon bilang "Deutsch's algorithm" ay ang unang halimbawa ng isang algorithm na nagagawa ito.

Ang problema

Narito ang problema:

Binibigyan ng input bit, $x = \{0,1\}$, at isang input function $f(x) = \{0,1\}$, tukuyin kung ang function ay balanced o constant. Ibig sabihin, kung balanced ito, ang output ng function ay 0 sa kalahati ng oras at 1 sa kabilang kalahati. Kung constant, ang output ng function ay palaging 0 o palaging 1. Alalahanin ang talahanayan ng apat na posibleng function na kumukuha ng iisang bit at nagbibigay ng iisang bit:

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

Ang una at huling function, $f_1(x)$ at $f_4(x)$, ay constant, habang ang dalawang gitnang function, $f_2(x)$ at $f_3(x)$, ay balanced.

Ang algorithm

Ang paraan ng pagtugon ni Deutsch sa problemang ito ay sa pamamagitan ng "query model." Sa query model, ang input function ($f_i(x)$ sa itaas) ay nakalagay sa isang "black box" — wala tayong direktang access sa nilalaman nito, ngunit maaari tayong mag-query sa black box at ibibigay nito sa atin ang output ng function. Minsan sinasabi nating ang isang "oracle" ang nagbibigay ng impormasyong ito. Tingnan ang Lesson 1: Quantum Query Algorithms ng Fundamentals of Quantum Algorithms course para sa karagdagang impormasyon tungkol sa query model.

Para matukoy kung mas mahusay ang isang quantum algorithm kaysa sa isang klasikal na algorithm sa query model, maaari tayong ihambing lang ang bilang ng mga query na kailangan nating gawin sa black box sa bawat kaso. Sa klasikal na kaso, para malaman kung ang function na nakalagay sa black box ay balanced o constant, kailangan nating mag-query sa box nang dalawang beses para makuha ang $f(0)$ at $f(1)$.

Sa quantum algorithm ni Deutsch, nakahanap siya ng paraan para makuha ang impormasyon sa iisang query lang! Gumawa siya ng isang pagbabago sa "quantum parallelism" Circuit sa itaas, kung saan naghanda siya ng superposition state sa parehong qubit, sa halip na sa qubit 0 lang. Pagkatapos, ang dalawang output ng function, $f(0)$ at $f(1)$, ay nag-interfere para maibalik ang 0 kung kapwa sila 0 o kapwa 1 (ang function ay constant), at nagbabalik ng 1 kung magkaiba ang mga ito (ang function ay balanced). Sa ganitong paraan, kaya ni Deutsch na makilala ang pagitan ng isang constant at balanced na function sa iisang query.

Narito ang circuit diagram ng Deutsch's algorithm:

Para maunawaan kung paano gumagana ang algorithm na ito, tingnan natin ang mga quantum state ng mga qubit sa tatlong puntong nakasaad sa diagram sa itaas. Subukang alamin ang mga estado nang ikaw mismo bago i-click para makita ang mga sagot:

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong mga sagot, pagkatapos i-click ang mga tatsulok para makita ang mga solusyon.

Ano ang estado na $|\pi_1\rangle$?

Sagot:

Ang pag-apply ng Hadamard ay nagbabago ng estado $|0\rangle$ sa $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ at ng estado $|1\rangle$ sa $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Kaya, ang buong estado ay nagiging: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Ano ang estado na $|\pi_2\rangle$?

Sagot:

Bago natin i-apply ang $U_f$, tandaan kung ano ang ginagawa nito. Babaguhin nito ang estado ng qubit 1 batay sa estado ng qubit 0. Kaya, makatuwirang i-factor out ang estado ng qubit 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Pagkatapos, kung $f(0)=f(1)$, ang dalawang termino ay mag-tatransform nang parehong paraan at ang relatibong sign sa pagitan ng dalawang termino ay mananatiling positibo, ngunit kung $f(0)\neq f(1)$, nangangahulugan iyon na ang pangalawang termino ay kukuha ng minus sign kaugnay ng unang termino, binabago ang estado ng qubit 0 mula $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ patungong $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Kaya:

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

Ano ang estado na $|\pi_3\rangle$?

Sagot:

Ngayon, ang estado ng qubit 0 ay alinman sa $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ o $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, depende sa function. Ang pag-apply ng Hadamard ay magbubunga ng $|0\rangle$ o $|1\rangle$, ayon sa pagkakasunod.

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

Sa pagbabasa ng iyong mga sagot para sa mga tanong sa itaas, pansinin na may isang medyo nakakagulat na bagay na nangyayari. Kahit na ang $U_f$ ay hindi explicitly gumagawa ng anuman sa estado ng qubit 0, dahil binabago nito ang qubit 1 batay sa estado ng qubit 0, maaaring mangyari na nagdudulot ito ng phase shift sa qubit 0. Ito ay kilala bilang penomenong "phase-kickback," at tinatalakay nang mas detalyado sa Lesson 1: Quantum Query Algorithms ng Fundamentals of Quantum Algorithms course.

Ngayon na naiintindihan natin kung paano gumagana ang algorithm na ito, ipatupad natin ito gamit ang 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

Ang Deutsch-Jozsa algorithm

Ang algorithm ni Deutsch ay isang mahalagang unang hakbang sa pagpapakita kung paano maaaring mas mahusay ang isang quantum computer kaysa sa isang klasikal na computer, pero limitado lang ang pagpapabuti: isang query lang ang kailangan nito, kumpara sa dalawa sa klasikal na kaso. Noong 1992, pinalawak ni Deutsch at ng kanyang kasamahang si Richard Jozsa ang orihinal na two-qubit algorithm para sa mas maraming Qubit. Nananatili ang problema: tukuyin kung ang isang function ay balanced o constant. Pero ngayon, ang function ay mula sa $n$ bits patungo sa isang bit. Maaaring nagbabalik ang function ng 0 at 1 nang pantay (ito ay balanced), o laging nagbabalik ng 1 o laging 0 (ito ay constant).

Narito ang circuit diagram ng algorithm:

Gumagana ang algorithm na ito sa parehong paraan ng algorithm ni Deutsch: nagbibigay-daan ang phase-kickback na mabasa ang estado ng Qubit 0 para matukoy kung constant o balanced ang function. Medyo mas mahirap itong makita kaysa sa two-qubit na kaso ng Deutsch's algorithm, dahil maglalaman ang mga estado ng mga kabuuan sa $n$ na Qubit — kaya ang pagkalkula ng mga estado na iyon ay iiwan bilang opsyonal na ehersisyo para sa iyo sa katapusan ng module. Ang algorithm ay magbabalik ng bitstring na puro 0 kung ang function ay constant, at isang bitstring na may kahit isang 1 kung ang function ay balanced.

Para makita kung paano gumagana ang algorithm sa Qiskit, una, kailangan nating buuin ang ating oracle: ang random na function na garantisadong constant o balanced. Ang code sa ibaba ay magrerehistro ng balanced na function 50% ng pagkakataon, at isang constant na function 50% ng pagkakataon. Huwag mag-alala kung hindi mo ganap na naiintindihan ang code — ito ay kumplikado at hindi kinakailangan para sa ating pag-unawa sa quantum algorithm.

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

Ito ang oracle function, na maaaring balanced o constant. Makikita mo ba sa pamamagitan ng pagtingin sa Circuit na ito kung ang output sa huling Qubit ay nakasalalay sa mga value na inilagay para sa unang $n$ na Qubit? Kung ang output para sa huling Qubit ay nakasalalay sa unang $n$ na Qubit, masasabi mo ba kung ang dependent na output na iyon ay balanced o hindi?

Masasabi natin kung balanced o constant ang function sa pamamagitan ng pagtingin sa Circuit sa itaas, pero tandaan, para sa layunin ng problemang ito, inaakalang ito ay isang "black box." Hindi tayo maaaring sumilip sa loob ng box para makita ang circuit diagram. Sa halip, kailangan nating mag-query sa box.

Para mag-query sa box, ginagamit natin ang Deutsch-Jozsa algorithm at tinutukoy kung constant o balanced ang function:

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

Sa itaas, ang unang linya ng output ay ang bitstring ng mga resulta ng pagsukat. Ang pangalawang linya ay nagpapakita kung ang bitstring ay nagpapahiwatig na ang function ay balanced o constant. Kung ang bitstring ay naglalaman ng lahat ng zero, constant ito; kung hindi, balanced ito. Kaya, sa iisang run lang ng quantum circuit sa itaas, matutukoy natin kung constant o balanced ang function!

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong mga sagot, at i-click ang mga tatsulok para makita ang mga solusyon.

Ilang query ang kakailanganin ng isang klasikal na computer para matukoy nang 100% na katiyakan kung ang isang function ay constant o balanced? Tandaan, klasikal na, ang isang query ay nagbibigay-daan lamang sa iyo na ilapat ang function sa isang solong bitstring.

Sagot:

Mayroong $2^n$ posibleng bitstring na dapat suriin, at sa pinakamasamang kaso, kakailanganin mong subukan ang $2^n/2+1$ sa mga ito. Halimbawa, kung constant ang function, at patuloy kang nakakakuha ng "1" bilang output ng function, hindi ka magiging tiyak na talagang constant ito hanggang sa masuri mo ang mahigit kalahati ng mga resulta. Bago noon, maaari ka lang malas na patuloy na nakakakuha ng "1" sa isang balanced na function. Parang paulit-ulit na pagpupukpok ng barya at laging lupalop. Unlikely, pero posible.

Paano magbabago ang iyong sagot sa itaas kung kailangan mo lang magsukat hanggang ang isang resulta (balanced o constant) ay mas malamang kaysa sa isa pa? Ilang query ang kakailanganin sa kasong ito?

Sagot:

Sa kasong ito, maaari kang magsukat nang dalawang beses lang. Kung magkaiba ang dalawang sukat, alam mong balanced ang function. Kung magkapareho ang dalawang sukat, maaaring balanced o constant ito. Ang posibilidad na balanced ito batay sa set ng mga sukat na ito ay: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Ito ay mas mababa sa 1/2, kaya mas malamang na constant ang function sa kasong ito.

Kaya, nagpakita ang Deutsch-Jozsa algorithm ng exponential na pagpapabilis kumpara sa isang deterministic na klasikal na algorithm (isa na nagbabalik ng sagot nang may 100% na katiyakan), pero walang makabuluhang pagpapabilis kumpara sa isang probabilistic na algorithm (isa na nagbabalik ng resulta na malamang tamang sagot).

Ang problema ng Bernstein-Vazirani

Noong 1997, ginamit nina Ethan Bernstein at Umesh Vazirani ang Deutsch-Jozsa algorithm para malutas ng isang mas tiyak at limitadong problema kumpara sa problema ng Deutsch-Jozsa. Sa halip na subukang makilala lang ang pagitan ng dalawang iba't ibang klase ng function, tulad ng kaso ng D-J, ginamit nina Bernstein at Vazirani ang Deutsch-Jozsa algorithm para aktwal na matutunan ang isang string na naka-encode sa isang function. Narito ang problema:

Ang function $f:\{0,1\}^n \rightarrow \{0,1\}$ ay tumatanggap pa rin ng $n$-bit string at nagbubunga ng isang bit. Pero ngayon, sa halip na ipangako na ang function ay balanced o constant, ipinangako naman natin na ang function ay ang dot product ng input string $x$ at ng ilang lihim na $n$-bit string $s$, modulo 2. (Ang dot product modulo 2 na ito ay tinatawag na "binary dot product.") Ang problema ay alamin kung ano ang lihim na $n$-bit string.

Sa ibang salita, binibigyan tayo ng isang black-box function $f: {0,1}^n \rightarrow {0,1}$ na nagsasatisfy ng $f(x) = s \cdot x$ para sa ilang string $s$, at gusto nating matutunan ang string $s$.

Tingnan natin kung paano niresolba ng D-J algorithm ang problemang ito:

1. Una, inilalapat ang isang Hadamard Gate sa $n$ na input Qubit, at isang NOT Gate kasama ang isang Hadamard ang inilalapat sa output Qubit, na ginagawang estado:

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

Ang estado ng Qubit 1 hanggang $n$ ay maaaring isulat nang mas simple bilang kabuuan sa lahat ng $2^n$ na $n$-Qubit basis state na $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Tinatawag natin ang set ng mga basis state na ito na $\Sigma^n$. (Tingnan ang Fundamentals of Quantum Algorithms para sa mas detalyadong impormasyon.)

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

2. Susunod, inilalapat ang $U_f$ Gate sa mga Qubit. Gagamitin ng Gate na ito ang unang n na Qubit bilang input (na ngayon ay nasa pantay na superposisyon ng lahat ng posibleng n-bit string) at inilalapat ang function na $f(x)=s \cdot x$ sa output Qubit, para ang Qubit na ito ay nasa estado na: $|- \oplus f(x)\rangle$. Salamat sa mekanismo ng phase kickback, ang estado ng Qubit na ito ay nananatiling hindi nagbabago, pero ang ilan sa mga termino sa estado ng input Qubit ay nakakakuha ng minus sign:

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

3. Ngayon, inilalapat ang susunod na set ng Hadamard sa Qubit 0 hanggang $n-1$. Ang pagsubaybay ng mga minus sign sa kasong ito ay maaaring mahirap. Nakatutulong na malaman na ang pag-aplay ng isang layer ng Hadamard sa $n$ na Qubit sa isang standard basis state na $|x\rangle$ ay maaaring isulat bilang:

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

Kaya nagiging ganito ang estado:

$$|\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. Ang susunod na hakbang ay sukatin ang unang $n$ na bit. Pero ano ang ating susukatin? Lumalabas na ang estado sa itaas ay simplipikahin sa: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, pero malayo iyon sa halata. Kung gusto mong sundan ang matematika, tingnan ang kurso ni John Watrous na Fundamentals of Quantum Algorithms. Ang punto, gayunpaman, ay ang mekanismo ng phase kickback ay nagdudulot na ang mga input Qubit ay nasa estado na $|s\rangle$. Kaya, para malaman kung ano ang lihim na string $s$, kailangan mo lang sukatin ang mga Qubit!

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong mga sagot, at i-click ang mga tatsulok para makita ang mga solusyon.

I-verify na ang estado mula sa Hakbang 3 sa itaas ay talagang ang estado $|s\rangle$ para sa espesyal na kaso na $n=1$.

Sagot:

Kapag naisulat mo nang malinaw ang dalawang kabuuan, dapat makakuha ka ng estado na may apat na termino (ibukod natin ang output state na $|-\rangle$ para dito):

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

Kung $s=0$, ang unang dalawang termino ay nagdadagdag nang constructively at ang huling dalawang termino ay nagkakansela, na nag-iiwan sa atin ng $|\Psi\rangle = |0\rangle$. Kung $s=1$, ang huling dalawang termino ay nagdadagdag nang constructively at ang unang dalawang termino ay nagkakansela, na nag-iiwan sa atin ng $|\Psi\rangle = |1\rangle$. Kaya, sa alinmang kaso, $|\Psi\rangle = |s\rangle$. Sana ang pinakasimpleng kasong ito ay nagbibigay sa iyo ng ideya kung paano gumagana ang pangkalahatang kaso na may $n$ na Qubit: lahat ng termino na hindi $|s\rangle$ ay nagkakansela sa isa't isa, na nag-iiwan lang ng estado na $|s\rangle$.

Paano nireresolved ng parehong algorithm ang parehong problema ng Bernstein-Vazirani at Deutsch-Jozsa? Para maunawaan ito, isipin ang mga function ng Bernstein-Vazirani, na may anyo na $f(x) = s \cdot x$. Ang mga function na ito ba ay mga function din ng Deutsch-Jozsa? Ibig sabihin, tukuyin kung ang mga function ng ganitong anyo ay nagsasatisfy ng pangako ng problema ng Deutsch-Jozsa: na ang mga ito ay constant o balanced. Paano nito tinatalunan kung paano nireresolved ng parehong algorithm ang dalawang magkaibang problema?

Sagot:

Bawat function ng Bernstein-Vazirani na may anyo na $f(x) = s \cdot x$ ay nagsasatisfy din ng pangako ng problema ng Deutsch-Jozsa: kung ang s=00...00, ang function ay constant (laging nagbabalik ng 0 para sa bawat string x). Kung ang s ay anumang ibang string, ang function ay balanced. Kaya, ang pag-apply ng Deutsch-Jozsa algorithm sa isa sa mga function na ito ay sabay-sabay na nagreresolved ng parehong problema! Ibinabalik nito ang string, at kung ang string na iyon ay 00...00 alam nating constant ito; kung may kahit isang "1" sa string, alam nating balanced ito.

Maaari rin nating i-verify na matagumpay na nireresolved ng algorithm na ito ang problema ng Bernstein-Vazirani sa pamamagitan ng pagsubok nito nang eksperimentalmente. Una, ginagawa natin ang B-V function na nakatira sa loob ng black box:

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

Kaya, sa iisang query lang, ibibalik ng Deutsch-Jozsa algorithm ang string $s$ na ginamit sa function na: $f(x)=x \cdot s$ kapag inilapat natin ito sa problema ng Bernstein-Vazirani. Sa isang klasikal na algorithm, kakailanganin ang $n$ na query para malutas ang parehong problema.

Konklusyon

Umaasa kaming sa pamamagitan ng pagsusuri ng mga simpleng halimbawa na ito, nabigyan ka namin ng mas malalim na intuisyon kung paano nagagamit ng mga quantum computer ang superposisyon, entanglement, at interference para makamit ang kanilang kapangyarihan kumpara sa mga klasikal na computer.

Ang Deutsch-Jozsa algorithm ay napakahalaga sa kasaysayan dahil ito ang una na nagpakita ng anumang pagpapabilis kumpara sa isang klasikal na algorithm, pero polynomial lang na pagpapabilis iyon. Ang Deutsch-Jozsa algorithm ay simula pa lang ng kwento.

Pagkatapos gamitin nila ang algorithm para malutas ng kanilang problema, ginamit nina Bernstein at Vazirani ito bilang batayan para sa isang mas kumplikadong, recursive na problema na tinatawag na recursive Fourier sampling problem. Ang kanilang solusyon ay nag-aalok ng super-polynomial na pagpapabilis kumpara sa mga klasikal na algorithm. At kahit bago pa sina Bernstein at Vazirani, natuklasan na ni Peter Shor ang kanyang sikat na algorithm na nagpapahintulot sa mga quantum computer na mag-factor ng malalaking numero nang mas mabilis nang exponential kaysa sa anumang klasikal na algorithm. Ang mga resultang ito, magkakasama, ay nagpakita ng kapana-panabik na pangako ng hinaharap na quantum computer, at nag-udyok sa mga pisikista at inhinyero na gawing katotohanan ang kinabukasang ito.

Mga Tanong

Ang mga guro ay maaaring humiling ng mga bersyon ng mga notebook na ito na may mga susi ng sagot at gabay sa paglalagay sa karaniwang kurikula sa pamamagitan ng pagsagot sa mabilis na survey tungkol sa kung paano ginagamit ang mga notebook.

Mga kritikal na konsepto

• ang mga algorithm ng Deutsch at Deutsch-Jozsa ay gumagamit ng quantum parallelism kasama ang interference para mahanap ang sagot sa isang problema nang mas mabilis kaysa sa kayang gawin ng isang klasikal na computer.
• ang mekanismo ng phase kickback ay isang counterintuitive na quantum phenomena na naglilipat ng mga operasyon sa isang Qubit patungo sa phase ng isa pang Qubit. Ginagamit ng mga algorithm ng Deutsch at Deutsch-Jozsa ang mekanismong ito.
• Ang Deutsch-Jozsa algorithm ay nag-aalok ng polynomial na pagpapabilis kumpara sa anumang deterministic na klasikal na algorithm.
• Ang Deutsch-Jozsa algorithm ay maaaring ilapat sa ibang problema, na tinatawag na problema ng Bernstein-Vazirani, para mahanap ang isang nakatagong string na naka-encode sa isang function.

Tama/Mali

1. T/M Ang algorithm ni Deutsch ay isang espesyal na kaso ng Deutsch-Jozsa algorithm kung saan ang input ay isang solong Qubit.
2. T/M Ang mga algorithm ng Deutsch at Deutsch-Jozsa ay gumagamit ng quantum superposisyon at interference para makamit ang kanilang kahusayan.
3. T/M Ang Deutsch-Jozsa algorithm ay nangangailangan ng maraming pagsusuri ng function para matukoy kung ang isang function ay constant o balanced.
4. T/M Ang "Bernstein-Vazirani algorithm" ay talagang kapareho ng Deutsch-Jozsa algorithm, na inilapat sa ibang problema.
5. T/M Ang Bernstein-Vazirani algorithm ay maaaring makahanap ng maraming lihim na string nang sabay-sabay.

Maikling sagot

1. Gaano katagal ang kakailanganin ng isang klasikal na algorithm para malutas ang problema ng Deutsch-Jozsa sa pinakamasamang kaso?

2. Gaano katagal ang kakailanganin ng isang klasikal na algorithm para malutas ang problema ng Bernstein-Vazirani? Anong pagpapabilis ang inaalok ng DJ algorithm sa kasong ito?

3. Ilarawan ang mekanismo ng phase-kickback at kung paano ito gumagana para malutas ang mga problema ng Deutsch-Jozsa at Bernstein-Vazirani.

Hamon na problema

1. Ang Deutsch-Jozsa algorithm: Alalahanin na mayroon kang tanong sa itaas na humihingi sa iyo na kalkulahin ang mga intermediate na estado ng Qubit na $\pi_1$, at $\pi_2$ ng algorithm ni Deutsch. Gawin ang parehong bagay para sa mga intermediate na $(n+1)$-Qubit na estado na $\pi_1$, at $\pi_2$ ng Deutsch-Jozsa algorithm, para sa tiyak na kaso na $n=2$. Pagkatapos, i-verify na ang $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, muli, para sa tiyak na kaso na $n=2$.