Quantum Logic under Semiclassical Limit: Information Loss


  • M.V. Teslyk Taras Shevchenko National University of Kyiv, Ukraine
  • O.M. Teslyk Taras Shevchenko National University of Kyiv, Ukraine
  • L.V. Zadorozhna Taras Shevchenko National University of Kyiv, Ukraine




quantum logic, quantum algorithms, complexity


We consider the quantum computation efficiency from a new perspective. The efficiency is reduced to its classical counterpart by imposing the semiclassical limit. We show that this reduction is caused by the fact that any elementary quantum logic operation (gate) suffers the information loss during the transition to its classical analog. Amount of the information lost is estimated for any gate from the complete set. We demonstrate that the largest loss is obtained for non-commuting gates. This allows us to consider the non-commutativity as the quantum computational speed-up resource. Our method allows us to quantify advantages of a quantum computation as compared to the classical one by the direct analysis of the involved basic logic. The obtained results are illustrated by the application to a quantum discrete Fourier transform and Grover search algorithms.


G. Birkhoff, J. Neumann. The logic of quantum mechanics. Ann. Math. 37, 823 (1936).


N. Papanikolaou. Logic Column 13: Reasoning Formally about Quantum Systems: An Overview. ACM SIGACT News 36, 51 (2005).


M.L.D. Chiara, R. Giuntini. Quantum logics. In: Handbook of Philosophical Logic 6, 129 (Springer, 2002).


M.L.D. Chiara, R. Giuntini, R. Leporini. Quantum computational logics: A survey. Trends in Logic 21, 229 (Springer, 2003).


P.A. Marchetti, R. Rubele. Quantum logic and noncommutative geometry. Int. J. Theor. Phys. 46, 49 (2007).


D. Lehmann, K. Engesser, D.M. Gabbay. Algebras of measurements: The logical structure of quantum mechanics. Int. J. Theor. Phys. 45, 698 (2006).


O. Brunet. A rule-based logic for quantum information. https://arxiv.org/pdf/cs/0504018.pdf.

K. Svozil. Contexts in quantum, classical and partition logic. In: Handbook of Quantum Logic and Quantum Structures (Elsevier, 2008) [ISBN: 9780080931661].


G. Domenech, H. Freytes. Contextual logic for quantum systems. J. Math. Phys. 46, 012102 (2005).


S. Abramsky, R. Duncan. A categorical quantum logic. Mathematical Structures in Computer Science 16, 469 (2006).


S. Abramsky, B. Coecke. A categorical semantics of quantum protocols. In: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, Turku, Finland, 415 (2004).


J. Neumann. Mathematische Grundlagen der Quantenmechanik (Springer, 1933), p. 262.

G. Battilotti, P. Zizzi. Logical interpretation of a reversible measurement in quantum computing. https://arxiv.org/pdf/quant-ph/0408068.pdf.

M.V. Nest, H.J. Briegel. Measurement-based quantum computation and undecidable logic. Found. Phys. 38, 448 (2008).


M. Ying. A theory of computation based on quantum logic (I). Theor. Comp. Science. 344, 134 (2005).


C. Garola. Interpreting quantum logic as a pragmatic structure. Int. J. Theor. Phys. 56, 3770 (2017).


D. Lehmann. A presentation of quantum logic based on an and then connective. J. Logic and Computation 18, 59 (2008).


A. Tonder. A lambda calculus for quantum computation. SIAM J. Comput. 33, 1109 (2004).


C.J. Isham. Quantum logic and decohering histories. https://arxiv.org/pdf/quant-ph/9506028.pdf.

P.A. Zizzi. Basic logic and quantum entanglement. J. Phys.: Conf. Ser. 67, 012045 (2007).


G. Domenech, H. Freytes, C. Ronde. Scopes and limits of modality in quantum mechanics. Annalen der Physik 518, 853 (2006).


G. Domenech, H. Freytes, C. de Ronde. A topological study of contextuality and modality in quantum mechanics. Int. J. Theor. Phys. 47, 168 (2008).


P. Vitanyi. Three approaches to the quantitative definition of information in an individual pure quantum state. In: Proceedings 15th Annual IEEE Conference on Computational Complexity (2000), p. 263.

A. Berthiaume, W. van Dam, S. Laplante. Quantum Kolmogorov complexity. J. Comp. and Systems Sciences 63, 201 (2001).


C.E. Mora, H.J. Briegel. Algorithmic complexity and entanglement of quantum states. Phys. Rev. Lett. 95, 200503 (2005).


C.E. Mora, H.J. Briegel, B Kraus. Quantum Kolmogorov complexity and its applications. Int. J. Quant. Inf. 5, 729 (2007).


P. Ga'cs. Quantum algorithmic entropy. Phys. A: Math. Gen. 34, 6859 (2001).


P. D. Bruza, D. Widdows, J. Woods. A quantum logic of down below. In: Handbook of Quantum Logic and Quantum Structures: Quantum Logic. Edited by K. Engesser, D.M. Gabbay, D. Lehmann (Elsevier Science, 2009) [ISBN: 9780080931661].


C. Garola. Physical propositions and quantum languages. Int. J. Theor. Phys. 47, 90 (2008).


G. Domenech, F. Holik, C. Massri. A quantum logical and geometrical approach to the study of improper mixtures. J. Math. Phys. 51, 052108 (2010).


F. Holik, C. Massri, N. Ciancaglini. Convex quantum logic. Int. J. Theor. Phys. 51, 1600 (2012).


E.T.G. Alvarez. The logic behind Feynman's paths. Int. J. Modern Phys. D 20, 893 (2011).


J. Benadives. Sheaf logic, quantum set theory and the interpretation of quantum mechanics. https://arxiv.org/pdf/1111.2704.pdf.

D. Ellerman. The objective indefiniteness interpretation of quantum mechanics. https://arxiv.org/pdf/1210.7659.pdf.

G.L. Litvinov, V.P. Maslov, G.B. Shpiz. Idempotent (asymptotic) mathematics and the representation theory. In: Asymptotic Combinatorics with Application to Mathematical Physics. NATO Science Series. Edited by V. Malyshev, A. Vershi, 77 (Springer, 2002), pp. 267-278.


T. Yajima, K. Nakajima, N. Asano. Max-plus algebra for complex variables and its applications to discrete fourier transformation and partial difference equations. J. Phys. Soc. Japan 75, 064001 (2006).


A.Yu. Kitaev, A.H. Shen, M.N. Vyalyi. Classical and Quantum Computation (American Mathematical Society, 2002) [ISBN: 9780821832295].


M.A. Nielsen, I.L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition (Cambridge University Press, 2010) [ISBN: 9780511976667].

V.M. Kendon, W.J. Munro. Entanglement and its role in shor's algorithm. Quantum Info. Comput. 6, 630 (2006).


A. Nicolaidis. Relational quantum mechanics. https://arxiv.org/pdf/1211.2706.pdf.




How to Cite

Teslyk, M., Teslyk, O., & Zadorozhna, L. (2022). Quantum Logic under Semiclassical Limit: Information Loss. Ukrainian Journal of Physics, 67(5), 352. https://doi.org/10.15407/ujpe67.5.352



General physics