将贝尔采样扩展至任意维度量子系统,实现稳定子态高效学习与测试。
Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- 基于拉格朗日四平方定理构造新酉算符,实现四份稳定子态到其共轭的映射。
- 在任意维度d≥2下,稳定子态学习仅需O(n³)时间与O(n)样本。
- 首次在高维系统中建立伪随机性下界,适用于量子密码与复杂度研究。
贝尔采样是一种基于在贝尔基上测量两份量子态的简单但强大的工具,已在稳定子态和魔术度量等问题中广泛应用。然而,此前无法将该方法从比特推广到任意维度的量子系统——即多能级系统(qudits),对所有d > 2均无有效推广。已有研究(arXiv'24)表明,自然扩展方式在高维下会丢失有意义信息。本文克服上述困难,提出一种适用于所有d≥2的有用贝尔采样通用方法。核心在于构造一个新酉算符,基于拉格朗日四平方定理,可将任意稳定子态|S⟩的四份副本映射为共轭态|S*⟩(至多相差一个泡利算符),该构造本身具有独立价值。我们进一步利用此技术,将多个已知的比特结果推广至任意维度:1. 在O(n³)时间内用O(n)样本学习稳定子态;2. 在 ilde{O}(n³/ε)时间内用 ilde{O}(n/ε)样本解决隐藏稳定子群问题;3. 在 ilde{O}(n³/ε)时间内用 ilde{O}(n/ε)样本测试态的稳定子规模是否至少为d^t,或与所有此类态ε-远离;4. 含不超过n/2个单量子比特非泡利门的克里福电路无法生成伪随机态;5. 若ε₁ = O(ε₂/d²),则可用O(d²ε₂/(ε₂−ε₁)²)样本测试态的稳定子保真度是否至少为1−ε₁,或至多为1−ε₂。
原文摘要 · Abstract (English)
Bell sampling is a simple yet powerful tool based on measuring two copies of a quantum state in the Bell basis, and has found applications in a plethora of problems related to stabiliser states and measures of magic. However, it was not known how to generalise the procedure from qubits to $d$-level systems -- qudits -- for all dimensions $d > 2$ in a useful way. Indeed, a prior work of the authors (arXiv'24) showed that the natural extension of Bell sampling to arbitrary dimensions fails to provide meaningful information about the quantum states being measured. In this paper, we overcome the difficulties encountered in previous works and develop a useful generalisation of Bell sampling to qudits of all $d\geq 2$. At the heart of our primitive is a new unitary, based on Lagrange's four-square theorem, that maps four copies of any stabiliser state $|\mathcal{S}\rangle$ to four copies of its complex conjugate $|\mathcal{S}^\ast\rangle$ (up to some Pauli operator), which may be of independent interest. We then demonstrate the utility of our new Bell sampling technique by lifting several known results from qubits to qudits for any $d\geq 2$: 1. Learning stabiliser states in $O(n^3)$ time with $O(n)$ samples; 2. Solving the Hidden Stabiliser Group Problem in $\tilde{O}(n^3/\varepsilon)$ time with $\tilde{O}(n/\varepsilon)$ samples; 3. Testing whether $|ψ\rangle$ has stabiliser size at least $d^t$ or is $\varepsilon$-far from all such states in $\tilde{O}(n^3/\varepsilon)$ time with $\tilde{O}(n/\varepsilon)$ samples; 4. Clifford circuits with at most $n/2$ single-qudit non-Clifford gates cannot prepare pseudorandom states; 5. Testing whether $|ψ\rangle$ has stabiliser fidelity at least $1-\varepsilon_1$ or at most $1-\varepsilon_2$ with $O(d^2\varepsilon_2/(\varepsilon_2-\varepsilon_1)^2)$ samples if $\varepsilon_1 = O(\varepsilon_2/d^{2})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。