A compressed classical description of quantum states
A compressed classical description of quantum states
复制标题
量子态的压缩经典描述
DOI：
10.4230/lipics.tqc.2019.8
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
J. Smolin
中科院分区：
文献类型：
--
作者：
David Gosset;J. Smolin
我们展示了如何使用通常的经典存储量的平方根来近似表示量子态。N量子比特态$\psi$的经典表示由它的内积和$O(\Sqrt{2^n})$稳定子态组成。最初由其在计算基础中的$2^n$条目指定的量子态可以在时间$O(2^n\mathm{poly}(N))$被压缩为这种形式，随后，压缩的描述可以用于附加地近似任意可观量的期望值。我们的压缩方案直接为子空间中的矢量问题提供了一个新的协议，该协议具有随机化的单向通信复杂性，由于RAZ，它匹配(高达多个对数因子)最著名的上界。在计算效率方面，我们得到了比Raz协议指数级的改进。
We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an n-qubit state $\psi$ consists of its inner products with $O(\sqrt{2^n})$ stabilizer states. A quantum state initially specified by its $2^n$ entries in the computational basis can be compressed to this form in time $O(2^n \mathrm{poly}(n))$, and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the best known upper bound, due to Raz. We obtain an exponential improvement over Raz's protocol in terms of computational efficiency.