Bosons vs. Fermions – A computational complexity perspective

• Published in: Revista Brasileira de Ensino de Física 2021, Vol.43 (suppl 1)
• Main Author: Brod, Daniel Jost
• Format: Article
• Language: eng ; por
• Subjects: free fermions; linear optics; quantum complexity theory; Quantum computing
• ISSN: 1806-1117; 1806-1117; 1806-9126
• DOI: 10.1590/1806-9126-rbef-2020-0403

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. Os últimos anos presenciaram uma atividade crescente nas áreas de computação quântica e teoria de complexidade quântica. Essas áreas têm como objetivo analisar a complexidade e as capacidades computacionais de diversos sistemas quânticos através do uso das ferramentas desenvolvidas, ao longo das últimas décadas, no contexto da teoria de complexidade computacional. Este artigo explora as conexões conceitualmente ricas e tecnologicamente úteis entre a dinâmica de partículas quânticas livres e a teoria da complexidade. Eu reviso resultados sobre a complexidade computacional da simulação de dois sistemas quânticos simples, construídos com bósons não interagentes (ou seja, óptica linear), ou com férmions não interagentes. Tais sistemas podem ser vistos como tipos rudimentares de computadores quânticos, com potencialidades radicalmente distintas: por um lado, sabe-se que férmions livres são facilmente simulados por um computador clássico e, portanto, desprovidos de poder computacional não trivial; por outro lado, existe forte evidência de que um computador constr