The Importance of the Algorithmic Information Theory to Construct a Possible Example Where NP#P

2006/11/02 by Rubens Viana Ramos, Ramos, Rubens Viana
Computer Science · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.quant-ph/0611027

openalex publication_date 2006/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this short communication, it is shown a simple problem using quantum circuits for which the algorithmic information theory guarantee that the minimal length of the algorithm able to solve it grows exponentially with the number of qubits.

Related

• The Importance of the Algorithmic Information Theory to Construct a Possible Example Where NP # P - II: An Irreducible Sentence
• An explanation of the quantum speed up
• Quantum algorithmic information theory
• The Relation between Disentangled States and Algorithmic Information Theory
• Algorithmic Information Theoretic Issues in Quantum Mechanics