跳轉到

3.3 通用閘集合與電路模擬器實作#

概念說明#

通用閘集合（universal gate set）：一組閘，若任意 \(n\) 位元么正變換都能用這組閘的電路以任意精度逼近，則稱為通用的。理論結果（Solovay–Kitaev 定理）指出：只要集合能生成「稠密」的么正群，逼近精度 \(\varepsilon\) 所需的閘數只以 \(O(\log^c(1/\varepsilon))\) 成長（ \(c \approx 3.97\) ，最新結果可到 \(c=1\) ）。

最常用的通用集合是 {H, T, CNOT}：

  • H 提供非對角的「旋轉」能力；
  • T 提供無理相位的細微旋轉（ \(H,T\) 可逼近任意單量子位元么正）；
  • CNOT 提供位元間的相互作用。

事實上「所有單量子位元閘 + CNOT」也通用；實務上各硬體平台有自己的原生閘（如離子阱的 \(R_x, R_z, \mathrm{Mølmer{-}Sørensen}\) ）。

狀態向量模擬器：把 \(n\) 位元狀態存成 \(2^n\) 複數陣列，每個閘依其觸及的位元更新振幅。核心技巧是對單量子位元閘 \(U\) 與目標位元 \(k\) ：把振幅依「第 \(k\) 位是 0 或 1」分成兩半，做

\[ \begin{pmatrix}a'_{s0}\\ a'_{s1}\end{pmatrix} = U \begin{pmatrix}a_{s0}\\ a_{s1}\end{pmatrix}, \quad s \text{ 為其餘位元索引} \]

Python 範例：完整模擬器#

import numpy as np

class Simulator:
    def __init__(self, n):
        self.n = n
        self.state = np.zeros(2**n, dtype=complex)
        self.state[0] = 1.0            # |00...0>

    def apply_1q(self, U, k):
        """單量子位元閘 U 作用在第 k 位（0=最低位）"""
        for i in range(2**self.n):
            if (i >> k) & 1 == 0:      # 只處理第 k 位為 0 的索引
                j = i | (1 << k)
                a, b = self.state[i], self.state[j]
                self.state[i] = U[0,0]*a + U[0,1]*b
                self.state[j] = U[1,0]*a + U[1,1]*b

    def apply_cx(self, ctrl, targ):
        """CNOT：ctrl 為 1 時翻轉 targ 位振幅的符號排列"""
        for i in range(2**self.n):
            if (i >> ctrl) & 1 and (i >> targ) & 1 == 0:
                j = i | (1 << targ)
                self.state[i], self.state[j] = self.state[j], self.state[i]

    def h(self, k):  self.apply_1q(np.array([[1,1],[1,-1]],dtype=complex)/np.sqrt(2), k)
    def x(self, k):  self.apply_1q(np.array([[0,1],[1,0]],dtype=complex), k)
    def z(self, k):  self.apply_1q(np.array([[1,0],[0,-1]],dtype=complex), k)
    def t(self, k):  self.apply_1q(np.array([[1,0],[0,np.exp(1j*np.pi/4)]],dtype=complex), k)

    def measure(self, shots=1000, seed=None):
        p = np.abs(self.state)**2
        rng = np.random.default_rng(seed)
        return rng.choice(2**self.n, size=shots, p=p)

sim = Simulator(2)
sim.h(1); sim.apply_cx(1, 0)          # H(控制) + CNOT -> Bell 態
counts = np.bincount(sim.measure(shots=10000, seed=1), minlength=4)
print("Bell 態量測 (00,01,10,11):", counts)   # 只有 00 與 11
print("狀態:", np.round(sim.state, 3))

複雜度分析#

  • 記憶體： \(O(2^n)\) 個複數。
  • 單量子位元閘 / CNOT： \(O(2^n)\) 時間。
  • \(m\) 個閘的電路： \(O(m\,2^n)\) 。 \(n=30\) 時每閘約 10 億次運算，是實務上限。
  • 窮舉任意 \(n\) 位元么正需要 \(4^n \times 4^n\) 參數，通用閘集合的重要性在於把「任意變換」壓縮成多項式（大部分情形）個基本閘。

練習#

  1. 擴充 Simulator 加入 rz(theta, k) 與 swap(a, b)（用 3 個 CNOT），並用 swap 驗證 \(|01\rangle \to |10\rangle\) 。
  2. 用模擬器構造 3 位元 GHZ 態 \(\frac{|000\rangle+|111\rangle}{\sqrt2}\) ，量測 10000 次並統計只有 000 與 111 出現。
  3. （理論）查閱 Solovay–Kitaev 定理，說明為什麼「閘集合需要是稠密的」才可能通用，並舉一個不通用的小閘集合（如 {H, CNOT}）。