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

อัลกอริทึมของ Deutsch มีประสิทธิภาพเหนือกว่าอัลกอริทึมคลาสสิกทั้งหมดสำหรับปัญหา query แต่ข้อได้เปรียบยังค่อนข้างน้อย: หนึ่ง query แทนที่จะสอง อัลกอริทึม Deutsch-Jozsa ขยายข้อได้เปรียบนี้ออกไป และจริง ๆ แล้ว สามารถใช้แก้ปัญหา query ได้สองปัญหา

นี่คือคำอธิบายวงจรควอนตัมของอัลกอริทึม Deutsch-Jozsa ขั้นตอนการประมวลผลหลังคลาสสิกเพิ่มเติม ที่ไม่ได้แสดงในภาพ อาจจำเป็นด้วยขึ้นอยู่กับปัญหาเฉพาะที่ต้องการแก้

แน่นอน เรายังไม่ได้พูดถึงว่าอัลกอริทึมนี้แก้ปัญหาอะไร ซึ่งจะอธิบายในสองส่วนถัดไป

ปัญหา Deutsch-Jozsa

เราจะเริ่มจากปัญหา query ที่อัลกอริทึม Deutsch-Jozsa ถูกออกแบบมาเพื่อแก้โดยตรง ซึ่งเรียกว่า ปัญหา Deutsch-Jozsa

ฟังก์ชันอินพุตของปัญหานี้อยู่ในรูปแบบ $f:\Sigma^n \rightarrow \Sigma$ สำหรับจำนวนเต็มบวก $n$ ที่กำหนดใด ๆ เหมือนกับปัญหาของ Deutsch งานคือการแสดงผล $0$ ถ้า $f$ เป็น constant และ $1$ ถ้า $f$ เป็น balanced ซึ่งหมายความอีกครั้งว่าจำนวนสตริงอินพุตที่ฟังก์ชันให้ค่า $0$ เท่ากับจำนวนสตริงอินพุตที่ฟังก์ชันให้ค่า $1$

สังเกตว่า เมื่อ $n$ มีค่ามากกว่า $1$ มีฟังก์ชันรูปแบบ $f:\Sigma^n \rightarrow \Sigma$ ที่ไม่เป็นทั้ง constant และ balanced ตัวอย่างเช่น ฟังก์ชัน $f:\Sigma^2\rightarrow\Sigma$ ที่นิยามโดย

$$\begin{aligned} f(00) & = 0 \\ f(01) & = 0 \\ f(10) & = 0 \\ f(11) & = 1 \end{aligned}$$

ไม่อยู่ในหมวดหมู่ใดหมวดหมู่หนึ่ง สำหรับปัญหา Deutsch-Jozsa เราไม่ต้องกังวลเกี่ยวกับฟังก์ชันแบบนี้ — พวกมันถือเป็นอินพุต "don't care" นั่นคือ สำหรับปัญหานี้เรามี promise ว่า $f$ เป็นทั้ง constant หรือ balanced

ปัญหา Deutsch-Jozsa

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

อัลกอริทึม Deutsch-Jozsa ด้วย query เดียว แก้ปัญหานี้ในความหมายต่อไปนี้: ถ้าทุกผลการวัด $n$ ตัวเป็น $0$ แล้วฟังก์ชัน $f$ เป็น constant และในทางกลับกัน ถ้าผลการวัดอย่างน้อยหนึ่งตัวเป็น $1$ แล้วฟังก์ชัน $f$ เป็น balanced อีกวิธีหนึ่งในการพูดคือวงจรที่อธิบายข้างต้นตามด้วยขั้นตอนการประมวลผลหลังคลาสสิกที่คำนวณ OR ของผลการวัดเพื่อสร้างเอาต์พุต

การวิเคราะห์อัลกอริทึม

เพื่อวิเคราะห์ประสิทธิภาพของอัลกอริทึม Deutsch-Jozsa สำหรับปัญหา Deutsch-Jozsa เป็นประโยชน์ที่จะเริ่มด้วยการคิดถึงการกระทำของ Hadamard Gate ชั้นเดียว การดำเนินการ Hadamard สามารถแสดงเป็นเมทริกซ์ตามปกติ

$$H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix},$$

แต่เราสามารถแสดงการดำเนินการนี้ในแง่ของการกระทำบนสถานะฐานมาตรฐานได้ด้วย:

$$\begin{aligned} H \vert 0\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle\\[3mm] H \vert 1\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 \rangle. \end{aligned}$$

สองสมการนี้สามารถรวมเป็นสูตรเดียวได้

$$H \vert a \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} (-1)^a \vert 1 \rangle = \frac{1}{\sqrt{2}} \sum_{b\in\{0,1\}} (-1)^{ab} \vert b\rangle,$$

ซึ่งเป็นจริงสำหรับทั้งสองค่าของ $a\in\Sigma$

ทีนี้สมมติว่าแทนที่จะมี Qubit เดี่ยว เรามี $n$ Qubit และดำเนินการ Hadamard บนแต่ละตัว การดำเนินการรวมบน $n$ Qubit อธิบายด้วย tensor product $H\otimes \cdots \otimes H$ ($n$ ครั้ง) ซึ่งเราเขียนสั้น ๆ ว่า $H^{\otimes n}$ โดยใช้สูตรข้างต้น ตามด้วยการขยายแล้วลดรูป เราสามารถแสดงการกระทำของการดำเนินการรวมนี้บนสถานะฐานมาตรฐานของ $n$ Qubit ได้ดังนี้:

$$\begin{aligned} & H^{\otimes n} \vert x_{n-1} \cdots x_1 x_0 \rangle \\ & \qquad = \bigl(H \vert x_{n-1} \rangle \bigr) \otimes \cdots \otimes \bigl(H \vert x_{0} \rangle \bigr) \\ & \qquad = \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{n-1}\in\Sigma} (-1)^{x_{n-1} y_{n-1}} \vert y_{n-1} \rangle \Biggr) \otimes \cdots \otimes \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{0}\in\Sigma} (-1)^{x_{0} y_{0}} \vert y_{0} \rangle \Biggr) \\ & \qquad = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle. \end{aligned}$$

ที่นี่ เราเขียนสตริงไบนารีความยาว $n$ เป็น $x_{n-1}\cdots x_0$ และ $y_{n-1}\cdots y_0$ ตามข้อตกลงการจัดดัชนีของ Qiskit

สูตรนี้เป็นเครื่องมือที่มีประโยชน์สำหรับการวิเคราะห์วงจรควอนตัมข้างต้น หลังจากดำเนินการ Hadamard Gate ชั้นแรกแล้ว สถานะของ $n+1$ Qubit (รวมถึง Qubit ซ้ายสุด/ล่าง ซึ่งได้รับการจัดการแยกจากส่วนที่เหลือ) คือ

$$\bigl( H \vert 1 \rangle \bigr) \bigl( H^{\otimes n} \vert 0 \cdots 0 \rangle \bigr) = \vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \vert x_{n-1} \cdots x_0 \rangle.$$

เมื่อดำเนินการ $U_f$ สถานะนี้จะถูกแปลงเป็น

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \vert x_{n-1} \cdots x_0 \rangle$$

ผ่านปรากฏการณ์ phase kick-back เดิมที่เราเห็นในการวิเคราะห์อัลกอริทึมของ Deutsch

จากนั้นดำเนินการ Hadamard Gate ชั้นที่สอง ซึ่ง (ตามสูตรข้างต้น) แปลงสถานะนี้เป็น

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0) + x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle.$$

นิพจน์นี้ดูซับซ้อนพอสมควร และไม่สามารถสรุปอะไรมากนักเกี่ยวกับความน่าจะเป็นในการได้ผลการวัดต่าง ๆ โดยไม่รู้ข้อมูลเพิ่มเติมเกี่ยวกับฟังก์ชัน $f$

โชคดีที่สิ่งที่เราต้องรู้คือความน่าจะเป็นที่ผลการวัดทุกตัวเป็น $0$ — เพราะนั่นคือความน่าจะเป็นที่อัลกอริทึมตัดสินว่า $f$ เป็น constant ความน่าจะเป็นนี้มีสูตรที่เรียบง่าย

$$\Biggl\vert \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \Biggr\vert^2 = \begin{cases} 1 & \text{if $f$ is constant}\\[1mm] 0 & \text{if $f$ is balanced} \end{cases}$$

อธิบายอย่างละเอียด ถ้า $f$ เป็น constant ดังนั้นไม่ว่า $f(x_{n-1}\cdots x_0) = 0$ สำหรับทุกสตริง $x_{n-1}\cdots x_0$ ซึ่งในกรณีนี้ค่าของผลรวมคือ $2^n$ หรือ $f(x_{n-1}\cdots x_0) = 1$ สำหรับทุกสตริง $x_{n-1}\cdots x_0$ ซึ่งในกรณีนี้ค่าของผลรวมคือ $-2^n$ หารด้วย $2^n$ แล้วหาค่ากำลังสองของค่าสัมบูรณ์จะได้ $1$

ถ้าในทางกลับกัน $f$ เป็น balanced ดังนั้น $f$ ให้ค่า $0$ ในครึ่งหนึ่งของสตริง $x_{n-1}\cdots x_0$ และค่า $1$ ในอีกครึ่งหนึ่ง ดังนั้นพจน์ $+1$ และ $-1$ ในผลรวมหักล้างกันและเราได้ค่า $0$

เราสรุปได้ว่าอัลกอริทึมทำงานถูกต้องตราบใดที่ promise ถูกปฏิบัติตาม

ความยากของคลาสสิก

อัลกอริทึม Deutsch-Jozsa ทำงานได้ทุกครั้ง ให้คำตอบที่ถูกต้องเสมอเมื่อ promise ถูกปฏิบัติตาม และต้องใช้ query เดียวเท่านั้น ซึ่งเปรียบเทียบกับอัลกอริทึมคลาสสิกสำหรับปัญหา Deutsch-Jozsa ได้อย่างไร?

ก่อนอื่น อัลกอริทึมคลาสสิก deterministic ใด ๆ ที่แก้ปัญหา Deutsch-Jozsa ได้อย่างถูกต้องต้องทำ query จำนวนมากในลำดับเลขชี้กำลัง: ต้องการ query $2^{n-1} + 1$ ครั้งในกรณีที่แย่ที่สุด เหตุผลคือ ถ้าอัลกอริทึม deterministic ทำ query $f$ บนสตริงที่แตกต่างกันไม่เกิน $2^{n-1}$ ตัวและได้ค่าฟังก์ชันเดิมทุกครั้ง ทั้งสองคำตอบยังเป็นไปได้อยู่ ฟังก์ชันอาจเป็น constant หรืออาจเป็น balanced แต่โชคร้ายที่ query ทั้งหมดบังเอิญให้ค่าฟังก์ชันเดิม

ความเป็นไปได้ที่สองอาจดูไม่น่าเป็นไปได้ — แต่สำหรับอัลกอริทึม deterministic ไม่มีความสุ่มหรือความไม่แน่นอน ดังนั้นพวกมันจะล้มเหลวอย่างเป็นระบบสำหรับฟังก์ชันบางตัว ดังนั้นเราจึงมีข้อได้เปรียบที่สำคัญของควอนตัมเหนือคลาสสิกในแง่นี้

อย่างไรก็ตาม มีข้อจำกัด นั่นคืออัลกอริทึมคลาสสิก probabilistic สามารถแก้ปัญหา Deutsch-Jozsa ด้วยความน่าจะเป็นสูงมากโดยใช้เพียงไม่กี่ query โดยเฉพาะอย่างยิ่ง ถ้าเราแค่เลือกสตริงความยาว $n$ สองสามตัวแบบสุ่ม แล้วทำ query $f$ บนสตริงเหล่านั้น ไม่น่าจะเป็นไปได้ที่เราจะได้ค่าฟังก์ชันเดิมทั้งหมดเมื่อ $f$ เป็น balanced

พูดอย่างเฉพาะเจาะจง ถ้าเราเลือกสตริงอินพุต $k$ ตัว $x^1,\ldots,x^k \in \Sigma^n$ แบบ uniform random ประเมิน $f(x^1),\ldots,f(x^k)$ แล้วตอบ $0$ ถ้าค่าฟังก์ชันเหมือนกันทั้งหมด และ $1$ ถ้าไม่ เราจะถูกต้องเสมอเมื่อ $f$ เป็น constant และผิดพลาดในกรณีที่ $f$ เป็น balanced ด้วยความน่าจะเป็นแค่ $2^{-k + 1}$ ถ้าเราใช้ $k = 11$ เช่น อัลกอริทึมนี้จะตอบถูกต้องด้วยความน่าจะเป็นมากกว่า $99.9$%

ด้วยเหตุนี้ เรายังคงมีข้อได้เปรียบที่ค่อนข้างน้อยของควอนตัมเหนือคลาสสิก — แต่ก็ยังเป็นข้อได้เปรียบที่วัดได้และแสดงถึงการปรับปรุงเหนืออัลกอริทึมของ Deutsch

Deutsch-Jozsa ด้วย Qiskit

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

เพื่อนำอัลกอริทึม Deutsch-Jozsa ไปใช้งานใน Qiskit เราจะเริ่มด้วยการนิยามฟังก์ชัน dj_query ที่สร้างวงจรควอนตัมที่นำ query gate ไปใช้งาน สำหรับฟังก์ชันที่เลือกแบบสุ่มที่ปฏิบัติตาม promise ของปัญหา Deutsch-Jozsa ด้วยความน่าจะเป็น 50% ฟังก์ชันเป็น constant และด้วยความน่าจะเป็น 50% ฟังก์ชันเป็น balanced สำหรับทั้งสองความเป็นไปได้นั้น ฟังก์ชันถูกเลือกแบบ uniform จากฟังก์ชันประเภทนั้น อาร์กิวเมนต์คือจำนวนบิตอินพุตของฟังก์ชัน

def dj_query(num_qubits):
    # Create a circuit implementing for a query gate for a random function
    # satisfying the promise for the Deutsch-Jozsa problem.

    qc = QuantumCircuit(num_qubits + 1)

    if np.random.randint(0, 2):
        # Flip output qubit with 50% chance
        qc.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance
        return qc

    # Choose half the possible input strings
    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, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc.x(qubit)
        return qc

    for state in on_states:
        qc.barrier()  # Barriers are added to help visualize how the functions are created.
        qc = add_cx(qc, f"{state:0b}")
        qc.mcx(list(range(num_qubits)), num_qubits)
        qc = add_cx(qc, f"{state:0b}")

    qc.barrier()

    return qc

เราสามารถแสดงการนำ query gate ไปใช้งานด้วยวงจรควอนตัมโดยใช้เมธอด draw ตามปกติ

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

ต่อมาเราจะนิยามฟังก์ชันที่สร้างวงจร Deutsch-Jozsa โดยรับการนำ Circuit ของ query gate ไปใช้งานเป็นอาร์กิวเมนต์

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in the Deutsch-Jozsa algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)
    qc.h(range(n + 1))
    qc.compose(function, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

สุดท้าย นิยามฟังก์ชันที่รันวงจร Deutsch-Jozsa หนึ่งครั้ง

def dj_algorithm(function: QuantumCircuit):
    # Determine if a function is constant or balanced.

    qc = compile_circuit(function)

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

เราสามารถทดสอบการนำไปใช้งานโดยเลือกฟังก์ชันแบบสุ่ม แสดงการนำ Circuit ของ query gate ไปใช้งานสำหรับฟังก์ชันนั้น แล้วรันอัลกอริทึม Deutsch-Jozsa บนฟังก์ชันนั้น

f = dj_query(3)
display(f.draw("mpl"))
display(dj_algorithm(f))

'balanced'

ปัญหา Bernstein-Vazirani

ต่อมา เราจะพูดถึงปัญหาที่เรียกว่า ปัญหา Bernstein-Vazirani มันยังถูกเรียกว่า ปัญหา Fourier sampling แม้ว่าจะมีการกำหนดสูตรของปัญหานี้ที่ทั่วไปกว่าซึ่งก็ใช้ชื่อนี้เช่นกัน

ก่อนอื่น มาแนะนำสัญลักษณ์บางอย่าง สำหรับสตริงไบนารีสองตัว $x = x_{n-1} \cdots x_0$ และ $y = y_{n-1}\cdots y_0$ ความยาว $n$ ใด ๆ เรานิยาม

$$x \cdot y = x_{n-1} y_{n-1} \oplus \cdots \oplus x_0 y_0.$$

เราจะเรียกการดำเนินการนี้ว่า binary dot product อีกวิธีหนึ่งในการนิยามมีดังนี้

$$x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is odd}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is even} \end{cases}$$

สังเกตว่านี่เป็นการดำเนินการแบบสมมาตร หมายความว่าผลลัพธ์ไม่เปลี่ยนแปลงถ้าเราสลับ $x$ และ $y$ ดังนั้นเราสามารถทำได้เมื่อสะดวก บางครั้งมีประโยชน์ในการคิดถึง binary dot product $x \cdot y$ ว่าเป็น parity ของบิตของ $x$ ในตำแหน่งที่สตริง $y$ มี $1$ หรือเทียบเท่าคือ parity ของบิตของ $y$ ในตำแหน่งที่สตริง $x$ มี $1$

ด้วยสัญลักษณ์นี้ เราสามารถนิยามปัญหา Bernstein-Vazirani ได้แล้ว

ปัญหา Bernstein-Vazirani

อินพุต: ฟังก์ชัน $f:\{0,1\}^n\rightarrow\{0,1\}$
Promise: มีสตริงไบนารี $s = s_{n-1} \cdots s_0$ ที่ $f(x) = s\cdot x$ สำหรับทุก $x\in\Sigma^n$
เอาต์พุต: สตริง $s$

เราไม่จำเป็นต้องมีอัลกอริทึมควอนตัมใหม่สำหรับปัญหานี้ อัลกอริทึม Deutsch-Jozsa แก้ปัญหานั้น เพื่อความชัดเจน มาเรียกวงจรควอนตัมจากข้างต้น ซึ่งไม่รวมขั้นตอนการประมวลผลหลังคลาสสิกของการคำนวณ OR ว่า วงจร Deutsch-Jozsa

การวิเคราะห์อัลกอริทึม

เพื่อวิเคราะห์ว่าวงจร Deutsch-Jozsa ทำงานอย่างไรสำหรับฟังก์ชันที่ปฏิบัติตาม promise ของปัญหา Bernstein-Vazirani เราจะเริ่มด้วยการสังเกตอย่างรวดเร็ว โดยใช้ binary dot product เราสามารถอธิบายการกระทำของ Hadamard Gate $n$ ตัวบนสถานะฐานมาตรฐานของ $n$ Qubit ในทางเลือกอื่นได้ดังนี้

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

คล้ายกับที่เราเห็นเมื่อวิเคราะห์อัลกอริทึมของ Deutsch เพราะค่า $(-1)^k$ สำหรับจำนวนเต็ม $k$ ใด ๆ ขึ้นอยู่กับว่า $k$ เป็นคู่หรือคี่เท่านั้น

กลับมาที่วงจร Deutsch-Jozsa หลังจากดำเนินการ Hadamard Gate ชั้นแรกแล้ว สถานะของ $n+1$ Qubit คือ

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} \vert x \rangle.$$

จากนั้นดำเนินการ query gate ซึ่ง (ผ่านปรากฏการณ์ phase kickback) แปลงสถานะเป็น

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} (-1)^{f(x)} \vert x \rangle.$$

โดยใช้สูตรของเราสำหรับการกระทำของ Hadamard Gate ชั้นหนึ่ง เราเห็นว่า Hadamard Gate ชั้นที่สองแปลงสถานะนี้เป็น

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{f(x) + x \cdot y} \vert y \rangle.$$

ตอนนี้เราสามารถทำการลดรูปบางอย่างในเลขชี้กำลังของ $-1$ ภายในผลรวม เราได้รับ promise ว่า $f(x) = s\cdot x$ สำหรับสตริงบางตัว $s = s_{n-1} \cdots s_0$ ดังนั้นเราสามารถแสดงสถานะได้ว่า

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{s\cdot x + x \cdot y} \vert y \rangle.$$

เนื่องจาก $s\cdot x$ และ $x\cdot y$ เป็นค่าไบนารี เราสามารถแทนที่การบวกด้วย exclusive-OR ได้ — อีกครั้งเพราะสิ่งเดียวที่สำคัญสำหรับจำนวนเต็มในเลขชี้กำลังของ $-1$ คือว่ามันเป็นคู่หรือคี่ โดยใช้สมมาตรของ binary dot product เราได้นิพจน์ของสถานะดังนี้:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\cdot x) \oplus (y \cdot x)} \vert y \rangle.$$

(ได้เพิ่มวงเล็บเพื่อความชัดเจน แม้ว่าจะไม่จำเป็นจริง ๆ เพราะเป็นธรรมเนียมที่จะให้ binary dot product มีความสำคัญสูงกว่า exclusive-OR)

ณ จุดนี้เราจะใช้สูตรต่อไปนี้

$$(s\cdot x) \oplus (y \cdot x) = (s \oplus y) \cdot x$$

เราสามารถได้สูตรนี้ผ่านสูตรที่คล้ายกันสำหรับบิต

$$(a c) \oplus (b c) = (a \oplus b) c,$$

ร่วมกับการขยาย binary dot product และ bitwise exclusive-OR:

$$\begin{aligned} (s\cdot x) \oplus (y \cdot x) & = (s_{n-1} x_{n-1}) \oplus \cdots \oplus (s_{0} x_{0}) \oplus (y_{n-1} x_{n-1}) \oplus \cdots \oplus (y_{0} x_{0}) \\ & = (s_{n-1} \oplus y_{n-1}) x_{n-1} \oplus \cdots \oplus (s_{0} \oplus y_{0}) x_{0} \\ & = (s \oplus y) \cdot x \end{aligned}$$

ซึ่งช่วยให้เราแสดงสถานะของวงจรก่อนการวัดได้ดังนี้:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle.$$

ขั้นตอนสุดท้ายคือการใช้สูตรอีกสูตรหนึ่ง ซึ่งใช้ได้กับทุกสตริงไบนารี $z = z_{n-1}\cdots z_0$

$$\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{if $z = 0^n$}\\ 0 & \text{if $z\neq 0^n$} \end{cases}$$

ที่นี่เราใช้สัญลักษณ์ง่าย ๆ สำหรับสตริงที่เราจะใช้อีกหลายครั้งในบทเรียน: $0^n$ คือสตริงที่มีแต่ศูนย์ความยาว $n$

วิธีง่าย ๆ ในการแสดงว่าสูตรนี้ใช้ได้คือพิจารณาสองกรณีแยกกัน ถ้า $z = 0^n$ ดังนั้น $z\cdot x = 0$ สำหรับทุกสตริง $x\in\Sigma^n$ ดังนั้นค่าของแต่ละพจน์ในผลรวมคือ $1$ และเราได้ $1$ โดยการรวมและหารด้วย $2^n$ ในทางกลับกัน ถ้าบิตใดบิตหนึ่งของ $z$ เท่ากับ $1$ ดังนั้น binary dot product $z\cdot x$ เท่ากับ $0$ สำหรับครึ่งหนึ่งของทางเลือกที่เป็นไปได้ทั้งหมดสำหรับ $x\in\Sigma^n$ และ $1$ สำหรับอีกครึ่งหนึ่ง — เพราะค่าของ binary dot product $z\cdot x$ สลับ (จาก $0$ เป็น $1$ หรือจาก $1$ เป็น $0$) ถ้าเราสลับบิตใด ๆ ของ $x$ ในตำแหน่งที่ $z$ มี $1$

ถ้าเราใช้สูตรนี้เพื่อลดรูปสถานะของวงจรก่อนการวัด เราจะได้

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle = \vert - \rangle \otimes \vert s \rangle,$$

เนื่องจากข้อเท็จจริงที่ว่า $s\oplus y = 0^n$ ก็ต่อเมื่อ $y = s$ ดังนั้น การวัดจะเปิดเผยสตริง $s$ ที่เราต้องการอย่างแม่นยำ

ความยากของคลาสสิก

ในขณะที่วงจร Deutsch-Jozsa แก้ปัญหา Bernstein-Vazirani ด้วย query เดียว อัลกอริทึม query คลาสสิกใด ๆ ต้องทำ query อย่างน้อย $n$ ครั้งเพื่อแก้ปัญหานี้

ซึ่งสามารถให้เหตุผลได้ผ่านอาร์กิวเมนต์ที่เรียกว่า information theoretic ซึ่งในกรณีนี้ง่ายมาก การ query คลาสสิกแต่ละครั้งเปิดเผยข้อมูลหนึ่งบิตเกี่ยวกับคำตอบ และมีข้อมูล $n$ บิตที่ต้องค้นพบ — ดังนั้นจึงต้องใช้ query อย่างน้อย $n$ ครั้ง

จริง ๆ แล้ว เป็นไปได้ที่จะแก้ปัญหา Bernstein-Vazirani แบบคลาสสิกโดยทำ query ฟังก์ชันบนสตริง $n$ ตัวที่แต่ละตัวมี $1$ เดี่ยว ๆ ในแต่ละตำแหน่งที่เป็นไปได้ และ $0$ สำหรับบิตอื่นทั้งหมด ซึ่งเปิดเผยบิตของ $s$ ทีละตัว ดังนั้น ข้อได้เปรียบของควอนตัมเหนือคลาสสิกสำหรับปัญหานี้คือ $1$ query แทน $n$ query

Bernstein-Vazirani ด้วย Qiskit

เราได้นำวงจร Deutsch-Jozsa ไปใช้งานแล้วข้างต้น และที่นี่เราจะใช้มันเพื่อแก้ปัญหา Bernstein-Vazirani ก่อนอื่นเราจะนิยามฟังก์ชันที่นำ query gate ไปใช้งานสำหรับปัญหา Bernstein-Vazirani ด้วยสตริงไบนารี $s$ ใด ๆ

def bv_query(s):
    # Create a quantum circuit implementing a query gate for the
    # Bernstein-Vazirani problem.

    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_query("1011").draw(output="mpl"))

ตอนนี้เราสามารถสร้างฟังก์ชันที่รันวงจร Deutsch-Jozsa บนฟังก์ชันโดยใช้ฟังก์ชัน compile_circuit ที่นิยามไว้ก่อนหน้า

def bv_algorithm(function: QuantumCircuit):
    qc = compile_circuit(function)
    result = AerSimulator().run(qc, shots=1, memory=True).result()
    return result.get_memory()[0]

display(bv_algorithm(bv_query("1011")))

'1011'

หมายเหตุเกี่ยวกับการตั้งชื่อ

ในบริบทของปัญหา Bernstein-Vazirani เป็นเรื่องปกติที่อัลกอริทึม Deutsch-Jozsa จะถูกเรียกว่า "อัลกอริทึม Bernstein-Vazirani" ซึ่งทำให้เข้าใจผิดได้เล็กน้อย เพราะอัลกอริทึม คือ อัลกอริทึม Deutsch-Jozsa อย่างที่ Bernstein และ Vazirani ระบุไว้ชัดเจนในงานของพวกเขา

สิ่งที่ Bernstein และ Vazirani ทำหลังจากแสดงให้เห็นว่าอัลกอริทึม Deutsch-Jozsa แก้ปัญหา Bernstein-Vazirani (ตามที่ระบุไว้ข้างต้น) คือการนิยามปัญหาที่ซับซ้อนมากขึ้น ซึ่งเรียกว่า ปัญหา recursive Fourier sampling นี่เป็นปัญหาที่ถูกสร้างขึ้นอย่างประดิษฐ์ โดยคำตอบของอินสแตนซ์ต่าง ๆ ของปัญหาในทางปฏิบัติปลดล็อกระดับใหม่ของปัญหาที่จัดเรียงในโครงสร้างคล้ายต้นไม้ ปัญหา Bernstein-Vazirani เป็นกรณีพื้นฐานของปัญหาที่ซับซ้อนกว่านี้

ปัญหา recursive Fourier sampling เป็นตัวอย่างแรกที่รู้จักของปัญหา query ที่อัลกอริทึมควอนตัมมีข้อได้เปรียบแบบ super-polynomial เหนืออัลกอริทึม probabilistic ซึ่งเกินข้อได้เปรียบของควอนตัมเหนือคลาสสิกที่เสนอโดยอัลกอริทึม Deutsch-Jozsa พูดอย่างสัญชาตญาณ เวอร์ชัน recursive ของปัญหาขยายข้อได้เปรียบ $1$ ต่อ $n$ ของอัลกอริทึมควอนตัมให้ใหญ่โตมากขึ้น

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

ปัญหาของ Simon และอัลกอริทึมสำหรับมันที่อธิบายในส่วนถัดไป ให้ตัวอย่างที่ง่ายกว่ามากของข้อได้เปรียบแบบ super-polynomial (และจริง ๆ แล้วคือ exponential) ของควอนตัมเหนือคลาสสิก และด้วยเหตุนี้ปัญหา recursive Fourier sampling จึงถูกพูดถึงน้อยกว่า อย่างไรก็ตาม มันยังคงเป็นปัญหาการคำนวณที่น่าสนใจในแบบของตัวเอง