Квантовите компютри и квантовите изчисления — нов , който се добави в нашето информационно пространство наред с , и другите високо технологични термини. Въпреки това, не успях да намеря в интернет материал, който да постави в главата ми пъзела под името “как работят квантовите компютри”. Да, има много прекрасни трудове, включително и на Хабра (вж. ), коментарите на които, както обикновено, са още по-информативни и полезни, но картината в главата, така да се каже, не се сглобяваше.
Наскоро колеги ми се приближиха и попитаха “Разбираш ли как работи квантовият компютър? Можеш ли да ни разкажеш?” И тогава осъзнах, че проблемът с изграждането на цялостната картина не е само мой.
В резултат на това аз направих опит да компилирам информация за квантовите компютри в непротиворечива логическа схема, в която на основно ниво, без дълбочинно гмуркане в математиката и структурата на квантовия свят, се обяснява какво представлява квантовият компютър, на какви принципи работи, а също така какви проблеми стоят пред учените при неговото създаване и експлоатация.
Съдържание
Дисклеймер
Авторът не е специалист в квантовите изчисления и целевата аудитория на статията — също такива ИТ специалисти, не квантови специалисти, които също искат да изградят в главата си картината под името “Как работят квантовите компютри”. Поради това много понятия в статията са съзнателно опростени за по-добро разбиране на квантовите технологии на “основно” ниво, но без .
В статията на някои места са използвани материали от други източници, . Навсякъде, където е било възможно, са включени директни връзки и указания към оригинала на текста, таблицата или рисунка. Ако съм забравил нещо (или някого), пишете — ще поправя.
Въведение
В тази глава накратко ще разгледаме откъде започна квантовата ера, каква беше основната причина за възникването на идеята за квантовия компютър, кои (кои държави и корпорации) в момента са водещите играчи в тази област и накратко ще обсъдим основните направления в развитието на квантовите изчисления.
Как всичко започна
Началната точка на квантовата ера се счита за 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 черни топки. Възможно ли е? Вполне. Дава ли ни тази извадка разумна представа за истинското разпределение в чантата? Очевидно не. Какво трябва да направим — правилно, повторим експеримента милион пъти и да изчислим честотите на изтегляне на черни и бели топки. Получаваме, например 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 секунди ще ни даде оценка на вероятностното разпределение на правилните отговори..
Времето за изпълнение на квантовия алгоритъм (при определени допускания) може да се счита за константно O(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. Основното тук е, че ако увеличим броя на кутиите 100 пъти, средното число кутиите, които трябва да отворим, също ще се увеличи 100 пъти, преди да намерим кутията с топчето.
Сега ще направим още едно уточнение. Да предположим, че ние не отваряме кутиите с ръце и не проверяваме наличието на топчето във всяка от тях, а има посредник, да наречем го Оракул (Oracle). Ние казваме на Оракул — „провери кутия номер 732“, и Оракул честно проверява и отговаря „в кутия номер 732 няма топче“. Сега вместо да говорим за това колко кутии трябва да отворим средно, казваме „колко пъти средно трябва да се обърнем към Оракул, за да намерим номер на кутията с топчето“
Оказва се, че ако преведем тази задача с кутиите, топчето и Оракул на квантов език, се получава забележителен резултат: за да намерим номера на кутията с топчето сред N кутии, трябва да раздразним Оракула само около SQRT(N) пъти!
Тоест сложността на задачата при търсенето с алгоритма на Гровър намалява с квадратния корен.
Алгоритъм на Дойч-Йожи
Алгоритъмът на Дойч — Йожи (също известен като алгоритъм на Дойч — Джозы) — [квантов алгоритъм]((алгоритъм), предложен и в , и стана един от първите примери за алгоритми, предназначени за изпълнение на . _
Задачата на Дойч — Йожи се състои в определяне дали функцията на няколко двоични променливи F(x1, x2, … xn) е константна (приема стойност 0 или 1 при всякакви аргументи) или балансирана (през половината от областта на определение приема стойност 0, а за другата половина 1). При това се смята, че функциите или са константни, или са балансирани.
Можете да прочетете още . По-просто обяснение:
Алгоритъмът на Дойч (Дойч — Йожи) се основава на изчерпване, но позволява да го направим по-бързо от обикновеното. Представете си, че на масата лежи монета и трябва да узнаете дали е фалшива или не. За целта трябва да погледнете два пъти монетата и да определите: „орел“ и „решка“ – истинска, два „орла“, две „решки“ — фалшива. Ето, с използването на квантовия алгоритъм на Дойч, това определение може да се направи с един поглед – измерване.
Проблеми на квантовите компютри
При проектирането и експлоатацията на квантови компютри пред учените и инженерите възникват огромно количество проблеми, които в момента се решават с променлив успех. Според () могат да се посочат следните проблеми:
- Чувствителност към околната среда и взаимодействие с околната среда
- Натрупване на грешки при изчисленията
- Трудности с началната инициализация на състоянията на кубитите
- Трудности със създаването на многокубитни системи
Препоръчвам силно да прочетете статията "", особено коментарите към нея.
Нека организираме всички основни проблеми в три големи групи и да разгледаме по-подробно всеки от тях:
Декохерентност
.
Квантово състояние много крехко нещо, кубитите в заплетено състояние са изключително нестабилни, всяко външно въздействие може да разруши (и разрушава) тази връзка. Промяна на температурата с малка част от градус, налягане, случайно преминал фотон наблизо — всичко това дестабилизира нашата система.
За решаването на този проблем се изграждат нискотемпературни саркофаги, в които температурата (-273.14 градуса по Целзий) е малко по-висока от абсолютната нула, с максимална изолация на вътрешната камера с процесора от всички (възможни) въздействия на външната среда.
Максималното време на живот на квантова система от няколко заплетени кубита, през което тя запазва своите квантови свойства и може да бъде използвана за извършване на изчисления, се нарича време на декохерентност.
Към момента времето на декохерентност в най-добрите квантови решения е около десетки и стотици микросекунди.
Има прекрасен , на който можем да видим на всички създадени квантови системи. В тази статия за пример са включени само два топови процесора — от IBM и от . Както виждаме, времето на декохерентност (T2) не надвишава 200 микросекунди.
Не намерих точни данни за Sycamore, но в самата се посочват две цифри — 1 милион изчисления за 200 секунди, на друго място — за 130 секунди без загуби на управляващи сигнали и други. Във всеки случай, това ни дава време на декохерентност около 150 микросекунди. Помните нашия експериментатор с чанта? Ну так вот он.
| Computer Name | N Qubits | Macs свързани | T2 (мкс) |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~150-200 |
Какви са ни рисковете от декохерентност?
Основният проблем е, че след 150 микросекунди нашата изчислителна система от N заплетени кубита ще започне да извежда на изхода вместо вероятностно разпределение на верните решения — вероятностен бял шум.
Тоест трябва да:
- Инициализираме системата от кубити
- Извършване на изчисление (верига от вентилни операции)
- Да се запише резултатът
И всичко това да стане за 150 мкс. Не успеете — резултатът се превръща в тиква.
Но това не е всичко…
Грешки
Както вече споменахме, квантовите процеси и квантовите изчисления имат вероятностна природа, не можем да бъдем сигурни на 100% в нищо, а само с някаква вероятност. Ситуацията става още по-тежка, тъй като квантовите изчисления са подложени на грешки. Основните видове грешки при квантовите изчисления са:
- Грешки на декогерентност, причинени от сложността на системата и взаимодействието с външната среда
- Изчислителни грешки на вентилите (поради квантовата природа на изчисленията)
- Грешки при прочитане на финалното състояние (резултата)
Грешки, свързани с декогерентността, възникват веднага щом заплетем нашите кубити и започнем да извършваме изчисления. Колкото повече кубити заплетем, толкова по-сложна става системата, и толкова по-лесно е да я разрушим. Нискотемпературните саркофаги, защитените камери — всички тези технологични хитрости имат за цел да намалят броя на грешките и да удължат времето на декогерентност.
Изчислителни грешки на вентилите — всяка операция (вентил) върху кубитите може с определена вероятност да завърши с грешка, а за да реализираме алгоритъма, трябва да изпълним стотици вентилите, представете си какво ще получим в края на изпълнението на нашия алгоритъм. Класическият вариант на въпроса — “Каква е вероятността да срещнеш динозавър в асансьор?” — 50х50, или ще го срещнеш, или не.
Проблемът е още по-тежък, тъй като стандартните методи за корекция на грешки (дублиране на изчисления и средноаритметично) не работят в квантовия свят поради теоремата за забрана на клонирането. За в квантовите изчисления трябваше да измислим . На грубо ниво, взимаме N обикновени кубити и правим от тях 1 логически кубит с по-ниско ниво на грешки.
Но тук възниква друг проблем — общият брой кубити. Вижте, предположим, че имаме процесор с 100 кубита, от които 80 кубита са заети с корекция на грешки, тогава остават само 20 за изчисления.
Грешки при прочитане на финалния резултат — както помним, резултатът от квантовите изчисления ни се представя под формата на вероятностно разпределение на отговорите. Но разчитането на финалното състояние също може да завърши с грешка.
На същото има сравнителни таблици на процесорите по нива на грешки. За сравнение, да вземем същите процесори, които в предишния пример — IBM и :
| Компютър | 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 | Macs свързани | T2 (мкс) |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~150-200 |
И, за сравнение, таблица с данни от предишното поколение процесори. Сравнете броя на кубитите, времето на декохерентност и процента на грешки с това, което имаме сега от новото поколение. Все пак напредъка бавно, но сигурно върви напред.
И така:
- В момента няма напълно свързани архитектурни схеми с > 6 кубити
- За да заплетете кубит 0 с, например, 15-ти, може да са необходими няколко десетки допълнителни операции
- Повече операции -> повече грешки -> по-силно влияние на декохерентността
Резюме
Декохерентност — прокрустово ложе на съвременните квантови изчисления. В 150 мкс трябва да вместим всичко:
- Инициализиране на началното състояние на кубитите
- Изчисление на задача с помощта на квантови врати
- Извършване на корекция на грешки, за да се получи значим резултат
- Да се запише полученият резултат
Към момента резултатите не са утешителни, въпреки че декларират постигане на 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 за конкретна задача.
Няколко думи за емулацията на квантовите компютри
Квантовите изчисления могат да се емулират на обикновен компютър. В крайна сметка, :
- Състоянието на кубита може да като комплексно число, заемащо от 2x32 до 2x64 бита (8-16 байта), в зависимост от архитектурата на процесора.
- Състоянието на N свързани кубити може да бъде представено като 2^N комплексни числа, т.е. 2^(3+N) за 32-битова архитектура и 2^(4+N) за 64-битова.
- Квантовата операция над N кубити може да бъде представена с матрица 2^N x 2^N.
Тогава:
- За съхранение на емулираните състояния на 10 кубита са нужни 8 КБ.
- За съхранение на състояния на 20 кубита са нужни 8 МБ.
- За съхранение на състояния на 30 кубита са нужни 8 ГБ.
- За съхранение на състояния на 40 кубита са нужни 8 Терабайта.
- За съхранение на състояния на 50 кубита са нужни 8 Петабайта и т.н.
За сравнение, () носи всичко 2.8 Петабайта памет.
— 49 кубита, поставени миналата година на най-голямото китайско суперкомпютърно устройство ()
Пределът на симулацията на квантови компютри на класически системи е обусловен от количеството оперативна памет, необходимо за съхранение на състоянието на кубитите.
Препоръчвам още да прочетете . Оттам:
По операции — за точна емуляция на схемата с 49 кубита от 39 "такта" (независими слоя на вентилите) 2^63 комплексни умножения — 4 Пфлопса суперкомпютър за 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 мрежа n=50-60 кубита). След това експериментаторът изпраща С на квантовия компютър и го моли да приложи С върху началното състояние от 0, да измери резултата в базиса {0,1}, да изпрати обратно n-битната наблюдавана последователност (стринг) и да повтори няколко хиляди или милиона пъти. Накрая, използвайки знанията си за С, експериментаторът провежда статистическа проверка на съответствието на резултата с очаквания изход от квантовия компютър.
Съвсем накратко:
- Създава се случайна схема с дължина 20 от 53 кубита, използвайки вентилите
- Схемата се стартира с начално състояние [0…0] за изпълнение
- Изходът на схемата представлява случайна битова последователност (семпл)
- Разпределението на резултата не е случайно (интерференция)
- Разпределението на получените семпли се сравнява с очакваното
- Прави се заключение за квантово превъзходство
Тоест, Google е реализирал синтетична задача на 53-кубитен процесор и заявлението си за достигане на квантово превъзходство основава на факта, че такъв процесор не може да бъде еймулиран на стандартни системи в разумно време.
За по-добро разбиране — в тази част не се намалява постижението на Google, инженерите наистина са страхотни, а въпросът дали може да се счита за истинско квантово превъзходство или не, както вече беше споменато, е по-скоро философски, отколкото инженерни. Но трябва да разберем, че, достигайки такова изчислително превъзходство, не сме напреднали нито на крачка към възможността да стартираме алгоритъма на Шор на 2048-битови числа.
Резюме
Квантовите компютри и квантовите изчисления са много перспективна, много млада и все още малко приложима в промишлен план област на информационните технологии.
Развитието на квантовите изчисления ще позволи (някога) решаване на задачи:
- Моделиране на сложни физически системи на квантово ниво
- Нерешими на обикновен компютър поради изчислителна сложност
Основни проблеми при създаването и експлоатацията на квантови компютри:
- Декохерентност
- Грешки (декохерентност и вентилни)
- Архитектура на процесорите (пълносвързани схеми на кубити)
Състоянието на нещата в момента:
- По факта - на най-началния етап .
- НЯМА РЕАЛНА търговска експлоатация (и не е ясно кога ще има)
Какво може да помогне:
- Някакво физическо откритие, което да намали разходите за свързване и експлоатация на процесорите
- Откритие на нещо, което значително ще увеличи времето за декохерентност и/или ще намали броя на грешките
Според мен (изключително лично мнение), в текущата научна парадигма на знанията няма да постигнем значителни успехи в развитието на квантовите технологии, тук е необходим качествен пробив в някаква област на фундаменталната или приложната наука, който ще даде тласък на нови идеи и методи.
А засега - натрупваме опит в квантовото програмиране, събираме и създаваме квантови алгоритми, тестваме идеи и т.н. Чакме пробив.
Заключение
В тази статия разгледахме основните етапи в развитието на квантовите изчисления и квантовите компютри, обсъдимe принципа на тяхната работа, разгледахме основните проблеми, пред които инженерите са изправени при разработката и експлоатацията на квантови процесори, а също така и какво всъщност представляват многокубитните компютри D-Wave и неотдавнашното заявление на Google за постигане на квантово предимство.
На заден план останаха въпросите за програмирането на квантови компютри (езици, подходи, методи и т.н.) и въпросите, свързани с конкретната физическа реализация на процесорите, както се извършва управлението на кубитите, свързването, четенето и т.н. Възможно е това да бъде темата на следващата статия или статии.
Благодаря за вниманието, надявам се тази статия да е полезна за някого.
(С)
Благодарности
за прегледа и коментарите относно оригиналния текст, както и за статията
за информационно-наситените коментари към , а и не само към нея, които в значителна степен ми помогнаха да се справя с този пъзел.
На всички автори на статии и публикации, материалите на които бяха използвани при написването на тази статия.
Списък на ресурсите
Статии за текущото състояние от [The National Academies Press]
Статии от Хабра (в случайен ред)
Несортирани (но не по-малко интересни) статии от интернет пространството
Курсове и лекции
Източник: habr.com
