Квантова логіка у квазікласичному наближенні: втрата інформації
DOI:
https://doi.org/10.15407/ujpe67.5.352Ключові слова:
квантова логiка, квантовi алгоритми, складнiстьАнотація
Ми розглядаємо квантову обчислювальну ефективнiсть з нової точки зору. Дана ефективнiсть зводиться до класичної за допомогою квазiкласичного наближення. Ми показуємо, що дане спрощення викликане тим, що кожна елементарна квантова логiчна операцiя (вентиль) втрачає iнформацiю пiд час переходу до свого класичного аналогу. Проведено оцiнку втрати iнформацiї для всiх вентилiв, що утворюють повний набiр. Ми показуємо, що найбiльше iнформацiї втрачається для некомутуючих вентилiв. Це дозволяє розглядати некомутативнiсть як джерело квантового прискорення обчислень. Наш метод дозволяє кiлькiсно оцiнити переваги квантових обчислень порiвняно з класичними за допомогою прямого аналiзу використовуваної логiки. Отриманi результати проiлюстровано на прикладi квантового дискретного перетворення Фур’є та пошукового алгоритму Гровера.
Посилання
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
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ліцензійний Договір
на використання Твору
м. Київ, Україна
Відповідальний автор та співавтори (надалі іменовані як Автор(и)) статті, яку він (вони) подають до Українського фізичного журналу, (надалі іменована як Твір) з одного боку та Інститут теоретичної фізики імені М.М. Боголюбова НАН України в особі директора (надалі – Видавець) з іншого боку уклали даний Договір про таке:
1. Предмет договору.
Автор(и) надає(ють) Видавцю безоплатно невиключні права на використання Твору (наукового, технічного або іншого характеру) на умовах, визначених цим Договором.
2. Способи використання Твору.
2.1. Автор(и) надає(ють) Видавцю право на використання Твору таким чином:
2.1.1. Використовувати Твір шляхом його видання в Українському фізичному журналі (далі – Видання) мовою оригіналу та в перекладі на англійську (погоджений Автором(ами) і Видавцем примірник Твору, прийнятого до друку, є невід’ємною частиною Ліцензійного договору).
2.1.2. Переробляти, адаптувати або іншим чином змінювати Твір за погодженням з Автором(ами).
2.1.3. Перекладати Твір у випадку, коли Твір викладений іншою мовою, ніж мова, якою передбачена публікація у Виданні.
2.2. Якщо Автор(и) виявить(лять) бажання використовувати Твір в інший спосіб, як то публікувати перекладену версію Твору (окрім випадку, зазначеного в п. 2.1.3 цього Договору); розміщувати повністю або частково в мережі Інтернет; публікувати Твір в інших, у тому числі іноземних, виданнях; включати Твір як складову частину інших збірників, антологій, енциклопедій тощо, то Автор(и) мають отримати на це письмовий дозвіл від Видавця.
3. Територія використання.
Автор(и) надає(ють) Видавцю право на використання Твору способами, зазначеними у п.п. 2.1.1–2.1.3 цього Договору, на території України, а також право на розповсюдження Твору як невід’ємної складової частини Видання на території України та інших країн шляхом передплати, продажу та безоплатної передачі третій стороні.
4. Строк, на який надаються права.
4.1. Договір є чинним з дати підписання та діє протягом усього часу функціонування Видання.
5. Застереження.
5.1. Автор(и) заявляє(ють), що:
– він/вона є автором (співавтором) Твору;
– авторські права на даний Твір не передані іншій стороні;
– даний Твір не був раніше опублікований і не буде опублікований у будь-якому іншому виданні до публікації його Видавцем (див. також п. 2.2);
– Автор(и) не порушив(ли) права інтелектуальної власності інших осіб. Якщо у Творі наведені матеріали інших осіб за виключенням випадків цитування в обсязі, виправданому науковим, інформаційним або критичним характером Твору, використання таких матеріалів здійснене Автором(ами) з дотриманням норм міжнародного законодавства і законодавства України.
6. Реквізити і підписи сторін.
Видавець: Інститут теоретичної фізики імені М.М. Боголюбова НАН України.
Адреса: м. Київ, вул. Метрологічна 14-б.
Автор: Електронний підпис від імені та за погодження всіх співавторів.
.png){kind=small}
