This research applies concepts from algorithmic probability to Boolean and quantum combinatorial logic circuits. A tutorial-style introduction to states and various notions of the complexity of states are presented. Thereafter, the probability of states in the circuit model of computation is defined. Classical and quantum gate sets are compared to select some characteristic sets. The reachability and expressibility in a space-time-bounded setting for these gate sets are enumerated and visualized. These results are studied in terms of computational resources, universality and quantum behavior. The article suggests how applications like geometric quantum machine learning, novel quantum algorithm synthesis and quantum artificial general intelligence can benefit by studying circuit probabilities.
翻译:本研究应用算法概率的概念来处理布尔和量子组合逻辑电路。首先介绍了状态和各种复杂性概念,随后定义了计算模型中的状态概率。比较了经典和量子门集以选择一些特征集。计算这些门集在空时限制设置下的可达性和表达能力,然后进行可视化。通过计算资源、普适性和量子行为研究了这些结果。文章指出,几何量子机器学习、新型量子算法合成和量子人工智能等应用可以通过研究电路概率获益。