Quantum computational complexity

John Watrous

Stephen Fenner

Abstract We survey several applications to quantum computing of computational complexity theory, especially the complexity of problems related to counting. We show how the connection of quantum computation to counting is very close. We define counting complexity classes, relativization of both classical computation and quantum circuits, and present a number of results from disparate sources, recast into a single consistent formalism. We assume prior knowledge of the mathematical formalism of quantum mechanics, but we present the concepts of computational complexity in an introductory manner.

Lance Fortnow

The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions. Quantum computing often scares away many potential researchers from computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic. This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.

Marco O. Lanzagorta, Jeffrey K. Uhlmann

Jincheng Zhang

This paper presents a novel theoretical framework for dynamic complexity computation, leveraging the unique properties of quantum entanglement to enhance the assessment of complex system computational complexity. We propose a method that establishes a direct link between complexity metrics and entanglement, enabling the precise evaluation of computational stability and guiding algorithm optimization based on this understanding. The core mechanism involves associating complexity with entanglement's inherent characteristics, utilizing entanglement for stability assessment and algorithmic optimization. This approach offers a fundamentally different perspective on complexity, moving beyond traditional statistical methods and embracing the subtle yet powerful interplay of quantum mechanics. This research aims to provide a robust and potentially transformative tool for computational complexity analysis, particularly in the design and optimization of complex algorithms.

孝志 三原