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

Quantum Algorithmic Complexities

Fabio Benatti

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

Related papers

Algorithmic complexity of quantum capacity

Samad Khabbazi Oskouei, Stefano Mancini

arXiv:1608.07730•Quantum Information Processing•Mar 2, 2018•6 citations

Quantum Computational Complexity

John Watrous

Springer eBooks•Nov 2, 2011•55 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•61 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•27 citations

Quantum algorithmic primitives

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

Cambridge University Press eBooks•Apr 24, 2025•0 citations

Quantum computational complexity

Daowen Qiu

Elsevier eBooks•Aug 29, 2025•0 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.