On Kolmogorov Complexity of Unitary Transformations in Quantum Computing

A. Kaltchenko*
Wilfrid Laurier University, Waterloo, Ontario, Canada.
Periodicity:July - December'2022
DOI : https://doi.org/10.26634/jmat.11.2.19190


We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to unnormalized density operators, which are subsequently "purified" into unnormalized vectors in Hilbert space. We discuss the optimality of our notion of Kolmogorov complexity in a broad sense.


Quantum Information Theory, Information Theory, Quantum, Kolmogorov Complexity, Quantum Computing, Quantum Information, Unitary, Quantum State.

How to Cite this Article?

Kaltchenko, A. (2022). On Kolmogorov Complexity of Unitary Transformations in Quantum Computing. i-manager’s Journal on Mathematics, 11(2), 1-7. https://doi.org/10.26634/jmat.11.2.19190


[1]. Adleman, L. M., Demarrais, J., & Huang, M. D. A. (1997). Quantum computability. SIAM Journal on Computing, 26(5), 1524-1540. https://doi.org/10.1137/S0097539795293639
[2]. Benatti, F., Krüger, T., Müller, M., Siegmund-Schultze, R., & Szkoła, A. (2006). Entropy and quantum Kolmogorov complexity: A quantum Brudno's theorem. Communications in Mathematical Physics, 265(2), 437-461. https://doi.org/10.1007/s00220-006-0027-z
[3]. Berthiaume, A., Van Dam, W., & Laplante, S. (2001). Quantum kolmogorov complexity. Journal of Computer and System Sciences, 63(2), 201-221. https://doi.org/10.1006/jcss.2001.1765
[4]. Cover, T. & Thomas, J. (2006). Elements of Information Theory. John Wiley & Sons.
[5]. Deutsch, D. (1985). Quantum theory, the church–turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A Mathematical and Physical Sciences, 400(1818), 97-117. https://doi.org/10.1098/rspa.1985.0070
[6]. Gács, P. (2001). Quantum algorithmic entropy. Journal of Physics A: Mathematical and General, 34(35). https://doi.org/10.1088/0305-4470/34/35/312
[7]. Li, M., & Vitányi, P. (1993). An Introduction to Kolmogorov Complexity and its Applications. Springer, New York.
[8]. Mora, C. E., & Briegel, H. J. (2005). Algorithmic complexity and entanglement of quantum states. Physical Review Letters, 95(20), 200503. https://doi.org/10.1103/PhysRevLett.95.200503
[9]. Mora, C. E., Briegel, H. J., & Kraus, B. (2007). Quantum Kolmogorov complexity and its applications. International Journal of Quantum Information, 5(05), 729-750. https://doi.org/10.1142/S0219749907003171
[10]. Muller, J. (2006). Elementary Functions: Algorithms and Implementation. Birkhuser.
[11]. Nielsen, M. & Chuang, I. (2000). Quantum Computation and Quantum Information. Cambridge University Press.
[12]. Vitányi, P. M. (2001). Quantum Kolmogorov complexity based on classical descriptions. IEEE Transactions on Information Theory, 47(6), 2464-2479. https://doi.org/10.1109/18.945258
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
Pdf 35 35 200 20
Online 35 35 200 15
Pdf & Online 35 35 400 25

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.