Квантовите компютри и квантовото изчисление — нов , който се добави в нашето информационно пространство наред с , и други високотехнологични термини. Въпреки това, не успях да намеря в интернет материал, който да събере в главата ми пъзела с името “как работят квантовите компютри”. Да, има много отлични изследвания, включително и на Хабра (вж. ), коментарите на които, както обикновено, са още по-информативни и полезни, но картината в главата, така да се каже, не се сглобяваше.
Наскоро колеги дойдоха при мен и попитаха “Разбираш ли как работи квантовият компютър? Можеш ли да ни разкажеш?” И тогава осъзнах, че проблемът със съставянето на цялостна картина не е само мой.
В резултат на това се направи опит да се компилира информация за квантовите компютри в непротиворечива логическа схема, в която на базово ниво, без дълбоко задълбочаване в математиката и структурата на квантовия свят, се обяснява какво е квантов компютър, на какви принципи работи, както и какви проблеми стоят пред учените при създаването и експлоатацията му.
Съдържание
Дисклеймер
Авторът не е специалист в квантовите изчисления, и целевата аудитория на статията — също такива ИТ специалисти, не квантови специалисти, които искат да сглобят в главата си картината с името “Как работят квантовите компютри”. Поради това много понятия в статията са съзнателно опростени за по-добро разбиране на квантовите технологии на “базово” ниво, но без .
В статията на няколко места са използвани материали от други източници, . На всякъде, където е било възможно, са поставени директни линкове и указания към оригиналния текст, таблица или изображение. Ако нещо (или някой) е пропуснат, пишете — ще коригирам.
Въведение
В тази глава ще разгледаме накратко как започна квантовата епоха, каква беше подбудата за възникването на идеята за квантов компютър, кои (кои страни и корпорации) в момента са водещите играчи в тази област, а също така ще поговорим накратко за основните направления на развитие на квантовите изчисления.
Как всичко започна
Точката на отчитане на квантовата ера е приета за 1900 година, когато М. Планк за първи път предложи че енергията се излъчва и абсорбира не непрекъснато, а на отделни квантове (порции). Идеята беше подета и развита от много видни учени от това време — Бор, Айнщайн, Хайзенберг, Шрьодингер, което в крайна сметка доведе до създаването и развитието на науката наречена . В Съвета за развитие на квантовата физика като наука в интернет има много добри материали, в тази статия няма да се спираме подробно на това, но беше необходимо да посочим датата, когато навлязохме в новата квантова епоха.
Квантовата физика донесе в нашето обикновено ежедневие много изобретения и технологии, без които сега трудно можем да си представим заобикалящия ни свят. Например, лазерът, който сега се използва навсякъде, от битова техника (лазерни нивелири и други) до високотехнологични системи (лазери за корекции на зрението, привет ). Логично е да предположим, че рано или късно някой ще изтъкне идеята, че защо да не използваме квантови системи за изчисления. И ето, през 1980 година това се случи.
Уикипедия посочва, че първоначално идеята за квантовите изчисления е била предложена през 1980 година от нашия учен Юрий Манин. Но реално за нея заговориха едва през 1981, когато известният Р. Фейнман в , отбеляза, че не е възможно ефективно да се моделира еволюцията на квантова система на класически компютър. Той предложи елементарна модел , който ще може да проведе такова моделиране.
В мрежата има , в която е разгледана по-академично и подробно, ние ще минам кратко:
Основни етапи в историята на създаването на квантовите компютри:
- [1994]. П.Шор. Разработен
- [1998]. Създаден
- [2001]. IBM представи изпълнение на за разлагане на числото 15
- [2007-2016]. създава и развива компютър с 128-2000 кубита
- [2012]. В Университета на Калифорния реализират
- [2016]. Google на 9-кубитен компютър
- [2017]. (три атома)
- [2019]. . 20-кубитен компютър в облака
- [2019]. . 53-кубитен компютър. ?
Както виждате, преминаха 17 години (от 1981 до 1998) от момента на идеята до нейното първо реализиране в компютър с 2 кубита, и 21 година (от 1998 до 2019) до момента, когато броят на кубитите се увеличи до 53. Потребваха се 11 години (от 2001 до 2012), за да се подобри резултатът от изпълнението на алгоритъма на Шор (ще се спрем на него по-подробно малко по-късно) от числото 15 до 21. Също така само преди три години достигнахме до момента, когато можем да реализираме това, за което говореше Фейнман, и да научим да моделираме най-простите физически системи.
Развитието на квантовите изчисления върви бавно. Пред учените и инженерите стоят много сложни задачи, квантовите състояния са много краткотрайни и крехки, и за да ги запазим достатъчно дълго за извършване на изчисления, се налага да строим саркофази за десетки милиони долари, в които се поддържа температура малко над абсолютната нула и които са максимално защитени от външни въздействия. По-късно ще говорим за тези задачи и проблеми по-подробно.
Водещи играчи
Слайдове за тази част са взети от статията , от научния сътрудник Алекси Фьодов. Позволете ми да си позволя директни цитати:
Всички технологично напреднали страни в момента активно развиват квантови технологии. В тези изследвания се инвестират огромни средства, създават се специални програми за подкрепа на квантовите технологии.
В квантовата надпревара участват не само държави, но и частни компании. Общата сума, вложена от Google, IBM, Intel и Microsoft в развитието на квантовите компютри в последно време, възлиза на около 0,5 милиарда долара, с които са създадени големи лаборатории и изследователски центрове.
В Хабра и в мрежата има много статии, например, , и , в които текущото състояние на развитието на квантовите технологии в различни страни е разгледано по-подробно. За нас в момента е най-важно, че всички водещи технологично развити страни и играчи инвестираят огромни средства в изследвания в тази област, което дава надежда за излизане от текущия технологичен застой.
Направления на развитие
В момента (може да греша, поправете ме) основните усилия (и по-или-мене значимите резултати) на всички водещи играчи са концентрирани върху две направления:
- Специализирани квантови компютри, насочени към решаване на една конкретна специфична задача, например, задачата за оптимизация. Пример за продукт са квантовите компютри D-Wave.
- Универсални квантови компютри — които могат да реализират произволни квантови алгоритми (Шор, Гровър и др.). Реализации от IBM, Google.
Други вектори на развитието, които ни дава квантовата физика, такива като:
- като основа за
- и много други
разбира се, също са в списъка на направленията за изследване, но на този етап не изглежда, че има каквито и да е значими резултати.
Допълнително може да се прочете , а и да гуглите “”, например, , и .
Основи. Квантов обект и квантови системи
Най-важното, което трябва да разберете от този раздел, е, че
Квантовият компютър (за разлика от обикновения) използва квантови обекти, а за провеждане на изчисления квантовите обекти трябва да бъдат свързани в квантова система..
Какво всъщност е квантов обект?
Квантовият обект — обект на микросвета (квантовия свят), който проявява квантови свойства:
- Има определено състояние с два гранични нива
- Находи се в суперпозиция на своето състояние до момента на измерване
- Заплита се с други обекти, за да създаде квантови системи
- Изпълнява теоремата за забраната на клонирането (не може да се копира състоянието на обекта)
Нека разгледаме всяко свойство по-подробно:
Има определено състояние с две гранични нива (крайно състояние)
Класически пример от реалния свят — монета. Тя има състояние “страна”, което приема две гранични нива — “орак” и “решка”.
Находи се в суперпозиция на своето състояние до момента на измерване
Хвърлихме монетката, тя лети и се върти. Докато се върти, е невъзможно да се каже в кое от граничните нива се намира състоянието “страна”. Но щом я прихлопнем и погледнем резултата — суперпозицията на състоянията веднага се свива в едно от двете гранични — “орак” и “решка”. Прихлопването на монетката в нашия случай е измерването.
Заплита се с други обекти, за да създаде квантови системи
С монетката е трудно, но нека опитаме. Представете си, че сме хвърлили три монети така, че да се въртят, захващайки една за друга, като жонглиране с монети. В всеки момент всяка от тях не само се намира в суперпозиция на състояния, но тези състояния взаимно влияят едно на друго (монетите все пак се сблъскват).
Изпълнява теоремата за забраната на клонирането (не може да се копира състоянието на обекта)
Докато монетите летят и се въртят, ние по никакъв начин не можем да създадем отделна от системата копия на въртящото се състояние на която и да е от монетите. Системата живее сама за себе си и много ревностно се отнася към това да издаде навън каквато и да е информация.
Още няколко думи за самото понятие “суперпозиция”, практически във всички статии суперпозицията се обяснява като “намира се във всички състояния едновременно,” което, разбира се, е вярно, но понякога излишно заплита. Суперпозицията на състоянията може да се представи също така, че в всеки момент от времето квантовият обект има определени вероятности да се свие в всяко от своите гранични нива и в сумата тези вероятности, естествено, са равни на 1. По-нататък, при разглеждането на кубита, ще спрем на това по-подробно.
За монетите може да си го представите визуално — в зависимост от началната скорост, ъгъла на хвърляне, състоянието на околната среда, в която лети монетата, вероятността за получаване на "орел" или "решка" е различна в всеки момент от времето. И, както беше споменато по-рано, състоянието на такава летяща монета може да си представим като "намираща се във всички свои гранични състояния едновременно, но с различна вероятност за реализиране".
Всеки обект, който удовлетворява горепосочените свойства и който можем да създадем и управляваме, може да се използва като носител на информация в квантов компютър.
Някъде по-нататък ще говорим за текущото състояние на нещата с физическата реализация на кубитите като квантови обекти и какво в момента учените използват за това.
И така, третото свойство гласи, че квантовите обекти могат да се заплетат за създаване на квантови системи. Какво всъщност е квантова система?
Квантова система — система от заплетени квантови обекти, притежаваща следните свойства:
- Квантовата система е в суперпозиция на всички възможни състояния на обектите, от които се състои
- Не може да се определи състоянието на системата преди момента на измерване
- В момента на измерване системата реализира един от възможните варианти на своите гранични състояния
(и, забегвайки малко напред)
Следствие за квантовите програми:
- Квантовата програма има зададено състояние на системата на входа, суперпозиция вътре, суперпозиция на изхода
- На изхода на програмата след измерване имаме вероятностна реализация на едно от възможните краен състояния на системата (плюс възможни грешки)
- Всяка квантова програма има архитектура на коминна тръба (вход -> изход. Няма цикли, не може да се види състоянието на системата в средата на процеса.)
Сравнение на квантовия компютър и обикновения
Сега нека сравним обикновен компютър и квантов.
| Обикновен компютър | Квантовият компютър | |
Логика | 0 / 1 | `a|0> + b|1>, a^2+b^2=1` |
Физика | Полупроводников транзистор | Квантовият обект |
Носител на инф. | Нива на напрежение | Поляризация, спин,… |
Операции | NOT, AND, OR, XOR над битовете | Вентили: CNOT, Адамара,… |
Взаимовръзка | Полупроводников чип | Заплетеност помежду си |
Алгоритми | Стандартни (виж Кнут) | Специални (Шор, Гровер) |
Принцип | Цифров, детерминиран | Аналогов, вероятностен |
Логическо ниво
В обикновен компютър това е бит. Добре ни е познат. детерминиран бит. Може да приемате стойности или 0, или 1. Той отлично изпълнява ролята на логическа единица за обикновен компютър, но изобщо не е подходящ за описание на състоянието квантов обект, който, както вече споменахме, в природата се намира всуперпозиция на своите крайни състояния.
За това е създаден . В своите крайни състояния той реализира състояния, подобни на 0 и 1 , а в суперпозиция представлява вероятностно разпределение над своите крайни състояния |0> и |1>:
a|0> + b|1>, така че a^2 + b^2 = 1a и b в този случай представляват , а квадратите на техните модули — самите вероятности да получим именно такива стойности на крайна състояния |0> и |1> , ако сгънем кубита с измерване точно сега.
Физическо ниво
На текущото технологично ниво на развитие физическата реализация на бита за обикновен компютър е полупроводников транзистор, за квантов, както вече споменахме, всеки квантов обект. В следващия раздел ще говорим за това, което в момента се използва като физически носители на кубити.
Носител на информация
За обикновен компютър това е електрически ток — нива на напрежение, наличие или отсъствие на ток и т.н., за квантов — това е състоянието на квантовия обект (посока на поляризация, спин и т.н.), което може да бъде в състояние на суперпозиция.
Операции
За реализиране на логически схеми в обикновен компютър се използват известни на всички ни , за операциите върху кубити беше необходимо да се измисли напълно различна система от операции, наречена . Вентилите могат да бъдат еднокубитни и двукубитни в зависимост от това, върху колко кубита се извършва преобразуването.
Примери за квантови вентил
Има понятие за универсален набор от вентил, който е достатъчен за изпълнение на всяко квантово изчисление. Например, универсален е наборът, включващ вентил Адамара, вентил на фазовото изместване, вентил CNOT и вентил π⁄8. С тях може да се извърши всяко квантово изчисление на произволен набор от кубити.
В тази статия няма да се спираме подробно на системата на квантовите вентили, можете да прочетете повече за тях и логическите операции с Кубити, например, . Най-важното, което трябва да запомните:
- Операциите с квантови обекти изискват създаването на нови логически оператори (квантови вентили)
- Квантовите вентили са еднокубитни и двукубитни
- Съществуват универсални комплекти вентили, с помощта на които може да се извърши всяко квантово изчисление
Взаимовръзка
Един транзистор е напълно безполезен, за да извършваме изчисления, трябва да свържем много транзистори помежду си, т.е. да създадем полупроводников чип от милиони транзистори, на който вече да изградим логически схеми, и накрая, да получим съвременен процесор в класическия му вид.
Един кубит също е напълно безполезен (освен ако не е в академичен план),
за да извършваме изчисления, ни трябва система от кубити (квантови обекти)
която, както вече споменахме, се създава чрез заплитане на кубити помежду си, така че промените в техните състояния да се извършват в съответствие.
Алгоритми
Стандартните алгоритми, които човечеството е натрупало до момента, са напълно неподходящи за изпълнение на квантов компютър. Да не говорим, че и не е нужно. Квантовите компютри, основани на логиката на вентили с кубити, изискват създаването на съвсем различни алгоритми, квантови алгоритми. Сред най-известните квантови алгоритми можем да отделим три:
- (факторизация)
- (бързо търсене в нерегулирана база данни)
- (отговор на въпроса, постоянна или балансирана функция)
Принцип
И най-важната разлика — това е принципът на работа. При стандартния компютър това е цифров, строго детерминиран принцип, основан на факта, че ако зададем някакво начален статус на системата и го пропуснем през зададен алгоритъм, резултатът от изчисленията ще бъде един и същ, колкото пъти да сме стартирали тези изчисления. Всъщност, такова поведение е точно това, което очакваме от компютъра.
Квантовият компютър работи на аналогов, вероятностен принцип. Резултатът от работата на зададения алгоритъм на зададения начален статус представлява извадка от вероятностно разпределение конечни реализации на алгоритми плюс възможни грешки.
Тази вероятностна натура на квантовите изчисления е обусловена от самата вероятностна същност на квантовия свят. “Бог не играе на зарове с вселената”, — казвал старецът Айнщайн, но всички експерименти и наблюдения досега (в текущата научна парадигма) потвърдиха обратното.
Физически реализации на кубити
Както вече споменахме, кубит може да бъде представен като квантов обект, т.е. такъв физически обект, който реализира описаните по-горе квантови свойства. Тоест грубо казано, всеки физически обект, който има две състояния и тези две състояния са в състояние на суперпозиция, може да бъде използван за построяване на квантов компютър.
“Ако можем да поместим атом в два различни нива и да ги управляваме, ето ви кубит. Ако можем да направим това с йон, — кубит. С ток е същото. Ако го пуснем по часовниковата стрелка и против часовниковата стрелка едновременно, ето ви кубит.”
Има к , в която текущото многообразие на физическите реализации на кубита се разглежда по-подробно, ние просто ще изброим най-известните и разпространени:
- и множество други екзотични идеи (аниони и др.)
От всичкото това многообразие най-разработеният метод за получаване на кубити е основан на . , , и други водещи играчи използват именно него за построяване на своите системи.
Е, и още прочетете на възможните кубити от .
Основи. Принцип на работа на квантовия компютър
Материалите за този раздел (задача и изображения) са взети от статията .
И така, нека представим, че имаме следната задача:
Има група от трима души: (А)ндрей, (B)олодя и (С)ережа. Има две таксита (0 и 1).
Също така е известно, че:
- (А)ндрей, (B)олодя — приятели
- (А)ндрей, (С)ережа — врагове
- (B)олодя и (С)ережа — врагове
Задача: Разположете хората по таксита така, че Max(приятели) и Min(врагове)
Оценка: L = (брой приятели) — (брой врагове) за всеки вариант на разположение
ВАЖНО: Да предположим, че херистиките не съществуват, оптимално решение няма. В този случай задачата се решава само с пълно перебиране на вариантите.
Решение на обикновен компютър
Как да решим тази задача на обикновен (супер)компютър (или клъстер) — очевидно е, че трябва да прегледаме всички възможни варианти в цикъл.Ако имаме мултипроцесорна система, може да разпаралелим изчисленията на решенията на няколко процесора и след това да съберем резултатите.
Имаме 2 възможни варианта за разпределение (такси 0 и такси 1) и 3 души. Пространството на решения 2^3 = 8. Прегледането на 8 варианта може да се направи дори на калкулатор, това не е проблем. А сега нека усложним задачата — имаме 20 души и два автобуса, пространството на решения 2^20 = 1 048 576. Също нищо сложно. Увеличаваме броя на хората 2.5 пъти — взимаме 50 души и два влака, пространството на решения сега 2^50 = 1.12 x 10^15.При обикновен (супер)компютър вече започват сериозни проблеми. Увеличаваме броя на хората 2 пъти, 100 души ще ни дадат вече 1.2 x 10^30 възможни варианта.
Всичко, за разумно време, тази задача не може да бъде изчислена.
Свързваме суперкомпютър.
Най-мощният компютър в момента — номер 1 от това е с производителност 122 Да предположим, че за изчисление на един вариант ни трябват 100 операции, тогава за решаване на задачата за 100 души ще ни трябва:
(1.2 x 10^30 100) / 122×10^15 / (606024365) = 3 x 10^37 години.
Както виждаме, при увеличаване на размерността на изходните данни пространството на решения расте по степенен закон, в общия случай за N бита имаме 2^N възможни варианта на решение, които при сравнително малки N (100) ни дават непредвидимо (на текущото технологично ниво) пространство на решения.Има ли алтернативи? Както вече се досетихте, да, има.
Но преди да преминем към това как и защо квантовите компютри позволяват ефективно решаване на подобни задачи, нека си припомним какво представлява
вероятностното разпределение. Не се плашете, статията е обзорна, няма да имаме строга математика, ще се справим с класически пример с торба и топки.Съвсем малко комбинаторика, теория на вероятностите и странен експериментатор.
Взимаме торба и в нея поставяме
1000 бели и 1000 черни топки. Ще проведем експеримент — ще изваждаме топка, ще записваме цвета, ще връщаме топката в торбата и ще разбъркваме топките в торбата.Проведохме експеримента 10 пъти,
извадихме 10 черни топки. извадихме 10 черни топки.. Възможно ли е? Напълно. Дава ли ни тази извадка разумно представа за истинското разпределение в чувала? Очевидно не. Какво трябва да направим - правилно, повторете експеримента милион пъти и изчислете честотите на черните и белите топки. Получаваме, например 49,95% черни и 50,05% бели. В такъв случай структурата на разпределението, от което вземаме семпли (изваждаме една топка), е вече по-ясна.
Основното, което трябва да разберем, е, че самият експеримент има вероятностен характер, с един семпъл (топката) не можем да установим истинската структура на разпределението, необходимо е многократно да повторим експеримента и да усредним резултатите.
Да добавим в нашия чувал 10 червени и 10 зелени топки (грешки). Повтаряме експеримента 10 пъти. Визтеглихме 5 червени и 5 зелени. Възможно ли е? Да. Можем ли да кажем нещо за истинското разпределение — Не. Какво трябва да направим — вече разбрахте.
За да разберем структурата на вероятностното разпределение, трябва многократно да вземем единични изходи от него и да усредним резултатите.
Свързваме теорията с практиката
Сега вместо черни и бели топки, нека вземем билярдни топки и да сложим в чувала 1000 топки с номер 2, 1000 с номер 7 и 10 топки с други номера. Представете си експериментатор, който е обучен в основни действия (да извади топка, да запише номера, да върне топката в чувала, да разбърка топките в чувала) и това прави за 150 микросекунди. Някакъв такъв експериментатор на спийдове (не реклама на наркотици!!!). Тогава за 150 секунди той ще може да проведе нашия експеримент 1 милион пъти и да ни предостави резултатите от усредняването.
Седнахме експериментатора, дадохме му чувал, обърнахме се, изчакахме 150 секунди — получихме:
номер 2 — 49,5%, номер 7 — 49,5%, останалите номера в общо — 1%.
Да, всичко е вярно, нашият чувал — това е квантов компютър с алгоритъм, решаващ нашия проблем, а топките — възможните варианти за решение. Тъй като правилните решения са две, то квантовият компютър ще ни дава всяко от тези възможни решения с равна вероятност, и 0,5% (10/2000) грешки, за които ще говорим по-късно.
За да получим резултата от работата на квантовия компютър, трябва многократно да пускаме квантовия алгоритъм на един и същи набор от данни и да усредняваме резултата.
Масштабируемост на квантовия компютър
Сега си представете, че за задача, в която участват 100 души (пространството на решенията 2^100 бележим си това), правилните решения също са само две. Тогава, ако вземем 100 кубита и напишем алгоритъм, който пресмята нашата целева функция (L, вижте по-горе) върху тези кубити, ще получим чанта, в която ще има 1000 топки с номера на първия правилен отговор, 1000 с номера на втория правилен отговор и 10 топки с други номера. И нашият експериментатор за същите 150 секунди ще ни предостави оценка на вероятностното разпределение на правилните отговори.
Времето за изпълнение на квантовия алгоритъм (с някои допускания) може да се счита за константно О(1) относно размерността на пространството на решенията (2^N).
И точно това свойство на квантовия компютър — константността на времето за изпълнение относно нарастващата по степен сложност на пространството на решенията, е ключово.
Кубит и паралелни светове
Как се случва това? Какво позволява на квантовия компютър да извършва изчисления толкова бързо? Всичко е свързано с квантовата природа на кубита.
Вижте, ние казахме, че кубитът като квантов обект реализира едно от двете си състояния при наблюдение, но в „живата природа“ е в суперпозиция на състояния, т.е. е в и двете си крайни състояния едновременно (с определена вероятност).
Да вземем (А)ндрей и да представим неговото състояние (в какво превозно средство е — 0 или 1) като кубит. Тогава в квантовото пространство възникват два паралелни свята, в един (А) седи в такси 0, в другия свят — в такси 1. В същото време в две таксита, но с определена вероятност да го намерим в тях при наблюдение.
Да вземем (В)олодю и също да представим неговото състояние като кубит. Възникват два други паралелни свята. Но тези двойки светове (А) и (В) не взаимодействат по никакъв начин. Какво трябва да направим, за да създадем свързана система? Правилно, трябва да свържем тези кубити да заплетем. Вземаме и заплитаме (А) с (В) — получаваме квантова система от два кубита (А, В), която реализира вътре в себе си четири взаимозависими паралелни света. Добавяме (С)ергея и получаваме система от три кубита (АВС), която реализира осем взаимозависими паралелни света.
Сутринта квантовите изчисления (реализация на веригата от квантови вентил) представят факта, че изчислението става едновременно в всички паралелни светове.
И не е важно колко от тях имаме, 2^3 или 2^100, квантовият алгоритъм ще завърши за крайно време в всички тези паралелни светове и ще ни даде резултат, представляващ семплиране от вероятностно разпределение на отговорите на алгоритъма.
За по-добро разбиране, може да си представите, че квантовият компютър на квантово ниво стартира 2^N паралелни процеса на решаване,всеки от които работи върху един възможен вариант, след което събира резултатите — и ни предоставя отговор под формата на суперпозиция на решението (вероятностно разпределение на отговорите), от което ние всеки път (при всеки експеримент) семплираме един.
Запомнете времето, необходимо на нашия експериментатор (150 мкс) за провеждане на експеримента, това ще ни бъде от полза по-късно, когато говорим за основните проблеми на квантовите компютри и времето на декохерентност.
Квантови алгоритми
Както вече бе споменато, обикновените алгоритми, основани на бинарната логика, не могат да се прилагат на квантовия компютър, използващ квантова логика (квантови вентил). За него бяха измислени нови, които в пълна степен използват потенциала, заложен в квантовата природа на изчисленията.
Най-известните до момента алгоритми са:
В противовес на класическите, квантовите компютри не са универсални.
До момента е намерено само малко на брой квантови алгоритми.
Благодаря за линка към , място, където, според автора (), са събрани и продължават да се събират най-добрите представители на квантовото-алгоритмичното поле.
В тази статия не ще разглеждаме подробно квантовите алгоритми, в мрежата има много прекрасни материали на всяко ниво на сложност, но кратко да преминем през трите най-известни все пак трябва.
Алгоритъм на Шор.
Най-известният квантов алгоритъм е (изобретен през 1994 година от английския математик ), който е насочен към решаване на задачата за разлагане на числа на прости множители (задача за факторизация, дискретен логаритъм).
Този алгоритъм се споменава, когато се пише за това как банковите ви системи и пароли скоро ще бъдат разбити. Имайки предвид, че дължината на използваните в момента ключове е не по-малка от 2048 бита, времето за шапочката все още не е дошло.
В днешно време са повече от скромни. Най-добрите резултати от факторизация с помощта на алгоритъма на Шор — числа и , което е значително по-малко от 2048 бита. За останалите резултати от таблицата е използван друг за изчисления, но дори и най-добрият резултат по този алгоритъм (291311) е далеч от реалното приложение.
Можете да прочетете повече за алгоритъма на Шор, например,. За практическата реализация — .
Една от за сложността и необходимата мощност за факторизация на число от 2048 бита е компютър с . Спим спокойно.
Алгоритъм на Гровър
— за решаване на задача на проба, т.е. намиране на решение на уравнението F(X) = 1, където F е от n променливи. Беше предложен от американския математик в .
Алгоритъмът на Гровър може да бъде използван за намиране на и на числов ред. Освен това, той може да се прилага за решаване на задачи чрез изчерпателно търсене сред множеството възможни решения. Това може да доведе до значителен ръст на скоростта в сравнение с класическите алгоритми, макар и да не предоставя "" в общия вид..
Можете да прочетете повече, или . Освен това има добро обяснение на алгоритъма с примера на кутии и топка, но, за съжаление, по причини, независещи от мен, този сайт не се отваря от Русия. Ако при вас също е блокиран, то ето кратка извадка:
Алгоритъм на Гровър. Представете си, че имате N броя номерирани затворени кутии. Те всички са празни, освен една, в която се намира топка. Вашата задача: да разберете номера на кутията, в която се намира топката (този неизвестен номер често се обозначава с буквата w).
Как да решим този проблем? Най-глупавият начин е да отворите кутиите една по една, и рано или късно ще попаднете на кутията с топката. Колко кутийки трябва средно да проверите, преди да откриете кутията с топката? Средно трябва да отворите около половината кутийки N/2. Важно е, че ако увеличим броя на кутиите сто пъти, средният брой кутийки, които трябва да отворим, ще се увеличи също сто пъти.
Сега ще направим още едно уточнение. Да кажем, че не ние отваряме кутиите и проверяваме наличието на топка в тях, а имаме някакъв посредник, да го наречем Оракул. Казваме на Оракула - 'провери кутия номер 732', и Оракулът честно проверява и отговаря 'в кутия номер 732 няма топка'. Сега вместо да говорим колко кутийки средно трябва да отворим, казваме 'колко пъти средно трябва да се обърнем към Оракул, за да намерим номера на кутията с топката'
Оказва се, че ако преведем тази задача с кутиите, топката и Оракула на квантов език, получаваме забележителен резултат: за да намерим номера на кутията с топката сред N кутийки, трябва да разтремим Оракула само около SQRT(N) пъти!
Тоест сложността на задачата при избиране с алгоритъма на Гровър намалява на квадратен корен.
Алгоритъм на Дойч-Йожи
Алгоритъмът на Дойч – Йожи (споменава се също и като алгоритъм на Дойч – Джозы) - [квантов алгоритъм](алгоритъм), предложен и в , и става един от първите примери за алгоритми, предназначени за изпълнение на . _
Задачата на Дойч – Йожи е да установи дали функцията на няколко бинарни променливи F(x1, x2, … xn) е постоянна (приема или стойност 0, или 1 за всякакви аргументи) или сбалансирана (за половината от стойностите приема стойност 0, за другата половина 1). При това се счита, че предварително е известно, че функцията или е константа, или е сбалансирана.
Можете да прочетете още . По-просто обяснение:
Алгоритъмът на Дойч (Дойч — Йожи) е основан на перебора, но позволява да се извърши по-бързо от обичайното. Представете си, че на масата има монета и трябва да разберем дали е фалшива или не. За целта трябва да погледнем два пъти на монетата и да определим: „орел“ и „решка“ – истинска, две „орла“ или две „решки“ — фалшива. С квантовия алгоритъм на Дойч, това определение може да се направи с един поглед – измерване.
Проблеми на квантовите компютри
При проектирането и експлоатацията на квантови компютри пред учените и инженерите се налага да решават множество проблеми, които в момента се разрешават с променлив успех. Според () можем да отделим следния набор от проблеми:
- Чувствителност към околната среда и взаимодействие с нея
- Натрупване на грешки при изчисленията
- Трудности с началната инициализация на състоянията на кубитите
- Трудности със създаването на многокубитни системи
Препоръчвам силно да прочетете статията “”, особено коментарите под нея.
Нека организираме всички основни проблеми в три големи групи и да разгледаме по-подробно всяка от тях:
Декохерентност
.
Квантово състояние много крехка работа, кубитите в заплетено състояние са крайно нестабилни, всяко външно въздействие може да разруши (и разрушава) тази връзка. Промяната на температурата с най-малката част от градуса, натиска, преминалият до там случайно фотон — всичко това дестабилизира нашата система.
За разрешаване на този проблем се изграждат нискотемпературни саркофази, в които температурата (-273.14 градуса Целзий) е малко над абсолютната нула, с максимална изолация на вътрешната камера с процесора от всички (възможни) въздействия на външната среда.
Максималното време за живот на квантовата система от няколко заплетени кубита, през което тя запазва своите квантови свойства и може да бъде използвана за извършване на изчисления, се нарича време на декохерентност.
В момента времето на декохерентност в най-добрите квантови решения е около десетки и стотици микросекунди.
Има страхотен , на който можете да видите на всички създадени квантови системи. В тази статия за пример са представени само два топ процесора — от IBM и от . Както виждаме, времето на декохерентност (T2) не надвишава 200 μs.
Не намерих точни данни за Sycamore, но в самата се дават две числа — 1 милион изчисления за 200 секунди, на друго място — за 130 секунди без загуби на управляващи сигнали и други. Във всеки случай, това ни дава време на декохерентност около 150 μs. Помните нашия експериментатор с чанта? Ну так вот он.
| Computer Name | N Qubits | Max paired | T2 (μs) |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~150-200 |
Какви опасности носи декохерентността?
Основният проблем е, че след 150 μs нашата изчислителна система от N заплетени кубити ще започне да дава на изхода вместо вероятностно разпределение на правилни решения — вероятностен бял шум.
Тоест, трябва да:
- Инициализираме системата на кубитите
- Извършваме изчисление (верига от вентилни операции)
- Четем резултата
И да направим всичко това за 150 μs. Не успяхме — резултатът се превръща в тиква.
Но това още не е всичко...
Грешки
Както вече казахме, квантовите процеси и квантовите изчисления имат вероятностна природа, не можем да бъдем сигурни на 100% в нищо, а само с определена вероятност. Ситуацията се утежнява още и от това, че квантовите изчисления са подложени на грешки.Основните видове грешки при квантовите изчисления са:
- Грешки в декохерентността, предизвикани от сложността на системата и взаимодействието с външната среда
- Изчислителни грешки на вентилите (предизвикани от квантовата природа на изчисленията)
- Грешки при четене на финалното състояние (резултата)
Грешки, свързани с декохерентността, възникват веднага, щом заплетем нашите кубити и започнем да извършваме изчисления. Колкото повече кубити сме заплели, толкова по-сложна е системата, и толкова по-лесно е да я разрушим. Нискотемпературни саркофази, защитени камери, всички тези технологични трикове са точно насочени към намаляване на броя на грешките и удължаване на времето на декохерентност.
Изчислителни грешки на вентилите — всяка операция (вентил) над кубитите може с известна вероятност да завърши с грешка, а за реализиране на алгоритъма трябва да извършим стотици вентилни операции, представете си какво ще получим в края на изпълнението на нашия алгоритъм. Класическият отговор на въпроса — “Каква е вероятността да срещнете динозавър в асансьора?” — 50х50, или ще срещнете, или не.
Проблемата се усложнява от обстоятелството, че стандартните методи за корекция на грешки (дублиране на изчисления и средно аритметично) в квантовия свят не работят поради теоремата за забраната на клониране. За в квантовите изчисления трябваше да се измислят . Грубо казано, вземаме N обикновени кубита и правим от тях 1 логически кубит с по-ниско ниво на грешки.
Но тук възниква друг проблем — общият брой кубити. Да кажем, че имаме процесор с 100 кубита, от които 80 кубита са заети с корекция на грешките, тогава ни остават само 20 за изчисления.
Грешките при прочитане на окончателния резултат — както си спомняме, резултатът от квантовите изчисления е представен под формата на вероятностно разпределение на отговорите. Но прочитането на окончателното състояние също може да завърши с грешка.
На същия има сравнителни таблици на процесорите по нива на грешки. За сравнение, да вземем същите процесори, които в предишния пример — IBM и :
| Computer | 1-Qubit Gate Fidelity | 2-Qubit Gate Fidelity | Readout Fidelity |
| IBM Q System One | 99.96% | 98.31% | — |
| Google Sycamore | 99.84% | 99.38% | 96.2% |
Тук — мярка за сходство на две квантови състояния. Степента на грешка може грубо да се представи като 1-Fidelity. Както виждаме, грешките при 2-кубитни гейтове и грешките при прочитане са основната пречка за изпълнението на сложни и дълги алгоритми на съществуващите квантови компютри.
Можете да прочетете още година от по решаването на задача за корекция на грешки.
Архитектура на процесора
В теорията изграждаме и оперираме схеми от десетки заплетени кубити, в реалността обаче всичко е по-сложно. Всички съществуващи квантови чипове (процесори) са изградени по такъв начин, че осигуряват безболезнено заплитане на един кубит само със своите съседи, които не са повече от шест.
Ако трябва да заплетем 1-ви кубит, да кажем, с 12-ти, тогава ще трябва да изградим верига от допълнителни квантови операции, да ангажираме допълнителни кубити и др., което увеличава общото ниво на грешките. Да, и не забравяйте за времето за декохерентност, може би в момента, когато завършите свързването на кубитите в нужната ви схема, времето ще изтече и цялата схема ще се превърне в симпатичен генератор на бял шум.
Също така не забравяйте, че архитектурата на всички квантови процесори е различна, и програмата, написана в емулатора в режим “свързаност на всички с всички”, ще трябва да бъде “преподредена” към архитектурата на конкретен чип. Има дори за извършване на тази операция.
Максимална свързаност и максимален брой кубити за същите топови чипове:
| Computer Name | N Qubits | Max paired | T2 (μs) |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~150-200 |
И, за сравнение, таблица с данни от предишното поколение процесори. Сравнете броя на кубитите, времето на декохерентност и процента на грешки с това, което имаме в момента при новото поколение. Все пак напредъкът постепенно, но движи.
И така:
- Към момента няма напълно свързани архитектурни схеми с > 6 кубита
- За да заплетете кубит 0 с, например, 15-ти, може да са необходими десетки допълнителни операции
- Повече операции -> повече грешки -> по-силен влиянието на декохерентността
Итог
Декохерентността — прокрустово ложе на съвременните квантови изчисления. В 150 мкc трябва да поберем всичко:
- Инициализация на началното състояние на кубитите
- Изчисляване на задачата с използване на квантови Gates
- Извършване на корекции на грешките, за да получим значим резултат
- Да считаме получения резултат
Докато резултатите са незадоволителни, въпреки заявяват постигане на 0.5с време на задържане на когерентност на квантов компютър, основан на :
Сместваме времето на когерентност на кубит над 0.5 с и с магнитна защита очакваме това да се подобри и да надхвърли 1000 с
За тази технология може да се прочете или, например, .
Ситуацията е усложнена и от факта, че при извършване на сложни изчисления е необходимо да се използват квантови схеми за корекция на грешки, което също отнема време и налични кубити.
И накрая, съвременните архитектури не позволяват с минимални разходи да се реализират схеми за заплетеност по-добре от 1 към 4 или 1 към 6.
Пътища за решаване на проблемите
За решаване на посочените проблеми в момента се използват следните подходи и методи:
- Използване на криокамери с ниски температури (10 мК (–273,14°C))
- Използване на максимално защитени от външни влияния процесорни блокове
- Използване на системи за квантова корекция на грешки (Логически кубит)
- Използване на оптимизатори при програмиране на схеми за конкретен процесор
Също така се провеждат изследвания, насочени към увеличаване на времето на декохерентност, търсене на нови (и доработка на известни) физически реализации на квантови обекти, оптимизация на схеми за корекция и други. Напредък има (вижте по-горе характеристиките на по-ранни и настоящи топови чипове), но все още е бавен, много, много бавен.
D-Wave
2000-кубитен компютър D-Wave 2000Q. Източник:
На фона на изявлението на Google за достигане на квантово превъзходство, използвайки процесор с 53 кубита, и от компанията D-Wave, в които числото кубити е в хиляди, малко обърква. Наистина, ако 53 кубита могат да постигнат квантово превъзходство, какво би могъл да направи компютър с 2048 кубита? Но не е всичко толкова добре...
Ако накратко (взето от Уикипедия):
Компютрите работят на принципа на (), могат да решават изключително ограничен подклас задачи за оптимизация и не са подходящи за изпълнение на традиционни квантови алгоритми и квантови вентилни.
По-подробно може да се прочете, например, , (внимание, може да не се отваря от Русия), или при в от неговия . Между другото, много препоръчвам да прочетете изобщо неговия блог, има много добри материали.
Наистина, още от самото начало на анонсите научната общност имаше въпроси към компютрите D-Wave. Например, през 2014 г. IBM постави под съмнение факта, че D-Wave Ситуацията достигна до там, че през 2015 г. Google заедно с NASA купи един от тези квантови компютри и след изследвания , че наистина, компютърът работи и решава задачата по-бързо от обикновените. Още за изявлението на Google може да се прочете и, например, .
Най-важното е, че компютрите D-Wave, с техните стотици и хиляди кубити, не могат да се използват за изчисления и изпълнение на квантови алгоритми. На тях не може да се стартира алгоритъм на Шор, например. Всичко, което могат, е да използват определени квантови механизми за решаване на конкретна задача за оптимизация. Може да се счита, че D-Wave е подобен на квантов ASIC за конкретна задача.
Няколко думи за емулацията на квантови компютри
Квантовите изчисления могат да се емулитат на обикновен компютър. Всъщност, :
- Състоянието на кубита може да като комплексно число., заемащи от 2х32 до 2х64 бита (8-16 байта) в зависимост от архитектурата на процесора
- Състоянието на N свързани кубита може да се представи под формата на 2^N комплексни числа, т.е. 2^(3+N) за 32-битова архитектура и 2^(4+N) за 64-битова.
- Квантовата операция върху N кубита може да се представи с матрица 2^N x 2^N
Тогава:
- За съхранение на емулираните състояния на 10 кубита са необходими 8 KB
- За съхранение на състояния на 20 кубита са необходими 8 MB
- За съхранение на състояния на 30 кубита са необходими 8 GB
- За съхранение на състояния на 40 кубита са необходими 8 TB
- За съхранение на състояния на 50 кубита са необходими 8 PB и т.н.
За сравнение, () носи на себе си само 2.8 PB памет.
— 49 кубита, поставени миналата година на най-големия китайски суперкомпютър ()
Пределът на симулацията на квантов компютър на класически системи е обусловен от количеството оперативна памет, необходимо за съхранение на състоянието на кубитите.
Препоръчвам да прочетете . Оттам:
По операциите — за точна емиулация на схемата с 49 кубита от около 39 „такта“ (независими слоеве от вентилите) 2^63 комплексни умножения — 4 PFLOPS суперкомпютър за продължение от 4 часа
Емиулацията на квантов компютър с 50+ кубита на класически системи се счита за непостижима в разумно време. Именно поради този факт Google използва за експеримента си с квантово превосходство процесор с 53 кубита.
Квантово изчислително превъзходство.
Уикипедия дава следното определение на квантовото изчислително превосходство:
Ква́нтово превосхо́дство — способността устройства да решават проблеми, които класическите компютри практически не могат да решат.
Всъщност достигането на квантово превосходство означава, че, например, факторизацията на големи числа по алгоритъм на Шор може да бъде решавана за адекватно време, или може да се емулират на квантово ниво сложни химически молекули и т.н. Тоест, нова ера е настъпила.
Но в формулировката на определението има известна лазейка, "които класическите компютри практически не могат да решатВсъщност това означава, че ако се създаде квантов компютър с 50+ кубита и се пусне на него определена квантова схема, резултатът от работата на тази схема няма да може да бъде емулиран на обикновен компютър. Тоест класическият компютър не е в състояние да възпроизведе резултата от работата на такава схема..
Дали такъв резултат представлява истинско квантово превъзходство, или не, е по-скоро философски въпрос. Но е важно да разберем какво е направила Google и на какво се основава Трябва.
Изявлението на Google за постигане на квантово превъзходство
54-кубитният процесор Sycamore.
И така, през октомври 2019 година разработчиците на Google публикуваха в научно списание Nature статия "" Авторите обявиха, че за първи път в историята е постигнато квантово превъзходство с помощта на 54-кубитния процесор Sycamore.
В интернет в статии Sycamore често се споменава или като 54-кубитен процесор, или като 53-кубитен. Истината е, че според процесорът физически се състои от 54 кубита, но един от тях е неработещ и е изключен от експлоатация. Така че в реалността имаме 53-кубитен процесор.
В мрежата веднага материали по тази тема, чиято завист варираше от до .
По-късно служители от отдела за квантови изчисления на IBM заявиха, че В компанията твърдят, че обикновен компютър ще се справи с тази задача в най-лошия случай за 2,5 дни и получените отговори ще бъдат по-точни от тези на квантовия компютър. Такъв извод беше направен след теоретичен анализ на няколко метода за оптимизация.
Разбира се, в своя не можа да игнорира това изявление. Неговият заедно с всички линкове и както обикновено си заслужават да им се отдели време. В Хабра на това FAQ, и непременно прочетете коментарите, там има линкове към предварителни документи, изтекли в мрежата преди официалното обявление.
Какво всъщност направи Google? За детайлно разбиране прочетете Ааронсона, а накратко ето:
Разбира се, мога да ви кажа, но се чувствам малко глупаво. Изчислението е следното: експериментаторът генерира случайна квантова схема С (т.е. случайна последователност от 1-кубитни и 2-кубитни вентилите, между най-близките съседи, с дълбочина, например, 20, която действа на 2D мрежа от 50-60 кубита). След това експериментаторът изпраща С на квантовия компютър и го моли да приложи С към началното състояние от 0, да измери резултата в базиса {0,1}, да върне n-битната наблюдавана последователност (стринга) и да повтори това хиляди или милиони пъти. Накрая, използвайки знанието си за С, експериментаторът провежда статистическа проверка за съответствието на резултата с очакваното изходно значение от квантовия компютър.
Съвсем накратко:
- Създава се случайна схема с дължина 20 от 53 кубита, използвайки вентилите
- Схемата се стартира с начално състояние [0…0] за изпълнение
- Изходът на схемата представлява случайна битова последователност (семпъл)
- Распределението на резултата не е случайно (интерференция)
- Распределението на получените семпли се сравнява с очакваното
- Прави се заключение за квантово превосходство
Тоест, Google реализира синтетична задача на 53-кубитен процесор, и заявлението им за постигане на квантово превосходство се основава на факта, че е невъзможно да се емулира такъв процесор на стандартни системи за разумно време.
За по-добро разбиране — в този раздел по никакъв начин не се подценява постижението на Google, инженерите наистина са се справили отлично, а въпросът дали може да се счита за реално квантово превосходство или не, както вече бе споменато, е по-скоро философски, отколкото инженерен. Но трябва да разберем, че с достигане на такова изчислително превосходство не сме направили и крачка напред към възможността за изпълнение на алгоритъма на Шор върху 2048-битови числа.
Резюме
Квантовите компютри и квантовите изчисления са многообещаваща, още млада и засега слабо прилагана в индустриален план област на информационните технологии.
Развитието на квантовите изчисления ще позволи (някога) да се решават задачи:
- Моделиране на сложни физически системи на квантово ниво
- Неразрешими на обикновен компютър заради изчислителната сложност
Основни проблеми при създаването и експлоатацията на квантови компютри:
- Декохерентност
- Грешки (декохеренция и вентилни)
- Архитектура на процесорите (пълносвързани схеми на кубити)
Състояние на нещата в момента:
- Всъщност – най-началното .
- РЕАЛНАТА търговска експлоатация все още не е налична (и не е ясно, кога ще бъде)
Какво може да помогне:
- Физическо откритие, намаляващо разходите за свързване и експлоатация на процесорите
- Откритие, което многократно ще увеличи времето на декохеренция и/или ще намали броя на грешките
На мое мнение (изключително лично мнение), в настоящата научна парадигма на знанието не можем да постигнем значителен напредък в развитието на квантовите технологии, тук е нужен качествен пробив в някоя област на фундаменталната или приложна наука, който да даде тласък на нови идеи и методи.
А за сега – натрупваме опит в квантовото програмиране, събираме и създаваме квантови алгоритми, тестваме идеи и т.н. Очакваме пробив.
Заключение
В тази статия разгледахме основните етапи в развитието на квантовите изчисления и квантовите компютри, анализирахме принципа на тяхната работа, обсъдихме основните проблеми, пред които са изправени инженерите при разработването и експлоатацията на квантови процесори, а също така видяхме какво всъщност представляват многокубитните компютри D-Wave и неотдавнашното изявление на Google за постигане на квантово превъзходство.
Извън кадър останаха въпросите за програмирането на квантовите компютри (езици, подходи, методи и т.н.) и въпросите, свързани с конкретната физическа реализация на процесорите, как протича управлението на кубитите, свързването, четенето и т.н. Може би това ще е темата на следващата статия или статии.
Благодаря за вниманието, надявам се тази статия да бъде полезна на някого.
(C)
Благодарности
за корекция и забележки по оригиналния текст, както и за статията
за информационно наситените коментари към , а и не само към нея, които в голяма степен ми помогнаха да разгадая тази пъзел.
На всички автори на статии и публикации, материалите от които бяха използвани при написването на тази статия.
Списък на ресурсите
Статии за настоящото положение от [The National Academies Press]
Статии от Хабра (в произволен ред)
Несортирани (но не по-малко интересни) статии от пространствата на интернет
Курсове и лекции
Източник: habr.com
