跳轉到

7.2 QFT 電路的實作#

概念說明#

把 QFT 拆成電路需要一個改寫。對 \(N=2^n\) ，把 \(j\) 寫成二進位 \(j = j_1 2^{n-1} + \cdots + j_n\) ，可以證明：

\[ \mathrm{QFT}|j\rangle = \frac{1}{2^{n/2}}\bigotimes_{l=1}^{n}\Big(|0\rangle + e^{2\pi i\, 0.j_l j_{l+1}\cdots j_n}|1\rangle\Big) \]

其中 \(0.j_l j_{l+1}\cdots = j_l/2 + j_{l+1}/4 + \cdots\) （二進位小數）。這個張量積形式提示了電路：

電路（ \(n\) 個位元，從最高位 q0 開始）：

  1. 對每個位元 \(k = 0, 1, \dots, n-1\) ：
  2. 對第 \(k\) 位做 H；
  3. 依次做受控相位閘 \(\mathrm{CP}(\pi/2^{d})\) ：控制位元是第 \(k+d\) 位、標的是第 \(k\) 位， \(d = 1, \dots, n-1-k\) ；
  4. 最後把所有位元順序反轉（SWAP 網路， \(n/2\) 個 SWAP）。

其中 \(\mathrm{CP}(\theta) = \mathrm{diag}(1,1,1,e^{i\theta})\) 。

閘數： \(n\) 個 H + \(\frac{n(n-1)}{2}\) 個 CP + \(\frac{n}{2}\) 個 SWAP，總計 \(O(n^2)\) 。這正是相對 FFT 的（在閘計數意義下的）指數加速。

實作時的技巧：受控相位閘作用在狀態向量上只需對「兩控制位元皆為 1」的振幅乘 \(e^{i\theta}\) ， \(O(2^n)\) 。

Python 範例#

import numpy as np

def apply_cp(state, n, ctrl, targ, theta):
    """受控相位閘 CP(theta)"""
    s = state.copy()
    for i in range(2**n):
        if (i >> ctrl) & 1 and (i >> targ) & 1:
            s[i] *= np.exp(1j*theta)
    return s

def apply_h(state, n, k):
    H1 = np.array([[1,1],[1,-1]], dtype=complex)/np.sqrt(2)
    out = state.copy()
    for i in range(2**n):
        if (i >> k) & 1 == 0:
            j = i | (1 << k)
            a, b = out[i], out[j]
            out[i] = (a + b)/np.sqrt(2)
            out[j] = (a - b)/np.sqrt(2)
    return out

def qft_circuit(state, n):
    """QFT 電路（位元 0 為最高位）"""
    psi = state.copy()
    for k in range(n):
        psi = apply_h(psi, n, k)
        for d in range(1, n-k):
            psi = apply_cp(psi, n, k+d, k, np.pi/2**d)
    # 位元反轉
    out = np.zeros_like(psi)
    for i in range(2**n):
        rev = int(format(i, f"0{n}b")[::-1], 2)
        out[rev] = psi[i]
    return out

def qft_matrix(n):
    N = 2**n
    j, k = np.meshgrid(np.arange(N), np.arange(N))
    return np.exp(2j*np.pi*j*k/N)/np.sqrt(N)

n = 4
state = np.zeros(2**n, dtype=complex); state[5] = 1     # |5>
circ = qft_circuit(state, n)
ref = qft_matrix(n) @ state
print("電路版 QFT|5> =", np.round(circ, 3))
print("矩陣版       =", np.round(ref, 3))
print("兩者相同嗎?", np.allclose(circ, ref))

# 驗證 F 是么正的
F = qft_matrix(n)
print("F 么正嗎?", np.allclose(F.conj().T @ F, np.eye(2**n)))

複雜度分析#

  • 電路閘數： \(n + \frac{n(n-1)}{2} + \frac{n}{2} = O(n^2)\) 。
  • 狀態向量模擬：每個閘 \(O(2^n)\) ，總計 \(O(n^2 2^n)\) ——仍是指數，這是模擬器的宿命，但常數遠小於顯式構造 \(2^n\times2^n\) 矩陣（ \(O(4^n)\) ）。
  • 硬體考量：CP 閘的精度隨 \(d\) 指數變小，實務上超過 3~4 個控制位元的相位可捨去（approximate QFT），閘數可再省。

練習#

  1. 手算 \(n=3\) 電路對 \(|1\rangle\) 的作用，逐步寫出振幅，並與矩陣結果比對。
  2. （程式）把 qft_circuit 改成 approximate QFT：丟棄 \(\theta < 0.01\) 的 CP 閘，比較與精確版的內積保真度與閘數節省。
  3. （觀念）為什麼 QFT 電路最後需要位元反轉？在什麼情況下可以省略？