Quantum Randomness and Nondeterminism
Quantum Randomness and Nondeterminism
复制标题
量子随机性和非确定性
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
E. Knill
中科院分区：
文献类型：
--
作者：
E. Knill
量子随机或非确定性算法的概念是否有意义？如果有，量子随机性或非确定性是否增加了力量？虽然合理的量子随机源不会增加计算能力，但对量子随机性的讨论自然会导致量子态复杂性的几种定义。与经典的弦复杂性不同，确定性和非确定性量子态复杂性都很有趣。对决策问题引入了全量子不确定性的概念。这个概念可能是古典非决定论的一个适当的扩展。
Does the notion of a quantum randomized or nondeterministic algorithm make sense, and if so, does quantum randomness or nondeterminism add power? Although reasonable quantum random sources do not add computational power, the discussion of quantum randomness naturally leads to several definitions of the complexity of quantum states. Unlike classical string complexity, both deterministic and nondeterministic quantum state complexities are interesting. A notion of \emph{total quantum nondeterminism} is introduced for decision problems. This notion may be a proper extension of classical nondeterminism.