Bosons vs. Fermions – A computational complexity perspective

Recent years have seen a flurry of activity in the fields of quantum computing and quantum complexity theory, which aim to understand the computational capabilities of quantum systems by applying the toolbox of computational complexity theory. This paper explores the conceptually rich and technologically useful connection between the dynamics of free quantum particles and complexity theory. I review results on the computational power of two simple quantum systems, built out of noninteracting bosons (linear optics) or noninteracting fermions. These rudimentary quantum computers display radically different capabilities—while free fermions are easy to simulate on a classical computer, and therefore devoid of nontrivial computational power, a free-boson computer can perform tasks expected to be classically intractable. To build the argument for these results, I introduce concepts from computational complexity theory. I describe some complexity classes, starting with P and NP and building up to the less common #P and polynomial hierarchy, and the relations between them. I identify how probabilities in free-bosonic and free-fermionic systems fit within this classification, which then underpins their difference in computational power. This paper is aimed at graduate or advanced undergraduate students with a Physics background, hopefully serving as a soft introduction to this exciting and highly evolving field.近年来，量子计算与量子复杂性理论领域迎来了蓬勃的研究热潮，二者旨在通过运用计算复杂性理论的研究工具，解析量子系统的计算能力。本文聚焦自由量子粒子动力学与复杂性理论之间兼具理论内涵与应用价值的关联展开研究。本文综述了两类基础量子计算模型的计算能力相关研究成果，这两类模型分别由无相互作用玻色子（noninteracting bosons，线性光学体系）与无相互作用费米子（noninteracting fermions）构建而成。这类基础量子计算模型展现出截然不同的计算能力：无相互作用费米子系统可在经典计算机上轻松模拟，因此不具备非平凡的计算能力；而无相互作用玻色子系统则能够完成经典计算机预计难以求解的任务。为论证上述结论，本文引入计算复杂性理论的相关概念。本文将介绍若干复杂性类，从基础的P类、NP类出发，逐步拓展至相对小众的#P类与多项式谱系（polynomial hierarchy），并阐述各类之间的内在关联。本文将阐明自由玻色子与自由费米子系统中的概率分布如何归入上述复杂性分类框架，这一分析正是二者计算能力存在差异的核心理论依据。本文面向具备物理学背景的研究生或高年级本科生，以期为这一蓬勃发展的前沿领域提供一篇深入浅出的入门导读。