Algoritma Deutsch-Jozsa

Untuk modul Qiskit in Classrooms ini, siswa harus punya lingkungan Python yang berfungsi dengan paket-paket berikut terinstal:

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

Untuk mengatur dan menginstal paket-paket di atas, lihat panduan Install Qiskit. Untuk menjalankan job di komputer kuantum nyata, siswa perlu membuat akun di IBM Quantum® dengan mengikuti langkah-langkah di panduan Set up your IBM Cloud account.

Modul ini telah diuji dan menggunakan empat detik waktu QPU. Ini hanya estimasi. Penggunaan aktualmu mungkin berbeda.

# 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 video penjelasan modul oleh Dr. Katie McCormick di bawah, atau klik di sini untuk menontonnya di YouTube.

---

Intro

Pada awal 1980-an, fisikawan kuantum dan ilmuwan komputer punya gagasan samar bahwa mekanika kuantum bisa dimanfaatkan untuk membuat komputasi yang jauh lebih powerful daripada yang bisa dilakukan komputer klasik. Alasan mereka begini: sulit bagi komputer klasik untuk menyimulasikan sistem kuantum, tapi komputer kuantum seharusnya bisa melakukannya lebih efisien. Dan kalau komputer kuantum bisa menyimulasikan sistem kuantum lebih efisien, mungkin ada tugas lain yang bisa dilakukannya lebih efisien daripada komputer klasik.

Logikanya masuk akal, tapi detailnya masih perlu dikerjakan. Ini dimulai pada 1985, ketika David Deutsch mendeskripsikan "komputer kuantum universal" pertama. Dalam makalah yang sama, dia memberikan contoh masalah pertama di mana komputer kuantum bisa menyelesaikan sesuatu lebih efisien daripada komputer klasik. Contoh mainan pertama ini sekarang dikenal sebagai "algoritma Deutsch." Peningkatan dalam algoritma Deutsch cukup sederhana, tapi Deutsch kemudian bekerja sama dengan Richard Jozsa beberapa tahun kemudian untuk semakin memperlebar kesenjangan antara komputer klasik dan kuantum.

Algoritma-algoritma ini — Deutsch, dan ekstensi Deutsch-Jozsa — tidak terlalu berguna secara praktis, tapi tetap sangat penting karena beberapa alasan:

1. Secara historis, ini adalah beberapa algoritma kuantum pertama yang terbukti mengalahkan padanannya yang klasik. Memahaminya bisa membantu kita memahami bagaimana pemikiran komunitas tentang komputasi kuantum berkembang dari waktu ke waktu.
2. Algoritma-algoritma ini bisa membantu kita memahami beberapa aspek dari jawaban atas pertanyaan yang ternyata cukup rumit: Apa yang membuat komputasi kuantum begitu powerful? Kadang, komputer kuantum dibandingkan dengan prosesor paralel klasik yang sangat besar dan berskala eksponensial. Tapi ini tidak sepenuhnya tepat. Meskipun sebagian jawabannya terletak pada "paralelisme kuantum," mengekstrak informasi sebanyak mungkin dalam satu kali jalan adalah seni yang rumit. Algoritma Deutsch dan Deutsch-Jozsa menunjukkan bagaimana hal ini bisa dilakukan.

Dalam modul ini, kita akan belajar tentang algoritma Deutsch, algoritma Deutsch-Jozsa, dan apa yang bisa kita pelajari dari keduanya tentang kekuatan komputasi kuantum.

Paralelisme kuantum dan batasannya

Sebagian kekuatan komputasi kuantum berasal dari "paralelisme kuantum," yang pada dasarnya adalah kemampuan untuk melakukan operasi pada banyak input sekaligus, karena state input Qubit bisa berada dalam superposisi dari banyak state yang diperbolehkan secara klasik. NAMUN, meskipun sebuah Circuit kuantum mungkin bisa mengevaluasi banyak state input sekaligus, mengekstrak semua informasi itu dalam satu kali pengukuran adalah hal yang mustahil.

Untuk memahami maksudnya, katakanlah kita punya sebuah bit, $x$ dan suatu fungsi yang diterapkan pada bit tersebut, $f(x)$. Ada empat kemungkinan fungsi biner yang mengambil satu bit ke satu bit lainnya:

$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 tahu fungsi mana (1-4) yang merupakan $f(x)$ kita. Secara klasik, kita perlu menjalankan fungsi dua kali — sekali untuk $x=0$, sekali untuk $x=1$. Tapi mari lihat apakah kita bisa melakukan lebih baik dengan Circuit kuantum. Kita bisa mempelajari fungsinya dengan Gate berikut:

Di sini, Gate $U_f$ menghitung $f(x)$, di mana $x$ adalah state dari Qubit 0, dan menerapkannya ke Qubit 1. Jadi, state yang dihasilkan, $|x\rangle|y\oplus f(x)\rangle$, menjadi $|x\rangle|f(x)\rangle$ ketika $|y\rangle = |0\rangle$. Ini mengandung semua informasi yang kita butuhkan untuk mengetahui fungsi $f(x)$: Qubit 0 memberi tahu kita apa itu $x$, dan Qubit 1 memberi tahu kita apa itu $f(x)$. Jadi, jika kita menginisialisasi $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, maka state akhir dari kedua Qubit akan menjadi: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Tapi bagaimana kita mengakses informasi itu?

2.1. Coba di Qiskit:

Menggunakan Qiskit, kita akan memilih secara acak salah satu dari empat fungsi yang mungkin di atas dan menjalankan Circuit-nya. Kemudian tugasmu adalah menggunakan pengukuran Circuit kuantum untuk mempelajari fungsinya dengan sesedikit mungkin percobaan.

Dalam eksperimen pertama ini dan sepanjang modul, kita akan menggunakan kerangka kerja untuk komputasi kuantum yang dikenal sebagai "Qiskit patterns," yang membagi alur kerja menjadi langkah-langkah berikut:

• Langkah 1: Petakan input klasik ke masalah kuantum
• Langkah 2: Optimalkan masalah untuk eksekusi kuantum
• Langkah 3: Eksekusi menggunakan Qiskit Runtime Primitives
• Langkah 4: Post-processing dan analisis klasik

Mari mulai dengan memuat beberapa paket yang diperlukan, termasuk Qiskit Runtime primitives. Kita juga akan memilih komputer kuantum yang paling tidak sibuk yang tersedia untuk kita.

Ada kode di bawah untuk menyimpan kredensialmu saat pertama kali digunakan. Pastikan untuk menghapus informasi ini dari notebook setelah menyimpannya ke lingkunganmu, agar kredensialmu tidak sengaja dibagikan saat kamu berbagi notebook. Lihat Set up your IBM Cloud account dan Initialize the service in an untrusted environment untuk panduan lebih 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

Cell di bawah ini memungkinkanmu untuk beralih antara menggunakan simulator atau hardware nyata sepanjang notebook. Kami sarankan untuk 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)

Sekarang setelah kita memuat paket-paket yang diperlukan, kita bisa melanjutkan dengan alur kerja Qiskit patterns. Pada langkah pemetaan di bawah, kita pertama-tama membuat fungsi yang memilih di antara empat fungsi yang mungkin yang mengambil satu bit ke satu bit lainnya.

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

Pada Circuit di atas, Gate Hadamard "H" mengambil Qubit 0, yang awalnya dalam state $|0\rangle$, ke state superposisi $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Kemudian, $U_f$ mengevaluasi fungsi $f(x)$ dan menerapkannya ke Qubit 1.

Selanjutnya kita perlu mengoptimalkan dan mentranspilasi Circuit agar bisa dijalankan di 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 jalankan Circuit yang telah ditranspilasi di komputer kuantum dan visualisasikan hasilnya:

# 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 dari hasil kita. Tergantung pada jumlah shots yang kamu pilih untuk menjalankan Circuit di langkah 3 di atas, kamu mungkin melihat satu atau dua batang, yang mewakili state terukur dari kedua Qubit di setiap shot. Seperti biasa dengan Qiskit dan dalam notebook ini, kita menggunakan notasi "little endian," yang berarti state dari Qubit 0 hingga n ditulis dalam urutan naik dari kanan ke kiri, sehingga Qubit 0 selalu paling kanan.

Jadi, karena Qubit 0 berada dalam state superposisi, Circuit mengevaluasi fungsi untuk keduanya $x=0$ dan $x=1$ pada saat yang sama — sesuatu yang tidak bisa dilakukan komputer klasik! Tapi masalahnya muncul ketika kita ingin mempelajari fungsi $f(x)$ — ketika kita mengukur Qubit, kita meng-collapse state-nya. Jika kamu memilih "shots = 1" untuk hanya menjalankan Circuit sekali, kamu hanya akan melihat satu batang dalam histogram di atas, dan informasimu tentang fungsi tersebut akan tidak lengkap.

Uji pemahamanmu

Baca pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Berapa kali kita harus menjalankan algoritma di atas untuk mempelajari fungsi $f(x)$? Apakah ini lebih baik dari kasus klasik? Apakah kamu lebih memilih komputer klasik atau kuantum untuk menyelesaikan masalah ini?

Jawaban:

Karena pengukuran akan meng-collapse superposisi dan hanya mengembalikan satu nilai, kita perlu menjalankan Circuit minimal dua kali untuk mendapatkan kedua output dari fungsi $f(0)$ dan $f(1)$. Paling baik, ini bekerja sama seperti kasus klasik, di mana kita menghitung baik $f(0)$ maupun $f(1)$ dalam dua kueri pertama. Tapi ada kemungkinan kita perlu menjalankannya lebih dari dua kali, karena pengukuran akhir bersifat probabilistik dan mungkin mengembalikan nilai $f(x)$ yang sama di dua kali pertama. Aku lebih memilih komputer klasik dalam kasus ini.

Jadi, meskipun paralelisme kuantum bisa sangat powerful ketika digunakan dengan cara yang tepat, tidak benar untuk mengatakan bahwa komputer kuantum bekerja seperti prosesor paralel klasik yang sangat besar. Tindakan pengukuran meng-collapse state kuantum, sehingga kita hanya bisa mengakses satu output dari komputasi tersebut.

Algoritma Deutsch

Meskipun paralelisme kuantum saja tidak memberi kita keunggulan atas komputer klasik, kita bisa menggabungkannya dengan fenomena kuantum lain, interferensi, untuk mencapai percepatan. Algoritma yang sekarang dikenal sebagai "algoritma Deutsch" adalah contoh pertama dari algoritma yang berhasil melakukan ini.

Masalahnya

Inilah masalahnya:

Diberikan sebuah bit input, $x = \{0,1\}$, dan fungsi input $f(x) = \{0,1\}$, tentukan apakah fungsinya balanced atau constant. Artinya, jika balanced, maka output dari fungsinya adalah 0 setengah dari waktu dan 1 setengah lainnya. Jika constant, maka output dari fungsinya selalu 0 atau selalu 1. Ingat tabel empat fungsi yang mungkin yang mengambil satu bit ke satu bit lainnya:

$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 constant, sementara dua fungsi di tengah, $f_2(x)$ dan $f_3(x)$, adalah balanced.

Algoritmanya

Cara Deutsch mendekati masalah ini adalah melalui "model kueri." Dalam model kueri, fungsi input ($f_i(x)$ di atas) terkandung dalam sebuah "kotak hitam" — kita tidak punya akses langsung ke isinya, tapi kita bisa melakukan kueri ke kotak hitam tersebut dan ia akan memberikan output dari fungsinya. Kadang kita mengatakan bahwa sebuah "oracle" menyediakan informasi ini. Lihat Lesson 1: Quantum Query Algorithms dari kursus Fundamentals of Quantum Algorithms untuk informasi lebih lanjut tentang model kueri.

Untuk menentukan apakah algoritma kuantum lebih efisien dari algoritma klasik dalam model kueri, kita bisa membandingkan jumlah kueri yang perlu kita lakukan ke kotak hitam di setiap kasus. Dalam kasus klasik, untuk mengetahui apakah fungsi yang terkandung dalam kotak hitam itu balanced atau constant, kita perlu melakukan kueri ke kotak tersebut dua kali untuk mendapatkan $f(0)$ dan $f(1)$.

Dalam algoritma kuantum Deutsch, ia menemukan cara untuk mendapatkan informasi hanya dengan satu kueri! Ia membuat satu penyesuaian pada Circuit "paralelisme kuantum" di atas, sehingga ia menyiapkan state superposisi pada kedua Qubit, bukan hanya pada Qubit 0. Kemudian dua output dari fungsi, $f(0)$ dan $f(1)$ berinterferensi untuk mengembalikan 0 jika keduanya 0 atau keduanya 1 (fungsinya constant), dan mengembalikan 1 jika keduanya berbeda (fungsinya balanced). Dengan cara ini, Deutsch bisa membedakan antara fungsi constant dan balanced hanya dengan satu kueri.

Berikut adalah diagram Circuit dari algoritma Deutsch:

Untuk memahami cara kerja algoritma ini, mari lihat state kuantum dari Qubit pada tiga titik yang ditandai pada diagram di atas. Coba kerjakan state-nya sendiri sebelum mengklik untuk melihat jawabannya:

Uji pemahamanmu

Baca pertanyaan-pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Apa state $|\pi_1\rangle$?

Jawaban:

Menerapkan Hadamard mengubah state $|0\rangle$ menjadi $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ dan state $|1\rangle$ menjadi $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Jadi, state penuhnya menjadi: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Apa state $|\pi_2\rangle$?

Jawaban:

Sebelum kita menerapkan $U_f$, ingat apa yang dilakukannya. Ia akan mengubah state Qubit 1 berdasarkan state Qubit 0. Jadi, masuk akal untuk memfaktorkan state 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)$, dua suku tersebut akan bertransformasi dengan cara yang sama dan tanda relatif antara dua suku tetap positif, tapi jika $f(0)\neq f(1)$, maka itu berarti suku kedua akan mendapat tanda minus relatif terhadap suku pertama, mengubah state Qubit 0 dari $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ menjadi $\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}$$

Apa state $|\pi_3\rangle$?

Jawaban:

Sekarang, state Qubit 0 adalah $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ atau $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, tergantung pada fungsinya. Menerapkan Hadamard akan menghasilkan $|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 jawabanmu untuk pertanyaan-pertanyaan di atas, perhatikan bahwa ada sesuatu yang sedikit mengejutkan terjadi. Meskipun $U_f$ tidak secara eksplisit melakukan apa pun pada state Qubit 0, karena ia mengubah Qubit 1 berdasarkan state Qubit 0, hal ini bisa menyebabkan pergeseran fase pada Qubit 0. Ini dikenal sebagai fenomena "phase-kickback," dan dibahas lebih detail dalam Lesson 1: Quantum Query Algorithms dari kursus Fundamentals of Quantum Algorithms.

Sekarang setelah kita memahami cara kerja algoritma ini, mari implementasikan 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 awal yang penting dalam menunjukkan bagaimana komputer kuantum bisa lebih efisien dari komputer klasik, tapi peningkatannya masih terbatas: hanya butuh satu query, dibandingkan dua pada kasus klasik. Pada tahun 1992, Deutsch bersama rekannya, Richard Jozsa, memperluas algoritma dua-Qubit asli ke lebih banyak Qubit. Masalahnya tetap sama: menentukan apakah sebuah fungsi balanced atau constant. Tapi kali ini, fungsinya memetakan $n$ bit ke satu bit. Fungsi tersebut bisa mengembalikan 0 dan 1 dalam jumlah yang sama (balanced) atau selalu mengembalikan 1 atau selalu 0 (constant).

Berikut diagram Circuit dari algoritma ini:

Algoritma ini bekerja dengan cara yang sama seperti algoritma Deutsch: phase-kickback memungkinkan kita membaca keadaan Qubit 0 untuk menentukan apakah fungsinya constant atau balanced. Ini sedikit lebih sulit untuk dilihat dibanding kasus algoritma Deutsch dua-Qubit, karena keadaannya akan mencakup penjumlahan atas $n$ Qubit, sehingga menghitung keadaan tersebut akan ditinggalkan sebagai latihan opsional untukmu di akhir modul. Algoritma akan mengembalikan bitstring semua 0 jika fungsinya constant, dan bitstring yang mengandung setidaknya satu 1 jika fungsinya balanced.

Untuk melihat cara kerja algoritma ini di Qiskit, pertama-tama kita perlu membuat oracle: fungsi acak yang dijamin constant atau balanced. Kode di bawah akan menghasilkan fungsi balanced 50% dari waktu, dan fungsi constant 50% dari waktu. Jangan khawatir jika kamu tidak sepenuhnya memahami kodenya — ini cukup rumit dan tidak diperlukan untuk memahami algoritma kuantumnya.

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 bisa balanced atau constant. Bisakah kamu melihat dari Circuit tersebut apakah output pada Qubit terakhir bergantung pada nilai yang dimasukkan untuk $n$ Qubit pertama? Jika output untuk Qubit terakhir bergantung pada $n$ Qubit pertama, bisakah kamu menentukan apakah output yang bergantung itu balanced atau tidak?

Kita bisa menentukan apakah fungsinya balanced atau constant dengan melihat Circuit di atas, tapi ingat, untuk keperluan masalah ini, kita menganggap fungsi ini sebagai "kotak hitam." Kita tidak bisa mengintip ke dalam kotak untuk melihat diagram Circuit. Sebagai gantinya, kita perlu melakukan query ke kotak tersebut.

Untuk melakukan query ke kotak, kita menggunakan algoritma Deutsch-Jozsa dan menentukan apakah fungsinya constant atau balanced:

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 dari hasil pengukuran. Baris kedua menampilkan apakah bitstring tersebut mengimplikasikan fungsinya balanced atau constant. Jika bitstring berisi semua nol, maka fungsinya constant; jika tidak, maka balanced. Jadi, hanya dengan satu kali menjalankan Circuit kuantum di atas, kita bisa menentukan apakah fungsinya constant atau balanced!

Cek pemahamanmu

Baca pertanyaan-pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Berapa banyak query yang dibutuhkan komputer klasik untuk menentukan dengan kepastian 100% apakah sebuah fungsi constant atau balanced? Ingat, secara klasik, satu query hanya memungkinkan kamu menerapkan fungsi ke satu bitstring.

Jawaban:

Ada $2^n$ bitstring yang mungkin untuk dicek, dan dalam kasus terburuk, kamu perlu menguji $2^n/2+1$ di antaranya. Misalnya, jika fungsinya constant, dan kamu terus mengukur "1" sebagai output fungsi, maka kamu tidak bisa yakin bahwa fungsinya benar-benar constant sampai kamu memeriksa lebih dari separuh hasilnya. Sebelum itu, mungkin saja kamu hanya sangat sial terus mengukur "1" pada fungsi balanced. Ini seperti melempar koin berulang kali dan selalu mendapat kepala. Kemungkinannya kecil, tapi bukan tidak mungkin.

Bagaimana jawabanmu di atas berubah jika kamu hanya perlu mengukur sampai salah satu hasil (balanced atau constant) lebih mungkin dari yang lain? Berapa banyak query yang dibutuhkan dalam kasus ini?

Jawaban:

Dalam kasus ini, kamu hanya perlu mengukur dua kali. Jika dua pengukuran berbeda, kamu tahu fungsinya balanced. Jika dua pengukuran sama, bisa jadi balanced atau constant. Probabilitas bahwa fungsinya balanced dengan set pengukuran ini adalah: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Ini kurang dari 1/2, sehingga lebih mungkin fungsinya constant dalam kasus ini.

Jadi, algoritma Deutsch-Jozsa mendemonstrasikan percepatan eksponensial atas algoritma klasik deterministik (yang mengembalikan jawaban dengan kepastian 100%), tapi tidak ada percepatan signifikan atas algoritma probabilistik (yang mengembalikan hasil yang kemungkinan besar benar).

Masalah Bernstein-Vazirani

Pada tahun 1997, Ethan Bernstein dan Umesh Vazirani menggunakan algoritma Deutsch-Jozsa untuk menyelesaikan masalah yang lebih spesifik dan terbatas dibandingkan masalah Deutsch-Jozsa. Daripada sekadar membedakan dua kelas fungsi berbeda seperti pada kasus D-J, Bernstein dan Vazirani menggunakan algoritma Deutsch-Jozsa untuk benar-benar mempelajari string yang dikodekan dalam suatu fungsi. Berikut masalahnya:

Fungsi $f:\{0,1\}^n \rightarrow \{0,1\}$ masih menerima string $n$-bit dan menghasilkan satu bit. Tapi sekarang, alih-alih menjanjikan bahwa fungsinya balanced atau constant, kita dijanjikan bahwa fungsinya adalah hasil perkalian titik antara string input $x$ dan string $n$-bit rahasia $s$, modulo 2. (Perkalian titik modulo 2 ini disebut "perkalian titik biner.") Masalahnya adalah mencari tahu apa string $n$-bit rahasia tersebut.

Dengan kata lain, kita diberikan fungsi kotak-hitam $f: {0,1}^n \rightarrow {0,1}$ yang memenuhi $f(x) = s \cdot x$ untuk suatu string $s$, dan kita ingin mengetahui string $s$.

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

1. Pertama, Gate Hadamard diterapkan ke $n$ Qubit input, dan Gate NOT plus Hadamard diterapkan ke Qubit output, menghasilkan keadaan:

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

Keadaan Qubit 1 hingga $n$ bisa ditulis lebih sederhana sebagai penjumlahan atas semua $2^n$ keadaan basis $n$-Qubit $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Kita sebut himpunan keadaan basis ini $\Sigma^n$. (Lihat Fundamentals of Quantum Algorithms untuk detail lebih lanjut.)

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

2. Selanjutnya, Gate $U_f$ diterapkan ke Qubit-Qubit tersebut. Gate ini akan menerima $n$ Qubit pertama sebagai input (yang sekarang berada dalam superposisi merata dari semua string $n$-bit yang mungkin) dan menerapkan fungsi $f(x)=s \cdot x$ ke Qubit output, sehingga Qubit ini sekarang berada dalam keadaan: $|- \oplus f(x)\rangle$. Berkat mekanisme phase kickback, keadaan Qubit ini tetap tidak berubah, tapi beberapa suku dalam keadaan Qubit input mendapatkan tanda minus:

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

3. Sekarang, serangkaian Gate Hadamard berikutnya diterapkan ke Qubit 0 hingga $n-1$. Melacak tanda minus dalam kasus ini bisa rumit. Berguna untuk mengetahui bahwa menerapkan lapisan Hadamard ke $n$ Qubit dalam keadaan basis standar $|x\rangle$ bisa ditulis sebagai:

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

Sehingga keadaannya 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 berikutnya adalah mengukur $n$ bit pertama. Tapi apa yang akan kita ukur? Ternyata keadaan di atas menyederhanakan menjadi: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, tapi itu tidak terlihat jelas. Jika kamu ingin mengikuti matematikanya, lihat kursus Fundamentals of Quantum Algorithms oleh John Watrous. Intinya, mekanisme phase kickback menyebabkan Qubit input berada dalam keadaan $|s\rangle$. Jadi, untuk mengetahui apa string rahasia $s$, kamu cukup mengukur Qubit-Qubit tersebut!

Cek pemahamanmu

Baca pertanyaan-pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Verifikasi bahwa keadaan dari Langkah 3 di atas memang merupakan keadaan $|s\rangle$ untuk kasus khusus $n=1$.

Jawaban:

Ketika kamu menuliskan secara eksplisit dua penjumlahan tersebut, kamu akan mendapatkan keadaan dengan empat suku (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 suku pertama saling menguatkan dan dua suku terakhir saling menghapus, sehingga tersisa $|\Psi\rangle = |0\rangle$. Jika $s=1$, maka dua suku terakhir saling menguatkan dan dua suku pertama saling menghapus, sehingga tersisa $|\Psi\rangle = |1\rangle$. Jadi, dalam kedua kasus, $|\Psi\rangle = |s\rangle$. Semoga kasus paling sederhana ini memberimu gambaran tentang bagaimana kasus umum dengan $n$ Qubit bekerja: semua suku yang bukan $|s\rangle$ saling menghapus, menyisakan hanya keadaan $|s\rangle$.

Bagaimana algoritma yang sama bisa menyelesaikan baik masalah Bernstein-Vazirani maupun Deutsch-Jozsa? Untuk memahaminya, pikirkan tentang fungsi Bernstein-Vazirani yang berbentuk $f(x) = s \cdot x$. Apakah fungsi-fungsi ini juga merupakan fungsi Deutsch-Jozsa? Yaitu, tentukan apakah fungsi-fungsi dalam bentuk ini memenuhi janji masalah Deutsch-Jozsa: bahwa fungsinya constant atau balanced. Bagaimana ini membantu kita memahami bagaimana algoritma yang sama menyelesaikan dua masalah berbeda?

Jawaban:

Setiap fungsi Bernstein-Vazirani berbentuk $f(x) = s \cdot x$ juga memenuhi janji masalah Deutsch-Jozsa: jika s=00...00, maka fungsinya constant (selalu mengembalikan 0 untuk setiap string x). Jika s adalah string lain, maka fungsinya balanced. Jadi, menerapkan algoritma Deutsch-Jozsa ke salah satu fungsi ini secara bersamaan menyelesaikan kedua masalah! Algoritma mengembalikan stringnya, dan jika string itu 00...00 maka kita tahu fungsinya constant; jika ada setidaknya satu "1" dalam string, kita tahu fungsinya balanced.

Kita juga bisa memverifikasi bahwa algoritma ini berhasil menyelesaikan masalah Bernstein-Vazirani dengan mengujinya secara eksperimental. Pertama, kita buat fungsi B-V yang ada 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, hanya dengan satu query, algoritma Deutsch-Jozsa akan mengembalikan string $s$ yang digunakan dalam fungsi: $f(x)=x \cdot s$ ketika kita terapkan ke masalah Bernstein-Vazirani. Dengan algoritma klasik, seseorang membutuhkan $n$ query untuk menyelesaikan masalah yang sama.

Kesimpulan

Kami berharap dengan mengamati contoh-contoh sederhana ini, kami telah memberikanmu intuisi yang lebih baik tentang bagaimana komputer kuantum mampu memanfaatkan superposisi, entanglement, dan interferensi untuk mencapai keunggulannya atas komputer klasik.

Algoritma Deutsch-Jozsa memiliki kepentingan historis yang besar karena merupakan yang pertama mendemonstrasikan percepatan apa pun atas algoritma klasik, tapi itu hanya percepatan polinomial. Algoritma Deutsch-Jozsa hanyalah awal dari cerita ini.

Setelah menggunakan algoritma tersebut untuk menyelesaikan masalah mereka, Bernstein dan Vazirani menggunakannya sebagai dasar untuk masalah rekursif yang lebih kompleks yang disebut masalah recursive Fourier sampling. Solusi mereka menawarkan percepatan super-polinomial atas algoritma klasik. Dan bahkan sebelum Bernstein dan Vazirani, Peter Shor sudah menemukan algoritmanya yang terkenal yang memungkinkan komputer kuantum memfaktorkan bilangan besar secara eksponensial lebih cepat daripada algoritma klasik mana pun. Hasil-hasil ini secara kolektif menunjukkan janji menarik dari komputer kuantum masa depan, dan mendorong para fisikawan dan insinyur untuk mewujudkan masa depan tersebut.

Pertanyaan

Instruktur dapat meminta versi notebook ini dengan kunci jawaban dan panduan penempatan dalam kurikulum umum dengan mengisi survei singkat ini tentang bagaimana notebook digunakan.

Konsep kritis

• Algoritma Deutsch dan Deutsch-Jozsa menggunakan paralelisme kuantum dikombinasikan dengan interferensi untuk menemukan jawaban atas suatu masalah lebih cepat daripada komputer klasik.
• Mekanisme phase kickback adalah fenomena kuantum yang tidak intuitif yang mentransfer operasi pada satu Qubit ke fase Qubit lainnya. Algoritma Deutsch dan Deutsch-Jozsa memanfaatkan mekanisme ini.
• Algoritma Deutsch-Jozsa menawarkan percepatan polinomial atas algoritma klasik deterministik mana pun.
• Algoritma Deutsch-Jozsa bisa diterapkan ke masalah yang berbeda, yang disebut masalah Bernstein-Vazirani, untuk menemukan string tersembunyi yang dikodekan dalam suatu fungsi.

Benar/Salah

1. B/S Algoritma Deutsch adalah kasus khusus dari algoritma Deutsch-Jozsa di mana inputnya adalah satu Qubit.
2. B/S Algoritma Deutsch dan Deutsch-Jozsa menggunakan superposisi kuantum dan interferensi untuk mencapai efisiensinya.
3. B/S Algoritma Deutsch-Jozsa membutuhkan beberapa evaluasi fungsi untuk menentukan apakah suatu fungsi constant atau balanced.
4. B/S "Algoritma Bernstein-Vazirani" sebenarnya sama dengan algoritma Deutsch-Jozsa, diterapkan ke masalah yang berbeda.
5. B/S Algoritma Bernstein-Vazirani bisa menemukan beberapa string rahasia secara bersamaan.

Jawaban singkat

1. Berapa lama algoritma klasik untuk menyelesaikan masalah Deutsch-Jozsa dalam kasus terburuk?

2. Berapa lama algoritma klasik untuk menyelesaikan masalah Bernstein-Vazirani? Percepatan apa yang ditawarkan algoritma DJ dalam kasus ini?

3. Jelaskan mekanisme phase-kickback dan bagaimana cara kerjanya untuk menyelesaikan masalah Deutsch-Jozsa dan Bernstein-Vazirani.

Soal tantangan

1. Algoritma Deutsch-Jozsa: Ingat bahwa kamu punya pertanyaan di atas yang memintamu menghitung keadaan Qubit perantara $\pi_1$ dan $\pi_2$ dari algoritma Deutsch. Lakukan hal yang sama untuk keadaan $(n+1)$-Qubit perantara $\pi_1$ dan $\pi_2$ dari algoritma Deutsch-Jozsa, untuk kasus khusus $n=2$. Kemudian, verifikasi bahwa $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, sekali lagi, untuk kasus khusus $n=2$.