论文标题
从可计算的非随机序列中生成随机性
Generating Randomness from a Computable, Non-random Sequence of Qubits
论文作者
论文摘要
Nies和Scholz提出了一个状态的概念，以描述状态的无限量子序列和定义的量子马丁 - 马丁 - 马丁 - 洛夫·洛夫（Quantum-Martin-lof），类似于康托尔空间元素（无限序列的空间）的众所周知的Martin-Löf随机性概念。我们将状态“测量”在基础上的“测量”如何诱导cantor空间的概率度量。如果在任何可计算的基础上诱导的措施将概率分配给Martin-Löf随机物，则状态为“测量随机”（MR）。同等地，当且仅当以任何可计算的基础测量它时，一个状态是MR，才能随机产生Martin-Löf随机的概率。虽然量子 - 马丁 - 洛夫随机状态是MR，但相反的失败是：有一个MR状态，X不是量子 - 马丁 - 洛夫随机。实际上，更强大的事情是真实的。虽然X是可计算的，并且可以轻松构建，但在任何可计算的基础上进行测量都会产生具有概率一个的算术随机序列。即，可以从可计算的非量子随机量子序列中生成经典算术随机性。
Nies and Scholz introduced the notion of a state to describe an infinite sequence of qubits and defined quantum-Martin-Lof randomness for states, analogously to the well known concept of Martin-Löf randomness for elements of Cantor space (the space of infinite sequences of bits). We formalize how 'measurement' of a state in a basis induces a probability measure on Cantor space. A state is 'measurement random' (mR) if the measure induced by it, under any computable basis, assigns probability one to the set of Martin-Löf randoms. Equivalently, a state is mR if and only if measuring it in any computable basis yields a Martin-Löf random with probability one. While quantum-Martin-Löf random states are mR, the converse fails: there is a mR state, x which is not quantum-Martin-Löf random. In fact, something stronger is true. While x is computable and can be easily constructed, measuring it in any computable basis yields an arithmetically random sequence with probability one. I.e., classical arithmetic randomness can be generated from a computable, non-quantum random sequence of qubits.
