вгору

оперативний блогер

18.05.11

Квантові комп'ютери

ВСТУП
Для вирішення багатьох завдань, не тільки пов'язаних з обчисленнями, людина на допомогу винайшла комп'ютер. 

Це був цифровий комп'ютер, зроблений з напівпровідникових елементів. Комп'ютерна техніка стрімко розвивалася, знаходячи собі застосування в багатьох областях діяльності людини. Зменшувалися розміри комп’ютерів, підвищувався швидкодія, можливості комп'ютерів зростали[1]. Сучасні комп'ютери, маючи більшу швидкодію, здатні вирішувати найскладніші завдання при фізико-математичних розрахунках, оперувати складними системами в біологічних дослідах, управляти гігантськими комплексами на виробництвах. Однак існують завдання, які не можуть бути вирішені на звичайних класичних комп'ютерах, заснованих на напівпровідникових елементах (класичний комп'ютер). Достатньо наочним прикладом є задача комівояжера. В її умові фігурує N міст, які потрібно об'їхати, повернувшись у вихідне, але так, щоб загальний шлях виявився мінімальним. Як не просте це завдання на перший погляд, її рішення на комп'ютері поки можливий тільки шляхом повного перебору всіх варіантів. Є способи, що дозволяють скоротити об'єм, але загальної картини вони не міняють. А час, необхідний на повний перебір, зі збільшенням числа N зростає катастрофічними темпами: скажімо, при N = 100, порівняно з попереднім з N = 99, воно зросте в 100 разів. Неважко підрахувати значення N, при якому час перебору на звичайному ПК перевищить людське життя. Збільшивши N на кілька десятків і вийде, що всіх ПК планети Земля, що працюють паралельно, не вистачить, щоб встигнути вирішити це завдання в прийнятні терміни. Якщо збільшити ще, виявиться, що комп'ютер масою з Сонячну систему також виявиться нездатний зробити це. У цей же час не гарантовано, що це завдання можна вирішити в принципі для будь-якого N, але на практиці від цього мало користі. В цій задачі не допоможе ні швидкий комп'ютер (весь запас швидкості буде вичерпано при невеликому збільшенні розмірності), ні паралельні обчислення, оскільки значення продуктивності процесора на одиницю об'єму або маси чіпа залишається постійною. [2] От якби всі обчислення відбувалися паралельно, але не на різних процесорах, а всередині одного пристрою з обмеженим об'ємом і масою...
Отже, для вирішення подібних завдань класичного комп'ютера потрібна велика кількість часу або він взагалі не може вирішити через свої технічні особливості.
Останнім часом ми часом так сильно захоплюємося безпрецедентною гонкою гігантів процесорної індустрії, що абсолютно забуваємо про межі можливого. Появилися процесори з тактовою частотою 5000 MHz, ще трохи зусиль - і цей показник дотягнуть до номінального, але врешті-решт, бар'єр, нездоланний для існуючих процесорних технологій, вже досить близький. Навіть сьогодні в процесоробудування існує серйозна проблема - вироби надмірно нагріваються, і тепло, що виділяється ними потрібно відводити. Якщо цього не робити, неминучі помилки: не можна буде достеменно сказати, які числа зберігаються в комірках пам'яті процесора, і з'являться відхилення в його роботі. Але проблема відведення тепла вторинна. В основі всього тут лежить сам принцип зберігання інформації в сучасних процесорах. Для того щоб представити один біт даних в елементарній ділянці напівпровідника, необхідно надати їй деякий електричний заряд. Чим більше інформації ми хочемо упакувати в кремнієву пластину (а без цього тактову частоту не піднімеш), тим менші будуть ці ділянки і, отже, відчутніший їх взаємний вплив одна на одну, яке і заважає надійному зберіганню інформації. Крім того, можливі зовнішні впливи. Адже існують в світі такі явища, як радіаційний фон, різні інші види випромінювань. Наприклад, альфа - частка з космосу, несанкціоновано пронизує напівпровідник, впливає на елементарну ділянку[3]. Немає проблем, якщо його заряд досить великий, скажімо, еквівалентний мільйону електронів. Але чим меншими стають такі ділянки, тим менше можна їх зарядити і тим істотніший вплив зовнішніх ефектів. Якість самого напівпровідника, тобто його однорідність, теж відіграє все більш помітну роль, проте її не можна підвищувати безмежно, та ще й за прийнятну ціну. Іншими словами, "стіна" вже досить близька, і, схоже, при нинішній гонці в неї вріжуться на повному ходу.
Комбінаторні і їм подібні задачі вимагають нового підходу, нових технічних рішень. Але де їх узяти? Як перейти від класичних алгоритмів, реалізованих у звичайних комп'ютерах, до нових, абсолютно не схожим на колишні? Відповіді на ці запитання, теорія квантових комп'ютерів[4]. Справді, адже ми живемо в квантовому світі, і ми можемо створити комп'ютер, всі процеси в якому будуть підкорятися законам квантової механіки. Ідею про можливість створення квантових комп'ютерів вперше висловив в 1985 році Р. Фейнман.
Багато фізичних процесів для наочності моделюються на комп'ютері, що дозволяє проводити складні дорогі експерименти віртуальним чином. Змінюючи параметри програми і відстежуючи вихід ми можемо прогнозувати подальшу еволюцію системи. Але це наближене моделювання, в якому ми будуємо чисельні алгоритми для диференціальних рівнянь і потім використовуємо комп'ютер для обчислень цих алгоритмів і отримуємо наближену картину того, чим має бути фізика. Хотілось би більшого, тобто точного моделювання, коли комп'ютер робить те саме, що і природа. Фізичний світ - світ квантової механіки, і, отже, справжня проблема моделювання квантової фізики! Як би ми не намагалися, змоделювати будь-який квантовий процес на класичному комп'ютері не вийде, а було б не погано. Як бути[5]
Р.Фейнман висловив ідею про моделювання квантових об'єктів на самих же квантових об'єктах, тобто звернув увагу на можливість побудови процесора, що працює за квантово-механічним принципам. Цей момент вважається народженням теорії квантових комп'ютерів.
РОЗДІЛ 1
Квантові обчислення та комп'ютери      
Зворотні і незворотні класичні процесори. Викладу основних принципів квантових обчислень і квантових комп'ютерів наприклад опис деяких аспектів дії звичайних - класичних - комп'ютерів, не претендуючи на повноту опису, а ставить метою наочність переходу до обговорення особливостей квантових обчислень[6].
Класичні комп'ютери, як пристрої для обчислень, повинні оперувати з
числами. Простий пристрій, здатний представляти числа, - це пристрій, який
має два стійких стани. Так само, провідники зі струмом можуть знаходитися в двох станах: коли немає струму, відповідних значенням 0, а коли є, - 1. Використання таких пристроїв для проведення дій над числами можливо завдяки двійковій запису чисел.
[7] Для прикладу, натуральне число 9 у двійковій системі запишеться, як 1001 = (1х23) +(0х22) + (0х21) + (1х20), а додавання чисел виконується згідно з таблицею 
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0
(1 в наступному розряді, запам’ятати).
В даний час придумано безліч різних пристроїв, які здійснюють таку операцію додавання. Для наочності наведемо варіант механічного пристрою



Рис. 1.Механічна схема підсумовуючого процесора на кульках. 
Цей пристрій складається з заслінок (вентилів) і каналів, що з'єднують їх. По каналах можуть рухатися під дією сили тяжіння кульки, які переводять при цьому рух заслінки в одному з двох можливих положень. Т-станом заслінки приписується значення 0, а поверненому, λ-станом, - значення 1. до складу пристрою входять два типи заслінок: заслінки А і С, позначені сірим штрихуванням і виконують функцію запису стану каналу, в якому вони розташовані, а також заслінки В, позначені чорним кольором і виконують функцію логічних вентилів (тих самих gates) складення двох бітів. (А) Початковий стан процесора: на станах заслінок (В4, В3, В2, В1), "записано" число 5 = 10; на вході в пристрій за допомогою кульок "приготовлено" інше число: 3 = 11. (Б) Стан підсумовуючого процесора після дії кульки з першого розряду: на регістрі {Ai} "записалося" число 1, а на регістрі {Bi} - число 110 (5 +1). (В) Кінцевий стан підсумовуючого процесора після дії кульки з другого розряду: на регістрі {Ai} записано вихідне число 11, регістр {Bi}
переведений в стан, що відповідає сумі 101+11 = 1000 (5+3 = 8).
 Дійсно, кожен вентиль В має один підвідний канал (ліворуч) і два відвідних
(Праворуч), з яких нижній відповідає біту перенесення в наступний розряд, а верхній призначений для збору кульок. Якщо вважати, що наявність кульки на вході в вентиль В відповідає 1, а його відсутність - 0, то даний логічний блок здійснює своє дію
. [8]  Ця дія еквівалентна операції додавання двох бітів, якщо під першим бітом, що додається розуміти стан входу В, а під другим доданком початковий стан заслінки В, кінцевий стан якої і є результатом додавання спільно з кінцевим станом біта переносу. Об'єднуючи такі логічні вентилі в мережу шляхом приєднання каналу переносу до каналу входу логічного вентиля наступного розряду, отримаємо процесор для підсумовування чисел будь розрядності.
Квантові комп'ютери. 
На сьогодні описано багато типів квантових комп’ютерів, заснованих на різних підходах, принципах. Як зазначив акад. К. А. Валієв на семінарі з квантових обчислень, величезний потік все нових і нових пропозицій щодо
реалізації квантових комп'ютерів пов'язаний з тим, що в даний час вчені вигадують такий комп'ютер з підручних засобів, тобто на основі тих фізичних об'єктів, вивченням яких вони зайняті багато років. Насправді, квантові обчислення можна влаштувати практично на будь-якій квантовій системі. Треба тільки придумати способи зовнішньої взаємодії, що реалізують ті чи інші алгоритми, і подбати про досить великий проміжок часу порушення когерентності системи або про прийоми виправлення помилок. У загальному вигляді що таке квантовий комп'ютер можна описати таким чином. 
             Квантові комп'ютери - це фізичні пристрої, що виконують логічні операції над квантовими станами шляхом унітарних перетворень, що не порушують квантові суперпозиції в процесі обчислень.[9] Дуже схематично робота квантового комп’ютера може бути представлена, ​​як послідовність трьох операцій:
1. запис (приготування) початкового стану;
2. обчислення (унітарні перетворення початкових станів);
3. вивід результату (вимірювання, проектування кінцевого стану).   
          Розглянемо кожну з цих операцій окремо.    
1) Як продемонстровано вище, класичний комп'ютер оперує з бітами - булевими змінними, які приймають значення 0 або 1 - і на будь-якому етапі обчислень комп'ютер має певні значення в кожному біті, використовуваному для обчислень. Причому, ці значення можна виміряти. На першому етапі обчислень необхідно записати вихідні дані в регістр - набір бітів, кожен з яких повинен мати певні значення (0 або 1).
Квантовий комп'ютер оперує з станами. Найпростішою системою, виконуючою функцію, аналогічну бітам в класичних комп'ютерах, є система з двома можливими станами. Для позначення стану такий квантової дворівневої системи запропонований спеціальний термін: q-біт (від англ. quantum bit, qubit) - квантовий біт інформації - стану квантової системи з двома можливими базовими станами |0> і |1>. Загальний стан такої системи є суперпозиція
|q> = c0 | 0> + c1 | 1>,
щось більше, ніж булеві 0 або 1; q-біт - це квантова суперпозиція двох чисел: нуля і одиниці. Фізичними системами, що реалізовують q-біти, можуть бути будь-які об'єкти, що мають два квантових стани: поляризаційні стану фотонів, електронні стани ізольованих атомів або іонів, спінові стани ядер, нижні стани в квантових точках та ін. Придумати q-бітів, тобто дворівневих квантових систем, можна велику кількість.[10] Набагато складніше придумати, як влаштувати управління окремими q-бітами, організувати взаємодію між ними і забезпечити достатньо великий час декогеренції. Саме ці труднощі не дозволяють кожному з фізиків винайти власний квантовий комп'ютер.
 Вже перша операція всіх (класичних і квантових) обчислень – приготування початкового стану регістра - демонструє можливі переваги квантових операцій з q-бітами. При наборі початкового числа на класичному регістрі, що складається з n бітів, нам буде потрібно n операцій - на кожному біті встановити значення 0 або 1. При цьому         буде записано тільки одне число з довжиною n. При вчиненні n унітарних операцій з кожним q-бітом квантовому регістрі - пристрої, що складається, наприклад, з n ядерних спінів ми приготуємо когерентну суперпозицію всіх Q = 2n станів загальної системи квантового регістру. Тим самим ми приготуємо замість одного числа відразу 2n можливих значень регістру - когерентну суперпозицію всіх можливих для даного регістра чисел. Ця властивість може бути використано для квантових паралельних обчислень[11].   
2) Застосовуючи до приготованих станів унітарні перетворення, можна реалізувати власне квантовий процесор. Роль сполучень (проводів) в класичних комп'ютерах грають q-біти, а роль логічних блоків (гейтів), на які розбивається весь процес обчислень як в класичному, так і квантовому процесорі, - унітарні перетворення. Покажемо, як операторних формалізмом можна реалізувати такі логічні гейти, як NOT, CONTROLED NOT.
цей оператор діє на одиночний q-біт і змінює його стан:
  
Операція CONTROLED NOT (XOR гейт) подана в вигляді:
застосовувана до двох q-бітів, перший з яких не змінює стан під дією TXOR, а
другий змінює, але в залежності від стану першого q-біту. Наприклад,     

тобто операція TXOR трансформує суперпозиційні стани в переплутані і назад. Квантові логічні гейти, об'єднані разом і в певній послідовності, які діють на стани q-бітів, утворюють квантову мережу[12].
3) Операція виведення результату обчислення для класичного комп'ютера нічим не відрізняється від будь-якої іншої операції під час обчислень. Обчислення можуть бути зупинені в будь-якому місці, проміжні результати зчитані й обчислення продовжені.  Кінцевим результатом квантових обчислень є стан квантового регістра після зроблених унітарних перетворень, являють собою когерентну суперпозицію всіх можливих для даного регістра станів. Очевидно, що ми не можемо отримати всі амплітуди ймовірностей Сi в розкладанні цього суперпозиційного. Все, що ми можемо отримати від цього одиночного квантового об'єкта, що доступно нам згідно квантової теорії - квадратичні форми Σi,jСiСi*Rij, які відповідають виміру середнього значення якоїсь фізичної величини, якій відповідає оператор R. Причому, очевидно, що кінцевий результат квантових обчислень буде флуктувати від обчислення до обчислення. Тут використовуються спеціальні виправляючі коди. Однак навіть у таких умовах квантових невизначеностей квантові комп'ютери можуть дати суттєве прискорення обчислень деяких математичних задач.        
Тепер подивимося, як квантові обчислення можна реалізувати на практиці. У якості q-біта тут буде використана модель елементарної частинки зі спіном 1/2, такий, як, наприклад, протон. У цьому випадку можна розрізнити стан "спін вгору", позначаємо, як | 1>, і "спін вниз", що позначається як | 0>. Такий формалізм характерний для ядерного магнітного резонансу квантових комп'ютерів, які на сьогоднішній день вважаються перспективними. 
РОЗДІЛ 2
Квантова криптографія

Квантова криптографія - метод захисту комунікацій, який базується на певних явищах квантової фізики. На відміну від традиційної криптографії, яка використовує математичні методи, щоб забезпечити секретність інформації, квантова криптографія зосереджена на фізиці, розглядаючи випадки, коли інформація переноситься за допомогою об'єктів квантової механіки. Процес відправки та прийому інформації завжди виконується фізичними засобами, наприклад за допомогою електронів в електричному струмі, або фотонів в лініях волоконно-оптичного зв'язку. А підслуховування може розглядатися, як вимірювання певних параметрів фізичних об'єктів - у нашому випадку, носіїв інформації.
Технологія квантової криптографії спирається на принципову невизначеність поведінки квантової системи - неможливо одночасно отримати координати і імпульс частинки, неможливо виміряти один параметр фотона, не спотворивши інший. Це фундаментальне властивість природи у фізиці відомо як принцип невизначеності Гейзенберга, сформульований у 1927 р[13].
Використовуючи квантові явища, можна спроектувати і створити таку систему зв'язку, яка завжди може виявляти підслуховування. Це забезпечується тим, що спроба вимірювання взаємопов'язаних параметрів у квантовій системі вносить до неї порушення, руйнуючи вихідні сигнали, а значить, за рівнем шуму в каналі легітимні користувачі можуть розпізнати ступінь активності перехоплювача.
Один з надійних способів зберегти в таємниці телефонні розмови або передану по комп'ютерних мережах зв'язку інформацію - це використання квантової криптографії.
Ідея використовувати для цілей захисту інформації природу об'єктів мікросвіту - квантів світла (фотонів), поведінка яких підкоряється законам квантової фізики, стала найбільш актуальною.
Найбільше практичне застосування квантової криптографії знаходить сьогодні у сфері захисту інформації, переданої по волоконно-оптичних ліній зв'язку. Це пояснюється тим, що оптичні волокна ВОЛЗ дозволяють забезпечити передачу фотонів на великі відстані з мінімальними спотвореннями. В якості джерел фотонів застосовуються лазерні діоди передавальних модулів ВОЛЗ; далі відбувається істотне ослаблення потужності світлового сигналу - до рівня, коли середнє число фотонів на один імпульс стає багато менше одиниці. Системи передачі інформації з ВОЛЗ, в приймальному модулі яких застосовуються лавинні фотодіоди в режимі рахунку фотонів, називаються квантовими оптичними каналами зв'язку (КОКС).
Внаслідок малої енергетики сигналів швидкості передачі інформації в КОКС в порівнянні з можливостями сучасних ВОЛЗ не дуже високі (від кілобіт до мегабіт в секунду, в залежності від застосування). Тому в більшості випадків квантові криптографічні системи (ККС) застосовуються для розподілу ключів, які потім використовуються засобами шифрування високошвидкісного потоку даних. Важливо відзначити, що квантово-криптографічне обладнання поки серійно не випускається. Однак у міру вдосконалення і здешевлення застосовуваної елементної бази можна очікувати появи ККС на ринку телекомунікацій як, наприклад, додаткової послуги при побудові корпоративних волоконно-оптичних мереж.
Природа секретності квантового каналу зв'язку.
При переході від сигналів, де інформація кодується імпульсами, що містять тисячі фотонів, до сигналів, де середня кількість фотонів, що припадають на один імпульс, багато менше одиниці (порядку 0,1), вступають в дію закони квантової фізики. Саме на використанні цих законів у поєднанні з процедурами класичної криптографії заснована природа секретності ККС. Тут безпосередньо застосовується принцип невизначеності Гейзенберга, відповідно до якого спроба зробити вимірювання в квантовій системі спотворює її стан, і отримана в результаті такого виміру інформація не повністю відповідає стану до початку вимірювань.[14] Спроба перехоплення інформації з квантового каналу зв'язку неминуче призводить до внесення в нього перешкод, які виявляються легальними користувачами. КК використовують цей факт для забезпечення можливості двом сторонам, які раніше не зустрічалися і попередньо не обмінювалися ніякої секретною інформацією, здійснювати між собою зв'язок в обстановці повної секретності без остраху бути підслухати.
Принципи роботи ККС і перша експериментальна реалізація.
У 1984 році Ч. Беннетт (фірма IBM) і Ж. Брассард (Монреальський університет) запропонували просту схему захищеного квантового розподілу ключів шифрування. Ця схема використовує квантовий канал, по якому користувачі А і Б обмінюються повідомленнями, передаючи їх у вигляді поляризованих фотонів. Підслуховувальний їх зловмисник П може спробувати робити виміри цих фотонів, але він не може зробити це, не вносячи в них перекручування. А і Б використовують відкритий канал для обговорення та порівняння сигналів, переданих по квантовому каналу, перевіряючи їх на можливість перехоплення. Якщо при цьому вони не виявлять спотворень у процесі зв’язку, вони можуть отримати з отриманих даних інформацію, яка надійно розподілена, випадкова і секретна, незважаючи на всі технічні хитрощі та обчислювальні можливості, якими володіє П.
Схема працює в такий спосіб. Спочатку А генерує і посилає Б послідовність фотонів, поляризація яких обрано випадковим чином і може становити 0 °, 45 °, 90 ° або 135 °. Б приймає ці фотони і для кожного з них випадковим чином вирішує, заміряти його поляризацію як перпендикулярну або діагональну. Потім по відкритому каналу Б оголошує для кожного фотона, який тип вимірювань ним зроблено (перпендикулярний або діагональний), але не повідомляє результат цих вимірів, наприклад, 0 °, 45 °, 90 ° або 135 °. З цього ж відкритого каналу А повідомляє йому, чи правильний вид вимірів був обраний для кожного фотона. Потім А і Б відкидають всі випадки, коли Б зробив неправильні виміри або коли відбулися збої в його детекторах. Якщо квантовий канал не перехоплює, решта види поляризацій, які потім переводяться в біти, становитимуть сукупності поділену між А і Б секретну інформацію.
Наступне випробування на можливість перехоплення може здійснюватися користувачами А і Б по відкритому каналу шляхом порівняння і відкидання випадково вибраних ними підмножин отриманих даних. Якщо таке порівняння виявить наявність перехоплення, А і Б відкидають всі свої дані і починають з нової групи фотонів. В іншому випадку вони залишають колишню поляризацію, про яку не згадувалося по відкритому каналу, в якості секретної інформації про бітах, відомих тільки їм, беручи фотони з горизонтальною або 45-градусної поляризацією за двійковий нуль, а з вертикальною або 135-градусної поляризацією - за двійкову одиницю.
Згідно з принципом невизначеності, П не може заміряти як прямокутну, так і діагональну поляризації одного і того ж фотона. Навіть якщо він для будь-якого фотона справить неправильне вимірювання і перешле Б цей фотон відповідно до результату своїх вимірів, це неминуче внесе випадковість до первісної поляризацію, з якою він посилався А. У результаті з'являться помилки в одній четвертій частині бітів, складових дані Б , які були піддані перехопленню.
Більш ефективною перевіркою для А і Б є перевірка на парність, здійснювана з відкритого каналу. Наприклад, А може повідомити: "Я переглянув 1-й, 4-й, 5-й, 8-й, ... і 998-ї з моїх 1000 бітів даних, і вони містять парне число одиниць. Тоді Б підраховує кількість одиниць на тих же самих позиціях. Можна показати, що якщо дані у Б і А відрізняються, перевірка на парність випадкового підмножини цих даних виявить цей факт з ймовірністю 0,5 незалежно від числа і розташування помилок. Досить повторити такий тест 20 разів з 20 різними випадковими підмножинами, щоб зробити ймовірність невиявленої помилки дуже малою[15].
А і Б можуть також використовувати для корекції помилок коди, що виправляють помилки, обговорюючи результати кодування по відкритому каналі. Однак при цьому частина інформації може потрапити до П. Проте А і Б, знаючи інтенсивність спалахів світла і кількість виявлених та виправлених помилок, можуть оцінити кількість інформації, що потрапляє до П.
Знання П значної частини ключа може в багатьох випадках привести до розтину їм повідомлення. Беннетт і Брассард спільно з Ж. М. Робертом розробили математичний метод, званий посиленням секретності. Він полягає в тому, що при обговоренні по відкритому каналу з частини секретної бітової послідовності користувачі виділяють деяку кількість особливо секретних даних, з яких перехоплювач з великою ймовірністю не в змозі дізнатися навіть значення одного біта. Зокрема, було запропоновано використовувати деяку функцію зменшення довжини (функцію хешування). Після застосування цієї функції користувачами А і Б до наявних у них послідовностей бітів, часткова інформація перехоплювача про масиві їх даних перетворюється, практично за відсутності будь-якої інформації про вихідних даних функції.
Наприклад, якщо вхідна послідовність складається з 1000 біт, з яких П відомо більше 200, А і Б можуть виділити близько 800 особливо секретних бітів в якості вихідної послідовності. Серед таких вони можуть взяти будь-яку безліч таких бітів, які з найбільшою ймовірністю були ідентичні при проведенні ними вимірювань (при цьому їм слід зберігати в таємниці це відповідність, а не обговорювати його з відкритого каналу). Так, наприклад, А і Б можуть визначити кожен вихідний біт функції посилення секретності як парність незалежного публічно обумовленого випадкового набору бітів з повного масиву.
Відзначимо, що в якості відкритого каналу можуть використовуватися як звичайні лінії телефонного і радіозв'язку або локальні обчислювальні мережі, так і волоконно-оптична лінія зв'язку в стандартному режимі роботи.
У 1989 році в Дослідницькому центрі фірми IBM був побудований перший прототип КОКС, що містить передавальний модуль користувача А на одному кінці і прийомний модуль Б на іншому. Ця система розміщувалася на оптичній лаві довжиною близько 1 м у світлонепроникної кожусі. Квантовий канал представляв собою вільне повітряний простір завдовжки близько 30 см. Під час функціонування макет керувався від ПЕОМ, яка містила програмне уявлення користувачів А, Б і, крім того, можливого зловмисника П.
Ліва сторона передавального модуля А складається з діода, випромінюючого зелене світло, лінзи, булавочного отвори і фільтрів, які забезпечують пучок горизонтально поляризованого світла. Виходили імпульси з інтенсивністю 0,1 фотона на імпульс. Така низька інтенсивність прийнята для зведення до мінімуму можливості перехоплювача розділити окремий імпульс на два або більше фотонів. Потім розташовуються електрооптичні прилади, відомі як камери Покельса, які використовуються для зміни первісної горизонтальної поляризації в будь-яке з чотирьох стандартних поляризаційних станів, вибором яких управляє користувач А.
На протилежному кінці у приймальнику Б розташовується аналогічна камера Покельса, що дозволяє йому змінювати тип поляризації, яку приймач буде вимірювати. Після проходження через камеру Покельса пучок світла розщеплюється кальцитове призмою на два перпендикулярно поляризованих пучка, які направляються на два фотоелектронних помножувача з метою виділення окремих фотонів.
Сучасний стан робіт зі створення ККС.
За десять років, що минули з моменту створення першого прототипу КОКС, досягнутий величезний прогрес. Зараз квантове розподіл ключів по ВОЛЗ є можливим вже на відстані в десятки кілометрів.
Роботи в галузі квантової криптографії ведуться в багатьох країнах. У Росії, наприклад, цими питаннями активно займаються в Державному університеті телекомунікацій (Санкт-Петербург). У США в Лос-Аламоської національної лабораторії створена лінія зв'язку загальною довжиною 48 км, в якій здійснюється розподіл ключів зі швидкістю в кілька десятків Кбіт / с, а в університеті Дж. Гопкінса реалізована локальна обчислювальна мережа з квантовим каналом зв'язку довжиною 1 км, в якій досягнута швидкість передачі 5 кбіт / с. У Великобританії, в Оксфордському університеті, реалізований цілий ряд макетів квантово-криптографічних систем з використанням різних методів модуляції і детектування оптичних сигналів, а в лабораторії фірми British Telecom отримана найбільша довжина КОКС - 30 км при швидкості передачі близько 10 кбіт / с. У 1997 році була доведена можливість істотного підвищення швидкостей передачі - до рівня 1 Мбіт / с і більше.
ККС спочатку використовувалися для зв'язку окремих пар користувачів, але практичні застосування вимагають зв'язків з багатьма користувачами. І не так давно були запропоновані реалізації ККС для оптичних мереж зв'язку різної топології.
Розглянемо, як КК може застосовуватися до випадку пасивної оптичної мережі, що містить центральний мережевий контролер А, пов'язаний у вигляді пасивного оптичного світлоподілювача з безліччю мережних користувачів (Бi). У цій схемі просто використовується квантове поведінка оптичного світлоподілювача. Одиночний фотон в світлоподілювача не може розділятися, а, навпаки, направляється по одному (і тільки одному) з шляхів. Вибір шляху для кожного окремого фотона довільний і непередбачуваний. Отже, якщо стандартний протокол квантової передачі застосовується в мережі зі світлоподілювача, то кожен користувач буде забезпечений унікальним довільно обраним підмножиною бітів. З послідовності, яка передається в мережі, центр А може, виконуючи відкрите обговорення після передачі з кожним користувачем по черзі, ідентифікувати, які фотони були розділені з кожним з них, і створити з кожним секретний і унікальний індивідуальний ключ. Таким чином, мережа може бути надійно захищена, тому що, хоча шифрована інформація передається відкрито по мережі, А і Б можуть бути впевнені, що ніякий інший мережевий користувач або зовнішній зловмисник не отримав ніяких відомостей щодо їх загального ключа. Ця схема розподілу ключів корисна, наприклад, для забезпечення роботи користувачів з захищеною базою даних.
          Основні зусилля тепер спрямовані на те, щоб зробити використання квантового каналу економічно ефективним. Більшість схем КОКС вимагають постійної підлаштування та управління на кожній стороні каналу зв'язку, що здорожує систему. Проте нещодавно в Женевському університеті була запропонована реалізація КОКС, що не вимагає ніякої підстроювання, крім синхронізації. Експериментальні результати підтверджують, що подібні схеми дійсно багатообіцяючі для практичних реалізацій квантового каналу. Застосування в них так званих "дзеркал Фарадея" призводить до того, що всі світлові імпульси проходять однаковий шлях, тому, на відміну від звичайних схем, не потрібно ніякої підстроювання. Для організації квантового каналу необхідно просто підключити приймальний і передавальний модулі в кінці ВОЛЗ, синхронізувати сигнали і почати передачу. Саме тому цю систему називають системою Plug and Play ("підключай і працюй"). В експерименті швейцарських дослідників каналом зв'язку був підводний кабель довжиною 23 км, використовуваний для передачі даних між Ніоні та Женевою. Однак швидкості передачі інформації, отримані в даній системі, низькі для практичних додатків, і зараз ведеться доопрацювання схеми, щоб досягти більш конкурентоспроможних результатів.
Протоколи для квантово-криптографічних систем розподілу ключової інформації.
   Алгоритмічна частина ККС складається з стека протоколів, реалізація якого дозволяє законним користувачам забезпечити формування спільного ключа за умови витоку до зловмиснику не більше заданої кількості інформації або відмова від даного сеансу при невиконанні цієї умови.
У стек протоколів входять наступні елементи:
·       Протокол первинної квантової передачі.
·       Протокол виправлення помилок в бітових послідовностях, отриманих в результаті квантової передачі.
·       Протокол оцінки витоку до зловмиснику інформації про ключі.
·       Протокол посилення секретності та формування підсумкового ключа.
Кроки первинного протоколу квантової передачі залежить від типу оптичної схеми, використаної для створення квантового оптичного каналу зв'язку, і виду модуляції квантових станів. Приклад протоколу квантової передачі для КОКС з модуляцією поляризації фотонів по чотирьох станів був коротко описаний вище. Після реалізації такого протоколу користувачі A і Б будуть мати в основному збігаються послідовності, причому довжини цих послідовностей будуть близькі до половини довжини послідовності переданих фотонних імпульсів.
   Прикладом протоколу виправлення помилок в бітових послідовностях, отриманих після виконання первинного протоколу, є спосіб корекції помилок, що складається в тому, що блок даних, який повинен бути узгоджений між користувачами, розглядається як інформаційний блок деякого коду. Перевірочні символи цього коду можуть бути передані по відкритому каналу зв'язку і використані для виправлення або виявлення помилок у блоці. Для того щоб зловмисник не міг отримати додаткову інформацію з перевірочним символів, з інформаційного блоку виключається кілька певних бітів. Коди і безлічі відкидаємо бітів повинні бути вибрані так, щоб виконувалося вимога про не зростанню кількості інформації у зловмисника. Після застосування протоколу виправлення помилок легальні користувачі будуть мати однакові бітові послідовності і можуть оцінити ступінь втручання зловмисника в квантовому каналі зв'язку.
   Для цього реалізується протокол оцінки витоку інформації про ключі при перехоплення даних в квантовому каналі. У ньому користувач Б по заданій довжині витоку інформації до зловмисника визначає максимально можливу довжину ключа, при якій хешування даних після виправлення в них помилок до ключа необхідної довжини забезпечить виконання заданого вимоги стійкості. Якщо ця максимальна довжина виявляється припустимою, то сеанс зв'язку приймається для формування ключа, в іншому випадку він відкидається.
   У тому випадку, коли при реалізації попереднього протоколу робиться висновок про допустимість даного сеансу зв'язку, виконується протокол посилення секретності та формування підсумкового ключа - обидва користувачі застосовують до узгоджених після виправлення помилок даними хешуючу функцію (що перемішує і стискуюче перетворення), яка відображає ці дані в ключ . Функція вибирається одним з користувачів випадковим чином і передається іншому по відкритому каналу зв'язку.
         По-перше, тому, що сучасні схеми шифрування використовують ключ порядку одиниць кілобіт або менше для шифрування досить великих обсягів інформації, і ефективний спосіб розподілу ключа зі швидкістю порядку десятків кілобіт в секунду може бути більш ніж адекватний для багатьох потенційних застосувань.
По-друге, тому, що створення захищених з використанням методів квантової криптографії оптичних корпоративних і локальних мереж різних топологій є технічно цілком здійсненним завданням.
Об'єктивності заради відзначимо, що на сьогодні при використанні методів криптографії є можливість захищеної від підслуховування передачі інформації на відстань у кілька десятків кілометрів. При великих довжинах ліній зв'язку класичні методи розподілу ключів та захисту інформації виявляються поки що більш дешевими і надійними.
   Останнім часом з'явилися нові теоретичні ідеї для створення глобальних розподілених квантових криптографічних мереж. Вони засновані на використанні безпечної передачі інформації так званих квантових кореляцій між двома частинками, мають некласичні властивості, а також на використанні для зберігання цих частинок квантової пам'яті. Крім того, з'явилися повідомлення про експерименти з реалізації ККС для захисту каналів зв'язку між космічними апаратами і земними станціями.
Криптографія сьогодні - це найважливіша частина всіх інформаційних систем: від електронної пошти до стільникового зв'язку, від доступу до мережі Internet до електронної готівки. Криптографія забезпечує підзвітність, прозорість, точність і конфіденційність. Вона запобігає спробам шахрайства в електронній комерції і забезпечує юридичну силу фінансових транзакцій. Криптографія допомагає встановити вашу особистість, але і забезпечує вам анонімність. Вона заважає хуліганам зіпсувати сервер і не дозволяє конкурентам залізти у ваші конфіденційні документи. А в майбутньому, в міру того як комерція і комунікації будуть все тісніше зв'язуватися з комп'ютерними мережами, криптографія стане життєво важливою.
   Але присутні на ринку криптографічні засоби не забезпечують того рівня захисту, який обіцяний в рекламі. Більшість продуктів розробляється і застосовується аж ніяк не у співробітництві з криптографами. Цим займаються інженери, для яких криптографія - просто ще один компонент програми. Але криптографія - це не компонент. Не можна забезпечити безпеку системи, "вставляючи" криптографію після її розробки. На кожному етапі, від задуму до інсталяції, необхідно усвідомлювати, що і навіщо ви робите.
   Для того, щоб грамотно реалізувати власну криптосистему, необхідно не тільки ознайомиться з помилками інших і зрозуміти причини, за якими вони відбулися, але і, можливо, застосовувати особливі захисні прийоми програмування і спеціалізовані засоби розробки.
   На забезпечення комп'ютерної безпеки витрачаються мільярди доларів, причому велика частина грошей викидається на негідні продукти. На жаль, коробка із слабким криптографічним продуктом виглядає так само, як коробка із стійким. Два криптопакета для електронної пошти можуть мати схожий користувальницький інтерфейс, але один забезпечить безпеку, а другий допустить підслуховування. Порівняння може вказувати подібні риси двох програм, але в безпеці одній з них при цьому зяють дірки, яких позбавлена ​​інша система. Досвідчений криптограф зможе визначити різницю між цими системами. Те ж саме може зробити і зловмисник.
   На сьогоднішній день комп'ютерна безпека - це картковий будиночок, який у будь-яку хвилину може розсипатися. Дуже багато слабких продуктів до тепер не були зламані тільки тому, що вони мало використовуються. Як тільки вони розкрутяться, вони стануть притягати до себе злочинців. Преса відразу ж додасть розголосу ці атаки, підірвавши довіру публіки до цих криптосистемам. Врешті-решт, перемогу на ринку криптопродуктів визначить ступінь безпеки цих продуктів.

















РОЗДІЛ 3
Алгоритми квантових комп’ютерів
У цьому розділі готові алгоритми квантових обчислень для вирішення конкретних математичних задач у яких квантові комп'ютери мають переваги над класичними. Це алгоритм Шора - завдання факторизації великого N-значного числа. Інший алгоритм Гровера – задача повного перебору.
Алгоритм Гровера. Розглянемо задачу повного перебору. Зі списку N предметів потрібно визначити один, що задовольняє будь-якого специфічного властивості. Будь-який класичний алгоритм, імовірнісний або детермінований, повинен буде досліджувати, принаймні, N/2 предметів, щоб досягти успіху з ймовірністю 1/2. Квантові комп'ютери можуть перебувати в стані суперпозиції, завдяки чому можуть досліджувати велику кількість предметів одночасно. Недавно було показано, що квантовий комп'ютер міг дослідити список менше ніж за N кроків. Цей результат викликав значний інтерес, оскільки існує багато проблем, що вирішуються повним перебором, наприклад робота з невпорядкованими базами даних. Ще один цікавий приклад переваги алгоритму Гровера над алгоритмами класичними. Широко використовуваний стандарт шифрування даних використовує 56-бітний ключ. Щоб його зламати потрібно підібрати ключ з 256=7×1016 можливих ключів. Класичні методи дозволяють зробити це приблизно за 3,5х1016 число випробувань, що вимагає часу більше, ніж 1000 років.[16] Квантовому алгоритму потрібно всього близько 200 мільйонів випробувань, що у часовому еквіваленті є менше, ніж 4 хвилини. Перевага очевидна. 
Класичні алгоритми не можуть бути покращені за рахунок винаходу будь-яких нових, ефективних алгоритмів. Ці нові алгоритми все одно будуть мати потребу в середньому в N/2 числі випробувань, тому перевага алгоритму Гровера буде зберігатися. 
Комп'ютер, працюючи за алгоритмом Гровера, починає дослідження з приведення досліджуваної системи до стану суперпозиції всіх N можливих рішень, що дозволяє дослідити всі N предметів одночасно. Далі, що чергуються послідовності комбінацій фазового обертання і квантової дифузії працюють так, щоб привести систему до стану, близького до чистого, рекурентного стану. Фазовим обертанням виділяється стан, що відповідає необхідному вирішенню; дифузія, приводячи амплітуду всіх станів до суперпозиції, забирає частину її у всіх станів і передає її необхідному рішенню, забезпечуючи гарантоване накопичення амплітуди в цьому стані. Після визначеного числа таких повторень з'являється можливість визначити необхідний елемент з високою ймовірністю. Процедура виділення зі списку потрібного елемента для наочності показана на рис. 15
Рис.2. Дією квантового алгоритму пошуку: ймовірність бажаного стану посилюється за рахунок зменшення інших. 

Точне число повторень, що оптимізують амплітуду стану вирішення, було визначене Бассардом і його колегами. Вони показали, що кожне повторення відповідає обертанню на кут θ, де sinθ = 1 /
N і кут π / 4 відповідає бажаного рішення. Для великих N після πN/ 4 числа повторень ймовірність отримання неправильного результату менше ніж 1 / N. Однак якщо збільшувати число повторень, то ймовірність успіху починає спадати[17].
Розглянемо покрокову дію алгоритму Гровера. 
Кроки алгоритму. 
1) Початковий стан системи описується як суперпозиція: 
(1 N 1, N 1 ,..., N), тобто у кожному стані одна і та ж амплітуда.        Це досягається застосуванням Н.
Якщо, біт знаходиться в стані "0", то після впливу даної операції він переходить в суперпозицію двох станів ; якщо біт в "1", то в суперпозицію . Видно, що амплітуда в кожному стані одна і та ж , але в "1" стані фаза інвертований. Досягається це за О (журнал N) кроків
2) Крок, в якому такі унітарні операції повторюються О (N) разів. 
а) Якщо C (S) = 1, повертаємо фазу на π радіан.    
Якщо C (S) = 0 операція не проводиться.       
б) Дифузійне перетворення з використанням матриці D, яку можна представити, як добуток 3-х операторів D = WRW; де: 
 якщо  і     
W-матриця перетворення Волш-Хадамарда; 
,
 добуток двох n-бітних строк і і j     
R – матриця обертання :      
 якщо  і  якщо i=0;                
 якщо        
Докладно про дані операціях в [3,4,7,8]. 
      
3) Вимірюємо отриманий стан. Це буде стан
якщо  з імовірністю не менш 
0,5. 
Крок 2) є серцем АГ. Кожна ітерація в цьому кроці підвищує амплітуду бажаного стану і в результаті
 повторень, амплітуда ймовірності цього стану прямує до .     
 
Описані кроки алгоритму Гровера можна представити як показано на рис. 4. 
Рис. 3. 1) Ініціалізація. Комп'ютер приводить систему в стан суперпозиції всіх можливих рішень від 1 до N. Це робиться таким чином: N кубітів представляють N=2n можливих рішень, по черзі, незалежно один від одного, приводиться до суперпозиції .   
2)
Фазове обертання. Для кожного стану |r> комп'ютер перевіряє, чи є знайдений елемент у записуваної г базі даних. Якщо це так, то 
фаза стану змінюється на π. 
Це аналогічно множенню правильного |m> стану на -1. Комп'ютер може робити це для всіх N станів в суперпозиції за один крок.    3) Дифузія. Цей крок має сенс «інверсії відносно середнього»: стан з амплітудою π відображається сам в себе з амплітудою 2А-w, де
А -
 середня амплітуда (включаючи фазу) N станів.[18] На першій ілюстрації рис.2 середня амплітуда трохи менша ніж . Інверсія щодо середнього дзеркально відображає амплітуду стану правильного m до трохи меншого, ніж , а амплітуди неправильних станів трохи зменшуються. 
Алгоритм Шора. Завдання факторизації - задача про знаходження простих співмножників. Як приклад: завдання обчислення добутку двох простих чисел, скажімо 521 та 809, не викликає ніяких труднощів (521 × 809 = 421 489). Однак зворотна задача: знаходження простих співмножників числа 421489, потребує певного часу. Відомо що це час (при використанні відомих тепер класичних алгоритмів) зростає із зростанням довжини n числа, яке факторизується, як          . Досягнення Шора в тому, що він знайшов алгоритм, що зменшує зростання цього часу до поліноміального (n2)[19].   
         Алгоритм рішення задачі факторизації спирається на звідність її до знаходження періоду допоміжної функції. Такою функцією є залишок від ділення ступеневій функції ха на ціле число
N:
Ми хочемо факторизувати число N. Достатньо знайти хоча б один множник, так, як потім ми можемо звести задачу до більш простої. Перш за все, виберемо число х. За допомогою алгоритму Евкліда можна ефективно обчислити загальні множники в N і х.
ВИСНОВОК

В даній курсовій роботі розглянуто основні питання по квантових обчисленнях та комп'ютерах.
Розглянуто квантову криптографію, порівняння їх з класичними комп’ютерами. Розглянуто перспективи розвитку і сьогодення для цих всіх систем.
         Описано готові алгоритми квантових обчислень для вирішення
конкретних математичних задач у яких квантові комп'ютери мають переваги над класичними. Це алгоритм Шора - завдання факторизації великого N-значного числа. Інший алгоритм Гровера – задача повного перебору.
Описана робота квантового комп’ютера, її етапи виконання.
Проте, незважаючи на всю цю бурхливу діяльність, схоже, що перші корисні результати з’являться не скоро. 

1 коментар: