EITC/QI/QIF Quantum Information Fundamentals е европейската програма за ИТ сертифициране върху теоретични и практически аспекти на квантовата информация и квантовите изчисления, базирана на законите на квантовата физика, а не на класическата физика и предлагаща качествени предимства пред техните класически аналози.
Учебната програма на EITC/QI/QIF Quantum Information Fundamentals обхваща въведение в квантовата механика (включително разглеждане на експеримента с двоен процеп и интерференцията на материята), въведение в квантовата информация (кубити и тяхното геометрично представяне), поляризация на светлината, принцип на неопределеност, квант заплитане, EPR парадокс, нарушение на неравенството на Бел, изоставяне на локалния реализъм, обработка на квантовата информация (включително унитарна трансформация, еднокубитни и двукубитни порти), теорема за неклониране, квантова телепортация, квантово измерване, квантово изчисление (включително въведение в мултимедийно -кубитни системи, универсално семейство от порти, обратимост на изчисленията), квантови алгоритми (включително квантово преобразуване на Фурие, алгоритъм на Саймън, разширена теза на Чър-Тюринг, алгоритъм за квантово разлагане на Шор'к, алгоритъм за квантово търсене на Гроувър, квантов алгоритъм за наблюдение на квантово ниво), qubits реализации, квантова теория на сложността, адиабатно квантово изчисление ion, BQP, въведение в въртенето, в рамките на следната структура, включваща изчерпателно видео дидактическо съдържание като референция за това EITC сертифициране.
Квантовата информация е информацията за състоянието на квантовата система. Това е основният обект на изследване в теорията на квантовата информация и може да бъде манипулиран с помощта на техники за обработка на квантовата информация. Квантовата информация се отнася както до техническата дефиниция по отношение на ентропията на фон Нойман, така и до общия изчислителен термин.
Квантовата информация и изчисления е интердисциплинарна област, която включва квантова механика, компютърни науки, теория на информацията, философия и криптография наред с други области. Неговото изследване е от значение и за дисциплини като когнитивна наука, психология и невронаука. Основният му фокус е в извличането на информация от материята в микроскопичен мащаб. Наблюдението в науката е основен отличителен критерий на реалността и един от най-важните начини за придобиване на информация. Следователно измерването е необходимо, за да се определи количествено наблюдението, което го прави решаващо за научния метод. В квантовата механика, поради принципа на неопределеността, некомутиращите наблюдаеми не могат да бъдат точно измерени едновременно, тъй като собствено състояние в една база не е собствено състояние в другата база. Тъй като и двете променливи не са едновременно добре дефинирани, едно квантово състояние никога не може да съдържа окончателна информация за двете променливи. Поради това основно свойство на измерването в квантовата механика, тази теория може най-общо да се характеризира като недетерминистична, за разлика от класическата механика, която е напълно детерминистична. Индетерминизмът на квантовите състояния характеризира информацията, дефинирана като състояния на квантовите системи. В математически план тези състояния са в суперпозиции (линейни комбинации) на състояния на класическите системи.
Тъй като информацията винаги е кодирана в състоянието на физическа система, тя сама по себе си е физическа. Докато квантовата механика се занимава с изследване на свойствата на материята на микроскопично ниво, квантовата информационна наука се фокусира върху извличането на информация от тези свойства, а квантовите изчисления манипулират и обработват квантовата информация – извършват логически операции – използвайки техники за обработка на квантова информация.
Квантовата информация, подобно на класическата информация, може да се обработва с помощта на компютри, да се предава от едно място на друго, да се манипулира с алгоритми и да се анализира с компютърни науки и математика. Точно както основната единица на класическата информация е битът, квантовата информация се занимава с кубити, които могат да съществуват в суперпозиция на 0 и 1 (едновременно да бъдат донякъде верни и неверни). Квантовата информация може да съществува и в така наречените заплетени състояния, които проявяват чисто некласически нелокални корелации в своите измервания, позволявайки приложения като квантовата телепортация. Нивото на заплитане може да бъде измерено с помощта на ентропията на фон Нойман, която също е мярка за квантовата информация. Напоследък областта на квантовите изчисления се превърна в много активна изследователска област поради възможността да се наруши съвременните изчисления, комуникация и криптография.
Историята на квантовата информация започва в началото на 20-ти век, когато класическата физика е революционизирана в квантова физика. Теориите на класическата физика предсказваха абсурди като ултравиолетовата катастрофа или електроните, спирали в ядрото. Първоначално тези проблеми бяха премахнати чрез добавяне на хипотеза ad hoc към класическата физика. Скоро стана очевидно, че трябва да се създаде нова теория, за да се осмислят тези абсурди и се роди теорията на квантовата механика.
Квантовата механика е формулирана от Шрьодингер с помощта на вълнова механика и Хайзенберг с помощта на матрична механика. Еквивалентността на тези методи беше доказана по-късно. Техните формулировки описват динамиката на микроскопичните системи, но имат няколко незадоволителни аспекта при описанието на процесите на измерване. Фон Нойман формулира квантовата теория, използвайки операторна алгебра по начин, който описва измерването, както и динамиката. Тези проучвания наблягат на философските аспекти на измерването, а не на количествения подход за извличане на информация чрез измервания.
През 1960-те години на миналия век Стратонович, Хелстрьом и Гордън предложиха формулировка на оптични комуникации, използвайки квантовата механика. Това беше първата историческа поява на квантовата теория на информацията. Те основно изучаваха вероятностите за грешки и капацитета на каналите за комуникация. По-късно Холево получи горна граница на скоростта на комуникация при предаването на класическо съобщение по квантов канал.
През 1970-те години на миналия век започват да се разработват техники за манипулиране на едноатомни квантови състояния, като атомния капан и сканиращия тунелен микроскоп, което прави възможно изолирането на единични атоми и подреждането им в масиви. Преди тези разработки прецизният контрол върху единични квантови системи не беше възможен и експериментите използваха по-груб, едновременен контрол върху голям брой квантови системи. Развитието на жизнеспособни техники за манипулиране с едно състояние доведе до повишен интерес в областта на квантовата информация и изчисления.
През 1980-те години на миналия век възниква интерес към това дали е възможно да се използват квантови ефекти, за да се опровергае теорията на относителността на Айнщайн. Ако беше възможно да се клонира неизвестно квантово състояние, би било възможно да се използват заплетени квантови състояния за предаване на информация по-бързо от скоростта на светлината, което опровергава теорията на Айнщайн. Теоремата за забрана на клонирането обаче показа, че такова клониране е невъзможно. Теоремата е един от най-ранните резултати на квантовата теория на информацията.
Разработка от криптография
Въпреки цялото вълнение и интерес към изучаването на изолирани квантови системи и опитите за намиране на начин за заобикаляне на теорията на относителността, изследванията в областта на квантовата теория на информацията стават в застой през 1980-те години на миналия век. Въпреки това, приблизително по същото време друг път започна да се занимава с квантовата информация и изчисления: криптографията. В общ смисъл, криптографията е проблемът за осъществяване на комуникация или изчисление, включващи две или повече страни, които може да не се доверяват една на друга.
Бенет и Брасард разработиха комуникационен канал, по който е невъзможно да се подслушва, без да бъде открит, начин за тайна комуникация на големи разстояния с помощта на квантовия криптографски протокол BB84. Ключовата идея беше използването на основния принцип на квантовата механика, че наблюдението смущава наблюдаваното, а въвеждането на подслушвател в защитена комуникационна линия незабавно ще позволи на двете страни, които се опитват да комуникират, да знаят за присъствието на подслушвача.
Развитие от компютърните науки и математиката
С появата на революционните идеи на Алън Тюринг за програмируем компютър или машина на Тюринг, той показа, че всяко изчисление в реалния свят може да бъде преведено в еквивалентно изчисление, включващо машина на Тюринг. Това е известно като тезата на Чърч-Тюринг.
Съвсем скоро бяха направени първите компютри и компютърният хардуер нарасна с толкова бързи темпове, че растежът, чрез опит в производството, беше кодифициран в емпирична връзка, наречена закон на Мур. Този „закон“ е проективна тенденция, която гласи, че броят на транзисторите в интегралната схема се удвоява на всеки две години. Тъй като транзисторите започнаха да стават все по-малки и по-малки, за да опаковат повече мощност на повърхност, квантовите ефекти започнаха да се появяват в електрониката, което води до непреднамерени смущения. Това доведе до появата на квантовите изчисления, които използваха квантовата механика за проектиране на алгоритми.
В този момент квантовите компютри обещаха да бъдат много по-бързи от класическите компютри за определени специфични проблеми. Един такъв примерен проблем е разработен от Дейвид Дойч и Ричард Йоза, известен като алгоритъмът на Дойч-Джоза. Този проблем обаче нямаше почти никакви практически приложения. Питър Шор през 1994 г. излезе с много важен и практичен проблем, един от намирането на главните множители на цяло число. Проблемът с дискретния логаритъм, както се наричаше, може да бъде решен ефективно на квантов компютър, но не и на класически компютър, което показва, че квантовите компютри са по-мощни от машините на Тюринг.
Развитие от теорията на информацията
По времето, когато компютърните науки правеха революция, както и теорията на информацията и комуникацията, чрез Клод Шанън. Шанън разработи две основни теореми на теорията на информацията: теорема за безшумно кодиране на канал и теорема за кодиране на шумен канал. Той също така показа, че кодовете за коригиране на грешки могат да се използват за защита на изпращаната информация.
Квантовата теория на информацията също следва подобна траектория, Бен Шумахер през 1995 г. прави аналог на теоремата за безшумно кодиране на Шанън, използвайки кубита. Разработена е и теория за корекция на грешки, която позволява на квантовите компютри да правят ефективни изчисления независимо от шума и да осъществяват надеждна комуникация по шумни квантови канали.
Кубити и теория на информацията
Квантовата информация се различава силно от класическата информация, олицетворена от бита, по много поразителни и непознати начини. Докато основната единица на класическата информация е битът, най-основната единица на квантовата информация е кубитът. Класическата информация се измерва с помощта на ентропията на Шанън, докато квантовомеханичният аналог е ентропията на фон Нойман. Статистически ансамбъл от квантовомеханични системи се характеризира с матрицата на плътността. Много ентропийни мерки в класическата теория на информацията също могат да бъдат обобщени до квантовия случай, като ентропията на Холево и условната квантова ентропия.
За разлика от класическите цифрови състояния (които са дискретни), кубитът е с непрекъсната стойност и може да се опише с посока върху сферата на Блох. Въпреки че се оценява непрекъснато по този начин, кубитът е най-малката възможна единица квантова информация и въпреки че състоянието на кубита е с непрекъсната стойност, е невъзможно стойността да се измери точно. Пет известни теореми описват границите на манипулирането на квантовата информация:
- теорема за липса на телепортация, която гласи, че кубит не може да бъде (напълно) преобразуван в класически битове; тоест не може да се „прочете“ напълно,
- теорема без клониране, която предотвратява копирането на произволен кубит,
- теорема без изтриване, която предотвратява изтриването на произволен кубит,
- теорема за липса на излъчване, която предотвратява доставянето на произволен кубит до множество получатели, въпреки че може да бъде транспортиран от място на място (например чрез квантова телепортация),
- теорема без скриване, която демонстрира запазването на квантовата информация, Тези теореми доказват, че квантовата информация във Вселената се запазва и отварят уникални възможности в обработката на квантовата информация.
Квантова обработка на информация
Състоянието на кубита съдържа цялата му информация. Това състояние често се изразява като вектор върху сферата на Блох. Това състояние може да бъде променено чрез прилагане на линейни трансформации или квантови врати към тях. Тези унитарни трансформации се описват като ротации върху сферата на Блох. Докато класическите порти отговарят на познатите операции на булевата логика, квантовите порти са физически унитарни оператори.
Поради нестабилността на квантовите системи и невъзможността за копиране на състояния, съхраняването на квантовата информация е много по-трудно от съхраняването на класическа информация. Независимо от това, с използването на квантова корекция на грешки квантовата информация все още може да се съхранява надеждно по принцип. Наличието на квантови кодове за коригиране на грешки също е довело до възможността за устойчиви на грешки квантови изчисления.
Класическите битове могат да бъдат кодирани и впоследствие извлечени от конфигурации на кубити чрез използването на квантови порти. Сам по себе си един кубит може да предаде не повече от един бит достъпна класическа информация за неговото приготвяне. Това е теоремата на Холево. Въпреки това, при свръхплътно кодиране подателят, като действа върху един от два заплетени кубита, може да предаде два бита достъпна информация за тяхното общо състояние на получателя.
Квантовата информация може да се движи по квантов канал, аналогично на концепцията за класически комуникационен канал. Квантовите съобщения имат краен размер, измерен в кубити; квантовите канали имат краен капацитет на канала, измерен в кубити в секунда.
Квантовата информация и промените в квантовата информация могат да бъдат количествено измерени чрез използване на аналог на ентропията на Шанън, наречен ентропия на фон Нойман.
В някои случаи квантовите алгоритми могат да се използват за извършване на изчисления по-бързо, отколкото във всеки известен класически алгоритъм. Най-известният пример за това е алгоритъмът на Шор, който може да факторизира числа в полиномно време, в сравнение с най-добрите класически алгоритми, които отнемат субекспоненциално време. Тъй като факторизацията е важна част от безопасността на RSA криптирането, алгоритъмът на Шор предизвика новото поле на пост-квантовата криптография, която се опитва да намери схеми за криптиране, които остават безопасни, дори когато квантовите компютри са в игра. Други примери за алгоритми, които демонстрират квантово надмощие, включват алгоритъма за търсене на Гроувър, където квантовият алгоритъм дава квадратично ускорение спрямо възможно най-добрия класически алгоритъм. Класът на сложност на проблемите, ефективно решавани от квантов компютър, е известен като BQP.
Квантовото разпределение на ключове (QKD) позволява безусловно сигурно предаване на класическа информация, за разлика от класическото криптиране, което винаги може да бъде нарушено по принцип, ако не и на практика. Имайте предвид, че някои фини точки по отношение на безопасността на QKD все още се обсъждат горещо.
Изучаването на всички горепосочени теми и различия включва квантовата теория на информацията.
Връзка с квантовата механика
Квантовата механика изучава как микроскопичните физически системи се променят динамично в природата. В областта на квантовата теория на информацията, изучаваните квантови системи се абстрахират от всякакъв аналог в реалния свят. Кубитът може например физически да бъде фотон в линеен оптичен квантов компютър, йон в квантов компютър с уловени йони или може да бъде голяма колекция от атоми, както в свръхпроводящ квантов компютър. Независимо от физическата реализация, ограниченията и характеристиките на кубитите, заложени от квантовата теория на информацията, са валидни, тъй като всички тези системи са математически описани от един и същ апарат на матрици на плътност върху комплексните числа. Друга важна разлика с квантовата механика е, че докато квантовата механика често изучава безкрайномерни системи като хармоничен осцилатор, квантовата теория на информацията се отнася както до системите с непрекъснати променливи, така и до системите с крайни измерения.
Квантово изчисление
Квантовото изчисление е вид изчисление, което използва колективните свойства на квантовите състояния, като суперпозиция, интерференция и заплитане, за извършване на изчисления. Устройствата, които извършват квантови изчисления, са известни като квантови компютри.: I-5 Въпреки че настоящите квантови компютри са твърде малки, за да превъзхождат обичайните (класически) компютри за практически приложения, се смята, че са способни да решават определени изчислителни проблеми, като цяло число. (което е в основата на RSA криптирането), значително по-бързо от класическите компютри. Изучаването на квантовите изчисления е подполе на квантовата информационна наука.
Квантовите изчисления започват през 1980 г., когато физикът Пол Бениоф предлага квантовомеханичен модел на машината на Тюринг. Ричард Файнман и Юри Манин по-късно предполагат, че квантовият компютър има потенциал да симулира неща, които класическият компютър не може да направи. През 1994 г. Питър Шор разработи квантов алгоритъм за разлагане на цели числа с потенциал за декриптиране на RSA-криптирани комуникации. През 1998 г. Исак Чуанг, Нийл Гершенфелд и Марк Кубинец създават първия двукубитов квантов компютър, който може да извършва изчисления. Въпреки продължаващия експериментален напредък от края на 1990-те години на миналия век, повечето изследователи смятат, че „устойчивите на грешки квантови изчисления [все още са] доста далечна мечта“. През последните години инвестициите в изследвания на квантовите изчисления се увеличиха в публичния и частния сектор. На 23 октомври 2019 г. Google AI, в партньорство с Националната администрация по аеронавтика и пространство на САЩ (НАСА), твърди, че е извършил квантово изчисление, което е било неосъществимо на нито един класически компютър, но дали това твърдение е било или все още е валидно е тема на активни изследвания.
Има няколко вида квантови компютри (известни също като квантови изчислителни системи), включително модел на квантовата верига, квантова машина на Тюринг, адиабатен квантов компютър, еднопосочен квантов компютър и различни квантови клетъчни автомати. Най-широко използваният модел е квантовата схема, базирана на квантовия бит, или „кубит“, който е донякъде аналогичен на бита в класическото изчисление. Кубитът може да бъде в квантово състояние 1 или 0 или в суперпозиция на състоянията 1 и 0. Когато се измерва обаче, винаги е 0 или 1; вероятността за всеки изход зависи от квантовото състояние на кубита непосредствено преди измерването.
Усилията за изграждане на физически квантов компютър се фокусират върху технологии като трансмони, йонни капани и топологични квантови компютри, които имат за цел да създават висококачествени кубити.: 2–13 Тези кубити могат да бъдат проектирани по различен начин, в зависимост от изчислителния модел на пълния квантов компютър, независимо дали са квантови логически порти, квантово отгряване или адиабатно квантово изчисление. В момента има редица значителни пречки пред конструирането на полезни квантови компютри. Особено трудно е да се поддържат квантовите състояния на кубити, тъй като те страдат от квантова декохерентност и вярност на състоянието. Следователно квантовите компютри изискват корекция на грешки.
Всеки изчислителен проблем, който може да бъде решен от класически компютър, може да бъде решен и от квантов компютър. Обратно, всеки проблем, който може да бъде решен от квантов компютър, може да бъде решен и от класически компютър, поне по принцип при достатъчно време. С други думи, квантовите компютри се подчиняват на тезата на Чърч-Тюринг. Това означава, че докато квантовите компютри не предоставят допълнителни предимства пред класическите компютри по отношение на изчислимостта, квантовите алгоритми за определени проблеми имат значително по-ниска времева сложност от съответните известни класически алгоритми. По-специално, смята се, че квантовите компютри могат бързо да решат определени проблеми, които никой класически компютър не би могъл да реши за осъществим период от време – подвиг, известен като „квантово надмощие“. Изучаването на изчислителната сложност на проблемите по отношение на квантовите компютри е известно като квантова теория на сложността.
Преобладаващият модел на квантово изчисление описва изчислението от гледна точка на мрежа от квантови логически порти. Този модел може да се разглежда като абстрактно линейно-алгебрично обобщение на класическа схема. Тъй като този модел на веригата се подчинява на квантовата механика, се смята, че квантов компютър, способен ефективно да управлява тези вериги, е физически осъществим.
Памет, състояща се от n бита информация, има 2^n възможни състояния. Така вектор, представящ всички състояния на паметта, има 2^n записа (по един за всяко състояние). Този вектор се разглежда като вектор на вероятността и представлява факта, че паметта се намира в определено състояние.
В класическия изглед един запис ще има стойност 1 (т.е. 100% вероятност да бъде в това състояние), а всички други записи ще бъдат нула.
В квантовата механика векторите на вероятността могат да бъдат обобщени до оператори на плътност. Формализмът на квантовото състояние обикновено се въвежда първо, защото е концептуално по-прост и защото може да се използва вместо формализма на матрицата на плътността за чисти състояния, където е известна цялата квантова система.
едно квантово изчисление може да бъде описано като мрежа от квантови логически врати и измервания. Въпреки това, всяко измерване може да бъде отложено до края на квантовото изчисление, въпреки че това отлагане може да бъде с изчислителна цена, така че повечето квантови схеми изобразяват мрежа, състояща се само от квантови логически порти и без измервания.
Всяко квантово изчисление (което в горния формализъм е всяка унитарна матрица над n кубита) може да бъде представено като мрежа от квантови логически порти от доста малко семейство порти. Изборът на семейство порти, който позволява тази конструкция, е известен като универсален комплект порти, тъй като компютърът, който може да управлява такива вериги, е универсален квантов компютър. Един общ такъв набор включва всички еднокубитни порти, както и портата CNOT отгоре. Това означава, че всяко квантово изчисление може да бъде извършено чрез изпълнение на последователност от еднокубитни порти заедно с CNOT порти. Въпреки че този набор от врати е безкраен, той може да бъде заменен с краен набор от врати, като се прибегне до теоремата на Соловей-Китаев.
Квантови алгоритми
Напредъкът в намирането на квантови алгоритми обикновено се фокусира върху този модел на квантовата верига, въпреки че съществуват изключения като квантовия адиабатичен алгоритъм. Квантовите алгоритми могат да бъдат грубо категоризирани по вида на ускорението, постигнато спрямо съответните класически алгоритми.
Квантовите алгоритми, които предлагат повече от полиномно ускорение спрямо най-известния класически алгоритъм, включват алгоритъма на Шор за разлагане на множители и свързаните с него квантови алгоритми за изчисляване на дискретни логаритми, решаване на уравнението на Пел и по-общо решаване на проблема за скритата подгрупа за абелови крайни групи. Тези алгоритми зависят от примитива на квантовата трансформация на Фурие. Не е намерено математическо доказателство, което да показва, че еднакво бърз класически алгоритъм не може да бъде открит, въпреки че това се счита за малко вероятно.[самопубликуван източник?] Някои проблеми с оракула като проблема на Саймън и проблема Бернщайн–Вазирани наистина дават доказуеми ускорения, въпреки че това е така. е в модела на квантовата заявка, който е ограничен модел, при който долните граници са много по-лесни за доказване и не означава непременно ускорения за практически проблеми.
Други проблеми, включително симулацията на квантови физически процеси от химията и физиката на твърдото тяло, сближаването на определени полиноми на Джоунс и квантовия алгоритъм за линейни системи от уравнения имат квантови алгоритми, които изглежда дават суперполиномни ускорения и са BQP-пълни. Тъй като тези проблеми са BQP-пълни, еднакво бърз класически алгоритъм за тях би означавал, че нито един квантов алгоритъм не дава супер-полиномно ускорение, което се смята за малко вероятно.
Някои квантови алгоритми, като алгоритъма на Гроувър и амплитудното усилване, дават полиномни ускорения спрямо съответните класически алгоритми. Въпреки че тези алгоритми дават сравнително скромно квадратично ускорение, те са широко приложими и по този начин дават ускорения за широк спектър от проблеми. Много примери за доказуеми квантови ускорения за проблеми със заявките са свързани с алгоритъма на Гроувър, включително алгоритъма на Брасард, Хьойер и Тап за намиране на сблъсъци във функции две към едно, който използва алгоритъма на Гроувър и алгоритъма на Фархи, Голдстоун и Гутман за оценка на NAND дървета, което е вариант на проблема с търсенето.
Криптографски приложения
Забележително приложение на квантовите изчисления е за атаки срещу криптографски системи, които се използват в момента. Целочисленото разлагане на множители, което е в основата на сигурността на криптографските системи с публичен ключ, се смята за невъзможно изчислително с обикновен компютър за големи цели числа, ако те са продукт на няколко прости числа (напр. произведения на две 300-цифрени прости числа). За сравнение, квантовият компютър може ефективно да реши този проблем, използвайки алгоритъма на Шор, за да намери неговите фактори. Тази способност би позволила на квантов компютър да разбие много от криптографските системи, използвани днес, в смисъл, че ще има алгоритъм за полиномиално време (в броя на цифрите на цялото число) за решаване на проблема. По-специално, повечето от популярните шифри с публичен ключ се основават на трудността на разлагането на цели числа или на проблема с дискретния логаритъм, като и двете могат да бъдат решени от алгоритъма на Шор. По-специално, алгоритмите на RSA, Diffie–Hellman и елиптичната крива на Diffie–Hellman могат да бъдат нарушени. Те се използват за защита на защитени уеб страници, криптирана електронна поща и много други видове данни. Нарушаването им би имало значителни последици за електронната поверителност и сигурност.
Идентифицирането на криптографски системи, които могат да бъдат защитени срещу квантови алгоритми, е активно изследвана тема в областта на постквантовата криптография. Някои алгоритми с публичен ключ се основават на проблеми, различни от проблемите с целочислена факторизация и проблеми с дискретния логаритъм, към които се прилага алгоритъмът на Шор, като криптосистемата на McEliece, базирана на проблем в теорията на кодирането. Също така не е известно, че базираните на решетка криптосистеми са разбити от квантовите компютри и намирането на алгоритъм за полиномиално време за решаване на проблема със скритата подгрупа на диедрите, който би разрушил много криптосистеми, базирани на решетка, е добре проучен отворен проблем. Доказано е, че прилагането на алгоритъма на Гроувър за нарушаване на симетричен (секретен ключ) алгоритъм чрез груба сила изисква време, равно на приблизително 2n/2 извиквания на основния криптографски алгоритъм, в сравнение с приблизително 2n в класическия случай, което означава, че дължините на симетричните ключове са ефективно наполовина: AES-256 ще има същата сигурност срещу атака, използваща алгоритъма на Гроувър, която има AES-128 срещу класическото търсене с груба сила (вижте Размер на ключа).
Квантовата криптография може потенциално да изпълни някои от функциите на криптографията с публичен ключ. Следователно, базираните на квантови криптографски системи биха могли да бъдат по-сигурни от традиционните системи срещу квантово хакване.
Проблеми с търсенето
Най-известният пример за проблем, допускащ полиномно квантово ускоряване, е неструктурирано търсене, намиране на маркиран елемент от списък от n елемента в база данни. Това може да бъде решено чрез алгоритъма на Гроувър, използвайки O(sqrt(n)) заявки към базата данни, квадратично по-малко от Omega(n) заявките, необходими за класическите алгоритми. В този случай предимството е не само доказуемо, но и оптимално: доказано е, че алгоритъмът на Гроувър дава максималната възможна вероятност за намиране на желания елемент за произволен брой търсения на оракул.
Проблемите, които могат да бъдат решени с алгоритъма на Гроувър, имат следните свойства:
- Няма структура за търсене в колекцията от възможни отговори,
- Броят на възможните отговори за проверка е същият като броя на входовете в алгоритъма и
- Съществува булева функция, която оценява всеки вход и определя дали това е правилният отговор
За проблеми с всички тези свойства, времето за изпълнение на алгоритъма на Гроувър на квантов компютър се мащабира като корен квадратен от броя на входовете (или елементите в базата данни), за разлика от линейното мащабиране на класическите алгоритми. Общ клас проблеми, към които може да се приложи алгоритъма на Гроувър, е булева задача за удовлетворимост, където базата данни, през която алгоритъмът итерира, е тази от всички възможни отговори. Пример и (възможно) приложение на това е разбивач на парола, който се опитва да отгатне парола. Симетричните шифри като Triple DES и AES са особено уязвими към този вид атака. [необходим е цитат] Това приложение на квантовите изчисления е основен интерес на правителствените агенции.
Симулация на квантови системи
Тъй като химията и нанотехнологиите разчитат на разбирането на квантовите системи и такива системи е невъзможно да се симулират по ефективен начин класически, мнозина вярват, че квантовата симулация ще бъде едно от най-важните приложения на квантовите изчисления. Квантовата симулация може да се използва и за симулиране на поведението на атоми и частици при необичайни условия, като реакциите в колайдер. Квантовите симулации могат да се използват за прогнозиране на бъдещи пътища на частици и протони под суперпозиция в експеримента с двоен процеп. [необходимо е цитиране] Около 2% от годишното световно производство на енергия се използва за фиксиране на азот за производство на амоняк за процеса на Хабер в селското стопанство. производството на торове, докато естествено срещащите се организми също произвеждат амоняк. Квантовите симулации могат да се използват за разбиране на този процес, увеличаващ производството.
Квантово отгряване и адиабатна оптимизация
Квантовото отгряване или адиабатното квантово изчисление разчита на адиабатната теорема за извършване на изчисления. Системата е поставена в основно състояние за прост хамилтониан, който бавно еволюира до по-сложен хамилтониан, чието основно състояние представлява решението на въпросния проблем. Адиабатната теорема гласи, че ако еволюцията е достатъчно бавна, системата ще остане в основното си състояние през цялото време през процеса.
машина обучение
Тъй като квантовите компютри могат да произвеждат резултати, които класическите компютри не могат да произвеждат ефективно, и тъй като квантовите изчисления са основно линейни алгебрични, някои изразяват надежда в разработването на квантови алгоритми, които могат да ускорят задачите за машинно обучение. Например, смята се, че квантовият алгоритъм за линейни системи от уравнения или „HHL алгоритъм“, кръстен на своите откриватели Хароу, Хасидим и Лойд, осигурява ускоряване спрямо класическите аналози. Някои изследователски групи наскоро проучиха използването на хардуер за квантово отгряване за обучение на машини на Болцман и дълбоки невронни мрежи.
Изчислителна биология
В областта на изчислителната биология квантовите изчисления изиграха голяма роля при решаването на много биологични проблеми. Един от добре познатите примери би бил в изчислителната геномика и как компютрите са намалили драстично времето за секвениране на човешки геном. Като се има предвид как изчислителната биология използва общо моделиране и съхранение на данни, се очаква да възникнат и нейните приложения към изчислителната биология.
Компютърно проектиране на лекарства и генеративна химия
Моделите на дълбоката генеративна химия се очертават като мощни инструменти за ускоряване на откриването на лекарства. Въпреки това, огромният размер и сложността на структурното пространство на всички възможни лекарствени молекули създават значителни пречки, които могат да бъдат преодолени в бъдеще от квантовите компютри. Квантовите компютри са естествено добри за решаване на сложни квантови проблеми с много тела и по този начин могат да бъдат инструментални в приложения, включващи квантова химия. Следователно може да се очаква, че квантово подобрени генеративни модели, включително квантови GAN, в крайна сметка могат да бъдат разработени в крайни генеративни химически алгоритми. Хибридните архитектури, комбиниращи квантови компютри с дълбоки класически мрежи, като квантови вариационни автоенкодери, вече могат да бъдат обучени на наличните в търговската мрежа отгряващи устройства и да се използват за генериране на нови подобни на лекарства молекулярни структури.
Разработване на физически квантови компютри
Предизвикателства
Съществуват редица технически предизвикателства при изграждането на мащабен квантов компютър. Физикът Дейвид Ди Винченцо изброи тези изисквания за практически квантов компютър:
- Физически мащабируем за увеличаване на броя кубити,
- Кубити, които могат да бъдат инициализирани до произволни стойности,
- Квантовите порти, които са по-бързи от времето на декохерентност,
- Универсален комплект порта,
- Кубити, които могат да се четат лесно.
Снабдяването на части за квантовите компютри също е много трудно. Много квантови компютри, като тези, конструирани от Google и IBM, се нуждаят от хелий-3, страничен продукт за ядрени изследвания, и специални свръхпроводящи кабели, произведени само от японската компания Coax Co.
Управлението на мултикубитни системи изисква генериране и координация на голям брой електрически сигнали с строга и детерминирана времева разделителна способност. Това доведе до разработването на квантови контролери, които позволяват взаимодействие с кубитите. Мащабирането на тези системи за поддръжка на нарастващ брой кубити е допълнително предизвикателство.
Квантова декохерентност
Едно от най-големите предизвикателства, свързани с конструирането на квантови компютри, е контролирането или премахването на квантовата декохерентност. Това обикновено означава изолиране на системата от околната среда, тъй като взаимодействията с външния свят карат системата да се декохерира. Съществуват обаче и други източници на декохерентност. Примерите включват квантовите порти и вибрациите на решетката и фоновото термоядрен спин на физическата система, използвана за изпълнение на кубитите. Декохерентността е необратима, тъй като на практика не е единна и обикновено е нещо, което трябва да бъде силно контролирано, ако не и избягвано. Времената на декохерентност за кандидат системите, по-специално времето за напречна релаксация T2 (за ЯМР и ЯМР технологията, наричано още време за дефазиране), обикновено варира между наносекунди и секунди при ниска температура. Понастоящем някои квантови компютри изискват техните кубити да бъдат охладени до 20 миликелвина (обикновено използвайки хладилник за разреждане), за да се предотврати значителна декохерентност. Проучване от 2020 г. твърди, че йонизиращо лъчение като космическите лъчи все пак може да доведе до декохериране на определени системи в рамките на милисекунди.
В резултат на това, отнемащи време задачи могат да направят някои квантови алгоритми неработоспособни, тъй като поддържането на състоянието на кубити за достатъчно дълго време в крайна сметка ще повреди суперпозициите.
Тези проблеми са по-трудни за оптичните подходи, тъй като времевите скали са с порядък по-кратък и често цитираният подход за преодоляването им е оформянето на оптични импулси. Степента на грешки обикновено е пропорционална на съотношението на времето за работа към времето за декохерентност, следователно всяка операция трябва да бъде завършена много по-бързо от времето за декохерентност.
Както е описано в теоремата за квантовия праг, ако процентът на грешки е достатъчно малък, се смята, че е възможно да се използва квантова корекция на грешки за потискане на грешките и декохерентността. Това позволява общото време за изчисление да бъде по-дълго от времето за декохерентност, ако схемата за корекция на грешки може да коригира грешките по-бързо, отколкото декохерентността ги въвежда. Често цитирана цифра за необходимия процент на грешки във всяка порта за изчисление с толерантни към грешки е 10-3, като се приеме, че шумът се деполяризира.
Изпълнението на това условие за мащабируемост е възможно за широк спектър от системи. Въпреки това, използването на корекция на грешки носи със себе си цената на значително увеличен брой необходими кубити. Числото, необходимо за разлагане на цели числа с помощта на алгоритъма на Шор, все още е полиномно и се смята, че е между L и L2, където L е броят на цифрите в числото, което трябва да бъде разложено на множители; Алгоритмите за корекция на грешки биха увеличили тази цифра с допълнителен коефициент L. За 1000-битово число това предполага нужда от около 104 бита без корекция на грешки. С корекция на грешки цифрата ще се увеличи до около 107 бита. Времето за изчисление е около L2 или около 107 стъпки и при 1 MHz, около 10 секунди.
Много различен подход към проблема за стабилност-декохерентност е да се създаде топологичен квантов компютър с аниони, квазичастици, използвани като нишки и разчитащи на теорията на плитките за формиране на стабилни логически порти.
Квантово надмощие
Квантовото превъзходство е термин, въведен от Джон Прескил, отнасящ се до инженерния подвиг да демонстрира, че програмируемо квантово устройство може да реши проблем извън възможностите на най-съвременните класически компютри. Проблемът не трябва да е полезен, така че някои разглеждат теста за квантово надмощие само като потенциален бъдещ еталон.
През октомври 2019 г. Google AI Quantum, с помощта на НАСА, стана първият, който твърди, че е постигнал квантово надмощие чрез извършване на изчисления на квантовия компютър Sycamore повече от 3,000,000 XNUMX XNUMX пъти по-бързо, отколкото биха могли да бъдат направени на Summit, обикновено считан за най-бързия в света компютър. Това твърдение впоследствие беше оспорено: IBM заяви, че Summit може да изпълнява проби много по-бързо от заявеното и оттогава изследователите са разработили по-добри алгоритми за проблема с извадката, използван за заявяване на квантово надмощие, давайки значително намаляване или затваряне на пропастта между Sycamore и класически суперкомпютри.
През декември 2020 г. група в USTC приложи вид бозонно вземане на проби от 76 фотона с фотонен квантов компютър Jiuzhang, за да демонстрира квантово надмощие. Авторите твърдят, че класическият съвременен суперкомпютър ще изисква изчислително време от 600 милиона години, за да генерира броя на пробите, които техният квантов процесор може да генерира за 20 секунди. На 16 ноември 2021 г. на срещата на върха по квантовите изчисления IBM представи 127-кубитов микропроцесор на име IBM Eagle.
Физически реализации
За физическото внедряване на квантов компютър се преследват много различни кандидати, сред които (различаващи се с физическата система, използвана за реализиране на кубити):
- Свръхпроводящи квантови изчисления (кубит, реализиран от състоянието на малки свръхпроводящи вериги, връзки на Джоузефсън)
- Квантов компютър с уловени йони (кубит, реализиран от вътрешното състояние на уловените йони)
- Неутрални атоми в оптични решетки (кубит, реализиран от вътрешни състояния на неутрални атоми, хванати в оптична решетка)
- Компютър с квантови точки, базиран на спин (напр. квантовият компютър на Loss-DiVincenzo) (кубит, даден от спиновите състояния на хванатите електрони)
- Компютър с квантови точки, пространствено базиран (кубит, даден от позицията на електрона в двойна квантова точка)
- Квантови изчисления с помощта на проектирани квантови кладенци, които по принцип биха могли да позволят изграждането на квантови компютри, които работят при стайна температура
- Свързан квантов проводник (кубит, реализиран от двойка квантови проводници, съединени от квантов точков контакт)
- Ядрено-магнитен резонансен квантов компютър (NMRQC), реализиран с ядрено-магнитен резонанс на молекули в разтвор, където кубити се осигуряват от ядрени завъртания в разтворената молекула и се изследват с радиовълни
- Квантови компютри на Кейн с ЯМР в твърдо състояние (кубит, реализиран от ядреното спиново състояние на донори на фосфор в силиций)
- Квантови компютри електрони върху хелий (кубитът е въртенето на електрона)
- Квантова електродинамика на кухината (CQED) (кубит, осигурен от вътрешното състояние на уловените атоми, свързани с кухини с висока фина)
- Молекулен магнит (кубит, даден от спинови състояния)
- Квантов компютър ESR, базиран на фулерен (кубит, базиран на електронния спин на атоми или молекули, обвити в фулерени)
- Нелинеен оптичен квантов компютър (кубити, реализирани чрез обработка на състояния на различни режими на светлина чрез линейни и нелинейни елементи)
- Линеен оптичен квантов компютър (кубити, реализирани чрез обработка на състояния на различни режими на светлина чрез линейни елементи, например огледала, разделители на лъча и фазови превключватели)
- Квантов компютър, базиран на диаманти (кубит, реализиран от електронното или ядреното въртене на азотни свободни центрове в диаманта)
- Квантов компютър, базиран на кондензат на Бозе-Айнщайн
- Квантов компютър, базиран на транзистор – струнни квантови компютри с увличане на положителни дупки с помощта на електростатичен капан
- Квантови компютри на базата на неорганични кристали, легирани с йони от редки земни метали (кубит, реализиран от вътрешното електронно състояние на добавките в оптичните влакна)
- Квантови компютри, базирани на метални въглеродни наносфери
- Големият брой кандидати показва, че квантовите изчисления, въпреки бързия напредък, все още са в начален стадий.
Съществуват редица модели на квантови изчисления, които се отличават с основните елементи, в които изчислението е разложено. За практически реализации, четирите релевантни модела на изчисление са:
- Квантов масив от порти (изчисление, разложено на последователност от квантови порти с няколко кубита)
- Еднопосочен квантов компютър (изчисление, разложено на последователност от измервания с един кубит, приложени към силно заплетено първоначално състояние или състояние на клъстер)
- Адиабатен квантов компютър, базиран на квантово отгряване (изчисление, разложено на бавно непрекъснато преобразуване на начален хамилтониан в краен хамилтониан, чиито основни състояния съдържат решението)
- Топологичен квантов компютър (изчисление, разложено на сплитане на аниони в 2D решетка)
Квантовата машина на Тюринг е теоретично важна, но физическата реализация на този модел не е осъществима. Доказано е, че и четирите модела на изчисление са еквивалентни; всеки може да симулира другия с не повече от полиномни служебни разходи.
За да се запознаете в детайли с учебната програма за сертифициране, можете да разширите и анализирате таблицата по-долу.
Учебната програма за сертифициране на основите на квантовата информация EITC/QI/QIF препраща към дидактически материали с отворен достъп във видео форма. Процесът на обучение е разделен на структура стъпка по стъпка (програми -> уроци -> теми), обхващащи съответните части от учебната програма. Предоставят се и неограничени консултации с експерти по домейни.
За подробности относно процедурата за сертифициране проверете Как работи.
Основни бележки от лекцията
Бележки от лекцията на У. Вазирани:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Подкрепящи бележки от лекции
L. Jacak et al. бележки от лекции (с допълнителни материали):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Основен поддържащ учебник
Учебник по квантово изчисление и квантова информация (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Допълнителни бележки от лекцията
Бележки от лекцията на J. Preskill:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
A. Бележки от лекцията на Чайлдс:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
Бележки от лекцията на S. Aaronson:
https://scottaaronson.blog/?p=3943
Р. де Волф бележки от лекцията:
https://arxiv.org/abs/1907.09415
Други препоръчани учебници
Класически и квантови изчисления (Китаев, Шен, Вяли)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
Квантовите компютри от Демокрит (Ааронсън)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
Теорията на квантовата информация (Watrous)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
Квантова теория на информацията (Уайлд)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Изтеглете пълните офлайн подготвителни материали за самообучение за програмата EITC/QI/QIF Quantum Information Fundamentals в PDF файл
Подготвителни материали за EITC/QI/QIF – стандартна версия
Подготвителни материали за EITC/QI/QIF – разширена версия с въпроси за преглед