อัลกอริทึม Deutsch-Jozsa

สำหรับ Qiskit in Classrooms module นี้ นักเรียนต้องมีสภาพแวดล้อม Python ที่พร้อมใช้งานพร้อมติดตั้งแพ็กเกจต่อไปนี้:

• qiskit v2.1.0 หรือใหม่กว่า
• qiskit-ibm-runtime v0.40.1 หรือใหม่กว่า
• qiskit-aer v0.17.0 หรือใหม่กว่า
• qiskit.visualization
• numpy
• pylatexenc

สำหรับการตั้งค่าและติดตั้งแพ็กเกจข้างต้น ดูคู่มือ Install Qiskit เพื่อรัน jobs บนคอมพิวเตอร์ควอนตัมจริง นักเรียนจะต้องสร้างบัญชี IBM Quantum® โดยทำตามขั้นตอนในคู่มือ Set up your IBM Cloud account

โมดูลนี้ได้รับการทดสอบและใช้เวลา QPU สี่วินาที นี่เป็นเพียงการประมาณเท่านั้น การใช้งานจริงของคุณอาจแตกต่างออกไป

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

ชมการแนะนำโมดูลโดย Dr. Katie McCormick ด้านล่าง หรือคลิก ที่นี่ เพื่อดูบน YouTube

---

บทนำ

ในต้นทศวรรษ 1980 นักฟิสิกส์ควอนตัมและนักวิทยาการคอมพิวเตอร์มีแนวคิดคร่าวๆ ว่ากลศาสตร์ควอนตัมสามารถนำมาใช้ทำการประมวลผลที่ทรงพลังกว่าคอมพิวเตอร์คลาสสิกได้มาก เหตุผลของพวกเขาคือ: คอมพิวเตอร์คลาสสิกจำลองระบบควอนตัมได้ยาก แต่คอมพิวเตอร์ควอนตัมน่าจะทำได้มีประสิทธิภาพกว่า และหากคอมพิวเตอร์ควอนตัมสามารถจำลองระบบควอนตัมได้มีประสิทธิภาพกว่า บางทีก็อาจมีงานอื่นที่ทำได้มีประสิทธิภาพกว่าคอมพิวเตอร์คลาสสิกด้วย

ตรรกะนั้นสมเหตุสมผล แต่รายละเอียดยังต้องได้รับการพัฒนา จุดเริ่มต้นคือในปี 1985 เมื่อ David Deutsch อธิบาย "universal quantum computer" เครื่องแรก ในงานชิ้นเดียวกันนี้ เขายังได้ให้ตัวอย่างปัญหาแรกที่คอมพิวเตอร์ควอนตัมสามารถแก้ได้มีประสิทธิภาพกว่าคอมพิวเตอร์คลาสสิก ตัวอย่างทดสอบแรกนี้ปัจจุบันเรียกว่า "อัลกอริทึม Deutsch" การพัฒนาในอัลกอริทึม Deutsch นั้นยังไม่มากนัก แต่ Deutsch ได้ร่วมงานกับ Richard Jozsa ในภายหลังเพื่อขยายช่องว่างระหว่างคอมพิวเตอร์คลาสสิกและควอนตัมให้กว้างขึ้นอีก

อัลกอริทึมเหล่านี้ — ของ Deutsch และส่วนขยาย Deutsch-Jozsa — ไม่ได้มีประโยชน์มากนัก แต่ยังคงมีความสำคัญมากด้วยเหตุผลสองสามประการ:

1. ในแง่ประวัติศาสตร์ อัลกอริทึมเหล่านี้เป็นหนึ่งในอัลกอริทึมควอนตัมแรกๆ ที่แสดงให้เห็นว่าสามารถเอาชนะคู่แข่งคลาสสิกได้ การทำความเข้าใจจะช่วยให้เราเข้าใจว่าแนวคิดของชุมชนเกี่ยวกับการประมวลผลควอนตัมพัฒนามาอย่างไรตามกาลเวลา
2. ช่วยให้เราเข้าใจบางแง่มุมของคำตอบสำหรับคำถามที่น่าแปลกใจอย่างยิ่ง: อะไรทำให้การประมวลผลควอนตัมมีพลัง? บางครั้งคอมพิวเตอร์ควอนตัมถูกเปรียบเหมือนโปรเซสเซอร์ขนาน giant ที่ขยายแบบเอกซ์โพเนนเชียล แต่นั่นไม่ค่อยถูกต้องนัก แม้ว่าส่วนหนึ่งของคำตอบจะอยู่ที่สิ่งที่เรียกว่า "quantum parallelism" แต่การดึงข้อมูลให้ได้มากที่สุดในการรันครั้งเดียวนั้นเป็นศิลปะที่ละเอียดอ่อน อัลกอริทึม Deutsch และ Deutsch-Jozsa แสดงให้เห็นว่าทำได้อย่างไร

ในโมดูลนี้ เราจะเรียนรู้เกี่ยวกับอัลกอริทึม Deutsch, อัลกอริทึม Deutsch-Jozsa และสิ่งที่พวกมันสอนเราเกี่ยวกับพลังของการประมวลผลควอนตัม

Quantum parallelism และข้อจำกัดของมัน

ส่วนหนึ่งของพลังของการประมวลผลควอนตัมมาจาก "quantum parallelism" ซึ่งโดยพื้นฐานแล้วคือความสามารถในการดำเนินการกับ input หลายตัวพร้อมกัน เนื่องจาก state ของ Qubit input อาจอยู่ใน superposition ของ state ที่อนุญาตทางคลาสสิกหลาย state อย่างไรก็ตาม แม้ว่า quantum circuit อาจสามารถประเมิน input state หลาย state พร้อมกัน แต่การดึงข้อมูลทั้งหมดนั้นในครั้งเดียวเป็นสิ่งที่เป็นไปไม่ได้

เพื่อให้เห็นภาพ สมมติเราเีย bit $x$ และฟังก์ชันบางอย่างที่ใช้กับ bit นั้น $f(x)$ มีฟังก์ชันไบนารีสี่แบบที่เป็นไปได้ซึ่งรับ bit เดียวไปยัง bit เดียวอีกตัว:

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

เราต้องการหาว่า $f(x)$ ของเราเป็นฟังก์ชันไหน (1-4) ในทางคลาสสิก เราจะต้องรันฟังก์ชันสองครั้ง — ครั้งหนึ่งสำหรับ $x=0$ และอีกครั้งสำหรับ $x=1$ แต่ลองดูว่าเราสามารถทำได้ดีกว่าด้วย quantum circuit หรือไม่ เราสามารถเรียนรู้เกี่ยวกับฟังก์ชันด้วย gate ต่อไปนี้:

ที่นี่ Gate $U_f$ คำนวณ $f(x)$ โดยที่ $x$ คือ state ของ Qubit 0 และนำผลลัพธ์ไปใช้กับ Qubit 1 ดังนั้น state ที่ได้ $|x\rangle|y\oplus f(x)\rangle$ จะกลายเป็น $|x\rangle|f(x)\rangle$ เมื่อ $|y\rangle = |0\rangle$ ซึ่งประกอบด้วยข้อมูลทั้งหมดที่จำเป็นในการรู้ฟังก์ชัน $f(x)$: Qubit 0 บอกเราว่า $x$ คืออะไร และ Qubit 1 บอกเราว่า $f(x)$ คืออะไร ดังนั้น หากเราตั้งค่า $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ แล้ว state สุดท้ายของ Qubit ทั้งสองจะเป็น: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$ แต่เราจะเข้าถึงข้อมูลนั้นได้อย่างไร?

2.1. ลองทำบน Qiskit:

ด้วย Qiskit เราจะสุ่มเลือกฟังก์ชันหนึ่งในสี่ฟังก์ชันที่เป็นไปได้ข้างต้นแล้วรัน Circuit จากนั้นงานของคุณคือใช้ผลการวัดของ quantum circuit เพื่อเรียนรู้ฟังก์ชันด้วยการรันให้น้อยที่สุด

ในการทดลองแรกนี้และตลอดทั้งโมดูล เราจะใช้กรอบการทำงานสำหรับการประมวลผลควอนตัมที่เรียกว่า "Qiskit patterns" ซึ่งแบ่งขั้นตอนการทำงานออกเป็น:

• ขั้นตอนที่ 1: แปลง input คลาสสิกเป็นปัญหาควอนตัม
• ขั้นตอนที่ 2: ปรับปัญหาให้เหมาะสมสำหรับการรันควอนตัม
• ขั้นตอนที่ 3: รันโดยใช้ Qiskit Runtime Primitives
• ขั้นตอนที่ 4: การประมวลผลภายหลังและการวิเคราะห์คลาสสิก

เริ่มต้นด้วยการโหลดแพ็กเกจที่จำเป็น รวมถึง Qiskit Runtime primitives เราจะเลือกคอมพิวเตอร์ควอนตัมที่ไม่ยุ่งที่สุดที่เราสามารถใช้งานได้ด้วย

มีโค้ดด้านล่างสำหรับบันทึก credentials ของคุณในการใช้งานครั้งแรก อย่าลืมลบข้อมูลนี้ออกจาก notebook หลังจากบันทึกลงในสภาพแวดล้อมของคุณแล้ว เพื่อไม่ให้ credentials ของคุณถูกแชร์โดยไม่ตั้งใจเมื่อคุณแชร์ notebook ดู Set up your IBM Cloud account และ Initialize the service in an untrusted environment สำหรับแนวทางเพิ่มเติม

# 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

เซลล์ด้านล่างจะให้คุณสลับระหว่างการใช้ simulator หรือฮาร์ดแวร์จริงตลอดทั้ง notebook แนะนำให้รันทันที:

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

เมื่อโหลดแพ็กเกจที่จำเป็นแล้ว เราสามารถดำเนินการตามขั้นตอนการทำงานของ Qiskit patterns ได้ ในขั้นตอน mapping ด้านล่าง เราสร้างฟังก์ชันที่เลือกจากฟังก์ชันสี่แบบที่เป็นไปได้ซึ่งรับ bit เดียวไปยัง 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")

ใน Circuit ข้างต้น Hadamard gate "H" นำ Qubit 0 ซึ่งเริ่มต้นอยู่ใน state $|0\rangle$ ไปสู่ superposition state $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ จากนั้น $U_f$ ประเมินฟังก์ชัน $f(x)$ และนำผลลัพธ์ไปใช้กับ Qubit 1

ต่อไปเราต้องปรับปรุงและ transpile Circuit เพื่อรันบนคอมพิวเตอร์ควอนตัม:

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

สุดท้าย เรารัน Circuit ที่ transpile แล้วบนคอมพิวเตอร์ควอนตัมและแสดงผลลัพธ์:

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

ข้างต้นคือ histogram ของผลลัพธ์ของเรา ขึ้นอยู่กับจำนวน shots ที่คุณเลือกรัน Circuit ในขั้นตอนที่ 3 ข้างต้น คุณอาจเห็นหนึ่งหรือสองแท่ง แทน state ที่วัดได้ของ Qubit ทั้งสองในแต่ละ shot อย่างที่ทราบกันดีใน Qiskit และใน notebook นี้ เราใช้สัญลักษณ์ "little endian" ซึ่งหมายความว่า state ของ Qubit 0 ถึง n เขียนตามลำดับจากขวาไปซ้าย ดังนั้น Qubit 0 จะอยู่ทางขวาสุดเสมอ

ดังนั้น เนื่องจาก Qubit 0 อยู่ใน superposition state Circuit จึงประเมินฟังก์ชันสำหรับทั้ง $x=0$ และ $x=1$ พร้อมกัน — สิ่งที่คอมพิวเตอร์คลาสสิกทำไม่ได้! แต่ข้อจำกัดเกิดขึ้นเมื่อเราต้องการเรียนรู้ฟังก์ชัน $f(x)$ — เมื่อเราวัด Qubit state ของพวกมันจะ collapse หากคุณเลือก "shots = 1" เพื่อรัน Circuit เพียงครั้งเดียว คุณจะเห็นเพียงแท่งเดียวใน histogram ข้างต้น และข้อมูลเกี่ยวกับฟังก์ชันของคุณจะไม่สมบูรณ์

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ แล้วคลิกสามเหลี่ยมเพื่อดูเฉลย

ต้องรันอัลกอริทึมข้างต้นกี่ครั้งจึงจะเรียนรู้ฟังก์ชัน $f(x)$ ได้? นี่ดีกว่ากรณีคลาสสิกหรือไม่? คุณจะเลือกคอมพิวเตอร์คลาสสิกหรือควอนตัมเพื่อแก้ปัญหานี้?

เฉลย:

เนื่องจากการวัดจะ collapse superposition และคืนค่าเพียงค่าเดียว เราต้องรัน Circuit อย่างน้อย สองครั้งเพื่อได้ output ทั้งสองของฟังก์ชัน $f(0)$ และ $f(1)$ ในกรณีที่ดีที่สุด ประสิทธิภาพจะเท่ากับกรณีคลาสสิกซึ่งเราคำนวณทั้ง $f(0)$ และ $f(1)$ ในสอง query แรก แต่มีโอกาสที่เราอาจต้องรันมากกว่าสองครั้ง เนื่องจากการวัดสุดท้ายเป็นแบบ probabilistic และอาจคืนค่า $f(x)$ เดิมสองครั้งแรก ฉันจะเลือกคอมพิวเตอร์คลาสสิกในกรณีนี้

ดังนั้น แม้ว่า quantum parallelism จะทรงพลังเมื่อใช้ถูกวิธี แต่ก็ไม่ถูกต้องที่จะบอกว่าคอมพิวเตอร์ควอนตัมทำงานเหมือนโปรเซสเซอร์ขนานขนาดใหญ่แบบคลาสสิก การวัดทำให้ quantum state collapse ดังนั้นเราจึงสามารถเข้าถึง output เดียวของการคำนวณได้เสมอ

อัลกอริทึม Deutsch

แม้ว่า quantum parallelism เพียงอย่างเดียวจะไม่ได้ให้ข้อได้เปรียบเหนือคอมพิวเตอร์คลาสสิก แต่เราสามารถจับคู่มันกับปรากฏการณ์ควอนตัมอีกอย่างหนึ่งคือ interference เพื่อให้ได้ความเร็วที่เพิ่มขึ้น อัลกอริทึมที่ปัจจุบันรู้จักกันในชื่อ "อัลกอริทึม Deutsch" คือตัวอย่างแรกของอัลกอริทึมที่บรรลุสิ่งนี้

ปัญหา

ปัญหาคือ:

กำหนด input bit $x = \{0,1\}$ และ input function $f(x) = \{0,1\}$ ให้ระบุว่าฟังก์ชันนั้นbalanced หรือ constant นั่นคือ ถ้า balanced แสดงว่า output ของฟังก์ชันเป็น 0 ครึ่งหนึ่งของเวลาและเป็น 1 อีกครึ่งหนึ่ง ถ้า constant แสดงว่า output ของฟังก์ชันเป็น 0 หรือ 1 เสมอ ลองนึกถึงตารางฟังก์ชันสี่แบบที่เป็นไปได้ซึ่งรับ bit เดียวไปยัง bit เดียว:

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

ฟังก์ชันแรกและสุดท้าย $f_1(x)$ และ $f_4(x)$ เป็น constant ส่วนสองฟังก์ชันกลาง $f_2(x)$ และ $f_3(x)$ เป็น balanced

อัลกอริทึม

วิธีที่ Deutsch เข้าถึงปัญหานี้คือผ่าน "query model" ใน query model input function ($f_i(x)$ ข้างต้น) อยู่ใน "black box" — เราไม่มีสิทธิ์เข้าถึงเนื้อหาโดยตรง แต่เราสามารถ query black box และมันจะให้ output ของฟังก์ชันแก่เรา บางครั้งเราบอกว่า "oracle" ให้ข้อมูลนี้ ดู บทที่ 1: Quantum Query Algorithms ของหลักสูตร Fundamentals of Quantum Algorithms สำหรับข้อมูลเพิ่มเติมเกี่ยวกับ query model

เพื่อพิจารณาว่าอัลกอริทึมควอนตัมมีประสิทธิภาพมากกว่าอัลกอริทึมคลาสสิกใน query model หรือไม่ เราสามารถเปรียบเทียบจำนวน query ที่เราต้องทำกับ black box ในแต่ละกรณี ในกรณีคลาสสิก เพื่อทราบว่าฟังก์ชันใน black box เป็น balanced หรือ constant เราจะต้อง query กล่องสองครั้งเพื่อได้ทั้ง $f(0)$ และ $f(1)$

ในอัลกอริทึมควอนตัมของ Deutsch เขาพบวิธีที่จะได้ข้อมูลด้วยการ query เพียงครั้งเดียว! เขาทำการปรับเปลี่ยนหนึ่งอย่างใน Circuit "quantum parallelism" ข้างต้น โดยเตรียม superposition state บนทั้งสอง Qubit แทนที่จะเตรียมเฉพาะ Qubit 0 จากนั้น output ทั้งสองของฟังก์ชัน $f(0)$ และ $f(1)$ จะ interfere เพื่อคืนค่า 0 หากทั้งคู่เป็น 0 หรือทั้งคู่เป็น 1 (ฟังก์ชันเป็น constant) และคืนค่า 1 หากต่างกัน (ฟังก์ชันเป็น balanced) ด้วยวิธีนี้ Deutsch สามารถแยกแยะระหว่างฟังก์ชัน constant และ balanced ด้วยการ query เพียงครั้งเดียว

นี่คือ Circuit diagram ของอัลกอริทึม Deutsch:

เพื่อทำความเข้าใจว่าอัลกอริทึมนี้ทำงานอย่างไร มาดู quantum state ของ Qubit ที่จุดสามจุดที่ระบุในแผนภาพข้างต้น ลองหา state ด้วยตัวเองก่อนคลิกเพื่อดูคำตอบ:

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ แล้วคลิกสามเหลี่ยมเพื่อดูเฉลย

State $|\pi_1\rangle$ คืออะไร?

เฉลย:

การใช้ Hadamard แปลง state $|0\rangle$ เป็น $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ และ state $|1\rangle$ เป็น $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ ดังนั้น state ทั้งหมดจะกลายเป็น: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

State $|\pi_2\rangle$ คืออะไร?

เฉลย:

ก่อนที่เราจะใช้ $U_f$ ให้จำว่ามันทำอะไร มันจะเปลี่ยน state ของ Qubit 1 ตาม state ของ Qubit 0 ดังนั้นจึงสมเหตุสมผลที่จะแยก state ของ Qubit 0 ออก: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$ จากนั้น หาก $f(0)=f(1)$ สองพจน์จะแปลงในลักษณะเดียวกัน และ sign สัมพัทธ์ระหว่างสองพจน์ยังคงเป็นบวก แต่ถ้า $f(0)\neq f(1)$ แสดงว่าพจน์ที่สองจะได้ minus sign เทียบกับพจน์แรก เปลี่ยน state ของ Qubit 0 จาก $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ เป็น $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ ดังนั้น:

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

State $|\pi_3\rangle$ คืออะไร?

เฉลย:

ขณะนี้ state ของ Qubit 0 เป็นทั้ง $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ หรือ $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ ขึ้นอยู่กับฟังก์ชัน การใช้ Hadamard จะให้ $|0\rangle$ หรือ $|1\rangle$ ตามลำดับ

$$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

เมื่อดูคำตอบสำหรับคำถามข้างต้น สังเกตว่ามีบางอย่างที่น่าแปลกใจเกิดขึ้น แม้ว่า $U_f$ จะไม่ได้ทำอะไรกับ state ของ Qubit 0 โดยตรง แต่เนื่องจากมันเปลี่ยน Qubit 1 ตาม state ของ Qubit 0 อาจเกิดขึ้นได้ว่านี่ทำให้เกิด phase shift ใน Qubit 0 ปรากฏการณ์นี้เรียกว่า "phase-kickback" และได้รับการอธิบายในรายละเอียดเพิ่มเติมใน บทที่ 1: Quantum Query Algorithms ของหลักสูตร Fundamentals of Quantum Algorithms

เมื่อเข้าใจวิธีการทำงานของอัลกอริทึมนี้แล้ว มาลอง implement ด้วย 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

อัลกอริทึม Deutsch-Jozsa

อัลกอริทึม Deutsch เป็นก้าวแรกที่สำคัญในการแสดงให้เห็นว่าคอมพิวเตอร์ควอนตัมอาจมีประสิทธิภาพมากกว่าคอมพิวเตอร์คลาสสิก แต่เป็นเพียงการพัฒนาที่ไม่มากนัก: ต้องใช้เพียง query เดียว เทียบกับสองครั้งในกรณีคลาสสิก ในปี 1992 Deutsch และเพื่อนร่วมงาน Richard Jozsa ได้ขยายอัลกอริทึมสอง Qubit ดั้งเดิมให้รองรับ Qubit มากขึ้น ปัญหายังคงเหมือนเดิม: ระบุว่าฟังก์ชันเป็นbalanced หรือ constant แต่คราวนี้ฟังก์ชันรับ $n$ bits ไปยัง bit เดียว ไม่ว่าฟังก์ชันจะคืนค่า 0 และ 1 เท่ากัน (เป็นbalanced) หรือฟังก์ชันคืนค่า 1 หรือ 0 เสมอ (เป็นconstant)

นี่คือ Circuit diagram ของอัลกอริทึม:

อัลกอริทึมนี้ทำงานในลักษณะเดียวกับอัลกอริทึม Deutsch: phase-kickback ช่วยให้อ่าน state ของ Qubit 0 เพื่อระบุว่าฟังก์ชันเป็น constant หรือ balanced ซึ่งยากกว่าในกรณีอัลกอริทึม Deutsch สอง Qubit เล็กน้อย เนื่องจาก state จะรวม sums เหนือ $n$ Qubit ดังนั้นการหา state เหล่านั้นจึงเหลือเป็นแบบฝึกหัดเพิ่มเติมสำหรับคุณในตอนท้ายของโมดูล อัลกอริทึมจะคืนค่า bitstring ของเลข 0 ทั้งหมดหากฟังก์ชัน constant และคืน bitstring ที่มีอย่างน้อยหนึ่ง 1 หากฟังก์ชัน balanced

เพื่อดูว่าอัลกอริทึมทำงานใน Qiskit อย่างไร ก่อนอื่นเราต้องสร้าง oracle ของเรา: ฟังก์ชันสุ่มที่รับประกันว่าเป็น constant หรือ balanced โค้ดด้านล่างจะสร้างฟังก์ชัน balanced 50% ของเวลาและฟังก์ชัน constant 50% ของเวลา ไม่ต้องกังวลหากคุณไม่เข้าใจโค้ดทั้งหมด — มันซับซ้อนและไม่จำเป็นต้องใช้สำหรับความเข้าใจอัลกอริทึมควอนตัมของเรา

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

นี่คือฟังก์ชัน oracle ซึ่งเป็นทั้ง balanced หรือ constant คุณมองดู Circuit แล้วบอกได้ไหมว่า output บน Qubit สุดท้ายขึ้นอยู่กับค่าที่ใส่ใน $n$ Qubit แรกหรือไม่? ถ้า output ของ Qubit สุดท้ายขึ้นอยู่กับ $n$ Qubit แรก คุณบอกได้ไหมว่า output ที่ขึ้นอยู่กับนั้นเป็น balanced หรือไม่?

เราสามารถบอกได้ว่าฟังก์ชันเป็น balanced หรือ constant โดยดู Circuit ข้างต้น แต่จำไว้ว่าเพื่อจุดประสงค์ของปัญหานี้ เราคิดว่าฟังก์ชันนี้เป็น "black box" เราไม่สามารถแอบดู Circuit diagram ได้ แต่เราต้อง query กล่อง

เพื่อ query กล่อง เราใช้อัลกอริทึม Deutsch-Jozsa และระบุว่าฟังก์ชันเป็น constant หรือ 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

ข้างต้น บรรทัดแรกของ output คือ bitstring ของผลการวัด บรรทัดที่สองแสดงว่า bitstring บ่งบอกว่าฟังก์ชันเป็น balanced หรือ constant หาก bitstring มีเลข 0 ทั้งหมด แสดงว่าเป็น constant ถ้าไม่ใช่ แสดงว่าเป็น balanced ดังนั้นด้วยการรัน quantum circuit ข้างต้นเพียงครั้งเดียว เราสามารถระบุได้ว่าฟังก์ชันเป็น constant หรือ balanced!

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ แล้วคลิกสามเหลี่ยมเพื่อดูเฉลย

คอมพิวเตอร์คลาสสิกต้องใช้กี่ query เพื่อระบุด้วยความแน่นอน 100% ว่าฟังก์ชันเป็น constant หรือ balanced? จำไว้ว่า ในทางคลาสสิก query เดียวทำให้คุณใช้ฟังก์ชันกับ bitstring เดียวเท่านั้น

เฉลย:

มี $2^n$ bitstring ที่เป็นไปได้ที่ต้องตรวจสอบ และในกรณีที่แย่ที่สุด คุณจะต้องทดสอบ $2^n/2+1$ ของสิ่งเหล่านี้ ตัวอย่างเช่น ถ้าฟังก์ชันเป็น constant และคุณยังคงวัดค่า "1" เป็น output ของฟังก์ชัน คุณจะไม่แน่ใจว่ามันเป็น constant จริงๆ จนกว่าจะตรวจสอบผลลัพธ์มากกว่าครึ่ง ก่อนนั้น คุณอาจโชคร้ายมากที่ยังคงวัดค่า "1" บนฟังก์ชัน balanced ก็ได้ เหมือนกับการโยนเหรียญซ้ำๆ แล้วออกหัวทุกครั้ง มันไม่น่าจะเกิดขึ้น แต่ก็ไม่ใช่ไม่ไปเป็นไปได้

คำตอบข้างต้นของคุณจะเปลี่ยนอย่างไรหากคุณแค่ต้องวัดจนกว่าผลลัพธ์หนึ่ง (balanced หรือ constant) มีแนวโน้มมากกว่าอีกอันหนึ่ง? ในกรณีนี้ต้องใช้กี่ query?

เฉลย:

ในกรณีนี้ คุณวัดสองครั้งก็ได้ ถ้าสองการวัดต่างกัน คุณรู้ว่าฟังก์ชันเป็น balanced ถ้าสองการวัดเหมือนกัน มันอาจเป็น balanced หรือ constant ก็ได้ ความน่าจะเป็นที่เป็น balanced ด้วยชุดการวัดนี้คือ: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$ ซึ่งน้อยกว่า 1/2 ดังนั้นมีแนวโน้มมากกว่าที่ฟังก์ชันจะ constant ในกรณีนี้

ดังนั้น อัลกอริทึม Deutsch-Jozsa แสดงให้เห็น exponential speedup เหนืออัลกอริทึมคลาสสิกแบบ deterministic (อัลกอริทึมที่คืนคำตอบด้วยความแน่นอน 100%) แต่ไม่มี speedup ที่สำคัญเหนืออัลกอริทึมprobabilistic (อัลกอริทึมที่คืนผลลัพธ์ที่น่าจะเป็นคำตอบที่ถูกต้อง)

ปัญหา Bernstein-Vazirani

ในปี 1997 Ethan Bernstein และ Umesh Vazirani ใช้อัลกอริทึม Deutsch-Jozsa เพื่อแก้ปัญหาที่เฉพาะเจาะจงและจำกัดกว่าเมื่อเทียบกับปัญหา Deutsch-Jozsa แทนที่จะพยายามแยกแยะระหว่างฟังก์ชันสองประเภทที่แตกต่างกันดังในกรณี D-J Bernstein และ Vazirani ใช้อัลกอริทึม Deutsch-Jozsa เพื่อเรียนรู้ string จริงๆ ที่ encode ไว้ในฟังก์ชัน นี่คือปัญหา:

ฟังก์ชัน $f:\{0,1\}^n \rightarrow \{0,1\}$ ยังคงรับ $n$-bit string และ output bit เดียว แต่ตอนนี้แทนที่จะ promise ว่าฟังก์ชันเป็น balanced หรือ constant เราถูก promise ว่าฟังก์ชันคือ dot product ระหว่าง input string $x$ และ secret $n$-bit string $s$ บวก modulo 2 (dot product modulo 2 นี้เรียกว่า "binary dot product") ปัญหาคือหาว่า secret $n$-bit string คืออะไร

เขียนอีกแบบหนึ่ง เราได้รับ black-box function $f: {0,1}^n \rightarrow {0,1}$ ที่ satisfy $f(x) = s \cdot x$ สำหรับ string $s$ บางตัว และเราต้องการเรียนรู้ string $s$

มาดูว่าอัลกอริทึม D-J แก้ปัญหานี้อย่างไร:

1. ขั้นแรก Hadamard gate ถูกใช้กับ $n$ input Qubit และ NOT gate บวก Hadamard ถูกใช้กับ output Qubit ทำให้ state เป็น:

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

State ของ Qubit 1 ถึง $n$ สามารถเขียนได้ง่ายกว่าเป็น sum เหนือ $n$-qubit basis states ทั้งหมด $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$ เราเรียกชุดของ basis states เหล่านี้ว่า $\Sigma^n$ (ดู Fundamentals of Quantum Algorithms สำหรับรายละเอียดเพิ่มเติม)

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

2. ถัดไป Gate $U_f$ ถูกใช้กับ Qubit ต่างๆ Gate นี้จะรับ $n$ Qubit แรกเป็น input (ซึ่งตอนนี้อยู่ใน equal superposition ของ $n$-bit string ที่เป็นไปได้ทั้งหมด) และใช้ฟังก์ชัน $f(x)=s \cdot x$ กับ output Qubit ทำให้ Qubit นี้อยู่ใน state: $|- \oplus f(x)\rangle$ ต้องขอบคุณกลไก phase kickback state ของ Qubit นี้ยังคงไม่เปลี่ยนแปลง แต่บางพจน์ใน input Qubit state ได้รับ minus sign:

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

3. ตอนนี้ชุด Hadamard ถัดไปถูกใช้กับ Qubit 0 ถึง $n-1$ การติดตาม minus sign ในกรณีนี้อาจยุ่งยาก เป็นประโยชน์ที่จะรู้ว่าการใช้ layer ของ Hadamards กับ $n$ Qubit ใน standard basis state $|x\rangle$ สามารถเขียนได้เป็น:

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

ดังนั้น state กลายเป็น:

$$|\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. ขั้นตอนถัดไปคือวัด $n$ bits แรก แต่เราจะวัดอะไรได้? ปรากฎว่า state ข้างต้น simplify เป็น: $|\Psi\rangle = |-\rangle \otimes |s\rangle$ แต่นั่นไม่ชัดเจนเลย ถ้าต้องการติดตามคณิตศาสตร์ ดูหลักสูตร Fundamentals of Quantum Algorithms ของ John Watrous ประเด็นคือกลไก phase kickback ทำให้ input Qubit อยู่ใน state $|s\rangle$ ดังนั้น เพื่อหาว่า secret string $s$ คืออะไร คุณเพียงแค่วัด Qubit!

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ แล้วคลิกสามเหลี่ยมเพื่อดูเฉลย

ยืนยันว่า state จากขั้นตอนที่ 3 ข้างต้นเป็น state $|s\rangle$ จริงๆ สำหรับกรณีพิเศษของ $n=1$

เฉลย:

เมื่อเขียน summation ทั้งสองออกมาอย่างชัดเจน คุณควรได้ state ที่มีสี่พจน์ (ขอละเว้น output state $|-\rangle$ สำหรับสิ่งนี้):

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

ถ้า $s=0$ สองพจน์แรก add constructively และสองพจน์สุดท้าย cancel เหลือ $|\Psi\rangle = |0\rangle$ ถ้า $s=1$ สองพจน์สุดท้าย add constructively และสองพจน์แรก cancel เหลือ $|\Psi\rangle = |1\rangle$ ดังนั้นในทั้งสองกรณี $|\Psi\rangle = |s\rangle$ หวังว่ากรณีง่ายที่สุดนี้จะให้คุณเข้าใจว่ากรณีทั่วไปที่มี $n$ Qubit ทำงานอย่างไร: พจน์ทั้งหมดที่ไม่ใช่ $|s\rangle$ จะ interfere ออกไป เหลือแค่ state $|s\rangle$

อัลกอริทึมเดียวกันแก้ได้ทั้งปัญหา Bernstein-Vazirani และ Deutsch-Jozsa ได้อย่างไร? เพื่อทำความเข้าใจสิ่งนี้ ลองคิดถึงฟังก์ชัน Bernstein-Vazirani ซึ่งมีรูปแบบ $f(x) = s \cdot x$ ฟังก์ชันเหล่านี้ยังเป็นฟังก์ชัน Deutsch-Jozsa ด้วยไหม? นั่นคือ ระบุว่าฟังก์ชันในรูปแบบนี้ satisfy promise ของปัญหา Deutsch-Jozsa หรือไม่: ว่าเป็นconstant หรือ balanced สิ่งนี้ช่วยให้เราเข้าใจว่าอัลกอริทึมเดียวกันแก้สองปัญหาที่แตกต่างกันได้อย่างไร?

เฉลย:

ทุกฟังก์ชัน Bernstein-Vazirani ในรูปแบบ $f(x) = s \cdot x$ ยังคง satisfy promise ของปัญหา Deutsch-Jozsa: ถ้า s=00...00 ฟังก์ชันเป็น constant (คืนค่า 0 เสมอสำหรับทุก string x) ถ้า s เป็น string อื่นใด ฟังก์ชันเป็น balanced ดังนั้น การใช้อัลกอริทึม Deutsch-Jozsa กับฟังก์ชันเหล่านี้จะแก้ทั้งสองปัญหาพร้อมกัน! มันคืน string และถ้า string นั้นเป็น 00...00 เราก็รู้ว่ามันเป็น constant ถ้ามีอย่างน้อยหนึ่ง "1" ใน string เราก็รู้ว่ามันเป็น balanced

เราสามารถยืนยันได้ด้วยว่าอัลกอริทึมนี้แก้ปัญหา Bernstein-Vazirani ได้สำเร็จโดยทดสอบจริง ขั้นแรก เราสร้างฟังก์ชัน B-V ที่อยู่ใน 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}

ดังนั้น ด้วยการ query เพียงครั้งเดียว อัลกอริทึม Deutsch-Jozsa จะคืน string $s$ ที่ใช้ในฟังก์ชัน: $f(x)=x \cdot s$ เมื่อเราใช้กับปัญหา Bernstein-Vazirani ด้วยอัลกอริทึมคลาสสิก คุณจะต้องใช้ $n$ query เพื่อแก้ปัญหาเดียวกัน

บทสรุป

หวังว่าการตรวจสอบตัวอย่างง่ายๆ เหล่านี้จะช่วยให้คุณเข้าใจว่าคอมพิวเตอร์ควอนตัมสามารถใช้ superposition, entanglement และ interference เพื่อบรรลุพลังเหนือคอมพิวเตอร์คลาสสิกได้อย่างไร

อัลกอริทึม Deutsch-Jozsa มีความสำคัญทางประวัติศาสตร์อย่างมากเพราะเป็นอัลกอริทึมแรกที่แสดงให้เห็น speedup เหนืออัลกอริทึมคลาสสิก แต่เป็นเพียง polynomial speedup อัลกอริทึม Deutsch-Jozsa เป็นเพียงจุดเริ่มต้นของเรื่องราว

หลังจากที่ Bernstein และ Vazirani ใช้อัลกอริทึมนี้แก้ปัญหาของพวกเขา พวกเขาก็ใช้มันเป็นฐานสำหรับปัญหาที่ซับซ้อนและ recursive มากขึ้นที่เรียกว่า recursive Fourier sampling problem วิธีแก้ปัญหาของพวกเขาเสนอ super-polynomial speedup เหนืออัลกอริทึมคลาสสิก และก่อน Bernstein และ Vazirani Peter Shor ได้คิดค้นอัลกอริทึมอันโด่งดังของเขาที่ช่วยให้คอมพิวเตอร์ควอนตัมสามารถแยกตัวประกอบจำนวนขนาดใหญ่ได้เร็วกว่าอัลกอริทึมคลาสสิกใดๆ แบบเอกซ์โพเนนเชียล ผลลัพธ์เหล่านี้รวมกันแสดงให้เห็นสัญญาที่น่าตื่นเต้นของคอมพิวเตอร์ควอนตัมในอนาคต และกระตุ้นนักฟิสิกส์และวิศวกรให้ทำให้อนาคตนี้เป็นจริง

คำถาม

ผู้สอนสามารถขอเวอร์ชันของ notebooks เหล่านี้พร้อมเฉลยและแนวทางการจัดวางในหลักสูตรทั่วไปได้โดยการกรอกแบบสอบถามสั้นๆ นี้เกี่ยวกับวิธีการใช้งาน notebooks

แนวคิดสำคัญ

• อัลกอริทึม Deutsch และ Deutsch-Jozsa ใช้ quantum parallelism ร่วมกับ interference เพื่อหาคำตอบสำหรับปัญหาได้เร็วกว่าคอมพิวเตอร์คลาสสิก
• กลไก phase kickback เป็นปรากฏการณ์ควอนตัมที่ขัดกับสัญชาตญาณซึ่งถ่ายโอน operations บน Qubit หนึ่งไปยัง phase ของ Qubit อีกตัว อัลกอริทึม Deutsch และ Deutsch-Jozsa ใช้กลไกนี้
• อัลกอริทึม Deutsch-Jozsa มี polynomial speedup เหนืออัลกอริทึมคลาสสิก deterministic ใดๆ
• อัลกอริทึม Deutsch-Jozsa สามารถนำไปใช้กับปัญหาอื่นที่เรียกว่าปัญหา Bernstein-Vazirani เพื่อหา hidden string ที่ encode ไว้ในฟังก์ชัน

ถูก/ผิด

1. ถ/ผ อัลกอริทึม Deutsch เป็นกรณีพิเศษของอัลกอริทึม Deutsch-Jozsa ซึ่ง input เป็น Qubit เดียว
2. ถ/ผ อัลกอริทึม Deutsch และ Deutsch-Jozsa ใช้ quantum superposition และ interference เพื่อให้ได้ประสิทธิภาพ
3. ถ/ผ อัลกอริทึม Deutsch-Jozsa ต้องการการประเมินฟังก์ชันหลายครั้งเพื่อระบุว่าฟังก์ชันเป็น constant หรือ balanced
4. ถ/ผ "อัลกอริทึม Bernstein-Vazirani" จริงๆ แล้วเหมือนกับอัลกอริทึม Deutsch-Jozsa ที่นำไปใช้กับปัญหาต่างกัน
5. ถ/ผ อัลกอริทึม Bernstein-Vazirani สามารถหา secret string หลาย string พร้อมกันได้

คำถามสั้น

1. อัลกอริทึมคลาสสิกจะใช้เวลานานแค่ไหนในกรณีที่แย่ที่สุดเพื่อแก้ปัญหา Deutsch-Jozsa?

2. อัลกอริทึมคลาสสิกจะใช้เวลานานแค่ไหนในการแก้ปัญหา Bernstein-Vazirani? อัลกอริทึม DJ มี speedup เท่าไรในกรณีนี้?

3. อธิบายกลไก phase-kickback และวิธีที่มันทำงานเพื่อแก้ปัญหา Deutsch-Jozsa และ Bernstein-Vazirani

โจทย์ท้าทาย

1. อัลกอริทึม Deutsch-Jozsa: ระลึกว่าคุณมีคำถามข้างต้นที่ขอให้คำนวณ intermediate Qubit states $\pi_1$ และ $\pi_2$ ของอัลกอริทึม Deutsch ทำแบบเดียวกันสำหรับ intermediate $n+1$-qubit states $\pi_1$ และ $\pi_2$ ของอัลกอริทึม Deutsch-Jozsa สำหรับกรณีเฉพาะที่ $n=2$ จากนั้น ยืนยันว่า $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$ อีกครั้งสำหรับกรณีเฉพาะที่ $n=2$