Algoritma Deutsch-Jozsa

Untuk modul Qiskit in Classrooms ini, pelajar perlu mempunyai persekitaran Python yang berfungsi dengan pakej-pakej berikut dipasang:

• qiskit v2.1.0 atau lebih baharu
• qiskit-ibm-runtime v0.40.1 atau lebih baharu
• qiskit-aer v0.17.0 atau lebih baharu
• qiskit.visualization
• numpy
• pylatexenc

Untuk menyediakan dan memasang pakej-pakej di atas, lihat panduan Pasang Qiskit. Untuk menjalankan kerja pada komputer kuantum sebenar, pelajar perlu menyediakan akaun dengan IBM Quantum® dengan mengikuti langkah-langkah dalam panduan Sediakan akaun IBM Cloud anda.

Modul ini telah diuji dan menggunakan empat saat masa QPU. Ini adalah anggaran sahaja. Penggunaan sebenar anda mungkin berbeza.

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

Tonton panduan modul oleh Dr. Katie McCormick di bawah, atau klik di sini untuk menontonnya di YouTube.

---

Pengenalan

Pada awal tahun 1980-an, ahli fizik kuantum dan saintis komputer mempunyai gambaran samar bahawa mekanik kuantum boleh dimanfaatkan untuk membuat pengiraan yang jauh lebih berkuasa daripada yang boleh dilakukan oleh komputer klasik. Hujah mereka adalah begini: sukar bagi komputer klasik untuk mensimulasi sistem kuantum, tetapi komputer kuantum sepatutnya boleh melakukannya dengan lebih cekap. Dan jika komputer kuantum boleh mensimulasi sistem kuantum dengan lebih cekap, mungkin ada tugas-tugas lain yang boleh dilakukannya dengan lebih cekap berbanding komputer klasik.

Logiknya kukuh, tetapi perinciannya masih perlu diusahakan. Ini bermula pada tahun 1985, apabila David Deutsch menerangkan "komputer kuantum universal" yang pertama. Dalam kertas kerja yang sama, beliau memberikan contoh masalah pertama di mana komputer kuantum boleh menyelesaikan sesuatu dengan lebih cekap berbanding komputer klasik. Contoh permainan pertama ini kini dikenali sebagai "algoritma Deutsch." Peningkatan dalam algoritma Deutsch adalah sederhana, tetapi Deutsch bekerjasama dengan Richard Jozsa beberapa tahun kemudian untuk melebarkan lagi jurang antara komputer klasik dan kuantum.

Algoritma-algoritma ini — algoritma Deutsch, dan sambungan Deutsch-Jozsa — tidak terlalu berguna, tetapi ia tetap sangat penting atas beberapa sebab:

1. Dari segi sejarah, ia adalah antara algoritma kuantum pertama yang terbukti mengatasi padanannya yang klasik. Memahaminya boleh membantu kita memahami bagaimana pemikiran komuniti tentang pengkomputeran kuantum telah berkembang dari masa ke masa.
2. Ia boleh membantu kita memahami beberapa aspek jawapan kepada soalan yang mengejutkan halusnya: Apakah yang memberi kuasa kepada pengkomputeran kuantum? Kadangkala, komputer kuantum dibandingkan dengan pemproses selari berskala eksponen yang besar. Tetapi ini tidak tepat sepenuhnya. Walaupun sebahagian jawapan kepada soalan ini terletak pada "keselarian kuantum", mengekstrak maklumat sebanyak mungkin dalam satu larian adalah seni yang halus. Algoritma Deutsch dan Deutsch-Jozsa menunjukkan bagaimana ini boleh dilakukan.

Dalam modul ini, kita akan belajar tentang algoritma Deutsch, algoritma Deutsch-Jozsa, dan apa yang mereka ajarkan kita tentang kekuatan pengkomputeran kuantum.

Keselarian kuantum dan hadnya

Sebahagian daripada kekuatan pengkomputeran kuantum berasal daripada "keselarian kuantum", yang pada dasarnya adalah kemampuan untuk melakukan operasi ke atas pelbagai input pada masa yang sama, kerana keadaan input Qubit boleh berada dalam superposisi pelbagai keadaan yang dibenarkan secara klasik. NAMUN, walaupun Circuit kuantum mungkin dapat menilai pelbagai keadaan input sekaligus, mengekstrak semua maklumat itu dalam satu langkah adalah mustahil.

Untuk memahami maksud saya di sini, katakanlah kita mempunyai satu bit, $x$ dan beberapa fungsi yang digunakan pada bit itu, $f(x)$. Terdapat empat fungsi binari yang mungkin mengambil satu bit kepada satu bit lain:

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

Kita ingin mengetahui mana satu daripada fungsi-fungsi ini (1-4) yang merupakan $f(x)$ kita. Secara klasik, kita perlu menjalankan fungsi dua kali — sekali untuk $x=0$, sekali untuk $x=1$. Tetapi mari kita lihat jika kita boleh melakukan lebih baik dengan Circuit kuantum. Kita boleh mengetahui tentang fungsi tersebut dengan Gate berikut:

Di sini, Gate $U_f$ mengira $f(x)$, di mana $x$ adalah keadaan Qubit 0, dan menggunakannya pada Qubit 1. Jadi, keadaan yang terhasil, $|x\rangle|y\oplus f(x)\rangle$, menjadi $|x\rangle|f(x)\rangle$ apabila $|y\rangle = |0\rangle$. Ini mengandungi semua maklumat yang kita perlukan untuk mengetahui fungsi $f(x)$: Qubit 0 memberitahu kita apa itu $x$, dan Qubit 1 memberitahu kita apa itu $f(x)$. Jadi, jika kita memulakan $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, maka keadaan akhir kedua-dua Qubit akan menjadi: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Tetapi bagaimana kita mengakses maklumat itu?

2.1. Cuba dalam Qiskit:

Menggunakan Qiskit, kita akan memilih secara rawak salah satu daripada empat fungsi yang mungkin di atas dan menjalankan Circuit. Kemudian tugasan anda adalah menggunakan pengukuran Circuit kuantum untuk mengetahui fungsi tersebut dalam seberapa sedikit larian yang mungkin.

Dalam eksperimen pertama ini dan sepanjang modul, kita akan menggunakan rangka kerja untuk pengkomputeran kuantum yang dikenali sebagai "corak Qiskit", yang membahagikan aliran kerja kepada langkah-langkah berikut:

• Langkah 1: Petakan input klasik kepada masalah kuantum
• Langkah 2: Optimumkan masalah untuk pelaksanaan kuantum
• Langkah 3: Laksanakan menggunakan Qiskit Runtime Primitives
• Langkah 4: Pasca-pemprosesan dan analisis klasik

Mari mulakan dengan memuatkan beberapa pakej yang diperlukan, termasuk primitif Qiskit Runtime. Kita juga akan memilih komputer kuantum yang paling kurang sibuk yang tersedia untuk kita.

Terdapat kod di bawah untuk menyimpan kelayakan anda pada penggunaan pertama. Pastikan anda memadam maklumat ini daripada notebook selepas menyimpannya ke persekitaran anda, supaya kelayakan anda tidak terdedah secara tidak sengaja apabila anda berkongsi notebook. Lihat Sediakan akaun IBM Cloud anda dan Mulakan perkhidmatan dalam persekitaran yang tidak dipercayai untuk panduan lanjut.

# 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

Sel di bawah membolehkan anda bertukar antara menggunakan simulator atau perkakasan sebenar sepanjang notebook. Kami mengesyorkan anda menjalankannya sekarang:

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

Setelah memuatkan pakej yang diperlukan, kita boleh meneruskan dengan aliran kerja corak Qiskit. Dalam langkah pemetaan di bawah, kita pertama kali membuat fungsi yang memilih antara empat fungsi yang mungkin mengambil satu bit kepada satu bit lain.

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

Dalam Circuit di atas, Gate Hadamard "H" membawa Qubit 0, yang pada mulanya berada dalam keadaan $|0\rangle$, kepada keadaan superposisi $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Kemudian, $U_f$ menilai fungsi $f(x)$ dan menggunakannya pada Qubit 1.

Seterusnya kita perlu mengoptimumkan dan mentranspile Circuit untuk dijalankan pada komputer kuantum:

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

Akhirnya, kita melaksanakan Circuit yang telah ditranspile pada komputer kuantum dan menggambarkan keputusan kita:

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

Di atas adalah histogram keputusan kita. Bergantung pada bilangan shots yang anda pilih untuk menjalankan Circuit dalam langkah 3 di atas, anda mungkin melihat satu atau dua bar, yang mewakili keadaan yang diukur bagi kedua-dua Qubit dalam setiap shot. Seperti biasa dengan Qiskit dan dalam notebook ini, kita menggunakan notasi "little endian", bermaksud keadaan Qubit 0 hingga n ditulis dalam tertib menaik dari kanan ke kiri, jadi Qubit 0 sentiasa paling kanan.

Jadi, kerana Qubit 0 berada dalam keadaan superposisi, Circuit menilai fungsi untuk kedua-dua $x=0$ dan $x=1$ pada masa yang sama — sesuatu yang tidak dapat dilakukan oleh komputer klasik! Tetapi masalahnya timbul apabila kita ingin mengetahui tentang fungsi $f(x)$ — apabila kita mengukur Qubit, kita meruntuhkan keadaannya. Jika anda memilih "shots = 1" untuk hanya menjalankan Circuit sekali, anda hanya akan melihat satu bar dalam histogram di atas, dan maklumat anda tentang fungsi tersebut akan tidak lengkap.

Uji kefahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaian.

Berapa kali kita perlu menjalankan algoritma di atas untuk mengetahui fungsi $f(x)$? Adakah ini lebih baik daripada kes klasik? Adakah anda lebih suka mempunyai komputer klasik atau kuantum untuk menyelesaikan masalah ini?

Jawapan:

Memandangkan pengukuran akan meruntuhkan superposisi dan hanya mengembalikan satu nilai, kita perlu menjalankan Circuit sekurang-kurangnya dua kali untuk mendapatkan kedua-dua output fungsi $f(0)$ dan $f(1)$. Dalam kes terbaik, ini berjalan sama baiknya dengan kes klasik, di mana kita mengira kedua-dua $f(0)$ dan $f(1)$ dalam dua pertanyaan pertama. Tetapi ada kemungkinan kita perlu menjalankannya lebih daripada dua kali, kerana pengukuran akhir adalah kebarangkalian dan mungkin mengembalikan nilai $f(x)$ yang sama dua kali pertama. Saya lebih suka mempunyai komputer klasik dalam kes ini.

Jadi, walaupun keselarian kuantum boleh menjadi berkuasa apabila digunakan dengan cara yang betul, tidak tepat untuk mengatakan bahawa komputer kuantum berfungsi seperti pemproses selari klasik yang besar. Tindakan pengukuran meruntuhkan keadaan kuantum, jadi kita hanya boleh mengakses satu output pengiraan pada bila-bila masa.

Algoritma Deutsch

Walaupun keselarian kuantum sahaja tidak memberi kita kelebihan berbanding komputer klasik, kita boleh menggabungkannya dengan fenomena kuantum lain, iaitu interferens, untuk mencapai pecutan. Algoritma yang kini dikenali sebagai "algoritma Deutsch" adalah contoh pertama algoritma yang mencapai perkara ini.

Masalah

Inilah masalahnya:

Diberikan satu bit input, $x = \{0,1\}$, dan fungsi input $f(x) = \{0,1\}$, tentukan sama ada fungsi tersebut adalah seimbang atau malar. Iaitu, jika ia seimbang, maka output fungsi adalah 0 separuh masa dan 1 separuh masa yang lain. Jika ia malar, maka output fungsi adalah sentiasa 0 atau sentiasa 1. Ingat semula jadual empat fungsi yang mungkin mengambil satu bit kepada satu bit lain:

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

Fungsi pertama dan terakhir, $f_1(x)$ dan $f_4(x)$, adalah malar, manakala dua fungsi di tengah, $f_2(x)$ dan $f_3(x)$, adalah seimbang.

Algoritma tersebut

Cara Deutsch mendekati masalah ini adalah melalui "model pertanyaan." Dalam model pertanyaan, fungsi input ($f_i(x)$ di atas) terkandung dalam sebuah "kotak hitam" — kita tidak mempunyai akses langsung kepada kandungannya, tetapi kita boleh membuat pertanyaan kepada kotak hitam tersebut dan ia akan memberikan output fungsi tersebut kepada kita. Kita kadangkala berkata bahawa sebuah "oracle" menyediakan maklumat ini. Lihat Pelajaran 1: Algoritma Pertanyaan Kuantum dalam kursus Asas Algoritma Kuantum untuk maklumat lanjut tentang model pertanyaan.

Untuk menentukan sama ada algoritma kuantum lebih cekap daripada algoritma klasik dalam model pertanyaan, kita boleh membandingkan bilangan pertanyaan yang perlu kita buat kepada kotak hitam dalam setiap kes. Dalam kes klasik, untuk mengetahui sama ada fungsi yang terkandung dalam kotak hitam adalah seimbang atau malar, kita perlu membuat pertanyaan kepada kotak tersebut dua kali untuk mendapatkan kedua-dua $f(0)$ dan $f(1)$.

Dalam algoritma kuantum Deutsch, beliau menemui cara untuk mendapatkan maklumat dengan hanya satu pertanyaan! Beliau membuat satu penyelarasan pada Circuit "keselarian kuantum" di atas, supaya beliau menyediakan keadaan superposisi pada kedua-dua Qubit, bukan hanya pada Qubit 0 sahaja. Kemudian dua output fungsi, $f(0)$ dan $f(1)$ berinterferensi untuk mengembalikan 0 jika keduanya 0 atau keduanya 1 (fungsi adalah malar), dan mengembalikan 1 jika keduanya berbeza (fungsi adalah seimbang). Dengan cara ini, Deutsch boleh membezakan antara fungsi malar dan seimbang dengan satu pertanyaan sahaja.

Berikut adalah gambar rajah Circuit algoritma Deutsch:

Untuk memahami bagaimana algoritma ini berfungsi, mari kita lihat keadaan kuantum Qubit pada tiga titik yang dicatat pada gambar rajah di atas. Cuba usahakan keadaan-keadaan itu sendiri sebelum mengklik untuk melihat jawapannya:

Uji kefahaman anda

Baca soalan-soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaian.

Apakah keadaan $|\pi_1\rangle$?

Jawapan:

Menggunakan Hadamard mengubah keadaan $|0\rangle$ kepada $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ dan keadaan $|1\rangle$ kepada $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Jadi, keadaan penuh menjadi: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Apakah keadaan $|\pi_2\rangle$?

Jawapan:

Sebelum kita menggunakan $U_f$, ingat semula apa yang dilakukannya. Ia akan mengubah keadaan Qubit 1 berdasarkan keadaan Qubit 0. Jadi, masuk akal untuk memfaktorkan keadaan Qubit 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Kemudian, jika $f(0)=f(1)$, kedua-dua sebutan akan berubah dengan cara yang sama dan tanda relatif antara kedua-dua sebutan kekal positif, tetapi jika $f(0)\neq f(1)$, maka ini bermakna sebutan kedua akan mengambil tanda negatif relatif terhadap sebutan pertama, mengubah keadaan Qubit 0 dari $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ kepada $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Jadi:

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

Apakah keadaan $|\pi_3\rangle$?

Jawapan:

Sekarang, keadaan Qubit 0 adalah sama ada $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ atau $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, bergantung pada fungsi tersebut. Menggunakan Hadamard akan menghasilkan sama ada $|0\rangle$ atau $|1\rangle$, masing-masing.

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

Melihat jawapan anda untuk soalan-soalan di atas, perhatikan bahawa sesuatu yang agak mengejutkan berlaku. Walaupun $U_f$ tidak melakukan apa-apa secara eksplisit pada keadaan Qubit 0, kerana ia mengubah Qubit 1 berdasarkan keadaan Qubit 0, boleh berlaku bahawa ini menyebabkan peralihan fasa pada Qubit 0. Ini dikenali sebagai fenomena "phase-kickback", dan dibincangkan dengan lebih terperinci dalam Pelajaran 1: Algoritma Pertanyaan Kuantum dalam kursus Asas Algoritma Kuantum.

Setelah memahami cara algoritma ini berfungsi, mari kita laksanakannya dengan 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

Algoritma Deutsch-Jozsa

Algoritma Deutsch merupakan langkah pertama yang penting dalam menunjukkan bagaimana komputer kuantum boleh lebih cekap daripada komputer klasik, tetapi ia hanyalah satu peningkatan yang sederhana: ia hanya memerlukan satu pertanyaan, berbanding dua dalam kes klasik. Pada tahun 1992, Deutsch dan rakannya, Richard Jozsa, mengembangkan algoritma dua-Qubit asal kepada lebih banyak Qubit. Masalahnya tetap sama: tentukan sama ada fungsi adalah seimbang atau malar. Tetapi kali ini, fungsi tersebut bergerak dari $n$ bit kepada satu bit. Sama ada fungsi mengembalikan 0 dan 1 dalam bilangan yang sama (ia seimbang) atau fungsi sentiasa mengembalikan 1 atau sentiasa 0 (ia malar).

Berikut adalah gambar rajah Circuit untuk algoritma ini:

Algoritma ini berfungsi dengan cara yang sama seperti algoritma Deutsch: phase-kickback membolehkan seseorang membaca keadaan Qubit 0 untuk menentukan sama ada fungsi itu malar atau seimbang. Ini sedikit lebih rumit untuk dilihat berbanding kes algoritma Deutsch dua-Qubit, kerana keadaan akan merangkumi jumlah ke atas $n$ Qubit, jadi mengira keadaan tersebut akan ditinggalkan sebagai latihan pilihan untuk kamu di hujung modul. Algoritma akan mengembalikan bitstring yang semuanya 0 jika fungsi adalah malar, dan bitstring yang mengandungi sekurang-kurangnya satu 1 jika fungsi adalah seimbang.

Untuk melihat cara algoritma berfungsi dalam Qiskit, mula-mula, kita perlu menjana oracle kita: fungsi rawak yang dijamin sama ada malar atau seimbang. Kod di bawah akan menjana fungsi seimbang 50% daripada masa, dan fungsi malar 50% daripada masa. Jangan risau jika kamu tidak sepenuhnya memahami kod ini — ia rumit dan tidak perlu untuk pemahaman kita tentang algoritma kuantum.

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

Ini adalah fungsi oracle, yang sama ada seimbang atau malar. Bolehkah kamu lihat dengan melihatnya sama ada output pada Qubit terakhir bergantung pada nilai yang dimasukkan untuk $n$ Qubit pertama? Jika output untuk Qubit terakhir bergantung pada $n$ Qubit pertama, bolehkah kamu memberitahu sama ada output yang bergantung itu seimbang atau tidak?

Kita boleh mengetahui sama ada fungsi itu seimbang atau malar dengan melihat Circuit di atas, tetapi ingat, untuk tujuan masalah ini, kita menganggap fungsi ini sebagai "kotak hitam." Kita tidak boleh mengintip ke dalam kotak untuk melihat gambar rajah Circuit. Sebaliknya, kita perlu membuat pertanyaan pada kotak itu.

Untuk membuat pertanyaan pada kotak tersebut, kita menggunakan algoritma Deutsch-Jozsa dan menentukan sama ada fungsi itu malar atau seimbang:

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

Di atas, baris pertama output adalah bitstring hasil pengukuran. Baris kedua mengeluarkan sama ada bitstring menunjukkan fungsi tersebut seimbang atau malar. Jika bitstring mengandungi semua sifar, maka ia adalah malar; jika tidak, ia adalah seimbang. Jadi, dengan hanya satu jalankan Circuit kuantum di atas, kita boleh menentukan sama ada fungsi itu malar atau seimbang!

Semak pemahaman kamu

Baca soalan-soalan di bawah, fikirkan jawapan kamu, kemudian klik segi tiga untuk mendedahkan penyelesaiannya.

Berapa banyak pertanyaan yang diperlukan oleh komputer klasik untuk menentukan dengan kepastian 100% sama ada fungsi itu malar atau seimbang? Ingat, secara klasik, satu pertanyaan hanya membolehkan kamu menggunakan fungsi pada satu bitstring tunggal.

Jawapan:

Terdapat $2^n$ bitstring yang mungkin untuk diperiksa, dan dalam kes terburuk, kamu perlu menguji $2^n/2+1$ daripadanya. Sebagai contoh, jika fungsi itu malar, dan kamu terus mengukur "1" sebagai output fungsi, maka kamu tidak boleh pasti bahawa ia benar-benar malar sehingga kamu memeriksa lebih daripada separuh hasil. Sebelum itu, kamu mungkin sahaja sangat malang kerana terus mengukur "1" pada fungsi seimbang. Ia seperti melempar duit syiling berulang kali dan ia jatuh pada kepala setiap kali. Ia tidak mungkin, tetapi bukan mustahil.

Bagaimana jawapan kamu di atas akan berubah jika kamu hanya perlu mengukur sehingga satu hasil (seimbang atau malar) lebih mungkin daripada yang lain? Berapa banyak pertanyaan yang diperlukan dalam kes ini?

Jawapan:

Dalam kes ini, kamu hanya perlu mengukur dua kali. Jika dua pengukuran berbeza, kamu tahu fungsi itu seimbang. Jika kedua-dua pengukuran sama, maka ia mungkin seimbang, atau ia mungkin malar. Kebarangkalian bahawa ia seimbang dengan set pengukuran ini adalah: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Ini kurang daripada 1/2, jadi fungsi itu lebih mungkin malar dalam kes ini.

Jadi, algoritma Deutsch-Jozsa menunjukkan percepatan eksponen berbanding algoritma klasik deterministik (yang mengembalikan jawapan dengan kepastian 100%), tetapi tiada percepatan yang ketara berbanding algoritma kebarangkalian (yang mengembalikan hasil yang mungkin merupakan jawapan yang betul).

Masalah Bernstein - Vazirani

Pada tahun 1997, Ethan Bernstein dan Umesh Vazirani menggunakan algoritma Deutsch-Jozsa untuk menyelesaikan masalah yang lebih spesifik dan terhad berbanding masalah Deutsch-Jozsa. Daripada sekadar cuba membezakan antara dua kelas fungsi yang berbeza, seperti dalam kes D-J, Bernstein dan Vazirani menggunakan algoritma Deutsch-Jozsa untuk benar-benar mempelajari rentetan yang dikodkan dalam fungsi. Berikut adalah masalahnya:

Fungsi $f:\{0,1\}^n \rightarrow \{0,1\}$ masih mengambil rentetan $n$-bit dan mengeluarkan satu bit. Tetapi sekarang, daripada menjanjikan bahawa fungsi itu seimbang atau malar, kita kini dijanjikan bahawa fungsi itu adalah hasil darab titik antara rentetan input $x$ dan beberapa rentetan $n$-bit rahsia $s$, modulo 2. (Hasil darab titik modulo 2 ini dipanggil "hasil darab titik binari.") Masalahnya adalah untuk mengetahui apakah rentetan $n$-bit rahsia itu.

Ditulis dengan cara lain, kita diberi fungsi kotak hitam $f: {0,1}^n \rightarrow {0,1}$ yang memenuhi $f(x) = s \cdot x$ untuk beberapa rentetan $s$, dan kita ingin mempelajari rentetan $s$ tersebut.

Mari kita lihat bagaimana algoritma D-J menyelesaikan masalah ini:

1. Pertama, Gate Hadamard digunakan pada $n$ Qubit input, dan Gate NOT ditambah Hadamard digunakan pada Qubit output, menjadikan keadaan:

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

Keadaan Qubit 1 hingga $n$ boleh ditulis dengan lebih mudah sebagai jumlah ke atas semua $2^n$ keadaan basis $n$-Qubit $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Kita panggil set keadaan basis ini $\Sigma^n$. (Lihat Fundamentals of Quantum Algorithms untuk maklumat lanjut.)

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

2. Seterusnya, Gate $U_f$ digunakan pada Qubit. Gate ini akan mengambil $n$ Qubit pertama sebagai input (yang kini berada dalam superposisi sama rata semua rentetan $n$-bit yang mungkin) dan menggunakan fungsi $f(x)=s \cdot x$ pada Qubit output, supaya Qubit ini kini berada dalam keadaan: $|- \oplus f(x)\rangle$. Berkat mekanisme phase kickback, keadaan Qubit ini kekal tidak berubah, tetapi sebahagian sebutan dalam keadaan Qubit input mengambil tanda tolak:

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

3. Sekarang, set Hadamard seterusnya digunakan pada Qubit 0 hingga $n-1$. Menjejaki tanda tolak dalam kes ini boleh menjadi rumit. Adalah berguna untuk mengetahui bahawa menggunakan lapisan Hadamard pada $n$ Qubit dalam keadaan basis standard $|x\rangle$ boleh ditulis sebagai:

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

Jadi keadaan menjadi:

$$|\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. Langkah seterusnya adalah mengukur $n$ bit pertama. Tetapi apakah yang akan kita ukur? Rupanya, keadaan di atas memudah kepada: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, tetapi itu jauh dari jelas. Jika kamu ingin mengikuti matemat tersebut, lihat kursus Fundamentals of Quantum Algorithms oleh John Watrous. Intinya ialah mekanisme phase kickback menyebabkan Qubit input berada dalam keadaan $|s\rangle$. Jadi, untuk mengetahui apakah rentetan rahsia $s$ tersebut, kamu hanya perlu mengukur Qubit!

Semak pemahaman kamu

Baca soalan-soalan di bawah, fikirkan jawapan kamu, kemudian klik segi tiga untuk mendedahkan penyelesaiannya.

Sahkan bahawa keadaan dari Langkah 3 di atas memang keadaan $|s\rangle$ untuk kes khas $n=1$.

Jawapan:

Apabila kamu menulis secara eksplisit dua penjumlahan itu, kamu sepatutnya mendapat keadaan dengan empat sebutan (mari kita abaikan keadaan output $|-\rangle$ untuk ini):

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

Jika $s=0$, maka dua sebutan pertama bertambah secara membina dan dua sebutan terakhir dibatalkan, meninggalkan kita dengan $|\Psi\rangle = |0\rangle$. Jika $s=1$, maka dua sebutan terakhir bertambah secara membina dan dua sebutan pertama dibatalkan, meninggalkan kita dengan $|\Psi\rangle = |1\rangle$. Jadi, dalam kedua-dua kes, $|\Psi\rangle = |s\rangle$. Mudah-mudahan kes paling mudah ini memberi kamu gambaran tentang cara kes umum dengan $n$ Qubit berfungsi: semua sebutan yang bukan $|s\rangle$ saling mengganggu dan hilang, meninggalkan hanya keadaan $|s\rangle$.

Bagaimana algoritma yang sama boleh menyelesaikan kedua-dua masalah Bernstein-Vazirani dan Deutsch-Jozsa? Untuk memahami ini, fikirkan tentang fungsi Bernstein-Vazirani, yang berbentuk $f(x) = s \cdot x$. Adakah fungsi-fungsi ini juga merupakan fungsi Deutsch-Jozsa? Iaitu, tentukan sama ada fungsi berbentuk ini memenuhi janji masalah Deutsch-Jozsa: bahawa ia sama ada malar atau seimbang. Bagaimana ini membantu kita memahami cara algoritma yang sama menyelesaikan dua masalah yang berbeza?

Jawapan:

Setiap fungsi Bernstein-Vazirani berbentuk $f(x) = s \cdot x$ juga memenuhi janji masalah Deutsch-Jozsa: jika s=00...00, maka fungsi itu malar (sentiasa mengembalikan 0 untuk setiap rentetan x). Jika s adalah rentetan lain, maka fungsi itu seimbang. Jadi, menggunakan algoritma Deutsch-Jozsa pada salah satu fungsi ini secara serentak menyelesaikan kedua-dua masalah! Ia mengembalikan rentetan, dan jika rentetan itu adalah 00...00 maka kita tahu ia malar; jika ada sekurang-kurangnya satu "1" dalam rentetan, kita tahu ia seimbang.

Kita juga boleh mengesahkan bahawa algoritma ini berjaya menyelesaikan masalah Bernstein-Vazirani dengan mengujinya secara eksperimen. Pertama, kita cipta fungsi B-V yang tinggal di dalam kotak hitam:

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

Jadi, dengan hanya satu pertanyaan, algoritma Deutsch-Jozsa akan mengembalikan rentetan $s$ yang digunakan dalam fungsi: $f(x)=x \cdot s$ apabila kita menerapkannya pada masalah Bernstein-Vazirani. Dengan algoritma klasik, seseorang memerlukan $n$ pertanyaan untuk menyelesaikan masalah yang sama.

Kesimpulan

Kami berharap dengan mengkaji contoh-contoh mudah ini, kami telah memberi kamu intuisi yang lebih baik tentang bagaimana komputer kuantum dapat memanfaatkan superposisi, keterikatan, dan interferens untuk mencapai kekuatannya berbanding komputer klasik.

Algoritma Deutsch-Jozsa mempunyai kepentingan sejarah yang besar kerana ia adalah yang pertama menunjukkan sebarang percepatan berbanding algoritma klasik, tetapi ia hanyalah percepatan polinomial. Algoritma Deutsch-Jozsa hanyalah permulaan cerita.

Selepas mereka menggunakan algoritma itu untuk menyelesaikan masalah mereka, Bernstein dan Vazirani menggunakannya sebagai asas untuk masalah yang lebih rumit dan rekursif yang dipanggil masalah pensampelan Fourier rekursif. Penyelesaian mereka menawarkan percepatan super-polinomial berbanding algoritma klasik. Dan bahkan sebelum Bernstein dan Vazirani, Peter Shor sudah pun menghasilkan algoritmanya yang terkenal yang membolehkan komputer kuantum memfaktorkan nombor besar dengan lebih pantas secara eksponen daripada mana-mana algoritma klasik. Keputusan-keputusan ini secara kolektif menunjukkan janji menarik komputer kuantum masa depan, dan mendorong ahli fizik dan jurutera untuk menjadikan masa depan ini satu kenyataan.

Soalan

Pengajar boleh meminta versi buku nota ini dengan kunci jawapan dan panduan tentang penempatan dalam kurikulum umum dengan mengisi tinjauan ringkas ini tentang cara buku nota digunakan.

Konsep penting

• Algoritma Deutsch dan Deutsch-Jozsa menggunakan keselarian kuantum digabungkan dengan interferens untuk mencari jawapan kepada masalah lebih cepat daripada komputer klasik.
• Mekanisme phase kickback adalah fenomena kuantum yang berlawanan dengan intuisi yang memindahkan operasi pada satu Qubit kepada fasa Qubit lain. Algoritma Deutsch dan Deutsch-Jozsa menggunakan mekanisme ini.
• Algoritma Deutsch-Jozsa menawarkan percepatan polinomial berbanding mana-mana algoritma klasik deterministik.
• Algoritma Deutsch-Jozsa boleh digunakan pada masalah yang berbeza, yang dipanggil masalah Bernstein-Vazirani, untuk mencari rentetan tersembunyi yang dikodkan dalam fungsi.

Benar/salah

1. B/S Algoritma Deutsch adalah kes khas algoritma Deutsch-Jozsa di mana inputnya adalah Qubit tunggal.
2. B/S Algoritma Deutsch dan Deutsch-Jozsa menggunakan superposisi kuantum dan interferens untuk mencapai kecekapannya.
3. B/S Algoritma Deutsch-Jozsa memerlukan penilaian fungsi berbilang untuk menentukan sama ada fungsi itu malar atau seimbang.
4. B/S "Algoritma Bernstein-Vazirani" sebenarnya sama dengan algoritma Deutsch-Jozsa, yang digunakan pada masalah berbeza.
5. B/S Algoritma Bernstein-Vazirani boleh mencari pelbagai rentetan rahsia secara serentak.

Jawapan pendek

1. Berapa lama algoritma klasik akan mengambil masa untuk menyelesaikan masalah Deutsch-Jozsa dalam kes terburuk?

2. Berapa lama algoritma klasik akan mengambil masa untuk menyelesaikan masalah Bernstein-Vazirani? Apakah percepatan yang ditawarkan algoritma DJ dalam kes ini?

3. Huraikan mekanisme phase-kickback dan cara ia berfungsi untuk menyelesaikan masalah Deutsch-Jozsa dan Bernstein-Vazirani.

Masalah cabaran

1. Algoritma Deutsch-Jozsa: Ingat bahawa kamu mempunyai soalan di atas yang meminta kamu mengira keadaan Qubit perantaraan $\pi_1$, dan $\pi_2$ algoritma Deutsch. Lakukan perkara yang sama untuk keadaan $n+1$-Qubit perantaraan $\pi_1$, dan $\pi_2$ algoritma Deutsch-Jozsa, untuk kes khusus bahawa $n=2$. Kemudian, sahkan bahawa $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, sekali lagi, untuk kes khusus bahawa $n=2$.