i-manager Publications

On Kolmogorov Complexity of Unitary Transformations in Quantum Computing

Alexei Kaltchenko*

Wilfrid Laurier University, Waterloo, Ontario, Canada.

Periodicity:July - December'2022
DOI : https://doi.org/10.26634/jmat.11.2.19190

Abstract

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.

Keywords

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

References

[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

On Kolmogorov Complexity of Unitary Transformations in Quantum Computing

Abstract

Keywords

How to Cite this Article?

References

If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Options for accessing this content:

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