Bài 6: Quantum Principal Component Analysis
Nội dung
Giới thiệu
Thuật toán Principal Component Analysis (hay PCA) là một trong những kỹ thuật quan trọng trong Machine Learning để giảm chiều dữ liệu (Dimensionality Reduction). Thông thường data hay các feature vectors được biểu diễn trên không gian đa chiều, thậm chí số chiều có thể lên tới vài nghìn. Việc tính toán cũng như lưu trữ trên bộ dữ liệu như vậy sẽ gặp rất nhiều khó khăn. Do đó, việc giảm chiều dữ liệu là một bước quan trọng trong nhiều bài toán, và điển hình ở đây mình sẽ đề cập tới thuật toán PCA.
Thuật toán PCA được phát triển dựa theo mô hình tuyến tính để giữ lại $\mathcal{K}$ phần tử quan trọng nhất sao cho $\mathcal{K} < \mathcal{D}$ (số chiều của dữ liệu). Trong đó, tầm quan trọng của các phần tử được đánh giá dựa trên giá trị riêng (eigenvalues) của ma trận phương sai (covariance matrix) của dữ liệu. Nhưng với các bộ dữ liệu lớn, việc tính toán ma trận phương sai hay phân rã trị riêng cũng là một thách thức. Thực tế, với một bộ dữ liệu gồm $\mathcal{N}$ véc-tơ và mỗi véc-tơ được biển diễn trên không gian $\mathcal{D}$ chiều thì ta cần $O(\mathcal{D}^2\mathcal{N})$ để tính ma trận phương sai và $O(\mathcal{D}^3)$ cho việc phân rã trị riêng. Như vậy, độ phức tạp của thuật toán PCA sẽ là $O(\mathcal{D}^2\mathcal{N}+\mathcal{D}^3)$.
Trong bài viết này, mình sẽ giới thiệu một phương pháp lượng tử để giải quyết bài toán trên với độ phức tạp $O(\mathcal{D}poly(\log{\mathcal{D}}))$ nhờ vào khả năng tính toán vượt trội của máy tính lượng tử: Quantum Principal Component Analysis (hay qPCA).
Quantum PCA
Xét tập dữ liệu $\mathbb{X}$ gồm $\mathcal{N}$ véc-tơ. Giống với thuật toán PCA thông thường, qPCA cũng có bước chuẩn hóa dữ liệu sao cho kỳ vọng của dữ liệu là 0:
$$ x_i \rightarrow \frac{x_i - \frac{1}{\mathcal{N}}\sum_{i=1}^{\mathcal{N}}x_i}{||x_i||_2} . $$Từ đây ta hoàn toàn có thể biểu diễn dữ liệu trong máy tính lượng tử sử dụng phương pháp Amplitude Embedding như mình đã đề cập ở Bài 2:
$$ \ket{x_i} = \sum_{k=0}^{\mathcal{D}-1}x_{ik}\ket{k}. $$Giả sử ta gọi $\rho_i = \ket{x_i}\bra{x_i}$ là outer product của véc-tơ $\ket{x_i}$. $$ \rho_i = \sum_{k=0}^{\mathcal{D}-1}\sum_{m=0}^{\mathcal{D}-1}x_{ik}x_{im}\ket{k}\bra{m}, $$ Do đó ta xét trên toàn bộ tập dữ liệu $\mathcal{N}$ véc-tơ, ta có: $$ \rho = \frac{1}{\mathcal{N}}\sum_{i=1}^{\mathcal{N}}\rho_i = \frac{1}{\mathcal{N}}\sum_{i=1}^{\mathcal{N}}\sum_{k=0}^{\mathcal{D}-1}\sum_{m=0}^{\mathcal{D}-1}x_{ik}x_{im}\ket{k}\bra{m}, $$
Như mọi người có thể thấy thì amplitude của $\rho$ chính là các phần tử tương ứng của ma trận hiệp phương sai tại vị trí $(k,m)$.
Như vậy việc còn lại của chúng ta cần phải làm là tìm các trị riêng và véc-tơ riêng tương ứng của $\rho$. Từ đó, bài toán đưa ta tới với thuật toán Quantum Phase Estimation (hay QPE), như mình để cập ở Bài 4. Trong thuật toán QPE, cho một ma trận đơn nhất $U$ và một trong những véc-tơ riêng của nó thì ta luôn tính được giá trị riêng tương ứng của véc-tơ đó. Tuy nhiên, $\rho$ không là ma trận đơn nhất (unitary matrix), nên mình cần dùng một kỹ thuật khác để biến đổi: $\rho \longrightarrow U$. Vì $\rho$ là một ma trận Hermitian (chứng mính ở Box 1), giống nhưng cách ở Bài 5, mình có thể chọn ma trận đơn nhất $U = e^{i\rho t}$.
Box 1: Ma trận $H$ được gọi là Hermitian nếu $H = H^{\dagger}$. Ta có:
$$ \rho = \frac{1}{\mathcal{N}}\sum_{i=1}^{\mathcal{N}}\sum_{k=0}^{\mathcal{D}-1}\sum_{m=0}^{\mathcal{D}-1}x_{ik}x_{im}\ket{k}\bra{m}, $$
Dễ thấy $\rho$ đối xứng, và:
$$ \rho^{\dagger} = \frac{1}{\mathcal{N}}\sum_{i=1}^{\mathcal{N}}\sum_{k=0}^{\mathcal{D}-1}\sum_{m=0}^{\mathcal{D}-1}x_{ik}^{*}x_{im}^{*}\ket{k}\bra{m} $$
Trong đó, $x_{ik}^{*}$ là số liên hợp của $x_{ik}$. Tuy nhiên, ở đây ta xét véc-tơ $\overrightarrow{x} \in R$ nên $x_{ik}^{*} = x_{ik}$. Do đó, $\rho = \rho^{\dagger}$
Xét ma trận Hermitian $\rho = \sum_{j} \lambda_j \ket{\phi_j}\bra{\phi_j}$ (theo phân tích phổ - spectral decomposition), trong đó $\ket{\phi_j}$ và $\lambda_j$ là véc-tơ riêng và giá trị riêng tương ứng của $\rho$, ta có:
$$
U = e^{i\rho t} = \sum_{j} e^{i\lambda_j t} \ket{\phi_j}\bra{\phi_j} = \sum_{j} e^{2\pi i\frac{\lambda_j t}{2\pi}} \ket{\phi_j}\bra{\phi_j}
$$
Mình đặt $\tilde{\lambda_j} = \frac{\lambda_j t}{2\pi}$, thì bài toán sẽ được đưa về khuôn mẫu của thuật toán QPE. Tuy nhiên thuật toán QPE yêu cầu ta biết trước véc-tơ riêng $\ket{\phi_j}$ nên thay vào đó ta có thể dùng một điểm dữ liệu bất kỳ $x_i=\sum_{j} \alpha_{ij} \ket{\phi_j}$, trong đó $\alpha_{ij} = \left\langle \phi_j \vert x_i \right\rangle$. Do đó ta có thể biểu diễn thuật toán QPE như sau:
$$
\text{QPE:} \ket{0}^{\otimes n} \ket{x_i} \rightarrow \sum_{j}^{\mathcal{D}} \alpha_{ij} \ket{\tilde{\lambda_j}} \ket{\phi_j}
$$
Không mất tính tông quát, ta thay $\ket{x_i}$ bằng $\ket{x_i}\bra{x_i}$, ta được:
$$
\text{QPE:} \ket{0}^{\otimes n} \otimes \rho_i \rightarrow \sum_{j}^{\mathcal{D}} |\alpha_{ij}|^2 \ket{\tilde{\lambda_j}}\bra{\tilde{\lambda_j}} \otimes \ket{\phi_j}\bra{\phi_j}
$$
hay,
$$
\text{QPE:} \ket{0}^{\otimes n} \otimes \rho \rightarrow \frac{1}{\mathcal{N}}\sum_{i=1}^{\mathcal{N}} \sum_{j}^{\mathcal{D}} |\alpha_{ij}|^2 \ket{\tilde{\lambda_j}}\bra{\tilde{\lambda_j}} \otimes \ket{\phi_j}\bra{\phi_j}.
$$
Mặt khác, ta có: $$ \frac{1}{\mathcal{N}}\sum_{i=1}^{\mathcal{N}} |\alpha_{ij}|^2 = \frac{1}{\mathcal{N}}\sum_{i=1}^{\mathcal{N}} \left\langle \phi_j \vert x_i \right\rangle \left\langle x_i \vert \phi_j \right\rangle $$ $$ = \bra{\phi_j} (\frac{1}{\mathcal{N}}\sum_{i=1}^{\mathcal{N}} \ket{x_i}\bra{x_i}) \ket{\phi_j} = \bra{\phi_j} \rho \ket{\phi_j}. $$ Mà $\ket{\phi_j}$ là véc-tơ riêng của $\rho$ nên ta luôn có $\bra{\phi_j} \rho \ket{\phi_j} = \tilde{\lambda_j} \left\langle \phi_j \vert \phi_j \right\rangle = \tilde{\lambda_j}$. Thay vào kết quả trên ta được: $$ \text{QPE:} \ket{0}^{\otimes n} \otimes \rho \rightarrow \sum_{j}^{\mathcal{D}} \tilde{\lambda_j}\ket{\tilde{\lambda_j}}\bra{\tilde{\lambda_j}} \otimes \ket{\phi_j}\bra{\phi_j}. $$ Như vậy, thông qua phép đo của kết quả từ thuật toán QPE trên ta sẽ thu được véc-tơ riêng và giá trị riêng của ma trận hiệp phương sai $\rho$.
Giờ chúng ta hãy đi kỹ hơn vào độ phức tạp của thuật toán qPCA.
(1) Đầu tiên, ta cần độ phức tạp $O(\log{\mathcal{D}})$ để có được ma trận hiệp phương sai $\rho$, vì với Amplitude Embedding ta cần $\log{\mathcal{D}}$ qubits để mã hóa véc-tơ $\ket{x_i}$
(2) Với thuật toán tìm giá trị riêng và véc-tơ riêng - QPE, ta cần độ phức tạp $O(poly(\log{\mathcal{D}}))$ (như mình đã trình bày ở Bài 4) để thu được một cặp $(\lambda_j, \phi_j)$. Tuy nhiên bài toán yêu cầu ta tìm được $\mathcal{T}$ cặp có giá trị riêng lớn nhất, do đó trong trường hợp ma trận full rank $\rho$, độ phức tạp bài toán lên tới $O(\mathcal{D}poly(\log{\mathcal{D}}))$.
Từ (1) và (2), thuật toán qPCA sẽ có độ phức tạp $O(\mathcal{D}poly(\log{\mathcal{D}}))$. Nếu so với sánh với thuật toán PCA trên máy tính truyền thống có độ phức tạp $O(\mathcal{D}^2\mathcal{N}+\mathcal{D}^3)$, ta thấy rằng qPCA mang lại sự cải thiện đáng kể trong việc tính toán cũng như tối ưu được tài nguyên sử dụng đặc biệt trong các bài toán yêu cầu số chiều của dữ liệu lớn.
Cảm ơn mọi người đã đọc bài.
