跳轉到

5.2 Deutsch–Jozsa 演算法#

概念說明#

問題：已知 \(f:\{0,1\}^n \to \{0,1\}\) 保證是以下兩種之一——

  • 常數函式：所有 \(x\) 都有 \(f(x)=c\) ；
  • 平衡函式（balanced）：恰好一半的 \(x\) 有 \(f(x)=0\) 。

請判斷它是哪一種。古典演算法最壞情況需查詢 \(2^{n-1}+1\) 次（查到一半一樣仍無法確定）。量子演算法只要 1 次查詢。

演算法步驟（ \(n+1\) 個位元： \(x\) 暫存器與一個輔助位元 \(y\) ）：

  1. 初始化 \(|0\rangle^{\otimes n}|1\rangle\) ，對輔助位元做 H 得 \(|-\rangle\) ；
  2. 全部輸入位元做 H，得 \(\frac{1}{\sqrt{2^n}}\sum_x |x\rangle|-\rangle\) ；
  3. 作用一次 \(U_f\) ，由 phase kickback 得 \(\frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle|-\rangle\) ；
  4. 對輸入暫存器再做 H，測量輸入暫存器：全 0 ⟺ 常數，否則為平衡。

振幅推導：Hadamard 的變換是 \(H|x\rangle = \frac{1}{\sqrt{2^n}}\sum_z (-1)^{x\cdot z}|z\rangle\) ，因此第 4 步後輸入暫存器在 \(|0\rangle\) 的振幅為

\[ \frac{1}{2^n}\sum_x (-1)^{f(x)} \]

常數函式時此和為 \(\pm 1\) （機率 1 測得全 0）；平衡函式時恰好抵消為 0。

Python 範例#

import numpy as np

def dj_oracle_matrix(f, n):
    N = 2**(n+1)
    U = np.zeros((N, N), dtype=complex)
    for x in range(2**n):
        for y in range(2):
            col, row = (x << 1)|y, (x << 1)|(y ^ f(x))
            U[row, col] = 1
    return U

def deutsch_jozsa(f, n):
    Hn = np.kron(np.eye(2**n), np.array([[1,-1],[1,1]], dtype=complex))/np.sqrt(2)
    psi = np.zeros(2**(n+1), dtype=complex)
    psi[1] = 1                                    # |0...0>|1>
    psi = np.kron(np.eye(2**n), H) @ psi if False else psi
    # 直接構造：輸入暫存器 |+>^n、輔助 |->
    plus_all = np.ones(2**n, dtype=complex)/np.sqrt(2**n)
    aux = np.array([1,-1], dtype=complex)/np.sqrt(2)
    psi = np.kron(plus_all, aux)
    psi = dj_oracle_matrix(f, n) @ psi            # 一次查詢
    # 對輸入暫存器再做 H
    H1 = np.array([[1,1],[1,-1]], dtype=complex)/np.sqrt(2)
    Hn1 = np.eye(1)
    for _ in range(n): Hn1 = np.kron(Hn1, H1)
    psi = np.kron(Hn1, np.eye(2)) @ psi
    p_all_zero = abs(psi[0])**2                   # 機率:測得 |0...0>|.>
    return "常數" if p_all_zero > 0.99 else "平衡"

H = np.array([[1,1],[1,-1]], dtype=complex)/np.sqrt(2)

for n in [1, 2, 3]:
    f_const  = lambda x: 1                        # 常數
    f_bal    = lambda x: (x & 1) ^ ((x >> 1) & 1) # n>=2 平衡（XOR 各位）
    print(f"n={n}: 常數函式 ->", deutsch_jozsa(f_const, n),
          "| 平衡函式 ->", deutsch_jozsa(f_bal, n))

複雜度分析#

  • 量子：查詢複雜度 1；電路閘數 \(O(n)\) （ \(n\) 個 H + 一次 \(U_f\) ）。
  • 古典（確定性）：最壞 \(2^{n-1}+1\) 次查詢，這是可證明的最優。
  • 模擬器成本： \(O(2^n)\) 狀態向量 × \(O(n)\) 閘。

練習#

  1. 對 \(n=2\) 手算平衡函式 \(f(x)=x_0 \oplus x_1\) 在 DJ 演算法中最終測得全 0 的機率，應為 0。
  2. （程式）把 deutsch_jozsa 改成測量 1000 次統計分佈，對常數與平衡函式各印出結果。
  3. （觀念）若 \(f\) 既非常數也不平衡，DJ 演算法會輸出什麼？為什麼此演算法的前提（保證二選一）是必要的？