Демистифициране на принципите на квантовите изчисления

„Мисля, че мога спокойно да кажа, че никой не разбира квантовата механика.“ - Ричард Файнман

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

Статиите с популярна наука пропускат описания на квантовите системи и правят твърдения като:

Обикновеният бит може да бъде 1 или 0, но кубитът може да бъде 1 и 0 едновременно.

Ако имате голям късмет (в което не съм сигурен), ще ви бъде казано, че:

Кубитът е в суперпозиция между "1" и "0".

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

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

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

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

Общи логически портове и техните таблици на състоянията

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

Както споменах по-рано, имаме нужда от начин да представим цифровата логика математически. Първо, нека представим традиционната математическа логика. Използвайки линейна алгебра, класическите битове със стойности "1" и "0" могат да бъдат представени като два вектора на колони:

където са числата отляво Нотация на Дирак вектор. Като представяме нашите битове по този начин, можем да моделираме логически операции върху битовете, използвайки векторни трансформации. Моля, обърнете внимание: въпреки че използването на два бита в логическите портове може да извърши много операции (И, НЕ, XOR и т.н.), когато се използва един бит, могат да бъдат извършени само четири операции: преобразуване на идентичност, отрицание, изчисляване на константата „0“ и изчисляване на константата "1". При преобразуване на идентичност битът остава непроменен, при отрицание битовата стойност се променя на противоположната (от „0“ на „1“ или от „1“ на „0“) и изчисляването на константата „1“ или “0” задава бита на “1” или “0” независимо от предишната му стойност.

Идентичност	Трансформация на идентичността
отрицание	отричане
Константа-0	Изчисляване на константата "0"
Константа-1	Изчисляване на константата "1"

Въз основа на предложеното от нас ново представяне на бит е доста лесно да се извършват операции върху съответния бит с помощта на векторна трансформация:

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

С тензорно произведение отделните битове могат да бъдат представени от много битове:

Сега, когато имаме почти всички необходими математически концепции, нека преминем към нашата първа квантова логическа врата. Това е операторът NOT, или контролирано Не (NOT), което е от голямо значение при обратимото и квантово изчисление. Елементът CNOT се прилага към два бита и връща два бита. Първият бит е обозначен като „контролен“, а вторият като „контролен“. Ако контролният бит е зададен на "1", контролният бит променя стойността си; Ако контролният бит е настроен на "0", контролният бит не се променя.

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

За да демонстрирам всичко, което разгледахме досега, ще ви покажа как да използвате елемента CNOT върху множество битове:

За да обобщим вече казаното: в първия пример разлагаме |10⟩ на части от неговия тензорен продукт и използваме матрицата CNOT, за да получим ново съответстващо състояние на продукта; след това го факторизираме на |11⟩ според таблицата на стойностите на CNOT, дадена по-рано.

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

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

където a₀ и a₁ представляват съответно амплитудите |0⟩ и |1⟩. Те могат да се разглеждат като „квантови вероятности“, които представляват вероятността кубит да се срине в едно от състоянията, след като бъде измерен, тъй като в квантовата механика обект в суперпозиция се срива в едно от състоянията, след като бъде фиксиран. Нека разширим този израз и да получим следното:

За да опростя обяснението си, това е представянето, което ще използвам в тази статия.

За този кюбит шансът за свиване до стойността a₀ след измерване е равно на |a₀|² и шансът за свиване до стойността a₁ е равно на |a₁|². Например за следния кубит:

шансът за свиване в „1“ е равен на |1/ √2|² или ½, тоест 50/50.

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

Ако сте запознати с тригонометрията, ще забележите, че това уравнение съответства на Питагоровата теорема (a²+b²=c²), тоест можем да представим графично възможните състояния на кубита като точки върху единичната окръжност, а именно:

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

Преди да продължим, нека ви напомня, че амплитудните стойности a₀ и a₁ всъщност са комплексни числа, така че състоянието на кубита може най-точно да бъде картографирано върху триизмерна единична сфера, известна още като Сфера за бълхи:

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

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

Един от най-важните оператори е "елементът на Адамар": той взема бит в състояние "0" или "1" и го поставя в подходяща суперпозиция с 50% шанс да се свие в "1" или "0" след измерване. 

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

Друг важен момент за елемента на Адамар е неговата обратимост, което означава, че може да вземе кубит в подходящата суперпозиция и да го трансформира в |0⟩ или |1⟩.

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

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

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

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

Тоест, ако започнем с бит |0⟩, приложим битова инверсия и след това операция на Адамар, след това друга битова инверсия и отново операция на Адамар, последвана от последна битова инверсия, завършваме с вектора, даден от on дясната страна на веригата. Като наслагваме различни държавни машини една върху друга, можем да започнем от |0⟩ и да проследим цветните стрелки, съответстващи на всяка от трансформациите, за да разберем как работи всичко.

Тъй като стигнахме дотук, време е да разгледаме един от видовете квантови алгоритми, а именно - Алгоритъм на Deutsch-Jozsa, и показва предимството му пред класическия компютър. Струва си да се отбележи, че алгоритъмът на Deutsch-Jozsa е напълно детерминистичен, тоест връща правилния отговор в 100% от времето (за разлика от много други квантови алгоритми, базирани на вероятностната дефиниция на кубитите).

Нека си представим, че имате черна кутия, която съдържа функция/оператор на един бит (запомнете - с един бит могат да бъдат извършени само четири операции: преобразуване на идентичност, отрицание, оценка на константата "0" и оценка на константата "1" "). Каква точно функция изпълнява кутията? Не знаете кой, но можете да преминете през колкото искате варианти на входни стойности и да оцените изходните резултати.

Колко входа и изхода ще трябва да преминете през черната кутия, за да разберете коя функция се използва? Помислете за това за секунда.

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

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

Функцията, използвана в полето, е променлива, ако различни стойности на входния сигнал дават различни резултати на изхода (например преобразуване на идентичност и битова инверсия) и ако изходната стойност не се променя независимо от входната стойност, тогава функцията е постоянна (например изчисляване на константа "1" или изчисляване на константа "0").

С помощта на квантов алгоритъм можете да определите дали дадена функция в черна кутия е постоянна или променлива въз основа само на една заявка. Но преди да разгледаме как да направим това в детайли, трябва да намерим начин да структурираме всяка от тези функции на квантов компютър. Тъй като всички квантови оператори трябва да са обратими, веднага се сблъскваме с проблем: функциите за изчисляване на константите „1“ и „0“ не са.

Често срещано решение, използвано в квантовите изчисления, е да се добави допълнителен изходен кюбит, който връща каквато и да е входна стойност, която функцията получава. 

Преди:	след:

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

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

Например, ето как можете да приложите функцията за изчисляване на константата "0":

Изчисляване на константата "0":

Тук изобщо не ни трябват оператори. Първият входен кубит (който приехме, че е | 0⟩) ​​се връща със същата стойност, а втората входна стойност се връща сама - както обикновено.

С функцията за изчисляване на константата "1" ситуацията е малко по-различна:

Изчисляване на константата "1":

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

При картографирането на оператора за трансформация на идентичност задачата започва да се усложнява. Ето как да го направите:

Идентично преобразуване:

Използваният тук символ обозначава елемента CNOT: горният ред обозначава контролния бит, а долният ред обозначава контролния бит. Нека ви напомня, че когато използвате оператора CNOT, стойността на контролния бит се променя, ако контролният бит е равен на |1⟩, но остава непроменен, ако контролният бит е равен на |0⟩. Тъй като предположихме, че стойността на горния ред винаги е равна на |0⟩, неговата стойност винаги се присвоява на долния ред.

Продължаваме по подобен начин с оператора за отрицание:

отрицание:

Ние просто обръщаме бита в края на изходния ред.

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

За да разрешите този проблем с помощта на квантово изчисление в една заявка, е необходимо да поставите входните кубити в суперпозиция, преди да ги предадете на функцията, както е показано по-долу:

Елементът на Адамар се прилага отново към резултата от функцията, за да разбие кубитите от суперпозиция и да направи алгоритъма детерминистичен. Стартираме системата в състояние |00⟩ и по причини, които ще обясня след малко, получаваме резултат |11⟩, ако приложената функция е постоянна. Ако функцията в черната кутия е променлива, тогава след измерване системата връща резултата |01⟩.

За да разберем останалата част от статията, нека погледнем илюстрацията, която показах по-рано:

Чрез използване на оператора за инверсия на битове и след това прилагане на елемента на Адамар към двете входни стойности, равни на |0⟩, гарантираме, че те се превеждат в една и съща суперпозиция на |0⟩ и |1⟩, както следва:

С помощта на примера за предаване на тази стойност към функция на черна кутия е лесно да се демонстрира, че и двете функции с постоянна стойност извеждат |11⟩.

Изчисляване на константата "0":

По подобен начин виждаме, че функцията за изчисляване на константата „1“ също произвежда |11⟩ като изход, тоест:

Изчисляване на константата "1":

Обърнете внимание, че резултатът ще бъде |1⟩, тъй като -1² = 1.

По същия принцип можем да докажем, че когато използваме и двете променливи функции, винаги ще получаваме |01⟩ на изхода (при условие, че използваме същия метод), въпреки че всичко е малко по-сложно.

Идентично преобразуване:

Тъй като CNOT е оператор с два кубита, той не може да бъде представен като проста държавна машина и следователно е необходимо да се дефинират два изходни сигнала въз основа на тензорния продукт на двата входни кубита и умножение по матрицата CNOT, както е описано по-рано:

С този метод можем също да потвърдим, че изходната стойност |01⟩ е получена, ако функцията за отрицание е скрита в черната кутия:

отрицание:

Така току-що демонстрирахме ситуация, в която квантовият компютър е очевидно по-ефективен от конвенционалния компютър.

Каква е следващата стъпка?

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

Описанието ми едва ли може да се нарече пълноценно ръководство за квантово изчисление и алгоритми - по-скоро това е кратко въведение в математиката и нотацията, предназначено да разсее представите на читателите за темата, наложени от популярни научни източници (сериозно, много наистина не могат да разберат положението!). Нямах време да засегна много важни теми, като напр квантово заплитане на кубити, сложността на амплитудните стойности |0⟩ и |1⟩ и функционирането на различни квантови логически елементи по време на трансформация от сферата на Bloch.

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

Източник: www.habr.com