อัลกอริทึมของ Deutsch

อัลกอริทึมของ Deutsch แก้ปัญหา parity สำหรับกรณีพิเศษที่ $n = 1$ ในบริบทของการคำนวณเชิงควอนตัม ปัญหานี้บางครั้งเรียกว่า ปัญหาของ Deutsch และเราจะใช้ชื่อนี้ตลอดบทเรียน

พูดอย่างเจาะจง อินพุตแทนด้วยฟังก์ชัน $f:\Sigma \rightarrow \Sigma$ จากหนึ่งบิตไปยังหนึ่งบิต มีฟังก์ชันในรูปแบบนี้อยู่สี่ตัว:

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

ฟังก์ชันตัวแรกและตัวสุดท้ายเป็น ค่าคงที่ (constant) ส่วนสองตัวตรงกลางเป็น สมดุล (balanced) หมายความว่าค่าเอาต์พุตทั้งสองที่เป็นไปได้ปรากฏในจำนวนครั้งเท่ากันเมื่อวนผ่านอินพุตทั้งหมด ปัญหาของ Deutsch คือการตัดสินว่าฟังก์ชันอินพุตอยู่ในหมวดใด: constant หรือ balanced

ปัญหาของ Deutsch

อินพุต: ฟังก์ชัน $f:\{0,1\}\rightarrow\{0,1\}$
เอาต์พุต: $0$ ถ้า $f$ เป็น constant, $1$ ถ้า $f$ เป็น balanced

ถ้ามองฟังก์ชันอินพุต $f$ ในปัญหาของ Deutsch ว่าเป็นตัวแทนของการเข้าถึงสตริงแบบสุ่ม เราจะนึกถึงสตริงสองบิต: $f(0)f(1)$

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

เมื่อมองในมุมนี้ ปัญหาของ Deutsch คือการคำนวณ parity (หรือเทียบเท่าคือ exclusive-OR) ของสองบิต

อัลกอริทึม query แบบคลาสสิกทุกตัวที่แก้ปัญหานี้ได้อย่างถูกต้องต้อง query ทั้งสองบิต: $f(0)$ และ $f(1)$ ตัวอย่างเช่น ถ้าเรารู้ว่า $f(1) = 1$ คำตอบยังอาจเป็น $0$ หรือ $1$ ก็ได้ ขึ้นอยู่กับว่า $f(0) = 1$ หรือ $f(0) = 0$ ตามลำดับ ทุกกรณีอื่นก็คล้ายกัน การรู้เพียงหนึ่งในสองบิตไม่ให้ข้อมูลใด ๆ เกี่ยวกับ parity ของบิตทั้งสองเลย ดังนั้น วงจร Boolean ที่อธิบายในส่วนก่อนหน้าจึงเป็นสิ่งที่ดีที่สุดในแง่ของจำนวน query ที่ต้องใช้เพื่อแก้ปัญหานี้

การอธิบายด้วยวงจรควอนตัม

อัลกอริทึมของ Deutsch แก้ปัญหาของ Deutsch โดยใช้ query เดียว ซึ่งแสดงให้เห็นถึงข้อได้เปรียบเชิงปริมาณของควอนตัมเหนือคลาสสิก ข้อได้เปรียบนี้อาจดูไม่มากนัก — หนึ่ง query แทนที่จะสอง — แต่เราต้องเริ่มต้นที่ไหนสักที่ ความก้าวหน้าทางวิทยาศาสตร์บางครั้งมีจุดเริ่มต้นที่ดูธรรมดา

นี่คือวงจรควอนตัมที่อธิบายอัลกอริทึมของ Deutsch:

การวิเคราะห์

เพื่อวิเคราะห์อัลกอริทึมของ Deutsch เราจะติดตามการกระทำของวงจรข้างต้นและระบุสถานะของ Qubit ตามเวลาที่ภาพนี้แสดง:

สถานะเริ่มต้นคือ $\vert 1\rangle \vert 0 \rangle$ และการดำเนินการ Hadamard สองครั้งทางด้านซ้ายของวงจรแปลงสถานะนี้เป็น

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(เช่นเคย เราปฏิบัติตามข้อตกลงการจัดลำดับ Qubit ของ Qiskit ที่วาง Qubit บนไว้ทางขวาและ Qubit ล่างไว้ทางซ้าย) การเขียนสถานะผลคูณแบบกระจายบางส่วน (เหลือสถานะของ Qubit 1 แยกไว้) อาจดูไม่เป็นธรรมชาติ แต่จะทำให้นิพจน์ต่อ ๆ ไปกระชับมากขึ้น

ต่อมา Gate $U_f$ ถูกดำเนินการ ตามนิยามของ Gate $U_f$ ค่าของฟังก์ชัน $f$ สำหรับสถานะคลาสสิกของ Qubit บน/ขวาสุดจะถูก XOR เข้ากับ Qubit ล่าง/ซ้ายสุด ซึ่งแปลง $\vert \pi_1\rangle$ เป็นสถานะ

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

เราสามารถลดรูปนิพจน์นี้ได้โดยสังเกตว่าสูตร

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

ใช้ได้กับทั้งสองค่าที่เป็นไปได้ $a\in\Sigma$ อธิบายอย่างละเอียด ทั้งสองกรณีมีดังนี้

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

ดังนั้น เราสามารถแสดง $\vert\pi_2\rangle$ ในอีกรูปแบบหนึ่งได้:

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

มีบางอย่างน่าสนใจเกิดขึ้น! แม้ว่าการกระทำของ Gate $U_f$ บนสถานะฐานมาตรฐานจะปล่อย Qubit บน/ขวาสุดไว้ตามเดิมและ XOR ค่าฟังก์ชันเข้ากับ Qubit ล่าง/ซ้ายสุด แต่ที่นี่เราเห็นว่าสถานะของ Qubit บน/ขวาสุดเปลี่ยนแปลง (โดยทั่วไป) ในขณะที่สถานะของ Qubit ล่าง/ซ้ายสุดยังคงเดิม — โดยอยู่ในสถานะ $\vert - \rangle$ ทั้งก่อนและหลังการดำเนินการ Gate $U_f$ ปรากฏการณ์นี้เรียกว่า phase kickback และเราจะพูดถึงมันอีกในเร็ว ๆ นี้

ด้วยการลดรูปขั้นสุดท้าย ซึ่งคือการดึงตัวประกอบ $(-1)^{f(0)}$ ออกนอกผลรวม เราได้นิพจน์สถานะ $\vert\pi_2\rangle$ ดังนี้:

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

สังเกตว่าในนิพจน์นี้ เรามี $f(0) \oplus f(1)$ ในเลขชี้กำลังของ $-1$ แทนที่จะเป็น $f(1) - f(0)$ ซึ่งเป็นสิ่งที่เราอาจคาดจากมุมมองพีชคณิตล้วน ๆ แต่เราได้ผลลัพธ์เดียวกันทั้งสองทาง เพราะค่า $(-1)^k$ สำหรับจำนวนเต็ม $k$ ใด ๆ ขึ้นอยู่กับว่า $k$ เป็นคู่หรือคี่เท่านั้น

การใช้ Hadamard Gate สุดท้ายกับ Qubit บนทำให้เราได้สถานะ

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{if $f(0) \oplus f(1) = 1$}, \end{cases}$$

ซึ่งนำไปสู่ผลลัพธ์ที่ถูกต้องด้วยความน่าจะเป็น $1$ เมื่อวัด Qubit ขวา/บนสุด

หมายเหตุเพิ่มเติมเกี่ยวกับ phase kickback

ก่อนที่จะดำเนินต่อ มาดูการวิเคราะห์ข้างต้นจากมุมมองที่ต่างออกไปเล็กน้อย ซึ่งอาจช่วยให้เข้าใจปรากฏการณ์ phase kickback ได้ดีขึ้น

อันดับแรก สังเกตว่าสูตรต่อไปนี้ใช้ได้สำหรับทุกค่าของบิต $b,c\in\Sigma$

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

สูตรนี้สามารถตรวจสอบได้โดยแทนค่าสองค่าที่เป็นไปได้ $c = 0$ และ $c = 1$:

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

โดยใช้สูตรนี้ เราจะเห็นว่า

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

สำหรับทุกค่าของบิต $a,b\in\Sigma$ เนื่องจากสูตรนี้เป็นจริงสำหรับ $b=0$ และ $b=1$ เราจึงเห็นโดยความเป็นเชิงเส้นว่า

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

สำหรับเวกเตอร์สถานะ Qubit $\vert \psi\rangle$ ทั้งหมด และดังนั้น

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

กุญแจที่ทำให้สิ่งนี้ได้ผลคือ $X\vert - \rangle = - \vert - \rangle$ ในทางคณิตศาสตร์ เวกเตอร์ $\vert - \rangle$ คือ eigenvector ของเมทริกซ์ $X$ ที่มี eigenvalue เป็น $-1$

เราจะพูดถึง eigenvector และ eigenvalue อย่างละเอียดในบทเรียนถัดไปเรื่อง การประมาณ phase และการแยกตัวประกอบ ซึ่งเราจะขยายแนวคิด phase kickback ให้ครอบคลุมการดำเนินการ unitary อื่น ๆ ด้วย

โดยระลึกว่าสเกลาร์ลอยผ่าน tensor product ได้อิสระ เราพบวิธีอื่นในการให้เหตุผลว่าการดำเนินการ $U_f$ แปลง $\vert \pi_1\rangle$ เป็น $\vert \pi_2\rangle$ ในการวิเคราะห์ข้างต้นอย่างไร:

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

การนำไปใช้งานใน Qiskit

ตอนนี้มาดูกันว่าเราสามารถนำอัลกอริทึมของ Deutsch ไปใช้งานใน Qiskit ได้อย่างไร เราจะเริ่มด้วยการตรวจสอบเวอร์ชันแล้วทำการ import ที่จำเป็นสำหรับการนำไปใช้งานนี้โดยเฉพาะ สำหรับการนำไปใช้งานของอัลกอริทึมอื่น ๆ ที่ตามมา เราจะ import ที่จำเป็นแยกกันเพื่อความเป็นโมดูลาร์มากขึ้น

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"qiskit": "qiskit", "qiskit_aer": "qiskit-aer"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

ก่อนอื่นเราจะนิยามวงจรควอนตัมที่นำ query gate สำหรับฟังก์ชันใดฟังก์ชันหนึ่งในสี่ตัว $f_1,$ $f_2,$ $f_3,$ หรือ $f_4$ จากหนึ่งบิตไปยังหนึ่งบิตที่อธิบายไว้ก่อนหน้า ดังที่กล่าวถึงแล้ว การนำ query gate ไปใช้งานไม่ใช่ส่วนหนึ่งของอัลกอริทึมของ Deutsch จริง ๆ ที่นี่เราแค่แสดงวิธีหนึ่งในการเตรียมอินพุต ในรูปแบบการนำ query gate ไปใช้งานด้วยวงจร

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    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

เราสามารถดูว่าแต่ละวงจรหน้าตาเป็นอย่างไรโดยใช้เมธอด draw นี่คือวงจรสำหรับฟังก์ชัน $f_3$

display(deutsch_function(3).draw(output="mpl"))

ต่อมาเราจะสร้างวงจรควอนตัมจริงสำหรับอัลกอริทึมของ Deutsch โดยแทนที่ query gate ด้วยวงจรควอนตัมที่รับเข้ามาเป็นอาร์กิวเมนต์ ในไม่ช้าเราจะเสียบหนึ่งในสี่วงจรที่นิยามโดยฟังก์ชัน deutsch_function ที่เราสร้างก่อนหน้า มีการเพิ่ม Barrier เพื่อแสดงการแบ่งแยกทางภาพระหว่างการนำ query gate ไปใช้งานและส่วนที่เหลือของวงจร

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

เราสามารถดูว่าวงจรหน้าตาเป็นอย่างไรอีกครั้งโดยใช้เมธอด draw

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

สุดท้าย เราจะสร้างฟังก์ชันที่รันวงจรที่นิยามไว้ก่อนหน้าหนึ่งครั้งและแสดงผลลัพธ์ที่เหมาะสม: "constant" หรือ "balanced"

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

ตอนนี้เราสามารถรันอัลกอริทึมของ Deutsch บนฟังก์ชันใดหนึ่งในสี่ตัวที่นิยามไว้ข้างต้นได้แล้ว

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'