Булеві квантові логічні операції
The paper proposes generalization of Boolean logic operations intended for quantum computing. It is shown that the basic set of Boolean one-qubit operations contains 6 ones and has 2 variants of sets of 4 operations. 9 unary quantum operations are proposed in addition to 7 classical ones (equivalenc...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/272 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479641030131712 |
|---|---|
| author | Budnyk, Mykola |
| author_facet | Budnyk, Mykola |
| author_institution_txt_mv | [
{
"author": "Mykola Budnyk",
"institution": "д. т. н., г. н. с., Інститут кібернетики ім. В.М. Глушкова НАН України, просп. Академіка Глушкова, 40, 03680, Київ; д. т. н., професор, ННІ високих технологій, Київський національний університет імені Тараса Шевченка, просп. Академіка Глушкова, 4Г, 03680; д. т. н., професор, кафедра комп’ютерних наук, Сумський державний університет, вул. Римського-Корсакова, 2, 40007, Суми"
}
] |
| author_sort | Budnyk, Mykola |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | The paper proposes generalization of Boolean logic operations intended for quantum computing. It is shown that the basic set of Boolean one-qubit operations contains 6 ones and has 2 variants of sets of 4 operations. 9 unary quantum operations are proposed in addition to 7 classical ones (equivalence, OR, XOR, AND, NOR, NAND, implication). As a result, a complete set of 16 one-qubit operations was obtained, which provides 164 = 65 thousand 536 binary (two-qubit) logical operations that corresponds to the number of base states of a 16-qubit quantum processor. Large  number of operations will allow increase performance of computing in digital simulators of quantum processors from the viewpoint of computing parallelism and reducing the program cod. |
| first_indexed | 2026-06-09T01:09:30Z |
| format | Article |
| fulltext |
38
doi.org/10.15407/fmmit2023.36.038
Булеві квантові логічні операції
Микола Будник1,2,3
1 д. т. н., г. н. с., Інститут кібернетики ім. В.М. Глушкова НАН України, просп. Академіка Глушкова, 40, 03680,
Київ, e-mail: budnykmykola@gmail.com
2 д. т. н., професор, ННІ високих технологій, Київський національний університет імені Тараса Шевченка,
просп. Академіка Глушкова, 4Г, 03680, Київ, e-mail: budnykmykola@gmail.com
3 д. т. н., доцент, кафедра комп’ютерних наук, Сумський державний університет, вул. Римського-Корсакова, 2,
40007, Суми, e-mail: budnykmykola@gmail.com
У роботі запропоновано узагальнення булевих операцій для квантових обчислень. Показано,
що базовий набір булевих однокубітних операцій містить 6 операцій та має 2 варіанти
наборів по 4 операції. Запропоновано 9 квантових операцій додатково до 7-ми класичних
(еквіваленція, диз’юнкція, кон’юнкція, імплікація, заперечення диз’юнкції, заперечення
кон’юнкції, виключна диз’юнкція). В результаті отримано повний набір 16 однокубітних
операцій, які забезпечують 164 = 65 тисяч 536 бінарних (двокубітних) логічних операцій,
що відповідає кількості базових станів 16-кубітного квантового процесора. Велика
кількість операцій дозволить підвищити продуктивність квантових обчислень в цифрових
симуляторах квантових процесорів з точки зору паралельності обчислень та скорочення
програмного коду.
Ключові слова: квантові обчислення, логічні операції, булева алгебра
Вступ. На сьогодні у галузі зв’язку та високопродуктивних обчислень активними
темпами розробляють та активно впроваджують квантові технології. Багато
дослідників вважають, що у найближчому майбутньому квантові технології
забезпечать ключові досягнення у багатьох сферах діяльності людини, які
потребують надшвидке вирішення обчислювальних задач великої складності,
зокрема в криптографії та моделюванні надскладних процесів [1].
Перспективи в галузі високопродуктивних обчислень ґрунтуються на
застосуванні квантових комп’ютерів, які використовують заплутані (зчеплені)
квантові стани. При цьому стани включають як чисті стани окремих кубітів, так і
змішані стани, які є результатом взаємодії (інтерференції) декількох кубітів.
Всього кількість таких, так званих базових, станів становить 2
N
, де N - кількість
кубітів. Тобто для 8-кубітного квантового процессора кількість станів рівна
2
8
=256, а для 16-кубітного – вже 2
16
=65 536 станів [2].
З точки зору теорії обчислень, кожний стан – це сигнал (число), записаний
у певному розряді вихідного квантового регістру, що має 2
N
розрядів. На
кожному такті роботи процесора кожний сигнал – це результат виконання певної
логічної операції. На сьогодні в класичній теорії обчислень відомо 8 операцій, з
яких одна унарна – заперечення та 7 бінарних – еквіваленція, диз’юнкція (АБО),
кон’юнкція (І), імплікація, заперечення диз’юнкції (НЕАБО), заперечення
кон’юнкції (НЕІ), виключна диз’юнкція (виключне АБО, сума по модулю 2, ).
УДК 164; 510
mailto:budnykmykola@gmail.com
mailto:budnykmykola@gmail.com
mailto:budnykmykola@gmail.com
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 38-42
39
Зрозуміло, що ця кількість катастрофічно мала порівняно з потенціалом
квантових обчислень. Отже, в симуляторах квантових обчислень потрібно
забезпечити не сотні, а навіть тисячі логічних операцій. В даній роботі
вирішується завдання збільшення кількості булевих логічних операцій для
квантових обчислень.
1. Базові квантові логічні операції
Під булевими будемо розуміти операції, елементи матриць яких можуть
набувати лише значення 0 чи 1. Тому операції типу Адамара, які мають нецілі
значення елементів матриці, а також комплексні значення, тут не розглядаються.
Також відмітимо, що квантові булеві операції мають інший смисл – це не таблиці
істинності, а матричні оператори, з точки зору теорії функцій – вектор функції
векторного аргументу з розмірністю вектора рівному 2. Тобто багатомісні
операції не є згортками, а є векторними, тобто мають кількість результатів
(виходів), яка рівна кількості входів (операндів).
З літератури відомо такі булеві квантові операції [3]
0100
1000
0010
0001
,
01
10
,
10
01
CNOTNOTEQV
, (1)
Перші 2 операцій з них – Еквіваленція EQV (операція Паулі) та Квантове
Заперечення NOT є однокубітними, а третя – Кероване Заперечення CNOT є
двокубітною. З точки зору класичної теорії обчислень, однокубітна операція
завжди є одномісною, в той час як 2-кубітна може бути 1- чи 2-місною, залежно
від того, кубіти є розрядами одного регістра (в який записано якесь число -
операнд), чи належать двом різним регістрам, в які записані різні операнди.
Для розуміння спочатку розглянемо питання про набір базових операцій,
на основі яких можна реалізувати логічні обчислення. Це питання не є
принциповим для квантових обчислень в тому сенсі, що для квантових
обчислень їх занадто замало. З іншого боку, це дасть розуміння відмінності між
неквантовими та квантовими булевими операціями.
У класичній булевій логіці прийнято, що логічні операції – заперечення,
диз’юнкція та кон’юнкція є базовими в тому сенсі, що за їх допомогою можна
реалізувати довільний логічний вираз. Цей результат суперечить квантовим
обчисленням тому, що класична одномісна операція заперечення відсутня, вона
має вигляд матриці NOT (1). Отже, в якості операції заперечення потрібно в
набір базових операцій включати операцію NOT (1).
Щодо диз’юнкції (І) та кон’юнкції (АБО) теж не все так просто. У
цифрових процесорах реально реалізуються електронні схеми (у квантовій
інформатиці – так звані гейти) операції НЕ-АБО та НЕ-І. З точки зору класичних
обчислень немає різниці, чи у даному процесорі реалізується АБО чи І, чи їх
заперечення НЕ-АБО чи НЕ-І.
Микола Будник
Булеві квантові логічні операції
40
У квантовій інформатиці це питання принципове тому, що базові квантові
логічні операції повинні бути ортогональними (у строгому сенсі по меншій мірі
лінійно незалежними). Це значить, що їх скалярний добуток (тобто згортка
прямого добутку їх матриць) повинен бути рівний нулю. Отже, допустимо
комбінувати лише пару АБО та НЕ- АБО, чи пару НЕ-І та І. В результаті, для
квантових обчислень існує 4 базових булевих операцій, причому має місце 2
варіанти їх наборів (2) чи (3)
,
11
10
,
00
01
,
01
10
,
10
01
АБОНЕАБОNOTEQV (2)
,
01
11
,
10
00
,
01
10
,
10
01
НЕІІNOTEQV (3)
2. Одномісні (однокубітні) операції
Розглянуте в попередньому пункті питання про базові операції має в основному
теоретичне значення, тому що цих операцій занадто мало. Єдине практичне
значення має місце у випадку «квазікласичного» симулятора квантового
процесора, у якому замість класичного набору операцій (заперечення,
диз’юнкція та кон’юнкція) будуть застосовані квантові набори (2) чи (3).
Для збільшення кількості операцій потрібно розглянути всі можливі
комбінаторні набори 0 та 1. Так як матриця має розмірність 2х2, тобто містить 4
елементи, то кількість можливих комбінацій становить 2
4
=16. Тоді всі можливі
16 квантових булевих операцій зручно упорядкувати у матрицю згідно Рис.1.
10
01
01
01
00
01
00
10
EQV Еквіваленція <Х1> НЕ І, заперечення
диз’юнкції
НЕ І
10
10
01
10
11
01
11
10
<Х2> NOT Заперечення АБО імплікація АБО диз’юнкція
10
00
01
00
00
00
11
00
I кон’юнкція І
<0>, НЕ <1>,
Квантовий нуль, НІ
<Y2>
10
11
01
11
00
11
11
11
НЕ АБО ,
комплементарна
імплікація
НЕ АБО
заперечення
кон’юнкції
<Y1>
<1>, НЕ <0>,
Квантова 1, ТАК
Рис. 1. Всі можливі квантові булеві операції (матриця операцій)
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 38-42
41
З рис. 1 видно, що матриця має 4 блоки по 4=2х2 елементи та симетрії, а
саме – сума матриць на діагоналях блоків завжди дають одиничну матрицю (4)
,1021211̂ YYXXNOTEQV (4а)
,1̂ АБОКІІКАБОНЕІІНЕАБОАБО (4б)
Тут враховано, що одномісна квантова операція має загальний вигляд (5),
де Aij – це 0 чи 1, а X1,2 та Y1,2 – вхідні та вихідні логічні операнди
,
2
1
2221
1211
2
1
X
X
AA
AA
Y
Y (5)
Назви операцій взяті по аналогії із класичними булевими операціями, хоч
потрібно пам’ятати, що в квантових обчисленнях вони мають інший смисл.
Слово НЕ означає квантове заперечення даної операції, наприклад NOT –
заперечення еквіваленції EQV. Квантове заперечення NOT формально відповідає
класичній сумі по модулю 2, чи виключному АБО (Exclusive OR, ХОR). Його
смисл в інверсії від обох операндів x та y (для відмінності операнди класичних
операцій позначаємо малими буками, бо вони мають інший смисл).
Штрихом зверху позначено так звані операції «часткового заперечення»
АБО і І , у матрицях яких стовпчики поміняні місцями. З точки зору класичної
інформатики це означає, що береться інверсія від першого операнду х. Тобто
воно має смисл неповного, часткового заперечення АБО лише по першому
операнду х. Таке «часткове заперечення» АБО має класичний аналог –
імплікацію, яка позначається як x → y, та в наших позначеннях має вигляд (6)
,,: yxАБОyxyxАБО (6)
Отже, класична імплікація – це «часткове заперечення» диз’юнкції по першому
операнду х. Квантова імплікація АБО - це «часткове заперечення» квантової
диз’юнкції АБО. Комплементарна квантова імплікація К АБО (7) означає, що у
матриці поміняні місцями рядки. Аналогічно, з точки зору класичної
інформатики це означає, що береться інверсія від другого операнду y
,,: yxАБОyxАБОК (7)
Для квантової операції І та комплементарної до неї К І відсутні класичні
аналоги. Проте, аналогічно (6-7) можна показати формальну відповідність з
класичними функціями у вигляді (8)
,,:,,: yxІyxІКyxІyxІ (8)
Для «примітивних» квантових операцій <Х1>, <Х2>, <Y1>, <Y2> також
відсутні класичні аналоги, їх визначення надається виразами (9-10)
,221:2,121:1 XYYXXYYX (9)
Микола Будник
Булеві квантові логічні операції
42
.01,212:2,02,211:1 YXXYYYXXYY (10)
2. Двокубітні операції
У загальному вигляді двокубітна булева операція має вигляд (11)
,
22
21
12
11
2221
1211
22
21
12
11
X
X
X
X
UU
UU
Y
Y
Y
Y
(11)
де Uij – одна із 16-ти операцій, наведена на Рис. 1. Матриця операції містить
2х2=4 блоки, кожен блок у свою чергу має 2х2 елементи і є матрицею якоїсь
однокубітної операції Uij. Таким чином, всього може бути реалізовано 16
4
= 65
тисяч 536 бінарних (двокубітних) логічних операцій. Наприклад, відома 2-
кубітна операція Кероване Заперечення CNOT (1) – це частковий випадок
операції загального виду (11), коли U12=U21=<0>, U11=EQV, U22=NOT.
Висновки. В роботі запропоновано 9 нових 1-кубітних булевих операцій та
отримано повний набір з 16-ти квантових операцій. Це забезпечує 16
4
= 65 тисяч
536 бінарних (двокубітних) операцій, що відповідає кількості базових станів 16-
кубітного квантового процесора. Велика кількість операцій реалізує потенціал
квантових обчислень в цифрових симуляторах квантових процесорів.
Література
[1] Wolf E.L. Quantum Nanoelectronics: An Introduction to Electronic Nanotechnology and Quantum
Computing. – Wiley. – 2009. – 472 р.
[2] Войтович І.Д., Корсунський В.М. Перспективи квантових обчислень з використанням
надпровідності // Математичні машини і системи. – 2008. – № 4. – С. 23–56
[3] Будник М.М., Баужа О.С., Войтович І.Д., Корсунський В.М. Вступ до квантових обчислень
та квантових комп’ютерів: навчальний посібник. – Київ: Інтерсервіс, 2014. – 95 с.
Boolean quantum logic operations
Mykola Budnyk
The paper proposes generalization of Boolean logic operations intended for quantum computing. It
is shown that the basic set of Boolean one-qubit operations contains 6 ones and has 2 variants of
sets of 4 operations. 9 unary quantum operations are proposed in addition to 7 classical ones
(equivalence, OR, XOR, AND, NOR, NAND, implication). As a result, a complete set of 16 one-
qubit operations was obtained, which provides 164 = 65 thousand 536 binary (two-qubit) logical
operations that corresponds to the number of base states of a 16-qubit quantum processor. Large
number of operations will allow increase performance of computing in digital simulators of
quantum processors from the viewpoint of computing parallelism and reducing the program cod.
Отримано 30.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-272 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:30Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/f9/6783a450076d6f546de498a543bfd6f9.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2722025-02-21T17:32:19Z Boolean quantum logic operations Булеві квантові логічні операції Budnyk, Mykola квантові обчислення, логічні операції, булева алгебра The paper proposes generalization of Boolean logic operations intended for quantum computing. It is shown that the basic set of Boolean one-qubit operations contains 6 ones and has 2 variants of sets of 4 operations. 9 unary quantum operations are proposed in addition to 7 classical ones (equivalence, OR, XOR, AND, NOR, NAND, implication). As a result, a complete set of 16 one-qubit operations was obtained, which provides 164 = 65 thousand 536 binary (two-qubit) logical operations that corresponds to the number of base states of a 16-qubit quantum processor. Large &nbsp;number of operations will allow increase performance of computing in digital simulators of quantum processors from the viewpoint of computing parallelism and reducing the program cod. У роботі запропоновано узагальнення булевих операцій для квантових обчислень. Показано, що базовий набір булевих однокубітних операцій містить 6 операцій та має 2 варіанти наборів по 4 операції. Запропоновано 9 квантових операцій додатково до 7-ми класичних (еквіваленція, диз’юнкція, кон’юнкція, імплікація, заперечення диз’юнкції, заперечення кон’юнкції, виключна диз’юнкція). В результаті отримано повний набір 16 однокубітних операцій, які забезпечують 164 = 65 тисяч 536 бінарних (двокубітних) логічних операцій, що відповідає кількості базових станів 16-кубітного квантового процесора. Велика кількість операцій дозволить підвищити продуктивність квантових обчислень в цифрових симуляторах квантових процесорів з точки зору паралельності обчислень та скорочення програмного коду. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/272 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 38-42 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 38-42 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/272/257 Авторське право (c) 2023 Микола Будник (Автор) |
| spellingShingle | квантові обчислення логічні операції булева алгебра Budnyk, Mykola Булеві квантові логічні операції |
| title | Булеві квантові логічні операції |
| title_alt | Boolean quantum logic operations |
| title_full | Булеві квантові логічні операції |
| title_fullStr | Булеві квантові логічні операції |
| title_full_unstemmed | Булеві квантові логічні операції |
| title_short | Булеві квантові логічні операції |
| title_sort | булеві квантові логічні операції |
| topic | квантові обчислення логічні операції булева алгебра |
| topic_facet | квантові обчислення логічні операції булева алгебра |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/272 |
| work_keys_str_mv | AT budnykmykola booleanquantumlogicoperations AT budnykmykola bulevíkvantovílogíčníoperacíí |