量子態識別問題之高效率演算法

Abstract

量子態同一性測試是量子資訊處理中的一項基本原語。雖然全域排列測試對於純態且完全相同的狀態具有嚴格的最優性，環境退相干等物理限制使得必須採用能處理有界誤差與混合態的測試協定。本論文系統性地研究放寬條件下的 QSI_n 問題。 首先，我們從數學上證明，標準排列測試在雙邊輸入放寬下，會因局部誤差在張量積空間中的乘法式累積而導致完備性發生災難性崩潰。為了克服這項根本限制並降低電路複雜度，我們研究一種以 SWAP tree 為基礎的驗證架構。此階層式架構將全域對稱性檢查分解為局部成對測量，並以良好的對數樣本複雜度達成高可區分性。 此外，為了處理去極化通道所引起的嚴重雜訊，我們提出一種穩健的兩階段架構。此方法將串流式量子態純化模組整合為識別測試前的預處理階段，從結構上分離誤差抑制與同一性驗證。分析結果證實，此整合可將初始環境雜訊有效降低至可忽略的殘餘參數，使後續的同一性測試維持近乎最優的成功機率。綜合而言，這些理論與演算法貢獻為現實物理環境中的量子態驗證提供了一個高效率且具抗雜訊能力的框架。

Quantum State Identity testing is a fundamental primitive in quantum information processing. While the global Permutation Test is strictly optimal for pure and perfectly identical states, physical constraints such as environmental decoherence necessitate testing protocols capable of handling bounded errors and mixed states. In this thesis, we systematically investigate the QSI_n problem under relaxed conditions. We first mathematically demonstrate that the standard Permutation Test suffers from a catastrophic collapse in completeness under a two-sided inputs relaxation due to the multiplicative accumulation of local errors. To circumvent this fundamental limitation and reduce circuit complexity, we study a SWAP-tree-based verification architecture. This hierarchical architecture decomposes the global symmetry check into localized pairwise measurements, achieving high distinguishability with a favorable logarithmic sample complexity. Furthermore, to combat severe noise induced by depolarizing channels, we introduce a robust two-stage architecture. By integrating a streaming quantum state purification gadget as a state preprocessing phase, this approach structurally decouples error suppression from identity verification. Analytical results confirm that this integration successfully drives the initial environmental noise down to a negligible residual parameter, allowing the subsequent identity tests to maintain near-optimal success probabilities. Collectively, these theoretical and algorithmic contributions provide a highly efficient and noise-resilient framework for quantum state verification in realistic physical environments.