Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computational Complexity: An Empirical View

Maël Pégny

Published Apr 3, 2013• 2 citations
OpenAlex

Abstract

Computational complexity theory (CCT) is usually construed as the mathematical study of the complexity of computational problems. In recent years, research work on unconventional computational models has called into question the purely mathematical nature of CCT, and has revealed potential relations between its subject matter and empirical sciences. In particular, recent debates surrounding quantum computing have raised the possibility of a new computational model, one based on quantum mechanics, which may be exponentially more efficient than any previously known machine. In this paper, I will show how those recent debates suggest an alternative , empirical view of CCT. I will then examine what are the fundamental arguments in the favor of this view, what are its consequences for our conception of CCT as a scientific field, and how further philosophical investigation should proceed.

Related papers

Quantum Field Theory-Based Computational Complexity Research

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.

•Sep 7, 2026•0 citations

Quantum computing

Guolin Wu

Quantum computing operates by manipulating the quantum state of a system to solve problems intractable for classical computing. These problems, previously considered limitations of classical algorithms, have solutions through quantum approaches. Therefore, quantum computing suggests that the complexity of such problems lies in the current epistemic state rather than the objective state of the problem. Computational complexity can be classified into objective and epistemic complexity. Some classical problems exhibiting exponential complexity fall into the epistemic category, as their solutions depend on the current state of human knowledge and available tools. Quantum computing suggests that even mathematics isn’t entirely objective, and mathematics, in one sense, is human-made and a kind of technology, which reflects our intention and planning. Computational complexity, therefore, bridges the objective and subjective. Overcoming classical complexity necessitates advancements in scientific theories, algorithms, and quantum technology, all of which rely on the development of human cognitive abilities. Quantum computing is not just a mathematical construct, but also has physical meaning. If it were purely mathematical, classical physics and systems could potentially achieve the same results. What makes the quantum world special is its empirical nature—the physical reality of quantum chips, quantum algorithms, and quantum evolution. Quantum supremacy, or quantum advantage, refers to the potential superiority of quantum computers over classical ones. Controllable quantum systems offer an overwhelming advantage in terms of manipulation and dominance compared to classical systems. Essentially, quantum computing has the potential to significantly outperform classical computing. Many experts, including Shor, have proposed that quantum computing’s power stems from its ability to perform multiple computations simultaneously—a concept often referred to as the Quantum parallelism thesis. Rather, some argue that the true source of quantum computing acceleration lies in the fundamental differences between classical and quantum logic. However, it’s important to note that quantum logic, while providing a new perspective, does not directly address the core principle of quantum parallelism. This dominance stems from quantum physics’ unique properties: Exponential storage capacity, parallel computing inherent to its nature (ontological), and the ability to perform calculations with exponential speedup through quantum algorithms.

Routledge eBooks•Oct 8, 2025•0 citations

Identical Quantum Particles as Potential Parts

Philip Goyal

The mathematical rules used to handle systems of identical quantum particles bring into question whether the elementary constituents of matter, such as electrons, have the fundamental characteristics of persistence and reidentifiability that are usually attributed to classical particles. However, despite considerable philosophical debate, the metaphysical profile of these entities remains elusive. Previous debates have taken the mathematical rules, and the language in which these are usually couched, as a starting point. Here, we argue that this methodology is inherently limited, and develop a new conception of identical particles based on a recent mathematical reconstruction of these rules. Using this reconstruction, we demonstrate that the special behaviour of identical particles originates in the confluence of identicality and the active nature of the quantum measurements. We propose that identical particles are appropriately viewed as potential parts of a whole, and show how this leads to striking consequences such as restricted transtemporal identity.

quant-pharXiv:2603.23813•Mar 26, 2026•5 citations

Who or What Is Participating in Reality Formation? Beyond Mind, Matter, and Measurement

Yeshayahu Ben-Yehudah

Who or What Is Participating in Reality Formation? Beyond Mind, Matter, and Measurement Author: Yeshayahu Ben-Yehudah Affiliation: THE BEN-YEHUDAH INSTITUTE Original Publication Date: June 26, 2026 This interdisciplinary scientific and philosophical research paper examines the fundamental relationship between consciousness, observation, quantum measurement, and the formation of physical reality. Building upon the Ben-Yehudah Field Theory, the research investigates whether consciousness may function as an active participant in probabilistic state selection rather than merely emerging as a secondary product of biological processes. Central to this investigation is the Observer Problem in modern physics. Although quantum mechanics provides highly accurate mathematical descriptions of probabilistic physical systems, significant interpretive questions remain concerning measurement, observation, and the transition from quantum possibilities to definite observable outcomes. The research critically examines conventional frameworks of mind, matter, and measurement, questioning whether these approaches adequately explain the nature of the observer. It distinguishes physical measurement from conscious awareness and explores the possibility that the true observer is neither the biological brain, cognitive activity, nor the egoic self, but a deeper observing principle identified as the Subject or Witness. Within the proposed framework, consciousness is examined as a potentially fundamental aspect of existence rather than exclusively as an emergent property of matter. The brain and cognitive systems are considered possible biological interfaces or transducers through which consciousness participates in physical experience. The paper introduces a theoretical participatory sequence describing the proposed relationship between quantum possibility, observation, and manifested reality: Potential Field → Probabilistic States → Observation → State Selection → Manifest Reality This model proposes that reality formation may arise through interactions between consciousness and probabilistic physical systems rather than through purely material or purely subjective processes. The research further examines Cognitive Coherence, attentional stability, and observer alignment as proposed factors influencing the interaction between consciousness and probabilistic states. Within the Ben-Yehudah Field Theory, greater cognitive coherence is hypothesized to correspond with increased efficiency in conscious participation, although these relationships remain theoretical. Drawing upon the contributions of Niels Bohr, John Archibald Wheeler, Eugene Wigner, David Bohm, and contemporary consciousness researchers, the paper integrates quantum foundations, philosophy of mind, ontology, and consciousness studies to reconsider the relationship between the observer and observed reality. The investigation also explores the philosophical implications of distinguishing the experiencing self from the observing witness, suggesting that the nature of consciousness may require examination beyond thought, perception, memory, and individual identity. The proposed participatory model represents a theoretical and philosophical inquiry rather than an experimentally established mechanism of quantum state selection. Its central propositions require further empirical investigation and independent scientific evaluation. By examining the possible relationship between the Observer Problem and the fundamental nature of consciousness, this research advances a broader interdisciplinary inquiry into the architecture of reality and the role of conscious awareness within physical existence. Central Research Question: Who or what is participating in reality formation?

•Jun 26, 2026•0 citations

One Complexity Theorist's View of Quantum Computing

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.

arXiv:quant-ph/0003035•Mar 9, 2000•2 citations

One Complexity Theorist's View of Quantum Computing

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. Dieter van Melkebeek gave many useful comments on an earlier draft of this paper.

Electronic Notes in Theoretical Computer Science•Jan 1, 2000•15 citations
Computational complexity theory (CCT) is usually construed as the mathematical study of the complexity of computational problems. In recent years, research work on unconventional computational models has called into question the purely mathematical nature of CCT, and has revealed potential relations between its subject matter and empirical sciences. In particular, recent debates surrounding quantum computing have raised the possibility of a new computational model, one based on quantum mechanics, which may be exponentially more efficient than any previously known machine. In this paper, I will show how those recent debates suggest an alternative , empirical view of CCT. I will then examine what are the fundamental arguments in the favor of this view, what are its consequences for our conception of CCT as a scientific field, and how further philosophical investigation should proceed.
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.
Quantum computing operates by manipulating the quantum state of a system to solve problems intractable for classical computing. These problems, previously considered limitations of classical algorithms, have solutions through quantum approaches. Therefore, quantum computing suggests that the complexity of such problems lies in the current epistemic state rather than the objective state of the problem. Computational complexity can be classified into objective and epistemic complexity. Some classical problems exhibiting exponential complexity fall into the epistemic category, as their solutions depend on the current state of human knowledge and available tools. Quantum computing suggests that even mathematics isn’t entirely objective, and mathematics, in one sense, is human-made and a kind of technology, which reflects our intention and planning. Computational complexity, therefore, bridges the objective and subjective. Overcoming classical complexity necessitates advancements in scientific theories, algorithms, and quantum technology, all of which rely on the development of human cognitive abilities. Quantum computing is not just a mathematical construct, but also has physical meaning. If it were purely mathematical, classical physics and systems could potentially achieve the same results. What makes the quantum world special is its empirical nature—the physical reality of quantum chips, quantum algorithms, and quantum evolution. Quantum supremacy, or quantum advantage, refers to the potential superiority of quantum computers over classical ones. Controllable quantum systems offer an overwhelming advantage in terms of manipulation and dominance compared to classical systems. Essentially, quantum computing has the potential to significantly outperform classical computing. Many experts, including Shor, have proposed that quantum computing’s power stems from its ability to perform multiple computations simultaneously—a concept often referred to as the Quantum parallelism thesis. Rather, some argue that the true source of quantum computing acceleration lies in the fundamental differences between classical and quantum logic. However, it’s important to note that quantum logic, while providing a new perspective, does not directly address the core principle of quantum parallelism. This dominance stems from quantum physics’ unique properties: Exponential storage capacity, parallel computing inherent to its nature (ontological), and the ability to perform calculations with exponential speedup through quantum algorithms.
The mathematical rules used to handle systems of identical quantum particles bring into question whether the elementary constituents of matter, such as electrons, have the fundamental characteristics of persistence and reidentifiability that are usually attributed to classical particles. However, despite considerable philosophical debate, the metaphysical profile of these entities remains elusive. Previous debates have taken the mathematical rules, and the language in which these are usually couched, as a starting point. Here, we argue that this methodology is inherently limited, and develop a new conception of identical particles based on a recent mathematical reconstruction of these rules. Using this reconstruction, we demonstrate that the special behaviour of identical particles originates in the confluence of identicality and the active nature of the quantum measurements. We propose that identical particles are appropriately viewed as potential parts of a whole, and show how this leads to striking consequences such as restricted transtemporal identity.
Who or What Is Participating in Reality Formation? Beyond Mind, Matter, and Measurement Author: Yeshayahu Ben-Yehudah Affiliation: THE BEN-YEHUDAH INSTITUTE Original Publication Date: June 26, 2026 This interdisciplinary scientific and philosophical research paper examines the fundamental relationship between consciousness, observation, quantum measurement, and the formation of physical reality. Building upon the Ben-Yehudah Field Theory, the research investigates whether consciousness may function as an active participant in probabilistic state selection rather than merely emerging as a secondary product of biological processes. Central to this investigation is the Observer Problem in modern physics. Although quantum mechanics provides highly accurate mathematical descriptions of probabilistic physical systems, significant interpretive questions remain concerning measurement, observation, and the transition from quantum possibilities to definite observable outcomes. The research critically examines conventional frameworks of mind, matter, and measurement, questioning whether these approaches adequately explain the nature of the observer. It distinguishes physical measurement from conscious awareness and explores the possibility that the true observer is neither the biological brain, cognitive activity, nor the egoic self, but a deeper observing principle identified as the Subject or Witness. Within the proposed framework, consciousness is examined as a potentially fundamental aspect of existence rather than exclusively as an emergent property of matter. The brain and cognitive systems are considered possible biological interfaces or transducers through which consciousness participates in physical experience. The paper introduces a theoretical participatory sequence describing the proposed relationship between quantum possibility, observation, and manifested reality: Potential Field → Probabilistic States → Observation → State Selection → Manifest Reality This model proposes that reality formation may arise through interactions between consciousness and probabilistic physical systems rather than through purely material or purely subjective processes. The research further examines Cognitive Coherence, attentional stability, and observer alignment as proposed factors influencing the interaction between consciousness and probabilistic states. Within the Ben-Yehudah Field Theory, greater cognitive coherence is hypothesized to correspond with increased efficiency in conscious participation, although these relationships remain theoretical. Drawing upon the contributions of Niels Bohr, John Archibald Wheeler, Eugene Wigner, David Bohm, and contemporary consciousness researchers, the paper integrates quantum foundations, philosophy of mind, ontology, and consciousness studies to reconsider the relationship between the observer and observed reality. The investigation also explores the philosophical implications of distinguishing the experiencing self from the observing witness, suggesting that the nature of consciousness may require examination beyond thought, perception, memory, and individual identity. The proposed participatory model represents a theoretical and philosophical inquiry rather than an experimentally established mechanism of quantum state selection. Its central propositions require further empirical investigation and independent scientific evaluation. By examining the possible relationship between the Observer Problem and the fundamental nature of consciousness, this research advances a broader interdisciplinary inquiry into the architecture of reality and the role of conscious awareness within physical existence. Central Research Question: Who or what is participating in reality formation?
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.
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. Dieter van Melkebeek gave many useful comments on an earlier draft of this paper.