Математичні та комп’ютерні моделі в квантовій інформатиці

Размещено на http://www.allbest.ru/

Харківський національний університет імені В.Н. Каразіна

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

МАТЕМАТИЧНІ ТА КОМП'ЮТЕРНІ МОДЕЛІ В КВАНТОВІЙ ІНФОРМАТИЦІ

Спеціальність: Математичне моделювання та обчислювальні методи

Мезел Х. Таві

Харків, 2010 рік

1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Розвиток технологій обробки інформації привело до проникнення обчислювальних систем практично в усі галузі техніки. Математичне моделювання і комп'ютерний експеримент сьогодні стали неодмінним атрибутом науково-дослідних і проектних робіт. Масове застосування цих методів для дослідження складних технічних систем дозволило не тільки підвищити продуктивність інженерних робіт, але і виявило ряд обмежень щодо застосування комп'ютерного моделювання. Ці обмеження пов'язані, перш за все, з обчислювальною складністю задач, що виникають в процесі моделювання. Обчислювальна складність задачі є, часом, непереборним бар'єром для постановки практично значущого комп'ютерного експерименту. При цьому слід зазначити, що застосування паралельних обчислень і розподілених обчислювальних систем в силу закону Ж. Амдала дозволяє прискорити процес обчислення пропорційно кількості використовуваних обчислювачів.

У зв'язку з цим, ще у 1980 році Ю.І. Маніним було висловлено припущення, що завдання комп'ютерного моделювання складних об'єктів вимагають використання в якості носія моделі не класичні, а квантові системи. Особливістю квантових систем є, так званий квантовий паралелізм, що є наслідком принципу суперпозиції станів квантової системи, і що дозволяє експоненціально зменшити необхідні для вирішення задачі обчислювальні ресурси.

Аналогічні ідеї були висловлені й лауреатом Нобелівської премії Р. Фейнманом. Припущення Ю.І. Маніна і Р. Фейнмана про те, що перехід від класичного до квантового носія обчислювальної моделі дозволяє більш ніж поліноміально збільшити продуктивність обчислень, блискуче підтвердилося роботою П. Шора, в якій йому вдалося побудувати математичні моделі квантових пристроїв, здатних розв'язувати задачі розкладання натуральних чисел на множники і знаходження дискретного логарифма за поліноміальний час. Нагадаємо, що класична обчислювальна складність цих завдань забезпечує крипостійкість більшості сучасних криптографічних алгоритмів з відкритим ключем. Таким чином, робота П. Шора перетворила квантову інформатику з галузі знань, що представляє академічний інтерес, в область досліджень, що представляє значний практичний інтерес. Незважаючи на значний прогрес у розумінні природи квантових інформаційних процесів, у розробці технічних засобів для квантових обчислень, питань створення теорії програмування для квантових обчислювальних систем приділяється недостатньо уваги. У зв'язку з цим, задача розробки математичних і комп'ютерних моделей квантових обчислювальних систем, якій присвячена робота, є актуальною.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану науково-дослідних робіт Харківського національного університету імені В.Н. Каразіна в рамках теми №3-11-09 «Модельні представлення несамоспряжених або неунітарних операторів і їх застосування» (номер державної реєстрації 0109U001455).

Метою дослідження є побудова математичних і комп'ютерних моделей квантових обчислювальних систем, призначених для створення засобів, що забезпечують постановку комп'ютерних експериментів в ході розробки квантових засобів моделювання складних технічних систем і процесів, аналіз яких приводить до необхідності вирішення обчислювальних завдань більш ніж поліноміальної складності. Для досягнення цієї мети в роботі поставлені та вирішені такі задачі:

- проведено аналіз існуючих підходів до побудови математичних моделей класичних та квантових інформаційних систем, методів їх фізичного-чеський реалізації, виходячи з особливостей моделювання складних систем;

- проведено аналіз існуючих математичних моделей квантових систем з кінцевим числом рівнів, спрямований на виявлення можливостей їх вдосконалення в контексті використання в квантовій інформатиці;

- побудовані математична і комп'ютерна моделі операції на квантовій пам'яті;

- досліджено властивості квантових каналів, що виникають при реалізації квантової операції, на основі їх модельних уявлень;

- побудовані математична і комп'ютерна моделі квантового автомата як системи взаємодіючих квантових операцій;

- проведено імітаційне та аналітичне дослідження моделей поведінки найпростіших квантових автоматів з метою з'ясування його відповідності принципам квантової фізики.

Об'єкт дослідження є інформаційні процеси в квантових фізичних системах.

Предмет дослідження є математичні та комп'ютерні моделі інформаційних процесів у квантових фізичних системах, які використовуються як носії моделей складних технічних систем.

Методи дослідження.

У роботі застосовані методи теорії алгоритмів, лінійної та топологічної алгебри, теорії матриць, теорії ймовірностей, математичної статистики, системного аналізу, математичної логіки.

Наукова новизна результатів дисертаційної роботи. Наукова новизна отриманих результатів полягає в тому, що в роботі вирішена важлива науково-прикладна задача - вдосконалення методів математичного та комп'ютерного моделювання шляхом створення нових засобів моделювання та обчислень, при цьому:

1) удосконалено математичну модель квантової системи зі скінченим числом рівнів шляхом узагальнення традиційної моделі вимірювань та моделі вимірювань А.С. Холево, що дозволило побудувати, реалізувати у вигляді програмного прототипу та дослідити трьохкрокову модель операції на квантовій пам'яті, яка на відміну від існуючих забезпечує опис неточності апріорної інформації про стан, в якому відбувається вимірювання системи, та дозволяє прослідкувати перетворення цього стану;

2) вперше на базі трьохкрокової моделі операції на квантовій пам'яті побудовано та досліджено модель квантового обчислювального пристрою - квантового автомату. На відміну від існуючих, запропонована модель дозволяє описати унітарні перетворення квантової пам'яті і процес виміру її стану в термінах уніфікованого формалізму, що дозволяє, наприклад, дати математично замкнутий опис процесу телепортації квантового стану;

3) у роботі вперше введено поняття характеристичного оператора квантового каналу та встановлено його властивості, що дозволило запропонувати конструктивний метод синтезу квантових каналів, побудувати обчислювальний метод, що дозволяє відповісти на питання «Чи є відображення квантовим каналом?», встановити вид квантових каналів, що задовольняють спеціальним властивостям;

4) отримав подальший розвиток метод обчислювального експерименту для дослідження властивостей квантових автоматів шляхом їх імітаційного моделювання.

Практичне значення одержаних результатів. Практична цінність роботи полягає у тому, що усі теоретичні розробки автором доведені до конкретних інженерних методик, алгоритмів і реалізовані у вигляді прототипів програмних засобів, які базуються на результатах дослідження побудованих у роботі математичних моделей та використанні розроблених обчислювальних методів, зокрема, реалізовано каркас системи імітаційного моделювання поведінки квантових автоматів, що включає ядро імітаційного моделювання, транслятори описів квантових автоматів і сценаріїв імітаційних експериментів з ними, виведення результатів експерименту для подальшої статистичної обробки. Практична цінність роботи підтверджується також використанням її результатів у Фізико-технічному інституті низьких температур ім. Б.Є. Вєркіна НАН України. Акт про використання результатів роботи наведений у додатку до дисертації.

Особистий внесок здобувача. Всі результати дисертаційної роботи отримані автором самостійно.

Апробація результатів досліджень. Основні результати дисертації доповідалися на:

- DeSSerT - 2009 «Гарантоздатні (надійні та безпечні) системи, сервіси та технології» (Кіровоград, 2009 рік);

- Ukrainian Mathematical Congress. 7th International Algebraic Conference in Ukraine (Kharkiv, 2009);

- Науково-технічна конференція с міжнародною участю «Комп'ютерне моделювання в науково містких технологіях» (Харків, 2010).

Публікації. За результатами наукових досліджень опубліковано 4 наукові статті у виданнях, що входять до переліку видань, затвердженого ВАК України, та 2 тези доповідей на конференціях.

Структура та обсяг роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, списку використаних джерел та додатків. Повний обсяг дисертації складає 122 сторінки.

Вона містить 9 рисунків, 5 таблиць, список використаних джерел із 105 назв на 8сторінках, додаток на 1 сторінці.

2. ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтована тема дисертації, показаний її зв'язок з науковими темами, які виконуються у Харківському національному університеті імені В.Н. Каразіна, визначені мета і задачі дослідження, сформульовані наукова новизна і практична цінність отриманих результатів.

У першому розділі розглянута історія виникнення квантової інформатики. На підставі аналізу робіт Ю.І. Маніна, Р. Фейнмана, Д. Дойча та інших засновників теорії квантових обчислень встановлена основна мета розвитку цієї теорії - забезпечення засобів для комп'ютерного моделювання складних систем. Цей аналіз дозволив сформулювати основну вимогу до математичних і комп'ютерних моделей квантових інформаційних процесів, а саме, моделі мають спиратися лише на самі загальні положення квантової теорії та не нав'язувати фізичну реалізацію відповідних технічних систем. Основною проблемою при застосуванні класичних обчислювачів до задач моделювання складних систем є обчислювальна складність задач, які необхідно розв'язувати в ході комп'ютерного експерименту. Як видно з роботи застосування квантових принципів при побудові обчислювальних пристроїв дозволяє забезпечити прискорення обчислень, причому для деяких задач навіть експоненційне.

З метою подальшого узагальнення на квантовий випадок у розділі також подається математична модель машини Тюрінга, а саме, під машиною Тюрінга розуміється система, що складається з дев'яти компонентів:

На жаль аналогічної повністю формалізованої моделі для квантових обчислювачів не існує. Виходячи з цього формулюється мета і завдання дослідження.

Другий розділ дисертації присвячено аналізу математичних моделей квантових систем зі скінченим числом рівнів. Перш за все, аналізу піддана модель замкненої квантової системи («векторна» модель).

Вона базується на таких постулатах:

1) постулат простору станів: з кожною квантової системою з числом рівнів однозначно асоціюється - вимірний гільбертів простір, який називається далі простором системи, при цьому стан квантової системи повністю описується одновимірним підпростором простору. Оскільки стан описується одномірним підпростором простору, то воно може бути представлено одиничним вектором з точністю до скалярного множника за модулем рівного одиниці. З цієї причини ми назвали розглянуту модель «векторною». У векторній моделі прийнято вважати, що стан квантової системи представляється одномірним одиничним вектором. При цьому мається на увазі, що два одиничних вектора, які відрізняються на скалярний множник, представляють один і той же стан. Найпростішою квантовою системою зі скінченим числом рівнів є дворівнева система, яка відіграє особливу роль у квантовій інформатиці. Вона отримала назву «кубіт»;

2) еволюційний постулат: еволюція замкнутої квантової системи описується унітарним оператором, що діє у просторі системи. Це означає, що стан системи часу, який залежить тільки від моментів часу, за формулою:

3) постулат вимірювання: квантове вимірювання описується сім'єю операторів вимірювання. Оператори, що входять в сім'ю, діють на просторі системи й індексовані множиною можливих результатів вимірювання.

При цьому, якщо стан системи безпосередньо перед вимірюванням описується вектором,то ймовірність отримати як результат вимірювання задається формулою:

А стан системи безпосередньо після вимірювання, якщо результатом останнього є, описується вектором:

Причому оператори вимірювання повинні задовольняти рівнянню:

Показано, що в термінах цієї моделі неможливо описати операцію приготування квантової системи в початковому стані, що відповідає процедурі введення даних в обчислювальну систему. Аналогічно, в цьому випадку процедура виведення даних - вимірювання стану квантової системи, має інший формалізм, ніж формалізм, який використовується для опису процедури перетворення пам'яті. Істотним недоліком моделі замкненої квантової системи для квантової інформатики є неможливість описати можливу неточність знань про систему. Враховуючи зазначені недоліки, в роботі розглянута загальна статистична модель А.С. Холево та її спеціалізація для випадку квантових систем зі скінченим числом рівнів, яка в роботі названа «матричною» моделлю. В цій моделі стан квантової системи описується матрицею щільності у просторі системи, тобто ненегативно визначеним оператором, слід якого дорівнює одиниці.

Множина матриць щільності є опуклою та компактною. Її крайніми точками є ортогональні проектори на одновимірні підпростори. Таким чином, стани векторної моделі є спеціальними станами матричної моделі, які називають чистими станами.

У цій моделі за рахунок переходу від «векторного» опису станів квантової системи до «матричного» вдається вирішити задачу опису неточності знань про квантову систему.

Такі неточні знання описуються матрицями щільності, відмінними від одновимірних ортогональних проекторів.

У матричній моделі еволюція квантової системи, також як і у векторній моделі, визначається унітарним оператором.

А саме, перетворення має вигляд:

Таким чином, ця модель не дає засобів для опису зміни станів системи в процесі вимірювання.

З урахуванням вищевикладеного, третій підрозділ другого розділу присвячений синтезу ідей, використаних при побудові «векторної» і «матричної» моделей квантової системи, що призводить до трьохкрокової моделі операції на квантовій пам'яті. Таким чином квантова операція може розглядатися, як процес з трьох кроків:

1) перейти від матриці щільності до матриці щільності в просторі об'єднаної системи «система - прилад»;

2) матриця щільності об'єднаної системи усереднюється за станами приладу, що дає матрицю щільності системи після вимірювання.

Трьохкрокова модель дозволяє в рамках єдиного формалізму описати як операції, що забезпечують передачу інформації з квантової системи поза її межі, так і операції, що не передають таку інформацію - в цьому випадку складається з одного елементу, а ізометричний оператор є унітарним.

Наприкінці розділу розглядається важливий клас відображень просторів станів квантових систем - квантові канали. В роботі з кожним квантовим пов'язується лінійний оператор у просторі, а саме цей оператор є оператором, який породжує півторилінійну форму:

Це дозволяє побудувати модельні зображення квантових каналів.

Третій розділ дисертаційної роботи починається з побудови системи взаємодіючих операцій на квантовій пам'яті, що названа квантовим автоматом. Це поняття є центральним у роботі. Квантовий автомат будується як комплекс взаємодіючих операцій на квантовій системі зі скінченим числом рівнів. В основу побудови такої системи покладемо модель взаємодії двох автоматів, запропоновану В.М. Глушковим. Нагадаємо, що в моделі В.М. Глушкова абстрактна обчислювальна система подається як система, що складається з двох взаємодіючих автоматів: керуючого автомата (програми), і операційного автомата (пам'яті).

Керуючий автомат отримує від операційного автомата повідомлення, що містить результати перевірки (вимірювання) набору логічних умов, визначених на множині станів операційного автомата. На підставі поточного стану та отриманого повідомлення керуючий автомат формує вихідне повідомлення, яке визначає перетворення множини станів операційного автомата, та здійснює перехід у новий стан.

Зазначена послідовність дій повторюється до тих пір, поки керуючий автомат не опиниться в заключному стані - точці виходу з програми.

Кожне перетворення станів квантової пам'яті комп'ютера є операцією на відповідній квантовій системі.

В ролі керуючого автомата візьмемо орієнтований мультиграф з виділеною вхідною вершиною та виділеною термінальною вершиною. Його вершини, крім термінальної, помічені операціями на квантовій пам'яті, а ребра, що виходять з вершин, помічені мітками результатів відповідної квантової операції:

Перейдемо тепер до визначення формальної моделі квантового автомата.

Припустимо, що кожній контрольній точці, крім точки (), поставлена у відповідність квантова операція, що описується ізометрією:

Миттєвим описом квантового автомата в момент часу є пара, що включає матрицю щільності, що описує чистий стан квантової системи в цей момент часу, і контрольну точку, яка відповідає стану класичного керуючого пристрою.

Еволюція квантового автомату визначається у такий спосіб. Описана модель квантового автомата є моделлю, побудованою на базі двох взаємодіючих систем: класичного керуючого автомату та квантової пам'яті.

Як найпростіший приклад квантового автомата наведена процедура очищення кубіта - приготування кубіта в основному стані.

Простором квантової пам'яті автомата є простір кубіта Н1.

Четвертий розділ присвячено дослідженню простих квантових автоматів. На початку розділу визначається автомат послідовного бінарного тестування кубіта. На базі введеного визначення будується імітаційна модель цього автомата, після чого проводиться його дослідження шляхом постановки серій комп'ютерних експериментів.

Важливим результатом такого дослідження є спостереження квантового ефекту Зенона для автомата бінарного тестування.

Строго доведена відсутність оптимальної оцінки для параметра початкового стану квантової пам'яті може розглядатися як підтвердження наявності такого ефекту. Повне ж рішення в роботі не дано - воно сформульовано у вигляді гіпотези про асимптотичну поведінку автомата бінарного тестування кубіта.

Проведене далі дослідження автомата тернарного тестування кубіта, який не може бути реалізований в класичному випадку, дозволило отримати аналогічні результати. В цьому випадку, однак, квантовий ефект Зенона виявляється наслідком ергодичності ланцюга Маркова, що описує поведінку квантового автомата тернарного тестування кубіта.

ВИСНОВКИ

У дисертаційній роботі вирішена важлива науково-прикладна задача - шляхом синтезу існуючих фізичних та статистичних підходів до опису квантових фізичних систем зі скінченим числом рівнів побудована математичні модель квантової обчислювальної системи (квантового автомата). На базі цієї моделі розроблено технологію комп'ютерного експерименту, що призначена для дослідження квантових інформаційних процесів. Використання цієї технології дозволило перевірити на моделях ряд властивостей і ефектів, характерних для квантових інформаційних процесів. Основні результати, які були отримані в роботі, полягають у наступному:

1) побудована математична модель відповідно до вимог, сформульованих Ю.І. Маніним, базуються тільки на загальних принципах квантової фізики і не орієнтована на конкретну технічну реалізацію. Це дозволило розробити програмні засоби, що забезпечують постановку комп'ютерних експериментів в ході розробки квантових носіїв моделей складних технічних процесів, для аналізу яких традиційними засобами необхідно вирішувати обчислювальні задачі більш ніж поліноміальної складності; статистичний математичний обчислювання

2) на підставі аналізу існуючих підходів до створення квантових систем обробки та передачі інформації були виділені наступні основні функціональні елементи таких систем: класичний пристрій управління, квантова пам'ять, засоби, що забезпечують обмін інформацією із зовнішнім середовищем (введення чи виведення) та передачу даних між обчислювальними системами;

3) на підставі аналізу існуючих математичних моделей квантових систем зі скінченим числом рівнів встановлено, що традиційні моделі замкнутих квантових систем не дозволяють моделювати важливі операції, пов'язані з введенням даних (підготовка системи в потрібному стані залишається за рамками такої моделі). існуючі моделі, побудовані в термінах матриць щільності, не забезпечують уніфікованого формалізму для опису операцій читання даних з квантової пам'яті та операцій перетворення станів квантової пам'яті. Це дозволяє зробити висновок про те, що забезпечення уніфікованого формалізму для опису всіх операцій над квантової пам'яттю є основною вимогою при розробці моделі;

4) удосконалено математичну модель квантової системи зі скінченим числом рівнів шляхом узагальнення традиційної моделі вимірювань та моделі вимірювань А.С. Холево, що дозволило побудувати, реалізувати у вигляді програмного прототипу та дослідити трьохкрокову модель операції на квантовій пам'яті, яка на відміну від існуючих забезпечує опис неточності апріорної інформації про стан;

5) вперше на базі трьохкрокової моделі операції на квантовій пам'яті побудована та досліджена модель квантового обчислювального пристрою - квантового автомату. На відміну від існуючих, запропонована модель дозволяє описати унітарне перетворення квантової пам'яті і процес виміру її стану в термінах уніфікованого формалізму, що дозволяє, наприклад, дати математично замкнений опис процесу телепортації квантового стану;

6) в роботі вперше введено поняття характеристичного оператора квантового каналу та встановлено його властивості, що дозволило запропонувати обчислювальний метод синтезу квантових каналів, побудувати обчислювальний метод, що дозволяє відповісти на питання «Чи є відображення квантовим каналом?», встановити вид квантових каналів, що задовольняють спеціальним властивостям;

7) отримані в роботі результати доведені до прототипів програмних рішень, які дозволяють досліджувати властивості компонентів квантових інформаційних систем шляхом комп'ютерних експериментів.

Таким чином, в робота створює теоретичну та технологічну базу для дослідження принципово нових носіїв математичних моделей шляхом постановки серій комп'ютерних експериментів.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Тави М. Об одной модели квантового канала / Г.Н. Жолткевич, М. Тави // Вісн. Харк. нац. ун-ту. Сер. Математичне моделювання. Інформаційні технології. Автоматизовані системи управління. - 2008. - №9(809). - С. 88-101.

2. Об одной модели программ в задачах формальной верификации / Г.Н. Жолткевич, И.Д. Перепелица, Ю.В. Соляник, М. Тави // Радіоелектронні і комп'ютерні системи. - №7(41), 2009. - С. 182-185.

3. Thawi M. On the Structure of quantum channels / M. Thawi, G.M. Zholtkevych // Ukrainian Mathematical Congress. 7th Int. Alg. Conf. in Ukraine, 18-23 August, 2009, Kharkiv: abstracts of talks. - 2009, Kiev. - P. 137.

4. Thawi M. About One Model of Consecutive Qubit Binary Testing / M. Thawi, G.M. Zholtkevych // Компьютерное моделирование в наукоемких технологиях: труды научн. - техн. конф. с междунар. участием 18-21 мая 2010. - Х., 2010. - С. 251-255.

5. Thawi M. About One Model of Consecutive Qubit Binary Testing / M. Thawi, G.M. Zholtkevych // Вісн. Харк. нац. ун-ту. Сер. Математичне моделювання. Інформаційні технології. Автоматизовані системи управління. - 2010. - №13(890). - С. 71-81.

6. Тави М. Об одной математической модели квантового автомата / Г.Н. Жолткевич, М. Тави // Системи управління, навігації та зв'язку / ДП «Центр. наук. - досл. ін. - т навігац. та управл.» - 2010. - Вип. 4(16). - C. 94-98.

Размещено на Allbest.ru