Quantum algorithms, quantum field theory, and computational complexity

R. Hayakawa, Tomoyuki Morimae

Jincheng Zhang

This research investigates computational complexity problems through the lens of quantum field theory (QFT). Traditional approaches to complexity theory often rely on algorithmic and logical arguments, while QFT provides a powerful framework for analyzing systems with high dimensionality and entanglement. This paper explores how QFT concepts – such as renormalization, path integrals, and the representation of states as quantum fields – can be applied to understand and potentially mitigate the challenges inherent in certain computational problems. Specifically, we examine how the inherent probabilistic nature of QFT, combined with its ability to handle complex, high-dimensional spaces, might offer new perspectives on problems like NP-completeness and the limits of computation. We propose a framework for translating complexity problems into QFT-inspired models and discuss potential avenues for leveraging these models to explore the landscape of computational complexity. The core contribution of this work lies in establishing a novel methodology for tackling complexity questions by drawing upon the established tools and techniques of QFT. We investigate the potential for utilizing QFT's inherent parallelism and its ability to represent exponentially large state spaces to overcome limitations faced by classical algorithms.

Jincheng Zhang

This paper presents a novel quantum algorithm designed to accelerate the simulation of complex quantum field theories, addressing limitations of classical methods in handling high-dimensional scenarios. We propose a quantum mechanism centered around superposition and entanglement to represent quantum fields, aiming for a substantial reduction in computational cost. The core of the algorithm involves a carefully crafted quantum circuit that exploits these principles to achieve a more accurate and efficient simulation of these theories. We provide a detailed explanation of the algorithm's design, including the quantum operations involved and the potential benefits of its implementation. The paper concludes with a discussion of the challenges and future directions of this research.

Andris Ambainis

Marco O. Lanzagorta, Jeffrey K. Uhlmann

A. C. Manoharan

Because the subject of relativistic quantum field theory (QFT) contains all of non-relativistic quantum mechanics, we expect quantum field computation to contain (non-relativistic) quantum computation. Although we do not yet have a quantum theory of the gravitational field, and are far from a practical implementation of a quantum field computer, some pieces of the puzzle (without gravity) are now available. We consider a general model for computation with quantum field theory, and obtain some results for relativistic quantum computation. Moreover, it is possible to see new connections between principal models of computation, namely, computation over the continuum and computation over the integers (Turing computation). Thus we identify a basic problem in QFT, namely Wightman's computation problem for domains of holomorphy, which we call WHOLO. Inspired by the same analytic functions which are central to the famous CPT theorem of QFT, it is possible to obtain a computational complexity structure for QFT and shed new light on certain complexity classes for this problem WHOLO.