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

Theoretical and mathematical physics

Algorithmic Complexity

Fabio Benatti

Published Jan 1, 2009• 2 citations
Publisher
DOI
10.1007/978-1-4020-9306-7_4

Related papers

Complexity Theory

Jack D. Hidary

Springer eBooks•Jan 1, 2019•2 citations

Algorithmic Complexity and Entanglement of Quantum States

Caterina E. Mora, Hans J. Briegel

We define the algorithmic complexity of a quantum state relative to a given precision parameter, and give upper bounds for various examples of states. We also establish a connection between the entanglement of a quantum state and its algorithmic complexity.

arXiv:quant-ph/0505200•Physical Review Letters•Nov 9, 2005•59 citations

ALGORITHMIC COMPLEXITY OF QUANTUM STATES

Caterina E. Mora, Hans J. Briegel

We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.

arXiv:quant-ph/0412172•International Journal of Quantum Information•Aug 1, 2006•24 citations

Algorithms and Computation

Masanori Ohya, Igor Vasil'evich Volovich

Theoretical and mathematical physics•Jan 1, 2011•0 citations

Relative Complexity

Leonard Susskind

SpringerBriefs in physics•Jan 1, 2020•0 citations

Quantum Algorithmic Complexity of Three-Qubit Pure States

Martin Lukáč, Aikaterini Mandilara

For pure three-qubit states the classification of entanglement is both non-trivial and well understood. In this work, we study the quantum algorithmic complexity introduced in [1] of three-qubit pure states belonging to the most general class of entanglement. Contrary to expectations we find out that the degree of entanglement of states in this class quantified by the measure of 3-tangle, does not correlate with the quantum algorithmic complexity, defined as the length of the shortest circuit needed to prepare the state. For a given entangled state the evaluation of its quantum complexity is done via a pseudo random evolutionary algorithm. This algorithm allows us not only to determine the complexity of a quantum circuit in terms of the number of required quantum gates, but also to estimate another type of complexity related to the time required to obtain the correct answer.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2016•2 citations
We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.
For pure three-qubit states the classification of entanglement is both non-trivial and well understood. In this work, we study the quantum algorithmic complexity introduced in [1] of three-qubit pure states belonging to the most general class of entanglement. Contrary to expectations we find out that the degree of entanglement of states in this class quantified by the measure of 3-tangle, does not correlate with the quantum algorithmic complexity, defined as the length of the shortest circuit needed to prepare the state. For a given entangled state the evaluation of its quantum complexity is done via a pseudo random evolutionary algorithm. This algorithm allows us not only to determine the complexity of a quantum circuit in terms of the number of required quantum gates, but also to estimate another type of complexity related to the time required to obtain the correct answer.