Three approaches to the quantitative definition of information in an individual pure quantum state

In analogy of classical Kolmogorov complexity we develop a theory of the algorithmic information in bits contained in any one of continuously many pure quantum states: quantum Kolmogorov complexity. Classical Kolmogorov complexity coincides with the new quantum Kolmogorov complexity restricted to the classical domain. Quantum Kolmogorov complexity is upper bounded and can be effectively approximated from above. With high probability a quantum object is incompressible. There are two alternative approaches possible: to define the complexity as the length of the shortest qubit program that effectively describes the object, and to use classical descriptions with computable real parameters.

• Publication year

  1999

• Venue

  Proceedings 15th Annual IEEE Conference on Computational Complexity

• Publication date

  1999-07-09

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1109/CCC.2000.856757arXiv quant-ph/9907035
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Quantum Computability

  1997cited by this paper
• Quantum theory: Concepts and methods

  1997influential reference
• The Boltzmann entropy and randomness tests

  1994cited by this paper
• An Introduction to Kolmogorov Complexity and Its Applications

  1993influential reference
• Quantum complexity theory

  1993cited by this paper

• DeQompile: quantum circuit decompilation using genetic programming for explainable quantum architecture search

  2025cites this paper
• A Meta-Complexity Characterization of Quantum Cryptography

  2024cites this paper
• Research on Ocular Artifacts Removal from Single-Channel Electroencephalogram Signals in Obstructive Sleep Apnea Patients Based on Support Vector Machine, Improved Variational Mode Decomposition, and Second-Order Blind Identification

  2024cites this paper
• Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines

  2023cites this paper
• A Quantum EL Theorem

  2023cites this paper
• A refinement of the argument of local realism versus quantum mechanics by algorithmic randomness

  2023cites this paper
• Quantum Algorithmic Information Theory

  2021cites this paper
• Algorithmic Probability-Guided Machine Learning on Non-Differentiable Spaces

  2021influential citation
• On the Algorithmic Content of Quantum Measurements

  2021cites this paper
• pat‐geom: A software package for the analysis of animal patterns

  2019cites this paper
• Complexity as L2-difficulty: Implications for syntactic change

  2019cites this paper
• J un 2 01 9 Quantum Coding Theorems

  2019cites this paper
• Algorithmic No-Cloning Theorem

  2018cites this paper
• The Impact of Video Length on Learning in a Middle-Level Flipped Science Setting: Implications for Diversity Inclusion

  2018cites this paper
• Bivariate Causal Discovery and Its Applications to Gene Expression and Imaging Data Analysis

  2018cites this paper
• EEG Multiscale Complexity in Schizophrenia During Picture Naming

  2018cites this paper
• Structural coding versus free-energy predictive coding

  2015cites this paper
• Static behaviour of induced seismicity

  2015cites this paper
• On Quantum Noncompression

  2015cites this paper
• A new statistical framework to assess structural alignment quality using information compression

  2014cites this paper
• All Sampling Methods Produce Outliers

  2013cites this paper
• Guided Self-Organization of Input-Driven Recurrent Neural Networks

  2013cites this paper
• Quantum Logic under Semiclassical Limit: Information Loss

  2013cites this paper
• On the role of simplicity in science

  2013cites this paper
• Quantum Logic Dequantization: Information Loss

  2013cites this paper
• Beyond crystals: the dialectic of materials and information

  2012cites this paper
• Fundamental principles of cognitive biology

  2012cites this paper
• Classification of the automorphisms of the noncommutative torus among the (chaotic and non-chaotic) shallow ones and the non-chaotic complex ones

  2011cites this paper
• Alan Turing and the origins of complexity

  2011cites this paper
• On Quantum Effects in a Theory of Biological Evolution

  2011cites this paper
• Kolmogorov Complexity

  2009cites this paper
• Survey of Kolmogorov Complexity and its Applications

  2009cites this paper
• Law of Excluded Quantum Gambling Strategies

  2008cites this paper
• Econophysics and Economic Complexity

  2008influential citation
• GENETIC PROGRAMMING THEORY AND PRACTICE

  2007influential citation
• QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS

  2006influential citation
• Towards a Coherent Theory of Physics and Mathematics: The Theory–Experiment Connection

  2004cites this paper
• Complexity of Graph State Preparation

  2004cites this paper
• Physical Complexity of Classical and Quantum Objects and Their Dynamical Evolution From an Information-Theoretic Viewpoint

  2004cites this paper
• ALGORITHMIC COMPLEXITY OF QUANTUM STATES

  2004cites this paper
• On quantum computation theory

  2002influential citation
• Dynamically Multivalued, Not Unitary or Stochastic, Operation of Real Quantum, Classical and Hybrid Micro-Machines

  2002cites this paper
• Towards a Coherent Theory of Physics and Mathematics

  2002cites this paper
• Model Selection and the Principle of Minimum Description Length

  2001influential citation
• Quantum Kolmogorov complexity based on classical descriptions

  2001cites this paper
• Law of Excluded Quantum Gambling Strategies

  2001cites this paper
• The Incompressibility Method

  2000cites this paper
• On quantum coding for ensembles of mixed states

  2000cites this paper
• 1 SYMMETRY , LEVELS AND ENTRAINMENT

  2000cites this paper
• Quantum algorithmic entropy

  2000cites this paper
• Bibliographic guide to the foundations of quantum mechanics and quantum information

  2000cites this paper
• Quantum Kolmogorov complexity

  2000influential citation