Quantum Logic under Semiclassical Limit: Information Loss
DOI:
https://doi.org/10.15407/ujpe67.5.352Keywords:
quantum logic, quantum algorithms, complexityAbstract
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.
References
G. Birkhoff, J. Neumann. The logic of quantum mechanics. Ann. Math. 37, 823 (1936).
https://doi.org/10.2307/1968621
N. Papanikolaou. Logic Column 13: Reasoning Formally about Quantum Systems: An Overview. ACM SIGACT News 36, 51 (2005).
https://doi.org/10.1145/1086649.1086668
M.L.D. Chiara, R. Giuntini. Quantum logics. In: Handbook of Philosophical Logic 6, 129 (Springer, 2002).
https://doi.org/10.1007/978-94-017-0460-1_2
M.L.D. Chiara, R. Giuntini, R. Leporini. Quantum computational logics: A survey. Trends in Logic 21, 229 (Springer, 2003).
https://doi.org/10.1007/978-94-017-3598-8_9
P.A. Marchetti, R. Rubele. Quantum logic and noncommutative geometry. Int. J. Theor. Phys. 46, 49 (2007).
https://doi.org/10.1007/s10773-006-9193-1
D. Lehmann, K. Engesser, D.M. Gabbay. Algebras of measurements: The logical structure of quantum mechanics. Int. J. Theor. Phys. 45, 698 (2006).
https://doi.org/10.1007/s10773-006-9062-y
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].
https://doi.org/10.1016/B978-0-444-52869-8.50015-3
G. Domenech, H. Freytes. Contextual logic for quantum systems. J. Math. Phys. 46, 012102 (2005).
https://doi.org/10.1063/1.1819525
S. Abramsky, R. Duncan. A categorical quantum logic. Mathematical Structures in Computer Science 16, 469 (2006).
https://doi.org/10.1017/S0960129506005275
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).
https://doi.org/10.1109/LICS.2004.1319636
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).
https://doi.org/10.1007/s10701-008-9212-6
M. Ying. A theory of computation based on quantum logic (I). Theor. Comp. Science. 344, 134 (2005).
https://doi.org/10.1016/j.tcs.2005.04.001
C. Garola. Interpreting quantum logic as a pragmatic structure. Int. J. Theor. Phys. 56, 3770 (2017).
https://doi.org/10.1007/s10773-017-3309-7
D. Lehmann. A presentation of quantum logic based on an and then connective. J. Logic and Computation 18, 59 (2008).
https://doi.org/10.1093/logcom/exm054
A. Tonder. A lambda calculus for quantum computation. SIAM J. Comput. 33, 1109 (2004).
https://doi.org/10.1137/S0097539703432165
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).
https://doi.org/10.1088/1742-6596/67/1/012045
G. Domenech, H. Freytes, C. Ronde. Scopes and limits of modality in quantum mechanics. Annalen der Physik 518, 853 (2006).
https://doi.org/10.1002/andp.20065181201
G. Domenech, H. Freytes, C. de Ronde. A topological study of contextuality and modality in quantum mechanics. Int. J. Theor. Phys. 47, 168 (2008).
https://doi.org/10.1007/s10773-007-9595-8
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).
https://doi.org/10.1006/jcss.2001.1765
C.E. Mora, H.J. Briegel. Algorithmic complexity and entanglement of quantum states. Phys. Rev. Lett. 95, 200503 (2005).
https://doi.org/10.1103/PhysRevLett.95.200503
C.E. Mora, H.J. Briegel, B Kraus. Quantum Kolmogorov complexity and its applications. Int. J. Quant. Inf. 5, 729 (2007).
https://doi.org/10.1142/S0219749907003171
P. Ga'cs. Quantum algorithmic entropy. Phys. A: Math. Gen. 34, 6859 (2001).
https://doi.org/10.1088/0305-4470/34/35/312
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].
https://doi.org/10.1016/B978-0-444-52869-8.50017-7
C. Garola. Physical propositions and quantum languages. Int. J. Theor. Phys. 47, 90 (2008).
https://doi.org/10.1007/s10773-007-9372-8
G. Domenech, F. Holik, C. Massri. A quantum logical and geometrical approach to the study of improper mixtures. J. Math. Phys. 51, 052108 (2010).
https://doi.org/10.1063/1.3429619
F. Holik, C. Massri, N. Ciancaglini. Convex quantum logic. Int. J. Theor. Phys. 51, 1600 (2012).
https://doi.org/10.1007/s10773-011-1037-y
E.T.G. Alvarez. The logic behind Feynman's paths. Int. J. Modern Phys. D 20, 893 (2011).
https://doi.org/10.1142/S0218271811018998
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.
https://doi.org/10.1007/978-94-010-0575-3_13
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).
https://doi.org/10.1143/JPSJ.75.064001
A.Yu. Kitaev, A.H. Shen, M.N. Vyalyi. Classical and Quantum Computation (American Mathematical Society, 2002) [ISBN: 9780821832295].
https://doi.org/10.1090/gsm/047
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).
https://doi.org/10.26421/QIC6.7-6
A. Nicolaidis. Relational quantum mechanics. https://arxiv.org/pdf/1211.2706.pdf.
Downloads
Published
How to Cite
Issue
Section
License
Copyright Agreement
License to Publish the Paper
Kyiv, Ukraine
The corresponding author and the co-authors (hereon referred to as the Author(s)) of the paper being submitted to the Ukrainian Journal of Physics (hereon referred to as the Paper) from one side and the Bogolyubov Institute for Theoretical Physics, National Academy of Sciences of Ukraine, represented by its Director (hereon referred to as the Publisher) from the other side have come to the following Agreement:
1. Subject of the Agreement.
The Author(s) grant(s) the Publisher the free non-exclusive right to use the Paper (of scientific, technical, or any other content) according to the terms and conditions defined by this Agreement.
2. The ways of using the Paper.
2.1. The Author(s) grant(s) the Publisher the right to use the Paper as follows.
2.1.1. To publish the Paper in the Ukrainian Journal of Physics (hereon referred to as the Journal) in original language and translated into English (the copy of the Paper approved by the Author(s) and the Publisher and accepted for publication is a constitutive part of this License Agreement).
2.1.2. To edit, adapt, and correct the Paper by approval of the Author(s).
2.1.3. To translate the Paper in the case when the Paper is written in a language different from that adopted in the Journal.
2.2. If the Author(s) has(ve) an intent to use the Paper in any other way, e.g., to publish the translated version of the Paper (except for the case defined by Section 2.1.3 of this Agreement), to post the full Paper or any its part on the web, to publish the Paper in any other editions, to include the Paper or any its part in other collections, anthologies, encyclopaedias, etc., the Author(s) should get a written permission from the Publisher.
3. License territory.
The Author(s) grant(s) the Publisher the right to use the Paper as regulated by sections 2.1.1–2.1.3 of this Agreement on the territory of Ukraine and to distribute the Paper as indispensable part of the Journal on the territory of Ukraine and other countries by means of subscription, sales, and free transfer to a third party.
4. Duration.
4.1. This Agreement is valid starting from the date of signature and acts for the entire period of the existence of the Journal.
5. Loyalty.
5.1. The Author(s) warrant(s) the Publisher that:
– he/she is the true author (co-author) of the Paper;
– copyright on the Paper was not transferred to any other party;
– the Paper has never been published before and will not be published in any other media before it is published by the Publisher (see also section 2.2);
– the Author(s) do(es) not violate any intellectual property right of other parties. If the Paper includes some materials of other parties, except for citations whose length is regulated by the scientific, informational, or critical character of the Paper, the use of such materials is in compliance with the regulations of the international law and the law of Ukraine.
6. Requisites and signatures of the Parties.
Publisher: Bogolyubov Institute for Theoretical Physics, National Academy of Sciences of Ukraine.
Address: Ukraine, Kyiv, Metrolohichna Str. 14-b.
Author: Electronic signature on behalf and with endorsement of all co-authors.
.png){kind=small}
