Квантово изчисление. Кратко въведение в квантовите изчисления (публикация за гости от Роман Душкин) Алгоритми за квантови изчисления

МИНИСТЕРСТВО НА ОБРАЗОВАНИЕТО НА РУСКАТА ФЕДЕРАЦИЯ

ДЪРЖАВНО УЧЕБНО ЗАВЕДЕНИЕ

Есе

Квантово изчисление

Въведение

Глава I. Основни понятия на квантовата механика

Глава II. Основни понятия и принципи на квантовите изчисления

Глава III. Алгоритъм на Гроувър

Заключение

Библиография

Въведение

Представете си компютър, чиято памет е експоненциално по-голяма от чистия му физически размер, който бихте очаквали; компютър, който може да обработва експоненциално по-голям набор от входни данни едновременно; компютър, който извършва изчисления в хилбертовото пространство, което е мъгливо за повечето от нас.

Тогава мислите за квантов компютър.

Идеята за изчислително устройство, базирано на квантовата механика, е разгледана за първи път в началото на 70-те и началото на 80-те години на миналия век от физици и компютърни учени като Чарлз Х. Бенет от IBM Thomas J. Watson Research Center и Пол А. Бениоф от Argonne National Лаборатория в Илинойс, Дейвид Дойч от Оксфордския университет, а по-късно Ричард П. Файнман от Калифорнийския технологичен институт (Caltech). Идеята възникна, когато учените се заинтересуваха от фундаменталните ограничения на изчислителната техника. Те разбраха, че ако технологията продължи постепенно да намалява размера на компютърните мрежи, опаковани в силициеви чипове, това ще доведе до това отделните елементи да станат не повече от няколко атома. Тогава възникна проблем, тъй като законите на квантовата физика важат на атомно ниво, а не на класическите. Това повдига въпроса дали е възможно да се конструира компютър, базиран на принципите на квантовата физика.

Файнман е един от първите, които се опитват да отговорят на този въпрос. През 1982г той предложи модел на абстрактна квантова система, подходяща за изчисления. Той също така обясни как такава система може да бъде симулатор в квантовата физика. С други думи, физиците биха могли да провеждат изчислителни експерименти на такъв квантов компютър.

По-късно, през 1985 г., Дойч осъзнава, че твърдението на Файнман може в крайна сметка да доведе до квантов компютър с общо предназначение и той публикува забележителна теоретична работа, показваща, че всеки физически процес по принцип може да бъде симулиран на квантов компютър.

За съжаление, всичко, което можеха да измислят по това време, бяха няколко доста пресилени математически задачи, докато Шор не издаде работата си през 1994 г., в която той представи алгоритъм за решаване на важен проблем от теорията на числата на квантов компютър, а именно, разлагане на прости множители. Той показа как може набор от математически операции, проектирани специално за квантов компютър факторизирам(разтворете) огромни числа фантастично бързо, много по-бързо от конвенционалните компютри. Това беше пробив, който премести квантовите изчисления от академичен интерес към проблем, представляващ интерес за целия свят.

Глава аз . Основни понятия на квантовата механика

В края на 19 век сред учените е широко разпространено мнението, че физиката е „практически завършена“ наука и че остава много малко за нейната пълна „завършеност“: да се обясни структурата оптични спектри на атомии спектрално разпределение топлинно излъчване . Оптични спектри на атомсе получават чрез излъчване или поглъщане на светлина (електромагнитни вълни) от свободни или слабо свързани атоми; По-специално едноатомните газове и пари имат такива спектри.

Топлинно излъчванее механизъм за пренос на топлина между пространствено разделени части на тялото поради електромагнитно излъчване.

Началото на 20 век обаче доведе до разбирането, че за никаква „завършеност“ не може да се говори. Стана ясно, че за да се обяснят тези и много други явления, е необходимо да се преразгледат радикално концепциите, залегнали в основата на физическата наука.

Например, въз основа на вълновата теория на светлината се оказа невъзможно да се даде изчерпателно обяснение на целия набор от оптични явления.

Когато решава проблема за спектралния състав на радиацията, немският физик Макс Планк през 1900 г. предполага, че излъчването и поглъщането на светлина от материята се извършва на ограничени порции, или кванти.В същото време енергията фотон - квант на електромагнитното излъчване(в тесен смисъл - светлина) се определя от израза

Къде е честотата на излъчената (или погълната) светлина и е универсалната константа, сега наричана константа на Планк.

Често се използва константата на Дирак

Тогава квантовата енергия се изразява като , където

Кръгова честота на излъчване.

Противоречията между разглеждането на светлината като поток от заредени частици и като вълни доведоха до концепцията дуалност вълна-частица.

От една страна, фотонът демонстрира свойствата на електромагнитната вълна в явленията дифракция(вълните се огъват около препятствия, сравними с дължината на вълната) и намеса(суперпозиция на вълни с еднаква честота и еднаква начална фаза) в мащаби, сравними с дължината на вълната на фотона. Например единични фотони, преминаващи през двоен процеп, създават интерференчен модел на екрана, който може да бъде описан Уравнения на Максуел. Експериментът обаче показва, че фотоните се излъчват и поглъщат изцяло от обекти, чиито размери са много по-малки от дължината на вълната на фотона (например атоми) или, като цяло, в някакво приближение могат да се считат за точковидни (например електрон), тоест те се държат като частици - корпускули. В макрокосмоса около нас има два основни начина за пренос на енергия и импулс между две точки в пространството: директното движение на материята от една точка в друга и вълновият процес на пренос на енергия без пренос на материя. Всички енергийни носители тук са строго разделени на корпускулярни и вълнови. Напротив, в микросвета такова разделение не съществува. На всички частици и по-специално на фотоните се приписват както корпускулярни, така и вълнови свойства. Ситуацията е неясна. Това е обективно свойство на квантовите модели.

Почти монохроматичното честотно излъчване, излъчвано от светлинен източник, може да се разглежда като състоящо се от „пакети радиация“, които наричаме фотони. Монохроматично лъчение – имащо много малко честотно разпространение, в идеалния случай една дължина на вълната.

Разпространението на фотоните в пространството се описва правилно от класическите уравнения на Максуел. В този случай всеки фотон се счита за класически във влак вълни, дефинирана от две векторни полета - напрегнатостта на електростатичното поле и индукцията на магнитното поле. Вълновият влак е поредица от смущения с прекъсвания между тях. Излъчването на отделен атом не може да бъде монохроматично, тъй като излъчването продължава ограничен период от време, като има периоди на нарастване и спадане.

Неправилно е сборът от квадратите на амплитудите да се тълкува като енергийна плътност в пространството, в което се движи фотонът; вместо това всяко количество, което зависи квадратично от амплитудата на вълната, трябва да се тълкува като количество, пропорционално на вероятността за някакъв процес. Да кажем, че не е равно на енергията, внесена от фотона в тази област, но е пропорционално на вероятността за откриване на фотон в тази област.

Енергията, пренесена към всяко място в пространството от фотон, винаги е равна на . По този начин където е вероятността да се намери фотон в дадена област и е броят на фотоните.

През 1921 г. експериментът на Щерн-Герлах потвърждава наличието на атоми обратнои фактът на пространствено квантуване на посоката на техните магнитни моменти (от англ. spin - въртене, въртене.). Завъртете- собственият ъглов момент на елементарните частици, който има квантов характер и не е свързан с движението на частицата като цяло. При въвеждането на концепцията за спин се приема, че електронът може да се разглежда като „въртящ се връх“, а неговият спин като характеристика на такова въртене. Спинът също е името, дадено на собствения ъглов импулс на атомно ядро ​​или атом; в този случай спинът се определя като векторна сума (изчислена съгласно правилата за добавяне на моменти в квантовата механика) на спиновете на елементарните частици, образуващи системата, и орбиталните моменти на тези частици, дължащи се на тяхното движение в рамките на система.

Спинът се измерва в единици (редуцирани константи на Планк или константи на Дирак) и е равен на , където Дж- цяло число (включително нула) или полуцяло положително число, характерно за всеки тип частица - спиново квантово число, което обикновено се нарича просто спин (едно от квантовите числа). В тази връзка те говорят за цяло или полуцяло въртене на частица. Въпреки това понятията спин и спиново квантово число не трябва да се бъркат. Спиновото квантово число е квантово число, което определя спиновата стойност на квантова система (атом, йон, атомно ядро, молекула), т.е. нейният собствен (вътрешен) ъглов момент. Проекцията на въртенето върху всяка фиксирана посока z в пространството може да приеме стойностите Дж , J-1, ..., -J.По този начин, частица със спин Джможе да е в 2J+1спинови състояния (при Дж= 1/2 - в две състояния), което е еквивалентно на наличието на допълнителна вътрешна степен на свобода.

Ключовият елемент на квантовата механика е Принцип на неопределеността на Хайзенберг, който казва, че е невъзможно едновременно да се определи точно положението на частица в пространството и нейния импулс. Този принцип обяснява квантуването на светлината, както и пропорционалната зависимост на енергията на фотона от неговата честота.

Движението на фотона може да се опише чрез системата от уравнения на Максуел, докато уравнението на движението на всяка друга елементарна частица като електрон се описва от уравнението на Шрьодингер, което е по-общо.

Системата от уравнения на Максуел е инвариантна спрямо трансформацията на Лоренц. Трансформации на Лоренцв специалната теория на относителността се наричат ​​трансформации, на които са подложени пространствено-времевите координати (x,y,z,t)всяко събитие по време на прехода от една инерционна отправна система към друга. По същество тези трансформации са трансформации не само в пространството, като трансформациите на Галилей, но и във времето.

Глава II . Основни понятия и принципи на квантовите изчисления

Въпреки че компютрите са станали по-малки и много по-бързи в задачата си от преди, самата задача остава същата: манипулиране на последователност от битове и тълкуване на тази последователност като полезен изчислителен резултат. Битът е основна единица информация, обикновено представена като 0 или 1 във вашия цифров компютър. Всеки класически бит е физически реализиран от макроскопична физическа система, като намагнитването на твърд диск или заряда на кондензатор. Например текст, съставен от нсимволи и се съхранява на типичния твърд диск на компютъра, се описва от низ от 8nнули и единици. Тук се крие фундаменталната разлика между вашия класически компютър и квантов компютър. Докато класическият компютър се подчинява на добре разбраните закони на класическата физика, квантовият компютър е устройство, което използва квантово-механични явления (особено квантова интерференция) за прилагане на напълно нов начин за обработка на информация.

В квантов компютър, основната единица информация (наречена квантов бит или кубит), не е бинарен, а по-скоро кватернерен по природа. Това свойство на кубита възниква като пряко следствие от подчиняването му на законите на квантовата механика, които са коренно различни от законите на класическата физика. Кубитът може да съществува не само в състояние, съответстващо на логическа 0 или 1, като класически бит, но също и в състояния, съответстващи на смесени или суперпозициитези класически състояния. С други думи, кубитът може да съществува като нула, като единица и като 0 и 1. В този случай можете да посочите определен числов коефициент, представляващ вероятността да бъдете във всяко състояние.

Идеите за възможността за изграждане на квантов компютър се връщат към работата на Р. Фейнман през 1982-1986 г. Разглеждайки въпроса за изчисляване на еволюцията на квантовите системи на цифров компютър, Файнман открива „неразрешимостта“ на този проблем: оказва се, че ресурсите на паметта и скоростта на класическите машини са недостатъчни за решаване на квантови проблеми. Например система от нквантови частици с две състояния (завъртания 1/2 ) То има 2 носновни състояния; за да се опише, е необходимо да се уточни (и запише в паметта на компютъра) 2 намплитудите на тези състояния. Въз основа на този отрицателен резултат Файнман предположи, че е вероятно „квантовият компютър“ да има свойства, които ще му позволят да решава квантови проблеми.

„Класическите“ компютри са изградени върху транзисторни вериги, които имат нелинейни зависимости между входното и изходното напрежение. Те са по същество бистабилни елементи; например, когато входното напрежение е ниско (логическа "0"), входното напрежение е високо (логическа "1") и обратно. В квантовия свят такава бистабилна транзисторна верига може да се сравни с двустепенна квантова частица: ние присвояваме логическите стойности на състоянието, състоянието, - булева стойност. Преходите в бистабилна транзисторна верига тук ще съответстват на преходи от ниво на ниво: . Въпреки това, квантовият бистабилен елемент, наречен кубит, има ново в сравнение с класическото свойство на суперпозиция на състояния: той може да бъде във всяко състояние на суперпозиция, където са комплексни числа, . Състояния на квантовата система от Пчастиците на две нива имат най-общо формата на суперпозиция 2 н основно състояние . В крайна сметка, квантовият принцип на суперпозиция на състояния прави възможно придаването на принципно нови „способности“ на квантов компютър.

Доказано е, че квантовият компютър може да бъде изграден само от два елемента (врати): еднокубитов елемент и двукубитов контролиран НЕ елемент (CNOT). Матрица 2x2елемент има формата:

(1)

Портата описва въртенето на вектора на състоянието на кубита от оста z към полярната ос, определена от ъглите . Ако са ирационални числа, тогава чрез многократно използване на вектора на състоянието може да се даде произволна предварително определена ориентация. Това е точно „универсалността“ на еднокубитова врата във формата (1). В конкретен случай получаваме еднокубитов логически елемент NOT (NOT): NOT=, NOT=. Когато физически внедрявате елемент, НЕ е необходимо да въздействате на квантова частица (кубит) с външен импулс, който прехвърля кубита от едно състояние в друго. Контролираният НЕ порта се изпълнява чрез повлияване на два взаимодействащи кубита: в този случай чрез взаимодействие единият кубит контролира еволюцията на другия. Преходите под въздействието на външни импулси са добре известни в импулсната магнитно-резонансна спектроскопия. Вентилът НЕ съответства на обръщане на въртене под въздействието на импулс (въртене на намагнитването около оста под ъгъл) . Портата CNOT се изпълнява на две завъртания 1/2 с Хамилтониан (контроли на въртене). CNOT се извършва в три стъпки: импулс + свободна прецесия във времето - импулс. Ако (контролиращият кубит е в състояние), тогава при посочените влияния контролираният кубит прави преходи (или ). Ако (контролиращият кубит е в състояние), тогава резултатът от еволюцията на контролирания кубит ще бъде различен: (). По този начин спинът се развива по различен начин при : тук е състоянието на контролиращия кубит.

Когато се разглежда въпросът за внедряване на квантов компютър в определени квантови системи, първо се изследват осъществимостта и свойствата на елементарните НЕ и контролираните НЕ порти.

За това, което следва, също е полезно да се въведе преобразуването на Адамар с един кубит:

В технологията на магнитния резонанс тези порти се осъществяват чрез импулси:

Диаграмата на квантов компютър е показана на фигурата. Преди компютърът да започне да работи, всички кубити (квантови частици) трябва да бъдат приведени в състояние, т.е. към основно състояние. Това условие само по себе си не е тривиално.

Изисква или дълбоко охлаждане (до температури от порядъка на миликелвин) или използването на поляризационни методи. система Пкубитите в състояние могат да се считат за регистър на паметта, подготвен за запис на входни данни и извършване на изчисления. В допълнение към този регистър обикновено се приема, че има допълнителни (спомагателни) регистри, необходими за записване на междинни резултати от изчисленията. Данните се записват чрез въздействие върху всеки кубит на компютъра по един или друг начин. Да приемем, например, че се извършва трансформация на Адамар на всеки кубит от регистъра:

В резултат на това системата премина в състояние на суперпозиция от 2 стрбазисни състояния с амплитуда 2 - н /2 . Всяко основно състояние е двоично число от до . Хоризонталните линии на фигурата показват времевите оси.

Изпълнението на алгоритъма се осъществява чрез унитарна трансформация на суперпозиция. е единна матрица на измерение 2 стр.Когато се реализира физически чрез импулсни въздействия върху кубити отвън, матрицата трябва да бъде представена като векторно произведение на матрици с размерност 2 и . Последното може да се извърши чрез последователно повлияване на единични кубити или двойки кубити :

Броят на факторите в това разширение определя продължителността (и сложността) на изчисленията. Всичко в (3) се изпълнява с помощта на операциите NOT, CNOT, H (или техните вариации).

Забележително е, че линейният унитарен оператор действа едновременно върху всички членове на суперпозицията

Резултатите от изчислението се записват в резервния регистър, който е бил в състоянието преди употреба. В едно изпълнение на изчислителния процес получаваме стойностите на желаната функция f за всички стойности на аргумента х = 0,..., 2 п - 1 . Това явление се нарича квантов паралелизъм.

Измерването на резултата от изчисленията се свежда до проектиране на вектора на суперпозицията в (4) върху вектора на едно от основните състояния :

(5)

Тук се проявява една от слабите страни на квантовия компютър: числото „изпада“ по време на процеса на измерване според закона на случайността. Да намериш за даденост , необходимо е да се извършват изчисления и измервания много пъти, докато произволно изпадне .

Когато се анализира единната еволюция на квантова система, изпълняваща изчислителен процес, се разкрива значението на физическите процеси като интерференция. Унитарните трансформации се извършват в пространството на комплексните числа и добавянето на фазите на тези числа има характер на интерференция. Производителността на преобразуванията на Фурие в явленията на интерференция и спектроскопия е известна. Оказа се, че квантовите алгоритми неизменно съдържат трансформации на Фурие. Преобразуването на Адамар е най-простото дискретно преобразуване на Фурие. Вратите от типовете NOT и CNOT могат да бъдат внедрени директно в интерферометъра Mach-Zehnder, като се използва феноменът на фотонна интерференция и въртене на неговия поляризационен вектор.

Проучват се различни начини за физическо внедряване на квантови компютри. Моделни експерименти за квантово изчисление бяха проведени на импулсен ядрено-магнитен резонансен спектрометър. В тези модели работят две или три завъртания (кубита), например две завъртания на 13 C ядра и едно завъртане на протон в молекула на трихлоретилен

В тези експерименти обаче квантовият компютър беше „ансамбъл“: изходните сигнали на компютъра са съставени от голям брой молекули в течен разтвор (~ 10 20).

Към днешна дата са направени предложения за прилагане на квантови компютри върху йони и молекули в капани във вакуум, върху ядрени завъртания в течности (виж по-горе), върху ядрени завъртания на 31 P атоми в кристален силиций, върху завъртания на електрони в квантов точки, създадени в двуизмерен електронен газ в GaAs хетероструктури, в Джоузефсонови преходи. Както виждаме, по принцип квантовият компютър може да бъде изграден върху атомни частици във вакуум, течност или кристали. Във всеки случай трябва да се преодолеят определени препятствия, но сред тях има няколко общи, определени от принципите на работа на кубитите в квантов компютър. Нека си поставим задачата да създадем пълномащабен квантов компютър, съдържащ, да речем, 10 3 кубита (макар и при n = 100 квантов компютър може да бъде полезен инструмент).

1. Трябва да намерим начини да „инициализираме“ кубитите на компютъра в състоянието. За центрофугиращите системи в кристалите е очевидно използването на ултра-ниски температури и ултра-силни магнитни полета. Използването на спинова поляризация чрез изпомпване може да бъде полезно, когато се прилагат едновременно охлаждане и силни магнитни полета.

За йони във вакуумни уловители се постига свръхниско охлаждане на йони (атоми) чрез лазерни методи. Нуждата от студ и свръхвисок вакуум също е очевидна.

2. Необходимо е да има технология за избирателно въздействие на импулси върху всеки избран кубит. В областта на радиочестотите и спиновия резонанс това означава, че всяко въртене трябва да има своя собствена резонансна честота (от гледна точка на спектроскопска разделителна способност). Разликите в резонансните честоти за спиновете в молекулите се дължат на химически измествания за спиновете на един изотоп и един елемент; съществуват необходимите честотни разлики за спиновете на ядрата на различни елементи. Здравият разум обаче диктува, че тези естествено възникващи разлики в резонансните честоти е малко вероятно да бъдат достатъчни за работа с 10 3 завъртания

По-обещаващи подходи изглеждат тези, при които резонансната честота на всеки кубит може да се контролира външно. В предложението за силициев квантов компютър кубитът е ядреното въртене на примесен атом 31 R. Резонансната честота се определя от константата Асвръхфиното взаимодействие на ядрените и електронните спинове на 31 R атома Електрическото поле на наноелектрода, разположен над 31 R атома, поляризира атома и променя константата. А(съответно резонансната честота на ядрения спин). По този начин наличието на електрод вгражда кубит в електронна верига и настройва неговата резонансна честота.

3. За извършване на операцията CNOT (контролирано НЕ) е необходимо взаимодействие между кубитите и формата . Такова взаимодействие възниква между спиновете на ядрата в молекула, ако ядрата са разделени от една химична връзка. По принцип е необходимо да можете да извършите операцията върху всяка двойка кубити . Едва ли е възможно да има физическо взаимодействие на кубити от еднакъв мащаб и според принципа „всички с всички“ в естествената среда. Съществува очевидна необходимост от начин за настройка на средата между кубитите отвън чрез въвеждане на електроди с контролиран потенциал. По този начин е възможно да се създаде, например, припокриване на вълновите функции на електроните в съседни квантови точки и появата на взаимодействие на формата между електронните завъртания [. Припокриването на вълновите функции на електроните на съседните 31 P атоми предизвиква появата на взаимодействие от типа между ядрените спинове.

За да се осигури операцията, където и са отдалечени кубити, между които няма взаимодействие на формата, е необходимо да се приложи в компютъра операцията за обмен на състояния по веригата, така че операцията да бъде осигурена, тъй като състоянието съвпада със състоянието .

4. По време на изпълнението на унитарна трансформация, съответстваща на избрания алгоритъм, кубитите на компютъра са изложени на влияние от околната среда; в резултат на това амплитудата и фазата на вектора на състоянието на кубита изпитват случайни промени - декохерентност. По същество декохерентността е релаксация на онези степени на свобода на частицата, които се използват в кубита. Времето на декохерентност е равно на времето на релаксация. При ядрено-магнитен резонанс в течности времето за релаксация е 1-10 s. За йони в капани с оптични преходи между нивата E 0И Е 1Времето на декохерентност е времето на спонтанно излъчване и времето на сблъсъци с остатъчни атоми. Очевидно е, че декохерентността е сериозна пречка за квантовите изчисления: стартираният изчислителен процес придобива характеристиките на случайност след изтичане на времето за декохерентност. Въпреки това е възможно да се постигне стабилен квантов изчислителен процес за произволно дълго време m > ma, ако систематично се използват методи за квантово кодиране и коригиране на грешки (фаза и амплитуда). Доказано е, че при относително ниски изисквания за безгрешно изпълнение на елементарни операции като NOT и CNOT (вероятност за грешка не повече от 10 -5), методите за квантова корекция на грешки (QEC) осигуряват стабилна работа на квантовия компютър.

Също така е възможно активно да се потисне процеса на декохерентност, ако се извършват периодични измервания на системата от кубити. Измерването най-вероятно ще открие частицата в „правилното“ състояние и малки произволни промени във вектора на състоянието ще се сринат по време на измерването (квантов ефект на Зенон). Трудно е обаче да се каже колко полезна може да бъде подобна техника, тъй като самите такива измервания могат да повлияят и нарушат изчислителния процес.

5. Състоянията на кубитите след завършване на изчислителния процес трябва да бъдат измерени, за да се определи резултатът от изчислението. Днес няма усвоена технология за подобни измервания. Въпреки това, пътят към търсенето на такава технология е очевиден: необходимо е да се използват методи за усилване в квантовите измервания. Например ядреното спиново състояние се прехвърля към електронното спиново състояние; орбиталната вълнова функция зависи от последната; познавайки орбиталната вълнова функция, е възможно да се организира пренос на заряд (йонизация); наличието или отсъствието на заряд на единичен електрон може да се открие чрез класически електрометрични методи. Методите на силовата микроскопия със сонда вероятно ще играят основна роля в тези измервания.

Към днешна дата са открити квантови алгоритми, които водят до експоненциално ускоряване на изчисленията в сравнение с изчисленията на класически компютър. Те включват алгоритъма на Шор за определяне на прости множители на големи (многоцифрени) числа. Този чисто математически проблем е тясно свързан с живота на обществото, тъй като съвременните кодове за криптиране са изградени върху „неизчислимостта“ на такива фактори. Именно това обстоятелство предизвика сензация, когато беше открит алгоритъмът на Шор. За физиците е важно решението на квантовите проблеми (решаване на уравнението на Шрьодингер за системи от много частици) да се ускори експоненциално, ако се използва квантов компютър.

И накрая, много е важно в хода на изследването на проблемите с квантовите изчисления основните проблеми на квантовата физика да бъдат подложени на нов анализ и експериментална проверка: проблеми на локалността, реалността, комплементарността, скрити параметри, колапс на вълновата функция.

Идеите за квантовите изчисления и квантовата комуникация възникват сто години след раждането на първоначалните идеи на квантовата физика. Възможността за изграждане на квантови компютри и комуникационни системи е демонстрирана от теоретични и експериментални изследвания, завършени до момента. Квантовата физика е „достатъчна“ за проектирането на квантови компютри, базирани на различни „елементни бази“. Квантовите компютри, ако могат да бъдат построени, ще бъдат технологията на 21-ви век. Тяхното производство ще изисква създаването и развитието на нови технологии на нанометрово и атомно ниво. Тази работа вероятно ще отнеме няколко десетилетия. Изграждането на квантови компютри би било още едно потвърждение на принципа за неизчерпаемостта на природата: природата разполага със средствата да изпълни всяка задача, правилно формулирана от човека.

В конвенционален компютър информацията се кодира като последователност от битове и тези битове се обработват последователно от булеви логически елементи, за да се получи желаният резултат. По подобен начин квантовият компютър обработва кубити чрез извършване на последователност от операции върху квантови логически порти, всяка от които представлява единна трансформация, действаща върху единичен кубит или двойка кубити. Чрез последователно извършване на тези трансформации, квантовият компютър може да извърши сложна единна трансформация върху целия набор от кубити, подготвени в някакво първоначално състояние. След това можете да направите измервания на кубитите, които ще дадат крайния резултат от изчисленията. Тези прилики в изчисленията между квантов компютър и класически компютър предполагат, че поне на теория класическият компютър може точно да възпроизведе работата на квантов компютър. С други думи, класическият компютър може да направи всичко, което може да направи квантовият компютър. Тогава защо е целият този шум с квантовия компютър? Въпросът е, че въпреки че теоретично един класически компютър може да симулира квантов компютър, той е много неефективен, толкова неефективен, че на практика класическият компютър не е в състояние да реши много проблеми, които може да направи квантовият компютър. Симулирането на квантов компютър на класически компютър е изчислително труден проблем, тъй като корелациите между квантовите битове са качествено различни от корелациите между класическите битове, както беше показано за първи път от Джон Бел. Например можем да вземем система от само няколкостотин кубита. Съществува в хилбертовото пространство с размерност ~10 90 , което би изисквало при моделиране с класически компютър използването на експоненциално големи матрици (за извършване на изчисления за всяко отделно състояние, което също е описано от матрицата). Това означава, че класическият компютър ще отнеме експоненциално повече време в сравнение дори с примитивен квантов компютър.

Ричард Файнман беше сред първите, които разпознаха потенциала на квантовата суперпозиция за решаване на подобни проблеми много по-бързо. Например, система от 500 кубита, която е почти невъзможно да се моделира класически, е квантова суперпозиция на 2 500 държави. Всяка стойност на такава суперпозиция е класически еквивалентна на списък от 500 единици и нули. Всякаква квантова операция върху такава система, например настроен импулс от радиовълни, който може да извърши контролирана НЕ операция върху, да речем, 100-ия и 101-вия кубит, ще повлияе едновременно 2 500 държави. По този начин, в един тик на часовника на компютъра, квантовата операция изчислява не едно състояние на машината, както конвенционалните компютри, а 2 500 заявява веднага! Въпреки това, в крайна сметка се извършва измерване на системата от кубити и системата се срива в едно квантово състояние, съответстващо на едно решение на проблема, единичен набор от 500 единици и нули, както е продиктувано от аксиомата за измерване на квантовата механика. Това е наистина вълнуващ резултат, тъй като това решение, намерено чрез колективен процес на квантово паралелно изчисление с произход от суперпозиция, е еквивалентно на извършване на същата операция на класически суперкомпютър с ~ 10 150 отделни процесори (което разбира се е невъзможно)!! Първите изследователи в тази област, разбира се, бяха вдъхновени от такива гигантски възможности и така скоро започна търсенето на подходящи проблеми за такава изчислителна мощност. Питър Шор, изследовател и компютърен учен в Bell Laboratories на AT&T в Ню Джърси, предложи проблем, който може да бъде решен на квантов компютър и с помощта на квантов алгоритъм на Шор използва силата на квантовата суперпозиция за разлагане на големи числа (от порядъка на). ~10 200 бита или повече) за няколко секунди. Този проблем има важни практически приложения за криптиране, където общоприетият (и най-добър) алгоритъм за криптиране, известен като RSA, се основава точно на сложността на разлагането на големи съставни числа. който лесно решава този проблем, разбира се, е от голям интерес за много правителствени организации, използващи RSA, който досега се смяташе за „неподлежащ на хакване“, и за всеки, който се интересува от сигурността на техните данни.

Шифроването обаче е само едно възможно приложение на квантов компютър. Шор е разработил цял набор от математически операции, които могат да се извършват изключително на квантов компютър. Някои от тези операции се използват в неговия алгоритъм за факторизация. Освен това Файнман твърди, че квантовият компютър може да действа като симулационно устройство за квантовата физика, потенциално отваряйки вратата към много открития в тази област. В момента мощността и възможностите на квантовия компютър са основно въпрос на теоретични спекулации; появата на първия наистина функционален квантов компютър несъмнено ще донесе много нови и вълнуващи практически приложения.

Глава III . Алгоритъм на Гроувър

Проблемът с търсенето е следният: има неподредена база данни, състояща се от N-елементи, от които само един отговаря на зададените условия - това е елементът, който трябва да бъде намерен. Ако даден елемент може да бъде проверен, тогава определянето дали той отговаря на необходимите условия или не е процес в една стъпка. Базата данни обаче е такава, че няма подреждане, което да помогне при избора на артикул. Най-ефективният класически алгоритъм за тази задача е да проверявате елементите от базата данни един по един. Ако елементът отговаря на необходимите условия, търсенето приключва; ако не, елементът се оставя настрана, така че да не се проверява отново. Очевидно този алгоритъм изисква да бъдат проверени средни елементи, преди да бъде намерен желаният.

Когато прилагате този алгоритъм, можете да използвате същото оборудване, както в класическия случай, но като посочите входа и изхода във формата суперпозициидържави, можете да намерите обект за О () квантово механични стъпкивместо ОТНОСНО( н )) класически стъпки. Всяка квантовомеханична стъпка се състои от елементарна единична операция, която ще разгледаме по-долу.

За да приложим този алгоритъм, са ни необходими следните три елементарни операции. Първият е подготовката на състояние, в което системата е с еднаква вероятност във всяко от своите N основни състояния; второто е преобразуването на Адамар, а третото е селективното фазово въртене на състоянията.

Както е известно, основната операция за квантовите изчисления е операцията М, действащ на бит, който е представен от следната матрица:

тоест бит в състояние 0 се превръща в суперпозиция на две състояния: (1/, 1/). По подобен начин бит в състояние 1 се трансформира в (1/, -1/,), т.е. стойността на амплитудата за всяко състояние е 1/, но фазата в състояние 1 е обърната. Фазата няма аналог в класическите вероятностни алгоритми. Възниква в квантовата механика, където амплитудата на вероятността е сложна. В система, в която се описва държавата Пбитове (т.е. има N = 2 pвъзможни състояния), можем да извършим трансформацията Мна всеки бит независимо, последователно променяйки състоянието на системата. В случай, че първоначалната конфигурация е била конфигурация с Пбитове в първото състояние, получената конфигурация ще има еднакви амплитуди за всяко състояние. Това е начинът да се създаде суперпозиция с еднаква амплитуда за всички състояния.

Третата трансформация, от която ще се нуждаем, е селективно да завъртим фазата на амплитудата в определени състояния. Трансформацията, представена тук за система с две състояния, е във формата:

Където й = И - произволни реални числа. Обърнете внимание, че за разлика от трансформацията на Адамар и други матрици за трансформация на състоянието, вероятността за всяко състояние остава същата, тъй като квадратът на абсолютната величина на амплитудата във всяко състояние остава същият.

Нека разгледаме проблема в абстрактна форма.

Нека системата има N = 2 pсъстояния, които се означават като ,..., . Тези 2 стрсъстоянията са представени като n-битови низове. Нека има едно състояние, да речем, което удовлетворява условието C() = 1, докато за всички останали състояния S, С( ,) = 0 (приема се, че за всяко състояние S условието се оценява за единица време). Задачата е да се признае държавата

Да преминем към самия алгоритъм

Стъпки (1) и (2) са последователност от елементарни унитарни операции, описани по-рано. Стъпка (3) е последното измерване, извършено от външната система.

(1) Привеждаме системата в състояние на суперпозиция:

с еднакви амплитуди за всяко от N състояния. Тази суперпозиция може да се получи на стъпки.

(2) Нека повторим следната единична операция ОТНОСНО( ) веднъж:

а. Нека системата е в някакво състояние S:

Кога С( С ) = 1, завъртете фазата по радиан;

Кога С(S) = 0, оставете системата непроменена.

b . Прилагане на дифузионна трансформация дкоето се определя от матрицата дкакто следва: ако ;" и . дможе да се реализира като последователно изпълнение на унитарни трансформации: , където У– матрица на трансформация на Адамар, R – матрица на фазово въртене.

(3) Измерете полученото състояние. Тази държава ще бъде държавата С( )„ (т.е. желаното състояние, което удовлетворява условието (C() = 1) с вероятност най-малко не по-малка от 0,5. Обърнете внимание, че стъпка (2а) е ротация на фазата. Нейното изпълнение трябва да включва състояние на процедура за разпознаване и последващото определяне дали да се осъществи ротацията на фазите, трябва да се извърши по такъв начин, че да не се остави следа върху състоянието на системата, така че да има увереност, че пътищата, водещи до едно и също крайно състояние, са неразличими. и може да попречи на тази процедура Невключва класически измервания.

Този алгоритъм за квантово търсене вероятно ще бъде по-лесен за изпълнение в сравнение с много други известни квантово-механични алгоритми, тъй като необходимите операции са само преобразуването на Walsh-Adamard и операцията за условно фазово изместване, всяка от които е относително проста в сравнение с операциите, използвани от другите квантово-механични алгоритми.

Заключение

В момента квантовите компютри и квантовите информационни технологии остават в състояние на пионерско развитие. Решаването на трудностите, с които се сблъскват тези технологии в момента, ще гарантира, че квантовите компютри ще напреднат на полагащото им се място като най-бързите физически изчислителни машини. Досега коригирането на грешки е напреднало значително, доближавайки ни до точката, в която можем да създаваме компютри, които са достатъчно здрави, за да издържат на ефектите от декохерентността. От друга страна, създаването на квантово оборудване все още е само нововъзникваща индустрия; но извършената до момента работа ни убеждава, че е само въпрос на време да можем да изградим достатъчно големи машини, за да изпълняват сериозни алгоритми като алгоритъма на Шор. Така определено ще се появят квантовите компютри. Най-малкото това ще бъдат най-модерните изчислителни устройства и компютрите, които имаме днес, ще остареят. Квантовото изчисление води началото си от много специфични области на теоретичната физика, но бъдещето му несъмнено ще окаже огромно влияние върху живота на цялото човечество.

Библиография

1. Квантово изчисление: плюсове и минуси. Изд. В.А. Садовничиго. – Ижевск: Издателство на Удмуртския университет, 1999. – 212 с.

2. Belonuchkin V.E., Zaikin D.A., Tsypenyuk Yu.M., Основи на физиката. Общ курс по физика: Учебник. В 2 т. Т. 2. Квантова и статистическа физика. – М.: ФИЗМАТЛИТ, 2001. – 504 с.

3. Валиев К.А. „Квантови компютри: могат ли да бъдат направени „големи“?“, Напредък във физическите науки, том 169, № 6, 1999 г.

4. Валиев К.А. “Квантова информатика: компютри, комуникации и криптография”, БЮЛЕТИН НА РУСКАТА АКАДЕМИЯ НА НАУКИТЕ, том 70, № 8, стр. 688-695, 2000 г

5. Маслов. D. „Квантово изчисление и комуникация: реалност и перспективи“, Computerra, № 46, 2004 г.

6. Халфин Л.А. “Квантов ефект на Зенон”, Напредък във физическите науки, т. 160, № 10, 1990 г.

7. Kholevo A. “Квантова информационна наука: минало, настояще, бъдеще”,

В СВЕТА НА НАУКАТА, бр.7, 2008г.

8. Център за квантови технологии, Национален университет на Сингапур www.quantumlah.org

Историческа справка

Квантовото изчисление е немислимо без контрол върху квантовото състояние на отделните елементарни частици. Двама физици - французинът Серж Лрош и американецът Дейвид Уайнланд - успяват. Лрош улови единични фотони в резонатора и ги „откачи“ от външния свят за дълго време. Wineland улавя единични йони със специфични квантови състояния и ги изолира от външни влияния. Харош използва атоми, за да наблюдава състоянието на фотона. Wineland използва фотони, за да промени състоянията на йони. Те успяха да постигнат напредък в изучаването на връзката между квантовия и класическия свят. Те бяха удостоени с Нобелова награда за физика за 2012 г. за „революционни експериментални техники, които направиха възможно измерването и контрола на отделни квантови системи“.

Работата на квантовите компютри се основава на свойствата на квантовия бит информация. Ако изчислителните процеси използват Пкубити, тогава пространството на състоянието на Хилберт на квантова система има измерение, равно на 2". Под Хилбертово пространствоние ще разберем дименсионално векторно пространство, в което скаларното произведение е дефинирано при условие, че стойността клони към Пдо безкрайност.

В нашия случай това означава, че има 2" базови състояния и компютърът може да работи върху суперпозиция на тези 2" базови състояния.

Обърнете внимание, че въздействието върху който и да е кубит незабавно води до едновременна промяна във всички 2” основни състояния. Това свойство се нарича „квантов паралелизъм».

Квантовото изчисление е единна трансформация. Това означава, че се извършва линейна трансформация с комплексни коефициенти, като сумата от квадратите на трансформираните променливи остава непроменена. Унитарната трансформация е ортогонална трансформация, при която коефициентите образуват унитарна матрица.

Под унитарна матрицаще разбираме квадратната матрица ||aj|, чийто продукт от комплексно спрегнатата и транспонираната матрица || aJI дава матрицата на идентичността. Числа айкИ a kiкомплекс. Ако числата a ikса реални числа, тогава унитарната матрица ще бъде ортогонална. Определен брой кубити образуват квантовия регистър на компютъра. В такава верига от квантови битове едно- и двубитовите логически операции могат да се извършват по същия начин, както операциите NOT, NAND, 2 OR-HE и т.н. се извършват в класически регистър. (фиг. 5.49).

Конкретен номер нрегистрите формират по същество квантов компютър. Работата на квантовия компютър се извършва в съответствие с разработени алгоритми за изчисление.

Ориз. 5.49.

НЕ - булево НЕ; CNOT - контролирано НЕ

Кубитите като носители на информация имат редица интересни свойства, които напълно ги отличават от класическите битове. Една от основните тези на квантовата теория на информацията е държавно заплитане.Да предположим, че има два кубита на две нива АИ IN,реализирани под формата на атом с електронен или ядрен спин, молекула с два ядрени спина. Поради взаимодействието на две подсистеми АИ INвъзниква нелокална корелация, която е чисто квантова по природа. Тази корелация може да бъде описана чрез матрицата на плътността на смесеното състояние

Където p i- популация или вероятност аз-състояние, т.н R ( + стр. 2 + стр. 3 + + Ra = 1-

Свойството на кохерентните квантови състояния да имат сума от вероятности, равна на единица, се нарича заплитане или свързване на състояния. Заплетените или заплетени квантови обекти са свързани помежду си, независимо колко далеч се намират един от друг. Ако се измери състоянието на един от свързаните обекти, веднага се получава информация за състоянието на други обекти.

Ако два кубита са свързани, тогава те са лишени от индивидуални квантови състояния. Те зависят един от друг по такъв начин, че измерването за единия тип дава "О", а за другия - "1" и обратно (фиг. 5.50). В този случай се казва, че максимално свързаната двойка носи едно е-битсплотеност.

Заплетените състояния са ресурс в квантовите изчислителни устройства и трябва да се разработят методи за надеждно генериране на заплетени кубити, за да се попълни броят на заплетените състояния. Един от методите

Ориз. 5.50.Схемата за максимално заплетена двойка кубити е алгоритмичен начин за получаване на заплетени кубити върху йони в капани, ядрени завъртания или двойка фотони. Процесът на разпадане на частица в синглетно състояние на две частици може да бъде много ефективен. В този случай се генерират двойки частици, които са заплетени в координата, импулс или спин.

Разработването на цялостна теория за заплитането е ключова цел на теорията на квантовата информация. С негова помощ ще бъде възможно да се доближим до решаването на проблемите с телепортацията, свръхплътното кодиране, криптографията и компресирането на данни. За тази цел се разработват квантови алгоритми, включително квантови трансформации на Фурие.

Изчислителната схема на квантов компютър има следния алгоритъм: формира се система от кубити, на която се записва първоначалното състояние. Чрез унитарни трансформации състоянието на системата и нейните подсистеми се променя, когато се извършват логически операции. Процесът завършва с измерване на нови стойности на кубити. Ролята на свързващи проводници на класически компютър се играе от кубити, а логическите блокове на класически компютър се играят от унитарни трансформации. Тази концепция за квантов процесор и квантови логически порти е формулирана през 1989 г. от Дейвид Дойч. След това той предложи универсален логически блок, който може да се използва за извършване на всякакви квантови изчисления.

Алгоритъм на Дойна-Джоживи позволява да определите „в едно изчисление“ дали функция на двоична променлива /(/?) е константа (f x (ri)= О, f 2 (ri) = 1 независимо П)или "балансиран" (f 3 ( 0) = 0,/ 3 (1) = 1;/ 4 (0) = 1, / 4 (1) = 0).

Оказа се, че за изграждането на всяко изчисление са достатъчни две основни операции. Квантовата система дава резултат, който е правилен само с известна вероятност. Но като увеличите леко операциите в алгоритъма, можете да доближите вероятността за получаване на правилния резултат възможно най-близо до единица. С помощта на основни квантови операции е възможно да се симулира работата на обикновени логически порти, които изграждат обикновените компютри.

Алгоритъм на Гроувърни позволява да намерим решение на уравнението f(x) = 1 за 0 x за време O(VN) и е предназначен за търсене в база данни. Квантовият алгоритъм на Гроувър очевидно е по-ефективен от всеки алгоритъм за неподредено търсене на класически компютър.

Алгоритъм на Шор за факторизацияви позволява да определите за прости множители аубдадено цяло число M= a"Xbчрез използване на подходяща квантова верига. Този алгоритъм ви позволява да намерите множителите на A-цифрено цяло число. Може да се използва за оценка на времето на изчислителния процес. В същото време алгоритъмът на Шор може да се тълкува като пример за процедура за определяне на енергийните нива на квантова изчислителна система.

Алгоритъм на Zalka-Wiesnerви позволява да симулирате единната еволюция на квантова система Пчастици в почти линейно време, използвайки На)кубити.

Алгоритъмът на Саймънрешава проблема с черната кутия експоненциално по-бързо от всеки класически алгоритъм, включително вероятностните алгоритми.

Алгоритъм за коригиране на грешкидава възможност да се повиши шумоустойчивостта на квантова изчислителна система, която е податлива на разрушаване на крехки квантови състояния. Същността на този алгоритъм е, че той не изисква клониране на кубити и определяне на тяхното състояние. Формира се квантова логическа верига, която е в състояние да открие грешка във всеки кубит, без действително да чете отделното състояние. Например триплет 010, преминаващ през такова устройство, открива неправилен среден бит. Устройството го обръща, без да определя конкретните стойности на някой от трите бита. Така въз основа на теорията на информацията и квантовата механика възниква един от основните алгоритми - квантова корекция на грешки.

Изброените проблеми са важни за създаването на квантов компютър, но попадат в компетенциите на квантовите програмисти.

Квантовият компютър е по-прогресивен от класическия по редица показатели. Повечето съвременни компютри работят по схемата на фон Нойман или Харвард: Пбитовете на паметта съхраняват състоянието и се променят от процесора всеки път, когато отметнете. В квантов компютър, система от П qubits е в състояние, което е суперпозиция на всички основни състояния, така че промяната в системата засяга всички 2" основни състояния едновременно. Теоретично новата схема може да работи експоненциално по-бързо от класическата. Почти квантов алгоритъм за търсене в база данни показва квадратично увеличение на мощността в сравнение с класическите алгоритми.

Съдържанието на понятието „квантов паралелизъм” може да бъде разкрито по следния начин: „Данните в процеса на изчисление представляват квантова информация, която в края на процеса се преобразува в класическа информация чрез измерване на крайното състояние на квантовия регистър. Печалбата в квантовите алгоритми се постига поради факта, че при прилагане на една квантова операция, голям брой коефициенти на суперпозиция на квантови състояния, които съдържат класическа информация във виртуална форма, се трансформират едновременно.“

Квантовото заплитане, наричано още „квантова суперпозиция“, обикновено означава следното: „Представете си атом, който може да претърпи радиоактивен разпад за определен период от време, или можем да очакваме, че този атом има само две възможни състояния: „разпад ” и „не разпад”, /…/ но в квантовата механика един атом може да има някакво единно състояние – „разпад – не разпад”, тоест нито едното, нито другото, а като че ли между това състояние се нарича „суперпозиция“.

Основните характеристики на квантовите компютри на теория им позволяват да преодолеят някои от ограниченията, срещани при работата на класическите компютри.

Теория

Кюбити

Идеята за квантовите изчисления, изразена за първи път от Ю. И. Манин и Р. Фейнман, е, че квантовата система на Лдвустепенните квантови елементи (кубити) имат 2 Ллинейно независими състояния и следователно, поради принципа на квантовата суперпозиция, 2 Л-мерно Хилбертово пространство на състоянията. Една операция в квантовите изчисления съответства на ротация в това пространство. По този начин, квантово изчислително устройство с размер Л qubit може да изпълни 2 паралелно Лоперации.

Да приемем, че има един кубит. В този случай, след измерване, в така наречената класическа форма, резултатът ще бъде 0 или 1. В действителност кубитът е квантов обект и следователно, поради принципа на неопределеността, той може да бъде както 0, така и 1 с a определена вероятност. Ако кубитът е 0 (или 1) със стопроцентова вероятност, състоянието му се обозначава със символа |0> (или |1>) - в нотацията на Дирак. |0> и |1> са основните състояния. В общия случай квантовото състояние на кубита е между базовите и се записва във вида , където | а|² и | b|² - вероятности за измерване съответно 0 или 1; ; | а|² + | b|² = 1. Освен това, веднага след измерването кубитът преминава в основното квантово състояние, подобно на класическия резултат.

Има кубит в квантово състояние В този случай вероятността да получим при измерване В този случай при измерване получихме 0 с 64% вероятност. Тогава кубитът преминава в ново квантово състояние 1*|0>+0*|1>=|0>, тоест следващия път, когато измерим този кубит, ще получим 0 със сто процента вероятност. Това се дължи на факта, че векторът на състоянието на Дирак не зависи от времето, т.е. той се разлага на сума от вектори на основни състояния с независещи от времето коефициенти.

За да обясним това, нека дадем два примера от квантовата механика: 1) фотонът е в състояние на суперпозиция на две поляризации; измерването веднъж завинаги свива състоянието на фотона в едно с определена поляризация; 2) радиоактивният атом има определен период на полуразпад; едно измерване може да разкрие, че то все още не се е разпаднало, но това не означава, че никога няма да се разпадне.

Нека да преминем към система от два кубита. Измерването на всяко от тях може да даде 0 или 1. Следователно системата има 4 класически състояния: 00, 01, 10 и 11. Основните квантови състояния са подобни на тях: |00>, |01>, |10> и |11 >. И накрая, общото квантово състояние на системата има формата . Сега | а|² - вероятност за измерване 00 и т.н. Обърнете внимание, че | а|²+| b|²+| ° С|²+| д|²=1 като общата вероятност.

Като цяло системите от Лима 2 кубита Лкласически състояния (00000...(L-нули),...00001(L-цифри),..., 11111...(L-единици)), всяко от които може да бъде измерено с вероятности от 0-100 %.

Така една операция върху група кубити засяга всички стойности, които може да приеме, за разлика от класическия бит. Това осигурява безпрецедентен паралелизъм на изчисленията.

Изчисляване

Опростена схема за изчисление на квантов компютър изглежда така: взема се система от кубити, на която се записва първоначалното състояние. След това състоянието на системата или нейните подсистеми се променя чрез основни квантови операции. Накрая се измерва стойността и това е резултатът от компютъра.

Оказва се, че за конструирането на всяко изчисление са достатъчни две основни операции. Квантовата система дава резултат, който е правилен само с известна вероятност. Но като увеличите леко операциите в алгоритъма, можете да доближите вероятността за получаване на правилния резултат възможно най-близо до единица.

С помощта на основни квантови операции е възможно да се симулира работата на обикновени логически порти, които изграждат обикновените компютри. Следователно всеки проблем, който е решен сега, ще бъде решен от квантов компютър и то почти за същото време. Следователно новата схема за изчисление няма да бъде по-слаба от сегашната.

Защо квантовият компютър е по-добър от класическия? Повечето съвременни компютри работят по същата схема: n бита от състоянието на паметта се съхраняват и се променят от процесора всеки времеви цикъл. В квантовия случай система от n кубита е в състояние, което е суперпозиция на всички основни състояния, така че промяната в системата засяга всички 2 nосновни състояния едновременно. Теоретично новата схема може да работи много (експоненциално много пъти) по-бързо от класическата. На практика алгоритъмът за търсене на (квантовата) база данни на Grover показва квадратично увеличение на мощността в сравнение с класическите алгоритми. Засега те не съществуват в природата.

Алгоритми

Беше показано, че "квантовото ускорение" не е възможно за всеки алгоритъм.

Квантова телепортация

Алгоритъмът за телепортация реализира точното прехвърляне на състоянието на един кубит (или система) към друг. Най-простата схема използва 4 кубита: източник, приемник и два спомагателни. Обърнете внимание, че в резултат на алгоритъма първоначалното състояние на източника ще бъде унищожено - това е пример за действието на общия принцип на невъзможност за клониране- невъзможно е да се създаде точно копие на квантово състояние, без да се разруши оригиналът. Всъщност е доста лесно да се създадат идентични състояния на кубити. Например, след като измерихме 3 кубита, ние ще прехвърлим всеки от тях в основните състояния (0 или 1) и поне на два от тях те ще съвпаднат. Не може да се копира произволенсъстояние, а телепортацията е заместител на тази операция.

Телепортацията ви позволява да прехвърлите квантовото състояние на система, като използвате обикновени класически комуникационни канали. По този начин е възможно по-специално да се получи свързаното състояние на система, състояща се от подсистеми, разположени на голямо разстояние.

Приложения на квантовите компютри

Специфика на приложението

Може да изглежда, че квантовият компютър е вид аналогов компютър. Но това не е вярно: в основата си това е цифрово устройство, но с аналогов характер.

Основните проблеми, свързани със създаването и използването на квантови компютри:

• необходимо е да се осигури висока точност на измерване;
• външните влияния могат да разрушат квантовата система или да внесат изкривявания в нея.

Приложения в криптографията

Благодарение на огромната скорост на разлагане на прости множители, квантовият компютър ще направи възможно дешифрирането на съобщения, криптирани с помощта на популярен асиметричен криптографски алгоритъм, отваряйки нови възможности в областта на предаването на съобщения. Прототипите на такива системи са в етап на разработка.

Реализации

Канадската компания D-Wave обяви през февруари 2007 г. създаването на примерен квантов компютър, състоящ се от 16 кубита (устройството беше наречено Orion). Информацията за това устройство обаче не отговаряше на строгите изисквания за точни научни доклади; новината не получи научно признание. Освен това по-нататъшните планове на компанията (създаване на 1024-кубитов компютър в близко бъдеще) предизвикаха скептицизъм сред членовете на експертната общност.

През ноември 2007 г. същата компания, D-Wave, демонстрира работата на примерен 28-кубитов компютър онлайн на конференция за суперкомпютри. Тази демонстрация предизвика и известен вид скептицизъм.

През декември 2008 г. компанията организира проекта за разпределени изчисления AQUA@home( Адиабатичен QUантум А lgorithms), който тества алгоритми, които оптимизират изчисленията на D-Wave адиабатни свръхпроводящи квантови компютри.

Вижте също

Бележки

Литература

• Килин С.Я.Кванти и информация / Прогрес в оптиката. - 2001. - кн. 42. - С. 1-90.
• Килин С. Я.Квантова информация / Напредък във физическите науки. - 1999. - Т. 169. - С. 507-527.
• Плюсове и минуси на квантовите изчисления. Изд. Садовничи В. А.
• Квантов компютър и квантово изчисление. Изд. Садовничи В. А.
• Валиев К. А., Кокин А. А. Квантовите компютри: надежди и реалност. Москва, Ижевск: Регулярна и хаотична динамика, 2004. 320 с. ISBN 5-93972-024-2

Връзки

• Квантов компютър и неговата полупроводникова елементарна база
• Китаев, А., Шен, А., Вялий, М.Класическо и квантово изчисление
• QWiki (английски) и Quantiki (английски) - Wiki ресурси за наука за квантовата информация
• Език за програмиране QCL за квантови компютри
• Курс „Съвременни проблеми на теоретичната компютърна наука“ (лекции по квантово изчисление: въведение, свръхплътно кодиране, квантова телепортация, алгоритми на Саймън и Шор)
• InFuture.ru: Бъдещето на квантовите компютри е в троичните изчисления
• Валиев К. А. “Квантови компютри и квантово изчисление” UFN 175 3 (2005)

Фондация Уикимедия. 2010 г.

• Ефект на квантовия размер
• Квантови размерни ефекти

Вижте какво е „Квантово изчисление“ в други речници:

Квантови компютри- 3 кубита от квантов регистър срещу 3 бита от конвенционален Квантовият компютър е хипотетично изчислително устройство, което чрез изпълнение на квантови алгоритми значително използва квантово-механични ефекти в работата си, като например ... ... Wikipedia.

ТОПОЛОГИЧНИ ТЕОРИИ ЗА КВАНТОВО ПОЛЕ- квантова механика или квантови теории на полето, всички корелационни функции, в които не зависят от избора на координати и метрики както в пространство-времето, така и в други пространства, включени в дефинирането на теорията. Това ви позволява да използвате... ... Физическа енциклопедия

Квантов компютър- 3 кубита на квантов регистър срещу 3 бита на конвенционален регистър Квантовият компютър е изчислително устройство, работещо на базата на квантовата механика. Квантовият компютър е фундаментално различен от класическите компютри, базирани на ... Wikipedia

Заради общия бум на блокчейн и всякакви големи данни, още една обещаваща тема отпадна от върха на технологичните новини – квантовите компютри. И те, между другото, са в състояние да революционизират няколко ИТ области наведнъж, като се започне с прословутата блокчейн и завърши с информационната сигурност. В следващите две статии Sberbank и Sberbank Technologies ще ви кажат защо квантовите изчисления са готини и какво правят с тях сега.

Класически изчисления: И, ИЛИ, НЕ

За да разберете квантовите изчисления, първо трябва да освежите класическите изчисления. Тук единицата обработвана информация е бит. Всеки бит може да бъде само в едно от две възможни състояния - 0 или 1. Регистър от N бита може да съдържа една от 2 N възможни комбинации от състояния и се представя като последователност от тях.

За обработка и преобразуване на информация се използват побитови операции, произхождащи от булевата алгебра. Основните операции са еднобитово НЕ и двубитово И и ИЛИ. Битовите операции са описани чрез таблици на истината. Те показват съответствието на входните аргументи с получената стойност.

Класическият изчислителен алгоритъм е набор от последователни битови операции. Най-удобно е да го възпроизведете графично, под формата на диаграма на функционални елементи (SFE), където всяка операция има свое собствено обозначение. Ето пример за SFE за проверка на два бита за еквивалентност.

Квантово изчисление. Физическа основа

Сега да преминем към нова тема. Квантовото изчисление е алтернатива на класическите алгоритми, базирани на процесите на квантовата физика. Той гласи, че без взаимодействие с други частици (т.е. до момента на измерване) електронът няма еднозначни координати в орбитата на атома, но се намира едновременно във всички точки на орбитата. Областта, в която се намира електронът, се нарича електронен облак. В известния експеримент с двоен процеп един електрон преминава през двата процепа едновременно, като се намесва сам в себе си. Само по време на измерване тази несигурност се срива и координатите на електрона стават недвусмислени.

Вероятностният характер на измерванията, присъщи на квантовите изчисления, е в основата на много алгоритми - например търсене в неструктурирана база данни. Алгоритмите от този тип стъпка по стъпка увеличават амплитудата на правилния резултат, което позволява да се получи на изхода с максимална вероятност.

Кюбити

В квантовите изчисления физическите свойства на квантовите обекти се реализират в така наречените кубити (q-битове). Един класически бит може да бъде само в едно състояние – 0 или 1. Преди измерване кубитът може да бъде в двете състояния едновременно, така че обикновено се означава с израза a|0⟩ + b|1⟩, където A и B са комплексни числа, отговарящи на условието |A | 2 +|B| 2 =1. Измерването на един кубит мигновено „свива“ състоянието му до едно от основните – 0 или 1. В този случай „облакът“ се свива в точка, първоначалното състояние се унищожава и цялата информация за него се губи безвъзвратно.

Едно приложение на това свойство е котката на Шрьодингер като истински генератор на случайни числа. Кубитът се въвежда в състояние, в което резултатът от измерването може да бъде 1 или 0 с еднаква вероятност. Това състояние се описва, както следва:

Квантово и класическо изчисление. Първи рунд

Да започнем с основите. Има набор от начални данни за изчисления, представени в двоичен формат чрез вектори с дължина N.

При класическите изчисления само една от 2 n опции за данни се зарежда в паметта на компютъра и стойността на функцията се изчислява за тази опция. В резултат на това само единот 2 n възможни набора от данни.

Всичките 2 n комбинации от изходни данни са едновременно представени в паметта на квантов компютър. Трансформациите се прилагат към всички тези комбинации наведнъж. В резултат на това с една операция изчисляваме функцията за всички 2 n възможни варианта на набора от данни (измерването ще даде само едно решение в крайна сметка, но повече за това по-късно).

Както класическото, така и квантовото изчисление използват логически трансформации - порти. В класическите изчисления входните и изходните стойности се съхраняват в различни битове, което означава, че в портите броят на входовете може да се различава от броя на изходите:

Нека разгледаме един реален проблем. Трябва да определим дали два бита са еквивалентни.

Ако по време на класически изчисления получим едно на изхода, тогава те са еквивалентни, в противен случай не:

Сега нека си представим този проблем с помощта на квантово изчисление. В тях всички трансформационни врати имат еднакъв брой изходи като входове. Това се дължи на факта, че резултатът от трансформацията не е нова стойност, а промяна в състоянието на текущите.

В примера сравняваме стойностите на първия и втория кубит. Резултатът ще бъде в нулевия кубит - флаговия кубит. Този алгоритъм е приложим само за основните състояния - 0 или 1. Това е редът на квантовите трансформации.

1. Ние влияем върху флага на кубита с портата „Не“, като го настройваме на 1.
2. Ние използваме двукубитовата порта „Controlled Not“ два пъти. Тази врата обръща стойността на кубита на флага само ако вторият кубит, участващ в трансформацията, е в състояние 1.
3. Ние измерваме нулевия кубит. Ако резултатът е 1, тогава и първият, и вторият кубит са или в състояние 1 (кубитът на флага промени стойността си два пъти) или в състояние 0 (кубитът на флага остана в състояние 1). В противен случай кубитите са в различни състояния.

Следващо ниво. Квантови еднокубитови врати на Паули

Нека се опитаме да сравним класическите и квантовите изчисления в по-сериозни проблеми. За целта ни трябват малко повече теоретични познания.

В квантовите изчисления обработваната информация е кодирана в квантови битове - наречени кубити. В най-простия случай кубитът, подобно на класическия бит, може да бъде в едно от двете основни състояния: |0⟩ (кратка нотация за вектора 1|0⟩ + 0|1⟩) и |1⟩ (за вектора 0 |0⟩ + 1 |1⟩). Квантовият регистър е тензорен продукт на кубитни вектори. В най-простия случай, когато всеки кубит е в едно от основните състояния, квантовият регистър е еквивалентен на класическия. Регистър от два кубита в състояние |0> може да бъде написан по следния начин:

(1|0⟩ + 0|1⟩)*(1|0⟩ + 0|1⟩) = 1|00⟩ + 0|01⟩ + 0|10⟩ + 0|11⟩ = |00⟩.

За обработка и трансформиране на информация в квантови алгоритми се използват така наречените квантови порти. Те са представени под формата на матрица. За да получим резултата от прилагането на портата, трябва да умножим вектора, характеризиращ кубита, по матрицата на портата. Първата координата на вектора е множителят преди |0⟩, втората координата е множителят преди |1⟩. Матриците на основните еднокубитови порти изглеждат така:

Ето пример за използване на портата Not:

X * |0⟩ = X * (1|0⟩ + 0|1⟩) = 0|0⟩ + 1|1⟩ = |1⟩

Факторите пред базисните състояния се наричат ​​амплитуди и са комплексни числа. Модулът на комплексно число е равен на корена на сумата от квадратите на реалната и имагинерната част. Квадратът на големината на амплитудата пред базовото състояние е равен на вероятността за получаване на това базово състояние при измерване на кубит, така че сумата от квадратите на големината на амплитудите винаги е равна на 1. Можем да използваме произволни матрици за трансформации над кубити, но поради факта, че векторът на нормата (дължината) винаги трябва да бъде равен на 1 (сумата от вероятностите на всички резултати винаги е равна на 1), нашата трансформация трябва да запази нормата на вектора . Това означава, че трансформацията трябва да е унитарна и съответната матрица трябва да е унитарна. Припомнете си, че унитарната трансформация е обратима и UU † =I.

За по-ясна работа с кубити те са изобразени като вектори върху сферата на Bloch. В тази интерпретация портите с един кубит представляват въртенето на вектора на кубита около една от осите. Например портата Not(X) завърта вектора на кубита с Pi спрямо оста X, така състоянието |0>, представено от вектор, сочещ право нагоре, преминава в състояние |1>, сочещ право надолу. Състоянието на кубита върху сферата на Блок се определя от формулата cos(θ/2)|0⟩+e iϕ sin(θ/2)|1⟩

Квантови двукубитови порти

За да изградим алгоритми, само еднокубитови порти не са достатъчни за нас. Необходими са порти, които извършват трансформации в зависимост от определени условия. Основният такъв инструмент е двукубитовият порт CNOT. Този гейт се прилага към два кубита и обръща втория кубит само ако първият кубит е в състояние |1⟩. Матрицата на CNOT gate изглежда така:

Ето пример за приложение:

CNOT *|10⟩ = CNOT * (0|00⟩ + 0|01⟩ + 1|10⟩ + 0|11⟩) = 0|00⟩ + 0|01⟩ + 1|11⟩ + 0|10⟩ = |11⟩

Използването на порта CNOT е еквивалентно на извършване на класическа операция XOR и записване на резултата във втория кубит. Наистина, ако погледнем таблицата на истината на операторите XOR и CNOT, ще видим съответствието:

XOR			CNOT
0	0	0	00	00
0	1	1	01	01
1	0	1	10	11
1	1	0	11	10

Порталът CNOT има интересно свойство – след прилагането му кубитите се заплитат или разплитат, в зависимост от първоначалното състояние. Това ще бъде показано в следващата статия, в раздела за квантовия паралелизъм.

Построяване на алгоритъма – класическа и квантова реализация

С пълен арсенал от квантови порти можем да започнем да разработваме квантови алгоритми. В графично представяне кубитите са представени от прави линии - „струни“, върху които са насложени врати. Единичните кубитни порти на Паули са обозначени с обикновени квадрати, вътре в които е изобразена оста на въртене. Портата CNOT изглежда малко по-сложна:

Пример за използване на вратата CNOT:

Едно от най-важните действия в алгоритъма е измерването на получения резултат. Измерването обикновено се обозначава с дъгова скала със стрелка и обозначение по отношение на коя ос се извършва измерването.

И така, нека се опитаме да изградим класически и квантов алгоритъм, който добавя 3 към аргумента.

Сумирането на обикновени числа в колона предполага извършване на две действия върху всяка цифра - сумата от цифрите на самата цифра и сумата от резултата с прехвърляне от предишната операция, ако е имало такова прехвърляне.

В двоичното представяне на числата операцията за сумиране ще се състои от същите действия. Ето кода в python:

Arg = #задаване на аргумента резултат = #инициализиране на резултата carry1 = arg & 0x1 #добавяне с 0b11, така че пренасянето от ниския бит да се появи, ако аргументът има нисък бит = 1 резултат = arg ^ 0x1 #добавяне на ниските битове носят2 = носят1 | arg #add с 0b11, така че пренасянето от високия бит ще се появи, ако аргументът има високия бит = 1 или е имало пренасяне от ниския бит result = arg ^ 0x1 #добавете високите битове резултат ^= carry1 #apply carry от резултата с нисък бит ^= carry2 #приложи пренасяне от най-значимия бит print(result)
Сега нека се опитаме да разработим подобна програма за квантов компютър:

В тази схема първите два кубита са аргументът, следващите два са трансферите, а останалите 3 са резултатът. Ето как работи алгоритъмът.

1. Първата стъпка към бариерата е да зададете аргумента в същото състояние като в класическия случай - 0b11.
2. С помощта на оператора CNOT изчисляваме стойността на първото пренасяне - резултатът от операцията arg & 1 е равен на единица само когато arg е равно на 1, в който случай обръщаме втория кубит.
3. Следващите 2 гейта реализират добавянето на най-малките битове - прехвърляме кубит 4 в състояние |1⟩ и записваме резултата от XOR в него.
4. Големият правоъгълник представлява вратата CCNOT, разширение на вратата CNOT. Тази порта има два контролни кубита и третият е обърнат само ако първите два са в състояние |1. Комбинацията от 2 CNOT gate и един CCNOT gate ни дава резултата от класическата операция carry2 = carry1 | арг. Първите 2 порта пренасят към един, ако един от тях е 1, а портата CCNOT обработва случая, когато и двете са равни на единица.
5. Добавяме най-високите кубити и кубитите за трансфер.

Междинни заключения

Изпълнявайки двата примера, получаваме същия резултат. На квантов компютър това ще отнеме повече време, тъй като трябва да се извърши допълнителна компилация в код за квантов асемблиране и да се изпрати в облака за изпълнение. Използването на квантово изчисление би имало смисъл, ако скоростта на изпълнение на техните елементарни операции - порти - ще бъде многократно по-малка, отколкото в класическия модел.

Експертни измервания показват, че изпълнението на един гейт отнема около 1 наносекунда. Така че алгоритмите за квантовия компютър не трябва да копират класическите, а да използват максимално уникалните свойства на квантовата механика. В следващата статия ще разгледаме едно от основните такива свойства - квантовия паралелизъм - и ще говорим за квантовата оптимизация като цяло. След това ще идентифицираме най-подходящите области за квантово изчисление и ще опишем техните приложения.

Въз основа на материали