论文标题
量子状态携带多少经典信息？受Kolmogorov复杂性启发的方法
How much classical information is carried by a quantum state? An approach inspired by Kolmogorov complexity
论文作者
论文摘要
在量子力学中，状态是希尔伯特空间的元素，其维度成倍增长，随着粒子数量的增加（或量子位，在量子计算中）。模糊的问题“这是希尔伯特的巨大空间吗？”在计算复杂性理论中已被严格形式化；该研究对这个问题提出了积极的答案。沿着这一行，我给出了量子状态的（经典）信息内容的定义，从Kolmogorov的复杂性中汲取灵感。我表明，对于一些众所周知的量子电路（在量子数中具有多个门的多项式），根据我的定义评估了输出状态的信息内容，在量子数的数量中是多项式的。另一方面，采用已知结果，可以设计出产生更复杂状态的量子电路，具有成倍增长的信息内容。量子状态内可以真正存在大量的经典信息，但是，我表明，量子计算机不一定会利用此属性，甚至通过量子算法显示出相对于经典计算的指数加速。
In quantum mechanics, a state is an element of a Hilbert space whose dimension exponentially grows with the increase of the number of particles (or qubits, in quantum computing). The vague question "is this huge Hilbert space really there?" has been rigorously formalized inside the computational complexity theory; the research suggests a positive answer to the question. Along this line, I give a definition of the (classical) information content of a quantum state, taking inspiration from the Kolmogorov complexity. I show that, for some well-known quantum circuits (having a number of gates polynomial in the number of qubits), the information content of the output state, evaluated according to my definition, is polynomial in the number of qubits. On the other hand, applying known results, it is possible to devise quantum circuits that generate much more complex states, having an exponentially-growing information content. A huge amount of classical information can be really present inside a quantum state, however, I show that this property is not necessarily exploited by quantum computers, not even by quantum algorithms showing an exponential speed-up with respect to classical computation.
