МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Державні освітні установи
Реферат
Квантові обчислення
2009
Зміст
Введення
Глава I. Основні поняття квантової механіки
Глава II. Основні поняття і принципи квантових обчислень
Глава III. Алгоритм Гровера
Висновок
Список літератури
Введення
Уявіть собі комп'ютер, пам'ять якого експоненціально більше, ніж можна було б очікувати, оцінюючи його явний фізичний розмір; комп'ютер, який може оперувати одночасно з експоненціально великим набором вхідних даних; комп'ютер, який проводить обчислення в туманному для більшості з нас гільбертовому просторі.
Тоді ви думаєте про квантовий комп'ютер.
Ідея обчислювального пристрою, заснованого на квантовій механіці, вперше розглядалася ще в ранніх 1970-х роках і ранніх 1980-х фізиками і комп'ютерними вченими, такими, наприклад, як Чарльз Х. Беннет з IBM Thomas J. Watson Research Center, Пол А. Беніофф з Аргоннської національної лабораторії в Іллінойсі, Девідом Дойчем з Оксфордського університету, і пізніше Річардом П. Фейнманом з з Каліфрнійского технологічного інституту (Калтех). Ідея виникла тоді, коли вчені зацікавилися фундаментальними обмеженнями обчислень. Вони зрозуміли, що якщо технологія буде продовжувати дотримуватися поступового зменшення розмірів обчислювальних мереж упакованих у кремнієві чіпи, то це призведе до того, що індивідуальні елементи стануть не більше ніж кілька атомів. Тоді виникла проблема, тому що на атомному рівні діють закони квантової фізики, а не класичної. А це підняло питання, чи можна сконструювати комп'ютер, заснований на принципах квантової фізики.
Фейнман одним з перших спробував дати відповідь на це питання. У 1982р. він запропонував модель абстрактної квантової системи, придатної для обчислень. Він також пояснив, як така система може бути симулятором у квантовій фізиці. Іншими словами, фізики могли б проводити обчислювальні експерименти на такому квантовому комп'ютері.
Пізніше, в 1985 році, Дойч усвідомив, що затвердження Фейнмана могло б, врешті-решт, привести до квантовому комп'ютера загального призначення, і опублікував найважливішу теоретичну роботу, яка показує, що будь-який фізичний процес може в принципі бути промодельований на квантовому комп'ютері.
На жаль, все, що тоді змогли придумати, було кілька досить надуманих математичних задач, до тих пір, поки Шор випустив в 1994 році свою роботу, в якій представив алгоритм рішення на квантовому комп'ютері однієї важливої задачі з теорії чисел, а саме, розкладання на прості множники. Він показав, як набір математичних операцій, сконструйованих спеціально для квантового комп'ютера, може факторізовать (розкласти на прості множники) величезні числа фантастично швидко, значно швидше, ніж на звичайних комп'ютерах. Це був прорив, який перевів квантові обчислення з розряду академічного інтересу в розряд завдання, цікавою для всього світу.
Глава I. Основні поняття квантової механіки
У кінці 19 століття серед учених було широко поширена думка, що фізика - наука «практично завершена» і для повної її «завершеності» залишилося зовсім небагато: пояснити структуру оптичних спектрів атомів і спектральний розподіл теплового випромінювання. Оптичні спектри атома виходять при випущенні або поглинанні світла (електромагнітних хвиль) вільними або слабо пов'язаними атомами; такими спектрами мають, зокрема, одноатомні гази і пари.
Теплове випромінювання - це механізм перенесення тепла між просторово розділеними частинами тіла за рахунок електромагнітного випромінювання.
Однак початок 20 століття привело до розуміння того, що ні про яку «завершеності» не може бути й мови. Ставало ясним, що для пояснення цих та багатьох інших явищ потрібно кардинальним чином переглянути уявлення, що лежать в основі фізичної науки.
Наприклад, виходячи з хвильової теорії світла, виявилося неможливим дати вичерпне пояснення всієї сукупності оптичних явищ.
При вирішенні проблеми спектрального складу випромінювання німецьким фізиком Максом Планком у 1900 році було висловлено припущення про те, що випромінювання і поглинання світла речовиною відбувається кінцевими порціями, або квантами. При цьому енергія фотона - кванта електромагнітного випромінювання (у вузькому сенсі - світла) визначається виразом
,
Де - Частота випромінюваного (або поглинається) світла, а
- Універсальна стала, яка називається тепер постійної Планка.
Часто використовується постійна Дірака
Тоді енергія кванта виражається як , Де
- Кругова частота випромінювання.
Суперечності між розглядом світла як потоку заряджених частинок і як хвилі призвело до поняття корпускулярно-хвильового дуалізму.
З одного боку, фотон демонструє властивості електромагнітної хвилі в явищах дифракції (огинання хвилями перешкод, порівнянних з довжиною хвилі) і інтерференції (накладення хвиль з однаковою частотою і з однаковою початковою фазою) у масштабах, порівнянних з довжиною хвилі фотона. Наприклад, одиночні фотони, що проходять через подвійну щілину, створюють на екрані інтерференційну картину, яку можна описати рівняннями Максвелла. Тим не менше, експеримент показує, що фотони випромінюються й поглинаються цілком об'єктами, розміри яких багато менше довжини хвилі фотона (наприклад, атомами), або, взагалі, в деякому наближенні можуть вважатися точковими (наприклад, електрон), тобто ведуть себе як частки - корпускули. У навколишньому макросвіті існує два фундаментальних способу передачі енергії та імпульсу між двома точками простору: безпосереднє переміщення матерії в однієї точки в іншу і хвильової процес передачі енергії без перенесення речовини. Всі носії енергії тут строго розділені на корпускулярні і хвильові. Навпаки, у мікросвіті такого поділу не існує. Всім часткам, а зокрема і фотонів, приписуються одночасно і корпускулярні, і хвильові властивості. Ситуація ненаглядного. Це об'єктивна властивість квантових моделей.
Майже монохроматичне випромінювання з частотою випускається джерелом світла, можна уявити собі що складається з «пакетів випромінювання», які ми називаємо фотонами. Монохроматичне випромінювання - володіє дуже малим розкидом частот, в ідеалі - однією довжиною хвилі.
Поширення фотонів у просторі правильно описується класичними рівняннями Максвелла. При цьому кожен фотон вважається класичним цугом хвиль, певним двома векторними полями - напруженістю електростатичного поля і індукцією магнітного поля
. Цуг хвиль - це ряд збурень з перервами між ними. Випромінювання окремого атома не може бути монохроматичним, тому що випромінювання триває кінцевий проміжок часу, маючи періоди наростання і згасання.
Неправильно інтерпретувати суму квадратів амплітуд і
як щільність енергії в просторі, в якому рухається фотон; замість цього кожну величину, квадратично залежить від амплітуди хвилі слід інтерпретувати як величину пропорційну ймовірності якого-небудь процесу. Скажімо,
не дорівнює енергії, що вноситься фотоном в цю область, а пропорційний ймовірності виявити фотон в цій області.
Енергія, передана в будь-якому місці простору фотоном, завжди дорівнює . Тим самим
де
- Ймовірність перебування фотона в даній області, а
- Число фотонів.
У 1921 році досвідом Штерна-Герлаха було підтверджено наявність у атомів спина і факт просторового квантування напрями їх магнітних моментів (від англ. Spin - обертатися, крутитися.). Спін-власний момент кількості руху елементарних частинок, має квантову природу і не пов'язаний з переміщенням частинки як цілого. При введенні поняття спина передбачалося, що електрон можна розглядати як «обертається дзига», а його спін - як характеристику такого обертання. Спіном називають також власний момент імпульсу атомного ядра чи атома; в цьому випадку спін визначається як векторна сума (обчислена за правилами складання моментів у квантовій механіці) спінів елементарних частинок, що утворюють систему, і орбітальних моментів цих частинок, обумовлених їх рухом всередині системи.
Спін вимірюється в одиницях (наведених постійних Планка, або постійних Дірака) і дорівнює , Де J - характерне для кожного сорту частинок ціле (у т. ч. нульове) або напівцілим позитивне число - спінове квантове число, яке зазвичай називають просто спіном (одне з квантових чисел). У зв'язку з цим говорять про цілому або напівцілим спині частинки. Однак не слід плутати поняття спін і спінове квантове число. Спіновое квантове число - це квантове число, що визначає величину спина квантової системи (атома, іона, атомного ядра, молекули), тобто її власного (внутрішнього) моменту імпульсу. Проекція спина на будь-яке фіксоване напрямок z в просторі може приймати значення J, J-1, ...,-J. Т. о., частка зі спіном J може перебувати в 2J + 1 спінових станах (при J = 1 / 2 - у двох станах), що еквівалентно наявності у неї додаткової внутрішньої міри свободи.
Ключовим елементом квантової механіки є принцип невизначеності Гейзенберга, який говорить про те, що не можна одночасно точно визначити положення частинки в просторі і її імпульс. Цей принцип пояснює квантування світла, а також пропорційну залежність енергії фотона від його частоти.
Рух фотона можна описати системою рівнянь Максвелла, у той час як рівняння руху будь-якої іншої елементарної частинки типу електрона описується рівнянням Шредінгера, яке більш загальне.
Система рівнянь Максвелла інваріантна щодо перетворення Лоренца. Перетвореннями Лоренца в спеціальній теорії відносності називаються перетворення, яким піддаються просторово-часові координати (x, y, z, t) кожної події при переході від однієї інерціальної системи відліку до іншої. По суті, ці перетворення є перетворення не тільки в просторі, як перетворення Галілея, але і в часі.
Глава II. Основні поняття і принципи квантових обчислень
Хоча комп'ютери стали компактними і значно швидше, ніж раніше, справляються зі своїм завданням, саме завдання залишається колишньою: маніпулювати послідовністю бітів і інтерпретувати цю послідовність як корисний обчислювальний результат. Біт - це фундаментальна одиниця інформації, зазвичай надається як 0 або 1 у вашому цифровому комп'ютері. Кожен класичний біт фізично реалізується макроскопічної фізичної системою, такий як намагніченість на жорсткому диску або заряд конденсатора. Наприклад, текст, складений з n символів, і збережений на жорсткому диску типового комп'ютера, описується рядком з 8n нулів та одиниць. Тут і лежить фундаментальна відмінність між вашим класичним комп'ютером і квантовим комп'ютером. У той час як класичний комп'ютер підпорядковується добре зрозумілим законам класичної фізики, квантовий комп'ютер це пристрій, який використовує квантово-механічні явища (особливо квантову інтерференцію), щоб здійснювати абсолютно новий спосіб обробки інформації.
У квантовому комп'ютері фундаментальна одиниця інформації (звана квантовий біт або кубіт), не двійкова, а скоріше четверичная за своєю природою. Це властивість кубіта виникає як прямий наслідок його підпорядкованості законам квантової механіки, які радикально відрізняються від законів класичної фізики. Кубіт може існувати не тільки в стані, відповідному логічним 0 або 1, як класичний біт, але також у станах, відповідних смеслі або суперпозиції цих класичних станів. Іншими словами, кубіт може існувати як нуль, як одиниця, і як одночасно 0 і 1. При цьому можна вказати певний чисельний коефіцієнт, що представляє ймовірність опинитися в кожному стані.
Ідеї про можливість побудови квантового комп'ютера сходять до робіт Р. Фейнмана 1982 - 1986 рр.. Розглядаючи питання про обчислення еволюції квантових систем на цифровому комп'ютері, Фейнман виявив "не вирішується," цього завдання: виявляється, що ресурси пам'яті та швидкодії класичних машин недостатні для вирішення квантових завдань. Наприклад, система з n квантових частинок з двома станами (спини 1 / 2) має 2 n базисних станів; для її опису необхідно задати (і записати в пам'ять ЕОМ) 2 n амплітуд цих станів. Відштовхуючись від цього негативного результату, Фейнман висловив припущення, що, ймовірно, "квантовий комп'ютер" буде мати властивості, які дозволять вирішувати на ньому квантові завдання. [3]
"Класичні" комп'ютери побудовані на транзисторних схемах, що володіють нелінійними залежностями між вхідними і вихідними напругами. По суті, це бістабільні елементи; наприклад, при низькому вхідній напрузі (логічний "0") вхідний напруга висока (логічна "1"), і навпаки. Такий бістабільної транзисторної схемою в квантовому світі можна зіставити дворівневу квантову частинку: станом припишемо значення логічного
, Станом
,
- Значення логічної
. Переходам
в бістабільної транзисторної схемою тут будуть відповідати переходи з рівня на рівень:
. Проте квантовий бістабільний елемент, який отримав назву кубіт, має новий, в порівнянні з класичним, властивістю суперпозиції станів: він може бути в будь-якому суперпозіціонном стані
, Де
- Комплексні числа,
. Стану квантової системи з п дворівневих частинок мають у загальному випадку вид суперпозиції
2 n базових стані
. У кінцевому рахунку квантовий принцип суперпозиції станів дозволяє надати квантовому комп'ютера принципово нові "здібності".
Доведено, що квантова ЕОМ може бути побудована лише з двох елементів (вентилів): однокубітового елемента і двокубітових елемента контрольоване НЕ (CNOT). Матриця 2x2 елемента
має вигляд:
(1)
Вентиль описує поворот вектора стану кубіта від осі z до полярної осі, заданої кутами
. Якщо
- Ірраціональні числа, то багаторазовим застосуванням
вектору стану можна надати будь-яку наперед задану орієнтацію. Саме в цьому полягає "універсальність" однокубітового вентиля у формі (1). В окремому випадку отримуємо однокубітовий логічний елемент НЕ (NOT): НЕ
=
, НЕ
=
. При фізичній реалізації елемента НЕ необхідно впливати на квантову частку (кубіт) імпульсом ззовні, що переводять кубіт з одного стану в інший. Вентиль контрольоване НЕ виконують, впливаючи на два взаємодіючих між собою кубіта: при цьому за допомогою взаємодії один кубіт контролює еволюцію іншого. Переходи під впливом зовнішніх імпульсів добре відомі в імпульсній магніторезонансної спектроскопії. Вентиль НЕ відповідає перевороту спина
під дією імпульсу
(Обертання намагніченості навколо осі
на кут
). Вентиль CNOT виконується на двох спинах 1 / 2 з гамильтонианом
(Спін
контролює
). CNOT виконується в три кроки: імпульс
+ Вільна прецесія протягом часу
- Імпульс
. Якщо
(Контролюючий кубіт в стані
), То при зазначених впливах контрольований кубіт здійснює переходи
(Або
). Якщо ж
(Контролюючий кубіт в стані
), То результат еволюції контрольованого кубіта буде іншим:
(
). Таким чином, спін
, Еволюціонує по-різному при
:
тут в
- Стан контролюючого кубіта. [4]
При розгляді питання про реалізацію квантового комп'ютера на тих чи інших квантових системах в першу чергу досліджують реалізованість і властивості елементарних вентилів НЕ і контрольоване НЕ.
Для подальшого корисно також ввести однокубітовое перетворення Адамара:
У техніці магнітного резонансу ці вентилі здійснюються імпульсами :
Адамара:
Схема квантового комп'ютера представлена на малюнку. До початку роботи комп'ютера всі кубіти (квантові частинки) повинні бути приведені у стан , Тобто в основний стан. Це умова саме по собі не тривіально.
Воно вимагає чи глибокого охолодження (до температур порядку міллікельвіна), або застосування методів поляризації. Систему п кубітів у стані можна вважати регістром пам'яті, приготованим для запису вхідних даних та проведення обчислень. Крім цього регістра звичайно припускають існування додаткових (допоміжних) регістрів, необхідних для запису проміжних результатів обчислень. Запис даних здійснюється шляхом того чи іншого впливу на кожен кубіт комп'ютера. Приймемо, наприклад, що над кожним кубітом регістру відбувається перетворення Адамара:
(2)
У результаті система перейшла в стан суперпозиції з 2 п базисних станів з амплітудою 2 - n / 2. Кожне базисне стан представляє собою двійкове число від
до
. Горизонтальні лінії на малюнку позначають осі часу.
Виконання алгоритму здійснюється шляхом унітарного перетворення
суперпозиції
.
являє собою унітарну матрицю розмірності 2 п. При фізичному здійсненні за допомогою імпульсних впливів на кубіти ззовні матриця
повинна бути представлена як векторний добуток матриць розмірності 2
і
. Останні можуть бути виконані послідовним впливом на одиничні кубіти
або пари кубітів
:
(3)
Кількість співмножників в цьому розкладанні визначає тривалість (і складність) обчислень . Всі
в (3) виконуються з використанням операцій NOT, CNOT, Н (або їх різновидів).
Чудово, що лінійний унітарний оператор діє одночасно на всі члени суперпозиції
(4)
Результати обчислення записуються в запасному регістрі, який перед застосуванням
перебував у стані
. За один прогін обчислювального процесу ми отримуємо значення шуканої функції f при всіх значеннях аргументу х = 0 ,..., 2 п - 1. Цей феномен отримав назву квантового паралелізму.
Вимірювання результату обчислень зводиться до проектування вектора суперпозиції в (4) на вектор одного з базисних станів :
(5)
Тут проступає одне зі слабких місць квантового комп'ютера: число в процесі вимірювання "випадає" за законом випадку. Щоб знайти
при заданому
, Треба багато разів провести обчислення і вимірювання, поки випадково не випаде
.
При аналізі унітарної еволюції квантової системи, що здійснює обчислювальний процес, виявляється важливість фізичних процесів типу інтерференції. Унітарні перетворення відбуваються в просторі комплексних чисел, додавання фаз цих чисел носить характер інтерференції. Відома продуктивність перетворень Фур'є в явищах інтерференції та спектроскопії. Виявилося, що і в квантових алгоритмах незмінно присутні перетворення Фур'є. Перетворення Адамара є найпростішим дискретним фур'є-перетворенням. Вентилі типу NOT і СNOT можуть бути здійснені безпосередньо на інтерферометрі Маха-Зендер з використанням явища інтерференції фотона і обертання його вектора поляризації.
Досліджуються різні шляхи фізичної реалізації квантових комп'ютерів. Модельні експерименти по квантовому комп'ютингу виконані на імпульсному ядерному магнітно-резонансному спектрометрі. У цих моделях працювало два або три спина (кубіта), наприклад два спина ядер 13 С і один спін протона у молекулі трихлоретилену
Однак у цих дослідах квантовий комп'ютер був "ансамблевим": вихідні сигнали комп'ютера складені великим числом молекул в рідкому розчині (~ 10 20).
До теперішнього часу висловлені пропозиції про реалізацію квантових комп'ютерів на іони і молекулах в пастках у вакуумі, на ядерних спинах у рідинах (див. вище), на ядерних спинах атомів 31 Р в кристалічному кремнії, на спинах електронів у квантових точках, створених у двовимірному електронному газі в гетероструктурах GaAs, на переходах Джозеф-сона. Як бачимо, в принципі, квантовий комп'ютер можна побудувати на атомних частках у вакуумі, рідини, кристалах. При цьому в кожному разі потрібно буде подолати ті чи інші перешкоди, однак серед них можна виділити кілька загальних, обумовлених принципами дії кубітів у квантовому комп'ютері. Поставимо задачу створити повномасштабний квантовий комп'ютер, що містить, скажімо, 10 3 кубітів (хоча й за п = 100 квантовий комп'ютер може стати корисним інструментом).
1. Потрібно знайти способи "ініціалізації" кубітів комп'ютера в стан . Для спінових систем в кристалах очевидно застосування наднизьких температур і надсильних магнітних полів. Застосування поляризації спінів накачуванням може виявитися корисним при одночасному застосуванні охолодження і великих магнітних полів.
Для іонів у вакуумних пастках наднизьку охолодження іонів (атомів) досягається лазерними методами. Очевидна також необхідність холодного і надвисокого вакууму.
2. Необхідно мати технологію виборчого впливу імпульсами на будь-який обраний кубіт. В області радіочастот та спінового резонансу це означає, що кожен спін повинен володіти своєю резонансною частотою (в термінах спектроскопічного дозволу). Відмінності резонансних частот для спінів у молекулах обумовлені хімічними зрушеннями для спінів одного ізотопу і одного елемента; необхідні відмінності частот є для спінів ядер різних елементів. Однак здоровий глузд підказує, що ці даровані природою відмінності резонансних частот навряд чи достатні, щоб працювати з 10 березня спінів.
Більш перспективними представляються підходи, коли можна керувати ззовні резонансної частотою кожного кубіта. У пропозиції про кремнієвому квантовому комп'ютері кубітом служить ядерний спін домішкового атома 31 Р. Частота резонансу визначається константою А надтонкого взаємодії ядерного та електронного спінів атома 31 Р. Електричне поле на наноелектроде, що знаходиться над атомом 31 Р, поляризує атом і змінює константу А (відповідно резонансну частоту ядерного спина). Таким чином, наявність електрода вбудовує кубіт в електронну схему і налаштовує його резонансну частоту.
3. Для виконання операції CNOT (контрольоване НЕ) необхідна взаємодія між кубітами і
виду
. Така взаємодія виникає між спинами ядер в молекулі, якщо ядра
і
розділені однієї хімічної зв'язком. У принципі, необхідно мати можливість виконувати операцію
для будь-яких пар кубітів
. Мати фізична взаємодія кубітів одного масштабу величини і за принципом "всі зі всіма" в природному середовищі навряд чи можливо. Очевидна потреба в способі настройки середовища між кубітами ззовні шляхом введення електродів з керованим потенціалом. Таким шляхом можна створити, наприклад, перекриття хвильових функцій електронів в сусідніх квантових точках і виникнення взаємодії виду
між спинами електронів [. Перекриття хвильових функцій електронів сусідніх атомів 31 Р обумовлює виникнення взаємодії виду
між ядерними спинами.
Щоб забезпечити операцію , Де
і
- Віддалені кубіти, між якими взаємодія виду
відсутня, необхідно застосувати в комп'ютері операцію обміну станами по ланцюжку
так що
забезпечує операцію
, Оскільки стан
збігається зі станом
.
4. У ході виконання унітарного перетворення, відповідного обраному алгоритмом, кубіти комп'ютера піддаються впливу з боку середовища, у результаті амплітуди і фази вектора стану кубіта відчувають випадкові зміни - декогеренізацію. По суті, декогеренізація - це релаксація тих ступенів свободи частинки, які використовуються в кубіте. Час декогеренізаціі дорівнює часу релаксації. У ядерному магнітному резонансі в рідинах часи
і
релаксації становлять 1-10 с. Для іонів у пастках з оптичними переходами між рівнями Е 0 і Е 1 часом декогеренізаціі виступають час спонтанного випромінювання і час зіткнень із залишковими атомами. Очевидно, що декогеренізація - це серйозна перешкода квантовому обчисленню: початий обчислювальний процес набуває рис випадковості після закінчення часу декогеренізаціі. Однак можна досягти сталого квантового обчислювального процесу протягом як завгодно довгого часу т> та, якщо систематично використовувати методи квантового кодування і корекції помилок (фазових і амплітудних). Доведено, що при відносно невисоких вимогах до безпомилкового виконання елементарних операцій типу N ВІД і С N ВІД (ймовірність помилки не більше 10 -5) методи квантової корекції помилок (QEC) забезпечують стійку роботу квантового комп'ютера.
Можливо і активне придушення процесу декогеренізаціі, якщо над системою кубітів проводити періодичні вимірювання. Вимірювання з великою ймовірністю виявить частку в "правильному" стані, а малі випадкові зміни вектора стану при вимірюванні колапсує (квантовий ефект Зенона). Однак важко поки сказати, наскільки корисним може бути такий прийом, оскільки такі вимірювання самі по собі можуть впливати на обчислювальний процес і змінити його.
5. Стани кубітів після завершення обчислювального процесу повинні бути обмірювані, щоб визначити результат обчислення. Сьогодні немає освоєної технології таких вимірювань. Очевидний, однак, шлях пошуків такої технології: треба використовувати методи посилення в квантовому вимірюванні. Наприклад, стан ядерного спина передається електронною спину
; Від останнього залежить орбітальна хвильова функція; знаючи орбітальну хвильову функцію, можна організувати передачу зарядів (іонізацію); присутність або відсутність заряду одиночного електрона можна виявити класичними електрометричним методами. Велику роль у цих вимірах будуть грати, ймовірно, методи зондової силової мікроскопії.
До теперішнього часу відкрито квантові алгоритми, що призводять до експоненціального прискоренню обчислень у порівнянні з обчисленнями в класичному комп'ютері. До них відноситься алгоритм Шора визначення простих множників великих (багаторозрядних) чисел. Ця суто математична проблема тісно пов'язана з життям суспільства, оскільки на "невичіслімості" таких множників побудовані сучасні шифрувальні коди. Саме ця обставина викликала сенсацію, коли був відкритий алгоритм Шора. Для фізиків важливо, що і рішення квантових завдань (рішення рівняння Шредінгера для багаточастинкових систем) експоненціально прискорюється, якщо використовувати квантовий комп'ютер.
Нарешті, дуже важливо, що в ході досліджень завдань квантового комп'ютингу піддаються новому аналізу та експериментальної перевірки основні проблеми квантової фізики: проблеми локальності, реальності, додатковості, прихованих параметрів, колапсу хвильової функції.
Ідеї квантового комп'ютингу та квантової зв'язку виникли через сто років після народження початкових ідей квантової фізики. Можливість побудови квантових комп'ютерів і систем зв'язку показана виконаними до теперішнього часу теоретичними та експериментальними дослідженнями. Квантова фізика "достатня" для проектування квантових комп'ютерів на різній "елементної базі". Квантові комп'ютери, якщо їх вдасться побудувати, будуть технікою XXI століття. Для їх виготовлення потрібно створення і розвиток нових технологій на нанометровому і атомному рівні розмірів. Ця робота може тривати, очевидно, кілька десятиліть. Побудова квантових комп'ютерів було б ще одним підтвердженням принципу невичерпності природи: природа має кошти для здійснення будь-якої коректно сформульованої людиною завдання.
У звичайному комп'ютері інформація кодується послідовністю бітів, і ці біти послідовно обробляються Булевського логічними елементами, щоб отримати потрібний результат. Аналогічно квантовий комп'ютер обробляє кубіти, виконуючи послідовність операцій квантовими логічними елементами, кожний з яких представляє собою унітарне перетворення, що діє на одиничний кубіт або пару кубітів. Послідовно виконуючи ці перетворення, квантовий комп'ютер може виконати складне унітарна перетворення над усім набором кубітів приготованих у деякому початковому стані. Після цього можна зробити вимір над кубітами, яке і дасть кінцевий результат обчислень. Ця схожість обчислень між квантовим і класичним комп'ютером дозволяє вважати, що, принаймні, в теорії, класичний комп'ютер може в точності відтворювати роботу квантового комп'ютера. Іншими словами, класичний комп'ютер може робити все те ж саме, що і квантовий комп'ютер. Тоді навіщо вся ця метушня з квантовим комп'ютером? Справа в тому, що, хоча теоретично класичний комп'ютер може симулювати квантовий комп'ютер, це дуже неефективно, настільки неефективно, що практично класичний комп'ютер не в змозі вирішувати багато завдань, які під силу квантовому комп'ютера. Симуляція квантового комп'ютера на класичному комп'ютері обчислювально складна проблема, тому що кореляції між квантовими бітами якісно відрізняється від кореляцій між класичними бітами, як було вперше показано Джоном Беллом. Для прикладу можна взяти систему тільки з декількох сотень кубітів. Вона існує в просторі Гільберта розмірністю ~ 10 90, що зажадає, при моделюванні класичним комп'ютером, використання експоненціально великих матриць (щоб виконати розрахунки для кожного окремого стану, який також описується матрицею). Це означає, що класичного комп'ютера знадобиться екпоненціально більше часу, аніж навіть з примітивним квантовим комп'ютером.
Річард Фейнман був серед перших, хто усвідомив потенціал, закладений в явищі квантової суперпозиції для вирішення таких завдань значно швидше. Наприклад, система з 500 кубітів, яку практично неможливо промеделіровать класично, являє собою квантову суперпозицію з 2500 станів. Кожне значення такої суперпозиції класично еквівалентно списку з 500 одиниць і нулів. Будь-яка квантова операція над такою системою, наприклад, налаштований певним чином імпульс радіохвиль, який може виконати операцію кероване НЕ над, скажімо, 100-м і 101-м кубітом, одночасно впливати на 2 500 станів. Таким чином, за один тик комп'ютерних годин квантова операція обчислює не одне машинне стан, як звичайні комп'ютери, а 2 500 станів відразу! Однак, врешті-решт, над системою кубітів проводиться вимірювання, і система колапсує в єдине квантовий стан, відповідне єдиного вирішення завдання, єдиному набору з 500 одиниць і нулів, як це диктується вимірювальної аксіомою квантової механіки. Це воістину хвилюючий результат, оскільки це рішення, знайдене колективним процесом квантових паралельних обчислень, що беруть свої витоки в суперпозиції, еквівалентно виконання тієї ж самої операції на класичному суперкомп'ютері з ~ 10 150 окремих процесорів (що, звичайно, неможливо)!! Перші дослідники в цій області були, звичайно, натхненні такими гігантськими можливостями, і тому незабаром почалося справжнє полювання за відповідними завданнями для такої обчислювальної потужності. Пітер Шор, дослідник і комп'ютерний вчений з компанії AT & T's Bell Laboratories в Нью Джерсі, запропонував таку задачу, яку можна було б вирішити саме на квантовому комп'ютері і за допомогою квантового алгоритму. Алгоритм Шора використовує міць квантової суперпозиції, щоб розкладати великі числа (порядку ~ 10 200 двійкових розрядів і більше) на множники за кілька секунд. Ця задча має важливе практичне застосування для шифрування, де загальноприйнятий (і найкращий) алгоритм шифрування, відомий як RSA, заснований саме на складності розкладання великих складених чисел на прості множники. Комп'ютер, який з легкістю вирішує таке завдання, звичайно, представляє великий інтерес для безлічі урядових організацій, що використовують RSA, який до цих пір вважався "незламуваних", і для будь-якого хто зацікавлений в безопсаності своїх даних.
Шифрування, однак, тільки одне можливе застосування квантового комп'ютера. Шор розробив цілий набір математичних операцій, які можуть бути виконані виключно на квантовому комп'ютері. Деякі з цих операцій використовуються в його алгорітіе факторизації. Далі, Фейнман стверджував, що квантовий комп'ютер може діяти як моделює пристрій для квантової фізики, потенційно відкриваючи двері до багатьох відкриттів у цій області. В даний час потужність і можливості квантового комп'ютера, в основному, предмет теоретичних міркувань: появи першого по-справжньому функціонального квантового комп'ютера, безсумнівно, принесе багато нових і хвилюючих практичних застосувань.
Глава III. Алгоритм Гровера
Завдання пошуку полягає в наступному: є невпорядкована база даних, що складається з N-елементів, з яких лише один задовольняє даним умовам - саме цей елемент потрібно знайти. Якщо елемент можна оглянути, то визначення того, чи задовольняє він потрібними умовами чи ні, здійснюється за один крок. Однак база даних така, що в ній не існує будь-якого впорядкування, яке могло б допомогти вибору елемента. Найбільш ефективний класичний алгоритм для цього завдання полягає у перевірці елементів з бази даних одного за іншим. Якщо елемент задовольняє необхідним умовам, пошук закінчено, якщо немає, то даний елемент відкладається так, так щоб він знову не піддавався перевірці. Очевидно, що в цьому алгоритмі потрібно перевірити в середньому елементів перш, ніж буде знайдено потрібний. [1]
Реалізуючи даний алгоритм, можна використовуючи те ж саме обладнання, як в класичному випадку, але задаючи вхід і вихід у вигляді суперпозиції станів, можна знайти об'єкт за O ( ) Квантовомеханічний кроків замість О (N)) класичних кроків. Кожен квантовомеханічний крок складається з елементарної унітарної операції, які розглянемо далі.
Для здійснення даного алгоритму нам необхідні наступні три елементарні операції. Перша - це приготування стану, в якому система знаходиться з рівною імовірністю в будь-якому з її N базисних станів, друга - це перетворення Адамара і третя - вибірковий поворот фаз станів.
Як відомо основною операцією для квантових обчислень є операція М, що діє на один біт, яка представляється наступній матрицею:
тобто біт в стані 0 перетворюється в суперпозицію двох станів: (1 / , 1 / ). Аналогічно, біт в стані 1 трансформується в (1 / ,, -1 / ,), Тобто величина амплітуди для кожного стану дорівнює 1 / ,, Але фаза в стані 1 перегорнуто. Фаза не має аналога в класичних імовірнісних алгоритмах. Вона виникає у квантовій механіці, де амплітуда ймовірності комплексна. У системі, в якій стан описується п бітами (тобто є N = 2 п можливих станів), ми можемо здійснити перетворення М на кожному бите незалежно, послідовно змінюючи стан системи. У випадку, коли початкова конфігурація представляла собою конфігурацію з п бітами в першому стані, отримана конфігурація буде мати рівні амплітуди для кожного з станів. Це і є спосіб створення суперпозиції з тією ж самою амплітудою для всіх
станів.
Третє перетворення, яке нам знадобиться, - це вибіркове обертання фази амплітуди в певних станах. Перетворення, представлене тут для системи з двох станів, має форму:
де j = і - Довільні дійсні числа. Зауважимо, що на відміну від перетворення Адамара і інших матриць перетворення станів, ймовірність кожного стану залишається тією ж, тому що квадрат абсолютної величини амплітуди у кожному стані залишається тим самим.
Розглянемо завдання в абстрактній формі.
Нехай система має N = 2 п станів, які позначаються як ,..., . Ці 2 п стану представляються як n-бітні рядка. Нехай існує єдиний стан, скажімо , Яке довлетворяет умові C ( ) = 1, тоді як для всіх інших станів S, С (
,) = 0 (передбачається, що для будь-якого стану S умова оцінюється за одиницю часу). Завдання полягає в розпізнанні стану ,
Перейдемо власне до алгоритму
Кроки (1) і (2) є послідовністю елементарних унітарних операцій описаних раніше. Крок (3) є завершальне вимір, здійснюване зовнішньою системою.
(1) Наводимо систему в стан суперпозиції:
з однаковими амплітудами для кожного з N станів. Ця суперпозиція може бути отримана за кроків.
(2) Повторимо наступну унітарну операцію О ( ) Раз:
a. Нехай система буде в якомусь стані S:
У разі С (S) = 1, повернути фазу на радіан;
У разі С (S) = 0, залишити систему незміненою.
b. Застосувати перетворення дифузії D яке визначається матрицею D наступним чином: , Якщо ; 'І . D може бути реалізована як послідовне виконання унітарних перетворень:
, Де W - матриця перетворень Адамара, R - матриця фазового повороту.
(3) Провести вимірювання отриманого стані. Цей стан буде станом С ( ) "(Тобто шуканим станом, що задовольняє умові (C ( ) = 1) з ймовірністю, принаймні, не меншою, ніж 0.5. Зауважимо, що крок (2а) - це фазове обертання. У його реалізацію повинна бути включена процедура розпізнання стану і подальшого визначення здійснювати чи ні поворот фази. Вона повинна проводитися таким чином, щоб не залишати сліду на стан системи, так, щоб була впевненість, що шляхи, що призводять до того ж самому кінцевому стану, невиразні і можуть інтерферувати. Зауважимо, що ця процедура не включає класичного вимірювання.
Даний квантовий алгоритм пошуку, ймовірно, буде простіше реалізувати в порівнянні з багатьма іншими відомими квантово-механічними алгоритмами, тому що необхідні операції - це тільки перетворення Уолша-Адамара і операція умовного зсуву фази, кожна з яких відносно проста в порівнянні з операціями, використовуваних інших квантово-механічними алгоритмами.
Висновок
Зараз квантові комп'ютери і квантові інформаційні технології залишаються в стані піонерських розробок. Рішення труднощів, з якими зараз зіткнулися ці технології, забезпечить прорив квантових комп'ютерів до їх законному місцем найшвидших обчислювальних машин з усіх фізично можливих. До сьогоднішнього дня виправлення помилок істотно просунулося, наближаючи момент, коли ми зможемо створювати досить надійні комп'ютери, здатні протистояти ефектам декогеренції. З іншого боку, створення квантового обладнання поки залишається тільки виникає галуззю; але робота, виконана на сьогодні, переконує нас, що створення досить великих машин, здатних виконувати серйозні алгоритми, наприклад, алгоритм Шора, всього лише справа часу. Таким чином, квантові комп'ютери обов'язково з'являться. Щонайменше, це будуть найдосконаліші обчислювальні пристрої, а сучасні нам комп `ютери застаріють. Квантові обчислення беруть свій початок у вельми специфічних галузях теоретичної фізики, але їх майбутнє, безсумнівно, матиме неабиякий вплив на життя всього людства.
Список літератури
1. Квантові обчислення: за і проти. Під ред. В.А. Садовничого. - К.: Видавничий дім «Удмуртська університет», 1999. - 212 с.
2. Белонучкін В. E., Заїкін Д.А., Ципенюком Ю.М., Основи фізики. Курс загальної фізики: Навч. У 2 т. Т. 2. Квантова та статистична фізика. - М.: Фізматліт, 2001. - 504 с.
3. Валієв К.А. «Квантові комп'ютери: чи можна їх зробити« великими »?», Успіхи фізичних наук, т. 169, № 6, 1999р.
4. Валієв К.А. «Квантова інформатика: комп'ютери, зв'язок та криптографія», ВІСНИК РОСІЙСЬКОЇ АКАДЕМІЇ НАУК, тому 70, № 8, с. 688-695, 2000р.
5. Маслов. Д. «Квантові обчислення і комунікація: реальність і перспективи», Компьютерра, № 46, 2004р.
6. Халфін Л.А. «Квантовий ефект Зенона», Успіхи фізичних наук, т. 160, № 10, 1990р.
7. Холевой А. «Квантова інформатика: минуле, сучасне, майбутнє»,
У СВІТІ НАУКИ, № 7, 2008 р.
8. Centre for Quantum Technologies, National University of Singapore www.quantumlah.org