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

Comptes Rendus Mathématique

New barriers in complexity theory: On the solvability complexity index and the towers of algorithms

Jonathan Ben‐Artzi, Anders C. Hansen, Olavi Nevanlinna, Markus Seidel

Published Oct 1, 2015• 31 citations
Publisher

Abstract

We report on new barriers in the theory of computations. These barriers show that the standard theory of computations and complexity theory is insufficient for many core problems in computational theory. Thus we are in need for a new extended complexity theory. The new theory settles the long-standing computational spectral problem and also provides new fundamental algorithms for quantum mechanics.

DOI
10.1016/j.crma.2015.08.002

Related papers

Computational Complexity Analysis of Quantum Algorithms using Category Theory

Jincheng Zhang

Traditional methods for analyzing the computational complexity of algorithms, predominantly rooted in classical computer models, struggle to accurately characterize the potential advantages offered by quantum computation. This work proposes a novel approach utilizing category theory to provide a more fundamental and abstract framework for assessing the complexity of quantum algorithms. Instead of focusing on the specifics of quantum hardware, we examine the underlying categorical structures that define the computational processes inherent in these algorithms. This allows us to identify and analyze complexity properties that are independent of the physical implementation. We define key concepts like quantum states as objects and quantum gates as morphisms, establishing a formal connection between quantum computation and category theory. This framework facilitates a more rigorous and generalized understanding of quantum complexity, potentially revealing new insights and providing a basis for comparing different quantum algorithms. The core claim is that traditional complexity analysis is inadequate, and the mechanism is the application of category theory for a more abstract and generalized framework.

•Sep 7, 2026•0 citations

Algorithmic Quantum Complexity Theory

Jincheng Zhang

This paper investigates the computational complexity of quantum algorithms, proposing a new framework based on quantum superposition and entanglement. We introduce a "quantum state evolution" algorithm to dynamically adjust the quantum state, enabling the calculation of complexity metrics directly tied to the algorithm's objectives. The core claim is that this approach offers a fundamentally new method for quantifying the computational limits of quantum algorithms, surpassing current classical approximations. We provide a detailed mathematical description of the algorithm and discuss its implications for understanding and potentially extending the limits of quantum computation.

•Sep 5, 2026•0 citations

Computational Power of the Quantum Turing Automata

Sina Jafarpour, Mohammad Ghodsi, Keyvan Sadri +1 more

Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future

•Apr 1, 2007•0 citations

Quantum Complexity Theory for Algorithm Design

Jincheng Zhang

Quantum Complexity Theory (QCT) offers a novel framework for algorithm design, predicated on the principle that certain computational problems exhibit inherent quantum complexity. This paper explores the application of QCT to identify problems with a significantly enhanced computational advantage when tackled using quantum algorithms. We argue that by leveraging the unique properties of quantum mechanics, we can potentially develop algorithms that outperform their classical counterparts in solving complex problems, demonstrating a paradigm shift in algorithmic design. This work lays the foundation for a new area of research with significant implications for the future of computational science and engineering.

•Sep 4, 2026•0 citations

Quantum Topology Adaptive Algorithm for Complex Problem Solving

Jincheng Zhang

Quantum topology is a fascinating area of physics with profound implications for computation and information theory. The study of topological phases, which exhibit remarkable robustness and long-range connectivity, has inspired the development of novel algorithms. This paper introduces a new quantum algorithm, termed "Adaptive Quantum Topology Algorithm" (AQT), designed to address complex problems by dynamically adjusting quantum states. We propose a mechanism that leverages the unique properties of quantum topology to enhance problem-solving capabilities, offering a significant departure from traditional algorithmic approaches. This work explores the potential of AQT to tackle challenging scenarios where precise parameter tuning is insufficient. The paper details the core concepts, the proposed algorithm's architecture, and preliminary experimental results demonstrating its efficacy. The focus is on demonstrating the algorithm's ability to adapt to complex problem structures and achieve superior performance compared to conventional methods.

•Aug 31, 2026•0 citations

Computational complexity for physicists

Stephan Mertens

The theory of computational complexity has some interesting links to physics, in particular to quantum computing and statistical mechanics. The article contains an informal introduction to this theory and its links to physics.

Computing in Science & Engineering•Jan 1, 2002•60 citations
We report on new barriers in the theory of computations. These barriers show that the standard theory of computations and complexity theory is insufficient for many core problems in computational theory. Thus we are in need for a new extended complexity theory. The new theory settles the long-standing computational spectral problem and also provides new fundamental algorithms for quantum mechanics.
Traditional methods for analyzing the computational complexity of algorithms, predominantly rooted in classical computer models, struggle to accurately characterize the potential advantages offered by quantum computation. This work proposes a novel approach utilizing category theory to provide a more fundamental and abstract framework for assessing the complexity of quantum algorithms. Instead of focusing on the specifics of quantum hardware, we examine the underlying categorical structures that define the computational processes inherent in these algorithms. This allows us to identify and analyze complexity properties that are independent of the physical implementation. We define key concepts like quantum states as objects and quantum gates as morphisms, establishing a formal connection between quantum computation and category theory. This framework facilitates a more rigorous and generalized understanding of quantum complexity, potentially revealing new insights and providing a basis for comparing different quantum algorithms. The core claim is that traditional complexity analysis is inadequate, and the mechanism is the application of category theory for a more abstract and generalized framework.
This paper investigates the computational complexity of quantum algorithms, proposing a new framework based on quantum superposition and entanglement. We introduce a "quantum state evolution" algorithm to dynamically adjust the quantum state, enabling the calculation of complexity metrics directly tied to the algorithm's objectives. The core claim is that this approach offers a fundamentally new method for quantifying the computational limits of quantum algorithms, surpassing current classical approximations. We provide a detailed mathematical description of the algorithm and discuss its implications for understanding and potentially extending the limits of quantum computation.
Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future
Quantum Complexity Theory (QCT) offers a novel framework for algorithm design, predicated on the principle that certain computational problems exhibit inherent quantum complexity. This paper explores the application of QCT to identify problems with a significantly enhanced computational advantage when tackled using quantum algorithms. We argue that by leveraging the unique properties of quantum mechanics, we can potentially develop algorithms that outperform their classical counterparts in solving complex problems, demonstrating a paradigm shift in algorithmic design. This work lays the foundation for a new area of research with significant implications for the future of computational science and engineering.
Quantum topology is a fascinating area of physics with profound implications for computation and information theory. The study of topological phases, which exhibit remarkable robustness and long-range connectivity, has inspired the development of novel algorithms. This paper introduces a new quantum algorithm, termed "Adaptive Quantum Topology Algorithm" (AQT), designed to address complex problems by dynamically adjusting quantum states. We propose a mechanism that leverages the unique properties of quantum topology to enhance problem-solving capabilities, offering a significant departure from traditional algorithmic approaches. This work explores the potential of AQT to tackle challenging scenarios where precise parameter tuning is insufficient. The paper details the core concepts, the proposed algorithm's architecture, and preliminary experimental results demonstrating its efficacy. The focus is on demonstrating the algorithm's ability to adapt to complex problem structures and achieve superior performance compared to conventional methods.