Квантови компютри и квантово изчисление – ново , който беше добавен в нашето информационно пространство заедно с , и други високотехнологични термини. В същото време така и не успях да намеря в интернет материал, който да сглоби пъзела в главата ми, наречен „как работят квантовите компютри“. Да, има много отлични произведения, включително на Habr (вижте. ), коментари, към които, както обикновено се случва, са още по-информативни и полезни, но картината в главата ми, както се казва, не се нареди.
И наскоро мои колеги дойдоха при мен и ме попитаха: „Разбирате ли как работи квантовият компютър? Можете ли да ни кажете?“ И тогава разбрах, че не съм единственият, който има проблем да състави последователна картина в главата си.
В резултат на това беше направен опит да се компилира информация за квантовите компютри в последователна логическа схема, в която основно ниво, без дълбоко потапяне в математиката и структурата на квантовия свят, беше обяснено какво представлява квантовият компютър, на какви принципи работи и с какви проблеми се сблъскват учените при създаването и експлоатацията му.
Таблица на съдържанието
Опровержение
Авторът не е експерт по квантови изчисления и Целевата аудитория на статията са същите ИТ хора, а не квантовите специалисти, които също искат да съберат картина в главите си, наречена „Как работят квантовите компютри“. Поради това много концепции в статията са умишлено опростени, за да се разберат по-добре квантовите технологии на „базово“ ниво, но без .
Статията на места използва материали от други източници, . Където е възможно, се вмъкват директни връзки и указания към оригиналния текст, таблица или фигура. Ако някъде съм забравил нещо (или някой), пишете и ще го коригирам.
въведение
В тази глава ще разгледаме накратко как започна квантовата ера, каква е била мотивиращата причина за идеята за квантов компютър, кои (кои държави и корпорации) в момента са водещите играчи в тази област, а също така накратко ще говорим за основните насоки на развитие на квантовите изчисления.
Как започна всичко
За начална точка на квантовата ера се счита 1900 г., когато М. Планк за първи път излага че енергията се излъчва и поглъща не непрекъснато, а на отделни кванти (порции). Идеята беше подета и развита от много изключителни учени от онова време - Бор, Айнщайн, Хайзенберг, Шрьодингер, което в крайна сметка доведе до създаването и развитието на такава наука като . В интернет има много добри материали за формирането на квантовата физика като наука; в тази статия няма да се спираме подробно на това, но беше необходимо да посочим датата, когато влязохме в новата квантова ера.
Квантовата физика донесе много изобретения и технологии в нашето ежедневие, без които сега е трудно да си представим света около нас. Например лазер, който сега се използва навсякъде, от домакински уреди (лазерни нивелири и др.) До високотехнологични системи (лазери за корекция на зрението, здравей ). Би било логично да се предположи, че рано или късно някой ще излезе с идеята защо да не използваме квантови системи за изчисления. И тогава през 1980 г. това се случи.
Wikipedia показва, че първата идея за квантово изчисление е изразена през 1980 г. от нашия учен Юрий Манин. Но наистина започнаха да говорят за това едва през 1981 г., когато добре познатият Р. Фейнман , отбеляза, че е невъзможно да се симулира еволюцията на квантова система на класически компютър по ефективен начин. Той предложи елементарен модел , които ще могат да извършват подобно моделиране.
Има , в която се разглежда по-академично и подробно, но ще преминем накратко:
Основни етапи в историята на създаването на квантови компютри:
- [1994]. П. Шор. Проектирана от
- [1998]. Създаден
- [2001]. IBM представи изпълнение за разширяване на номер 15
- [2007-2016]. създава и разработва компютър с 128-2000 кубита
- [2012]. Внедрено в Калифорнийския университет
- [2016]. Google на 9-кубитов компютър
- [2017]. (три атома)
- [2019]. . 20-кубитов компютър в облака
- [2019]. . 53 qubit компютър. ?
Както можете да видите, изминаха 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` |
|
физика
|
Полупроводников транзистор | Квантов обект |
|
Медиен носител
|
Нива на напрежение | Поляризация, въртене,... |
|
операции
|
НЕ, И, ИЛИ, XOR върху битове | Клапани: CNOT, Hadamard,… |
|
Връзка
|
Полупроводников чип | Объркване един с друг |
|
алгоритми
|
Стандарт (виж Whip) | Специални (Шор, Гроувър) |
|
принцип
|
Цифров, детерминистичен | Аналогов, вероятностен |
Логическо ниво
В обикновен компютър това е малко. Добре познат ни докрай детерминиран бит. Може да приема стойности 0 или 1. Справя се перфектно с ролята логическа единица за обикновен компютър, но е напълно неподходящ за описание на състоянието квантов обект, който, както вече казахме, в дивата природа се намира всуперпозиции на техните гранични състояния.
Ето какво измислиха . В своите гранични състояния той реализира състояния, подобни на 0 и 1 , а в суперпозиция представлява разпределение на вероятността върху неговите гранични състояния |0> и |1>:
a|0> + b|1>, такое, что a^2+b^2=1a и b представляват , а квадратите на техните модули са реалните вероятности за получаване на точно такива стойности на граничните състояния |0> и |1>, ако свиете кюбита с измерване точно сега.
Физически слой
При сегашното технологично ниво на развитие физическото внедряване на бит за конвенционален компютър е полупроводников транзистор, за квант, както вече казахме, всеки квантов обект. В следващия раздел ще говорим за това, което в момента се използва като физическа среда за кубити.
Средство за съхранение
За обикновен компютър това е електричество - нива на напрежение, наличие или отсъствие на ток и др., за квантовите - същото състояние на квантов обект (посока на поляризация, спин и др.), които могат да бъдат в състояние на суперпозиция.
операции
За да реализираме логически схеми на обикновен компютър, ние използваме добре познати , за операциите върху кубитите беше необходимо да се измисли съвсем различна система от операции, т.нар . Гейтовете могат да бъдат с единичен кубит или с двоен кубит, в зависимост от това колко кубита се преобразуват.
Примери за квантови порти:
Има концепция универсален комплект вентили, които са достатъчни за извършване на всяко квантово изчисление. Например, универсален набор включва врата на Адамар, врата за фазово изместване, врата CNOT и врата π⁄8. С тяхна помощ можете да извършите всякакви квантови изчисления върху произволен набор от кубити.
В тази статия няма да се спираме подробно на системата от квантови врати, можете да прочетете повече за тях и логически операции върху кубити, например . Основното нещо, което трябва да запомните:
- Операциите върху квантовите обекти изискват създаването на нови логически оператори (квантови порти)
- Квантовите порти се предлагат в еднокубитови и двойнокубитови типове.
- Има универсални набори от порти, които могат да се използват за извършване на всякакви квантови изчисления
Връзка
Един транзистор е напълно безполезен за нас; за да извършим изчисления, трябва да свържем много транзистори един към друг, тоест да създадем полупроводников чип от милиони транзистори, върху който да изградим логически схеми, и в крайна сметка да получите модерен процесор в класическата му форма.
Един кубит също е напълно безполезен за нас (добре, макар и само в академичен план),
за извършване на изчисления се нуждаем от система от кубити (квантови обекти)
който, както вече казахме, се създава чрез заплитане на кубити един с друг, така че промените в техните състояния да се случват по координиран начин.
алгоритми
Стандартните алгоритми, които човечеството е натрупало до момента, са напълно неподходящи за внедряване на квантов компютър. Да, като цяло няма нужда. Квантовите компютри, базирани на гейт логика върху кубити, изискват създаването на напълно различни алгоритми, квантови алгоритми. От най-известните квантови алгоритми могат да се разграничат три:
- (факторизация)
- (бързо търсене в неподредена база данни)
- (отговор на въпроса, постоянна или балансирана функция)
принцип
И най-важната разлика е принципът на работа. За стандартен компютър това е цифров, строго детерминиран принцип, въз основа на факта, че ако зададем някакво първоначално състояние на системата и го прекараме през даден алгоритъм, тогава резултатът от изчисленията ще бъде същият, независимо колко пъти изпълняваме това изчисление. Всъщност това поведение е точно това, което очакваме от компютъра.
Квантовият компютър работи аналогов, вероятностен принцип. Резултатът от даден алгоритъм при дадено начално състояние е извадка от вероятностно разпределение крайни реализации на алгоритъма плюс възможни грешки.
Тази вероятностна природа на квантовите изчисления се дължи на самата вероятностна същност на квантовия свят. „Бог не играе на зарове с Вселената.“, каза старият Айнщайн, но всички експерименти и наблюдения досега (в настоящата научна парадигма) потвърждават обратното.
Физически реализации на кубити
Както вече казахме, кубитът може да бъде представен от квантов обект, тоест физически обект, който изпълнява квантовите свойства, описани по-горе. Тоест, грубо казано, всеки физически обект, в който има две състояния и тези две състояния са в състояние на суперпозиция, може да се използва за изграждане на квантов компютър.
„Ако можем да поставим атом на две различни нива и да ги контролираме, тогава имате кубит. Ако можем да направим това с йон, това е кубит. Същото е и с тока. Ако го пуснем по посока на часовниковата стрелка и обратно на часовниковата стрелка едновременно, имате кубит.
Има к , в който текущото разнообразие от физически реализации на кубита се разглежда по-подробно, просто ще изброим най-известните и често срещани:
- и много други екзотични идеи (аниони и др.)
От цялото това разнообразие най-развит е първият метод за получаване на кубити, базиран на . , , и други водещи играчи го използват за изграждане на своите системи.
Е, прочетете повече възможен кубити от .
Основи. Как работи квантовият компютър
Материалите за този раздел (задача и снимки) са взети от статията .
И така, представете си, че имаме следната задача:
Има група от трима души: (А)ндрей, (Б)олодя и (В)ережа. Има две таксита (0 и 1).
Също така е известно, че:
- (А)андрей, (Б)олодя са приятели
- (А)ндрей, (С)ережа са врагове
- (Б)олодя и (В)ережа са врагове
Задача: Поставете хората в такситата така, че Макс (приятели) и Мин (врагове)
Клас: L = (брой приятели) - (брой врагове) за всеки вариант за настаняване
ВАЖНО: Ако приемем, че няма евристика, няма оптимално решение. В този случай проблемът може да бъде решен само чрез пълно търсене на опции.
Решение на обикновен компютър
Как да решите този проблем на обикновен (супер) компютър (или клъстер) - това е ясно трябва да преминете през всички възможни опции. Ако имаме многопроцесорна система, тогава можем да паралелизираме изчислението на решения в няколко процесора и след това да съберем резултатите.
Имаме 2 възможни варианта за настаняване (такси 0 и такси 1) и 3 човека. Пространство за решение 2^3 = 8 XNUMX XNUMX. Можете дори да преминете през 8 опции с помощта на калкулатор, това не е проблем. Сега нека усложним проблема - имаме 20 души и два автобуса, пространството за решение 2^20 = 1 048 576. Нищо сложно също. Нека увеличим броя на хората 2.5 пъти - вземем 50 души и два влака, пространството на решението е сега 2^50 = 1.12 х 10^15. Един обикновен (супер) компютър вече започва да има сериозни проблеми. Да увеличим броя на хората 2 пъти, 100 души ще ни дадат вече 1.2 х 10^30 възможни варианти.
Това е, тази задача не може да бъде изчислена в разумен период от време.
Свързване на суперкомпютър
Най-мощният компютър в момента е номер 1 на , това , производителност 122 . Да приемем, че имаме нужда от 100 операции, за да изчислим една опция, тогава за решаване на проблема за 100 души ще ни трябва:
(1.2 x 10^30 100) / 122×10^15 / (606024365) = 3 х 10^37 години.
Както виждаме тъй като размерът на първоначалните данни се увеличава, пространството на решението расте според степенния закон, в общия случай за N бита имаме 2^N възможни опции за решение, които за сравнително малко N (100) ни дават неизчислено (на текущото технологично ниво) пространство за решение.
Има ли алтернативи? Както може би се досещате, да, има.
Но преди да навлезем в това как и защо квантовите компютри могат ефективно да решават проблеми като тези, нека отделим малко време, за да обобщим какви са те. разпределение на вероятностите. Не се тревожете, това е обзорна статия, тук няма да има сложна математика, ще се задоволим с класическия пример с чанта и топки.
Само малко комбинаторика, теория на вероятностите и странен експериментатор
Да вземем една чанта и да я сложим в нея 1000 бели и 1000 черни топки. Ще проведем експеримент - извадете топката, запишете цвета, върнете топката в торбата и смесете топките в торбата.
Експериментът е проведен 10 пъти, извади 10 черни топки. Може би? Съвсем. Тази проба дава ли ни разумна представа за истинското разпределение в чантата? Очевидно не. Какво трябва да се направи - прав, тповторете експеримента милион пъти и изчислете честотите на черните и белите топки. Получаваме напр 49.95% черно и 50.05% бяло. В този случай структурата на разпределението, от което вземаме проба (изваждаме една топка), вече е повече или по-малко ясна.
Основното нещо е да разберете това самият експеримент има вероятностен характер, с една проба (топка) няма да знаем истинската структура на разпределението, трябва да повторим експеримента много пъти и осреднете резултатите.
Нека го добавим в чантата си 10 червени и 10 зелени топки (грешки). Нека повторим експеримента 10 пъти. INизвади 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. В две таксита едновременно, но с известна вероятност да го намерите във всеки от тях по време на наблюдение.
Вземете (Б) млад и нека си представим състоянието му като кубит. Възникват два други паралелни свята. Но засега тези двойки светове (А) и (V) изобщо не си взаимодействат. Какво трябва да се направи, за да се създаде свързани система? Точно така, имаме нужда от тези кубити връзвам (обърквам). Вземаме го и го объркваме (A) с (B) — получаваме квантова система от два кубита (A, B), реализирайки в себе си четири взаимозависими паралелни светове. Добавете (С)ергей и получаваме система от три кубита (ABC), прилагане на осем взаимозависими паралелни светове.
Същността на квантовото изчисление (имплементирането на верига от квантови врати върху система от свързани кубити) е фактът, че изчислението се извършва във всички паралелни светове едновременно.
И няма значение колко от тях имаме, 2^3 или 2^100, квантовият алгоритъм ще бъде изпълнен за крайно време над всички тези паралелни светове и ще ни даде резултат, който е извадка от разпределението на вероятностите на отговорите на алгоритъма.
За по-добро разбиране, човек може да си представи това квантов компютър на квантово ниво изпълнява 2^N паралелни процеса на решаване, всеки от които работи по един възможен вариант, след което събира резултатите от работата - и ни дава отговора под формата на суперпозиция на решението (вероятностно разпределение на отговорите), от което вземаме по една проба всеки път (за всеки експеримент).
Запомнете времето, необходимо на нашия експериментатор (150 µs) за провеждане на експеримента, това ще ни бъде полезно малко по-нататък, когато говорим за основните проблеми на квантовите компютри и времето за декохерентност.
Квантови алгоритми
Както вече беше споменато, конвенционалните алгоритми, базирани на двоична логика, не са приложими към квантов компютър, използващ квантова логика (квантови порти). За него беше необходимо да се измислят нови, които да използват напълно потенциала, присъщ на квантовата природа на изчисленията.
Най-известните алгоритми днес са:
За разлика от класическите, квантовите компютри не са универсални.
Досега са открити само малък брой квантови алгоритми.
Благодаря за връзката към , място, където според автора (), най-добрите представители на квантово-алгоритмичния свят са събрани и продължават да се събират.
В тази статия няма да анализираме подробно квантовите алгоритми; в интернет има много отлични материали за всяко ниво на сложност, но все пак трябва да прегледаме накратко трите най-известни.
Алгоритъмът на Шор.
Най-известният квантов алгоритъм е (изобретен през 1994 г. от английския математик ), която е насочена към решаване на проблема с разлагането на числа на прости множители (проблем с разлагането на множители, дискретно логаритъм).
Именно този алгоритъм се посочва като пример, когато пишат, че банковите ви системи и пароли скоро ще бъдат хакнати. Като се има предвид, че дължината на използваните днес ключове е не по-малко от 2048 бита, времето за таван все още не е дошло.
днес повече от скромен. Най-добри резултати от факторизиране с алгоритъма на Шор - числа и , което е много по-малко от 2048 бита. За останалите резултати от таблицата различно изчисления, но дори най-добрият резултат според този алгоритъм (291311) е много далеч от реалното приложение.
Можете да прочетете повече за алгоритъма на Шор, например,. За практическото изпълнение - .
Един от сложността и необходимата мощност за факторизиране на 2048-битово число е компютърът с . Спим спокойно.
Алгоритъм на Гроувър
- решаване на проблема с изброяването, тоест намиране на решение на уравнението F(X) = 1, където F е от n променливи. Предложено от американски математик в .
Алгоритъмът на Гроувър може да се използва за намиране и числова серия. Освен това може да се използва за решаване проблеми чрез изчерпателно търсене сред много възможни решения. Това може да доведе до значително увеличаване на скоростта в сравнение с класическите алгоритми, макар и без да предоставя "" общо взето.
Можете да прочетете повечеИли , Още Има добро обяснение на алгоритъма, използвайки примера за кутии и топка, но, за съжаление, поради независещи от никого причини, този сайт не се отваря за мен от Русия. Ако имате също е блокиран, така че ето кратко резюме:
Алгоритъм на Гроувър. Представете си, че имате N броя номерирани затворени кутии. Всички те са празни с изключение на една, която съдържа топка. Вашата задача: разберете номера на кутията, в която се намира топката (това неизвестно число често се обозначава с буквата w).
Как да решим този проблем? Най-глупавият начин е да се редувате да отваряте кутиите и рано или късно ще попаднете на кутия с топка. Средно колко кутии трябва да бъдат проверени, преди да се намери кутия с топка? Средно трябва да отворите около половината от N/2 кутии. Основното тук е, че ако увеличим броя на кутиите със 100 пъти, тогава средният брой кутии, които трябва да бъдат отворени, преди да бъде намерена кутията с топката, също ще се увеличи със същите 100 пъти.
Сега нека направим още едно уточнение. Нека не отваряме сами кутиите с ръце и да проверяваме за наличието на топка във всяка, но има определен посредник, да го наречем Оракул. Ние казваме на Оракула „отметнете поле номер 732“, а Оракулът честно проверява и отговаря „няма топка в поле номер 732“. Сега, вместо да казваме колко кутии средно трябва да отворим, казваме „колко пъти средно трябва да отидем при Оракула, за да намерим номера на кутията с топката“
Оказва се, че ако преведем този проблем с кутии, топка и Оракул на квантов език, получаваме забележителен резултат: за да намерим номера на кутия с топка сред N кутии, трябва да смутим Оракула само относно SQRT (N) пъти!
Това означава, че сложността на задачата за търсене, използваща алгоритъма на Grover, се намалява с корен квадратен от пъти.
Алгоритъм на Deutsch-Jozi
Алгоритъм на Deutsch-Jozsa (наричан още алгоритъм на Deutsch-Jozsa) - [квантов алгоритъм](%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC), предложенный и в , и стана един от първите примери за алгоритми, предназначени да бъдат изпълнени на . _
Проблемът на Deutsch-Jozsi е да се определи дали функция от няколко двоични променливи F(x1, x2, ... xn) е постоянна (приема стойност 0 или 1 за всякакви аргументи) или балансирана (за половината от домейна отнема стойността 0, за другата половина 1). В този случай се счита, че априори е известно, че функцията е или постоянна, или балансирана.
Можете също да прочетете . По-просто обяснение:
Алгоритъмът Deutsch (Deutsch-Jozsi) се основава на груба сила, но позволява да се направи по-бързо от обикновено. Представете си, че на масата има монета и трябва да разберете дали е фалшива или не. За да направите това, трябва да погледнете монетата два пъти и да определите: „главите“ и „опашките“ са истински, две „глави“, две „опашки“ са фалшиви. Така че, ако използвате квантовия алгоритъм на Deutsch, тогава това определяне може да се направи с един поглед - измерване.
Проблеми на квантовите компютри
При проектирането и експлоатацията на квантови компютри учените и инженерите се сблъскват с огромен брой проблеми, които досега са решени с различна степен на успех. Според () може да се идентифицира следната поредица от проблеми:
- Чувствителност към околната среда и взаимодействие с околната среда
- Натрупване на грешки по време на изчисленията
- Трудности с първоначалната инициализация на състояния на кубити
- Трудности при създаването на многокубитови системи
Силно препоръчвам да прочетете статията "”, особено коментарите към него.
Нека организираме всички основни проблеми в три големи групи и да разгледаме по-отблизо всяка от тях:
Декохерентност
.
Квантово състояние много крехко нещокубитите в заплетено състояние са изключително нестабилни, всяко външно влияние може (и разрушава) тази връзка. Промяна на температурата с най-малката част от градуса, налягане, случаен фотон, летящ наблизо - всичко това дестабилизира нашата система.
За решаването на този проблем се изграждат нискотемпературни саркофази, в които температурата (-273.14 градуса по Целзий) е малко над абсолютната нула, с максимална изолация на вътрешната камера с процесора от всички (възможни) влияния на външната среда.
Максималният живот на квантова система от няколко заплетени кубита, през който тя запазва своите квантови свойства и може да се използва за изчисления, се нарича време на декохерентност.
В момента времето за декохерентност в най-добрите квантови решения е от порядъка на десетки и стотици микросекунди.
Има прекрасен където можете да погледнете на всички създадени квантови системи. Тази статия включва само два топ процесора като примери - от IBM и от . Както виждаме, времето за декохерентност (T2) не надвишава 200 μs.
За Явор не намерих точни данни, но в повечето дадени са две числа - 1 милион изчисления за 200 секунди, другаде - за 130 секунди без загуба на управляващи сигнали и др.. Във всеки случай това ни дава времето за декохерентност е около 150 μs. Помнете нашите експериментатор с чанта? Е, ето го.
| Име на компютър | N кубита | Макс сдвоен | T2 (µs) |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~ 150-200 |
С какво ни заплашва декохерентността?
Основният проблем е, че след 150 μs нашата изчислителна система от N заплетени кубита ще започне да извежда вероятностен бял шум вместо вероятностно разпределение на правилните решения.
Тоест имаме нужда от:
- Инициализирайте системата qubit
- Извършване на изчисление (верига от операции на портата)
- Прочетете резултата
И направете всичко това за 150 микросекунди. Нямах време - резултатът се превърна в тиква.
Но това не е всичко…
Грешки
Както казахме, квантовите процеси и квантовите изчисления са вероятностни по природа, не можем да бъдем 100% сигурни в нищо, но само с известна вероятност. Ситуацията се утежнява още повече от факта, че квантовите изчисления са податливи на грешки. Основните видове грешки в квантовите изчисления са:
- Грешките при декохерентност са причинени от сложността на системата и взаимодействието с външната среда
- Гейт изчислителни грешки (поради квантовия характер на изчислението)
- Грешки при четене на крайното състояние (резултат)
Грешки, свързани с декохерентност, се появяват веднага щом оплитаме нашите кубити и започнем да правим изчисления. Колкото повече кубити заплитаме, толкова по-сложна е системата, и толкова по-лесно е да го унищожите. Нискотемпературни саркофази, защитени камери, всички тези технологични трикове са точно насочени към намаляване на броя на грешките и удължаване на времето за декохерентност.
Гейт изчислителни грешки - всяка операция (gate) върху кубити може с известна вероятност да завърши с грешка и за да реализираме алгоритъма, трябва да изпълним стотици порти, така че си представете какво получаваме в края на изпълнението на нашия алгоритъм. Класическият отговор на въпроса е „Каква е вероятността да срещнете динозавър в асансьор?“ - 50х50 или ще срещнеш или не.
Проблемът допълнително се влошава от факта, че стандартните методи за коригиране на грешки (дублиране на изчисления и осредняване) не работят в квантовия свят поради теоремата за забрана на клонирането. За в квантовите изчисления трябваше да бъде изобретен . Грубо казано, вземаме N обикновени кубита и правим 1 от тях логически кубит с по-нисък процент грешки.
Но тук възниква друг проблем - общ брой кубити. Вижте, да кажем, че имаме процесор със 100 кубита, от които 80 кубита се използват за коригиране на грешки, тогава ни остават само 20 за изчисления.
Грешки при разчитане на крайния резултат — както си спомняме, резултатът от квантовите изчисления ни се представя във формата вероятностно разпределение на отговорите. Но четенето на крайното състояние също може да се провали с грешка.
На същото Има сравнителни таблици на процесори по нива на грешки. За сравнение, нека вземем същите процесори като в предишния пример - IBM и :
| компютър | 1-Qubit Gate Fidelity | 2-Qubit Gate Fidelity | Точност на четене |
| IBM Q System One | 99.96% | 98.31% | - |
| Google Sycamore | 99.84% | 99.38% | 96.2% |
Тук е мярка за сходството на две квантови състояния. Големината на грешката може грубо да се изрази като 1-вярност. Както виждаме, грешките на 2-кубитови порти и грешките при четене са основната пречка за изпълнението на сложни и дълги алгоритми на съществуващите квантови компютри.
Можете също да прочетете години от за решаване на проблема с коригирането на грешки.
Архитектура на процесора
На теория ние изграждаме и работим вериги от десетки заплетени кубити, в действителност всичко е по-сложно. Всички съществуващи квантови чипове (процесори) са изградени по такъв начин, че осигуряват безболезнено заплитане на един кубит само със съседите му, от които има не повече от шест.
Ако трябва да заплитаме първия кубит, да речем, с 1-ия, тогава ще трябва да изградете верига от допълнителни квантови операции, включват допълнителни кубити и т.н., което увеличава общото ниво на грешка. Да, и не забравяйте за време на декохерентност, може би докато завършите свързването на кубитите във веригата, от която се нуждаете, времето ще свърши и цялата верига ще се превърне в хубав генератор на бял шум.
Също така не забравяйте това Архитектурата на всички квантови процесори е различна, а програмата, написана в емулатора в режим „свързване от всички към всички“, ще трябва да бъде „прекомпилирана“ в архитектурата на конкретен чип. Има дори за извършване на тази операция.
Максимална свързаност и максимален брой кубити за едни и същи топ чипове:
| Име на компютър | N кубита | Макс сдвоен | T2 (µs) |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~ 150-200 |
И за сравнение, таблица с данни от предишното поколение процесори. Сравнете броя на кубитите, времето за декохерентност и процента на грешка с това, което имаме сега с новото поколение. Все пак напредъкът е бавен, но движещ се.
И така:
- Понастоящем няма напълно свързани архитектури с > 6 кубита
- За да заплита qubit 0 s на реален процесор, например, qubit 15 може да изисква няколко десетки допълнителни операции
- Повече операции -> повече грешки -> по-силно влияние на декохерентността
Резултати от
Декохерентността е Прокрустовото легло на съвременните квантови изчисления. Трябва да поберем всичко в 150 μs:
- Инициализация на първоначалното състояние на кубитите
- Изчисляване на проблем с помощта на квантови врати
- Коригирайте грешките, за да получите значими резултати
- Прочетете резултата
Засега обаче резултатите са разочароващи твърдят, че постигат време на задържане на кохерентност от 0.5 s на квантов компютър, базиран на :
Измерваме време на кохерентност на кубита над 0.5 s и с магнитно екраниране очакваме това да се подобри, за да бъде по-дълго от 1000 s
Можете също да прочетете за тази технология или например .
Ситуацията се усложнява допълнително от факта, че при извършване на сложни изчисления е необходимо да се използват схеми за квантова корекция на грешки, което също изяжда както времето, така и наличните кубити.
И накрая, модерните архитектури не позволяват прилагането на схеми на заплитане, по-добри от 1 към 4 или 1 към 6 при минимални разходи.
Начини за решаване на проблеми
За решаване на горните проблеми в момента се използват следните подходи и методи:
- Използване на криокамери с ниски температури (10 mK (–273,14°C))
- Използване на процесорни единици, които са максимално защитени от външни влияния
- Използване на системи за квантова корекция на грешки (Logic Qubit)
- Използване на оптимизатори при програмиране на схеми за конкретен процесор
Провеждат се и изследвания, насочени към увеличаване на времето за декохерентност, търсене на нови (и подобряване на известни) физически реализации на квантови обекти, оптимизиране на вериги за коригиране и т.н., и т.н. Има напредък (вижте по-горе характеристиките на по-ранните и днешните чипове от най-висок клас), но засега е бавен, много, много бавен.
D-Wave
D-Wave 2000Q 2000-кубитов компютър. източник:
На фона на съобщението на Google за постигане на квантово надмощие с помощта на 53-кубитов процесор, и от компанията D-Wave, в която броят на кубитите е хиляди, е донякъде объркващо. Е, наистина, ако 53 кубита са успели да постигнат квантово превъзходство, тогава на какво е способен компютър с 2048 кубита? Но не всичко е толкова хубаво...
Накратко (взето от wiki):
Компютри работят на принципа (), могат да решат много ограничен подклас оптимизационни проблеми и не са подходящи за прилагане на традиционни квантови алгоритми и квантови гейтове.
За повече подробности можете да прочетете напр. , (внимавайте, може да не се отвори от Русия), или в от неговия . Между другото, силно препоръчвам да прочетете неговия блог като цяло, има много добри материали там
Като цяло от самото начало на съобщенията научната общност имаше въпроси относно компютрите D-Wave. Например през 2014 г. IBM постави под въпрос факта, че D-Wave Стигна се дотам, че през 2015 г. Google, заедно с НАСА, закупиха един от тези квантови компютри и след проучване , че да, компютърът работи и изчислява проблема по-бързо от обикновения. Можете да прочетете повече за изявлението на 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 KB
- За да съхраните състоянията на 20 кубита са ви необходими 8 MB
- За съхраняване на състоянията на 30 кубита са необходими 8 GB
- 40 терабайта са необходими за съхраняване на състоянията на 8 кубита
- За съхраняване на състоянията на 50 кубита са необходими 8 петабайта и т.н.
За сравнение, () носи само 2.8 петабайта памет.
— 49 qubit, доставени миналата година на най-големия китайски суперкомпютър ()
Ограничението за симулиране на квантов компютър на класически системи се определя от количеството RAM, необходимо за съхраняване на състоянието на кубитите.
Препоръчвам също да се прочете . Оттам:
По работа - за точна емулация на 49-кубитова верига, състояща се от около 39 „цикъла“ (независими слоеве от порти) 2^63 комплексни умножения - 4 Pflops на суперкомпютър за 4 часа
Емулирането на 50+ qubit квантов компютър на класически системи се счита за невъзможно за разумно време. Ето защо Google използва 53-кубитов процесор за своя експеримент за квантово надмощие.
Превъзходство на квантовите изчисления.
Уикипедия ни дава следната дефиниция за надмощие на квантовите изчисления:
Квантово надмощие – способност устройства за решаване на проблеми, които класическите компютри практически не могат да решат.
Всъщност постигането на квантово превъзходство означава, че например факторизацията на големи числа с помощта на алгоритъма на Shor може да бъде решена за подходящо време или сложни химически молекули могат да бъдат емулирани на квантово ниво и т.н. Тоест настъпи нова ера.
Но има някаква вратичка във формулировката на определението, "които класическите компютри практически не могат да решат" Всъщност това означава, че ако създадете квантов компютър от 50+ кубита и стартирате някаква квантова верига върху него, тогава, както обсъдихме по-горе, резултатът от тази схема не може да бъде емулиран на обикновен компютър. Това е класическият компютър няма да може да пресъздаде резултата от такава схема.
Дали такъв резултат представлява истинско квантово превъзходство или не е по-скоро философски въпрос. Но разберете какво направи Google и на какво се основава необходимо.
Декларация за квантово превъзходство на Google
54-кубитов процесор Sycamore
Така през октомври 2019 г. разработчиците на Google публикуваха статия в научното издание Nature “" Авторите обявиха постигането на квантово надмощие за първи път в историята с помощта на 54-кубитовия процесор Sycamore.
Статиите в Sycamore онлайн често се отнасят или до 54-кубитов процесор, или до 53-кубитов процесор. Истината е, че според , процесорът физически се състои от 54 кубита, но един от тях не работи и е изваден от експлоатация. Така в действителност имаме 53-кубитов процесор.
Точно там в мрежата материали по тази тема, чиято степен варира от до .
Екипът за квантови изчисления на IBM по-късно заяви това . Компанията твърди, че конвенционален компютър ще се справи с тази задача в най-лошия случай за 2,5 дни, а полученият отговор ще бъде по-точен от този на квантов компютър. Това заключение е направено въз основа на резултатите от теоретичен анализ на няколко метода за оптимизация.
И разбира се, в неговия Не можех да пренебрегна това твърдение. Неговата заедно с всички връзки и както обикновено, те си струва да отделите времето си. На главината този ЧЗВ и не забравяйте да прочетете коментарите, има връзки към предварителни документи, които са изтекли онлайн преди официалното съобщение.
Какво всъщност направи Google? За подробно разбиране прочетете Арънсън, но накратко тук:
Мога, разбира се, да ви кажа, но се чувствам доста глупаво. Изчислението е както следва: експериментаторът генерира произволна квантова верига C (т.е. произволна последователност от 1-кубитови и 2-кубитови порти между най-близките съседи, с дълбочина, например 20, действаща върху 2D мрежа от n = 50-60 кубита). След това експериментаторът изпраща C на квантовия компютър и го моли да приложи C към първоначално състояние 0, да измери резултата на база {0,1}, да изпрати обратно n-битова наблюдавана последователност (низ) и да повтори няколко хиляди или милиони пъти. Накрая, използвайки знанията си за C, експериментаторът извършва статистически тест, за да види дали резултатът съответства на очаквания изход от квантовия компютър.
Съвсем накратко:
- Произволна верига с дължина 20 от 53 кубита се създава с помощта на порти
- Веригата започва с начално състояние [0…0] за изпълнение
- Изходът на веригата е произволен битов низ (проба)
- Разпределението на резултата не е случайно (интерференция)
- Разпределението на получените проби се сравнява с очакваното
- Заключва Quantum Supremacy
Това означава, че Google внедри синтетичен проблем на 53-кубитов процесор и основава твърдението си за постигане на квантово превъзходство на факта, че е невъзможно да се емулира такъв процесор на стандартни системи за разумно време.
За разбирането - Този раздел по никакъв начин не намалява постиженията на Google, инженерите са наистина страхотни и въпросът дали това може да се счита за истинско квантово превъзходство или не, както споменахме по-рано, е по-скоро философски, отколкото инженерен. Но трябва да разберем, че след като сме постигнали такова изчислително превъзходство, не сме напреднали нито една стъпка към способността да изпълняваме алгоритъма на Шор върху 2048-битови числа.
Обобщение
Квантовите компютри и квантовите изчисления са много обещаваща, много млада и засега малко индустриално приложима област на информационните технологии.
Развитието на квантовите изчисления (някой ден) ще ни позволи да решаваме проблеми:
- Моделиране на сложни физически системи на квантово ниво
- Неразрешим на обикновен компютър поради изчислителна сложност
Основните проблеми при създаването и работата на квантовите компютри:
- Декохерентност
- Грешки (декохерентност и гейт)
- Архитектура на процесора (напълно свързани qubit вериги)
Текущо състояние на нещата:
- Всъщност – самото начало .
- Все още няма РЕАЛНА търговска експлоатация (и не е ясно кога ще има)
Какво може да помогне:
- Някакво физическо откритие, което намалява разходите за окабеляване и работа с процесори
- Откриване на нещо, което ще увеличи времето за декохерентност с порядък и/или ще намали грешките
Според мен (чисто лично мнение), В настоящата научна парадигма на познанието няма да постигнем значителен успех в развитието на квантовите технологии, тук се нуждаем от качествен пробив в някаква област на фундаменталната или приложна наука, който да даде тласък на нови идеи и методи.
Междувременно трупаме опит в квантовото програмиране, събираме и създаваме квантови алгоритми, тестваме идеи и т.н., и т.н. Чакаме пробив.
Заключение
В тази статия минахме през основните етапи в развитието на квантовите изчисления и квантовите компютри, разгледахме принципа на тяхната работа, разгледахме основните проблеми, пред които са изправени инженерите при разработването и експлоатацията на квантовите процесори, а също така разгледахме какво представлява мултикубитът D-компютрите всъщност са. Скорошното съобщение на Wave и Google за постигане на квантово надмощие.
Зад кулисите остават въпроси за програмиране на квантови компютри (езици, подходи, методи и т.н.) и въпроси, свързани със специфичната физическа реализация на процесорите, как кубитите се контролират, свързват, четат и т.н. Може би това ще бъде темата на следващата статия или статии.
Благодаря ви за вниманието, надявам се тази статия да бъде полезна за някого.
(C)
Признания
за корекция и коментари на изходния текст, както и на статията
за богати на информация коментари по , а и не само на нея, което до голяма степен ми помогна да разгадая този пъзел.
До всички автори на статии и публикации, чиито материали са използвани при написването на тази статия.
Списък с ресурси
Актуални статии от [The National Academies Press]
Статии от Habr (в произволен ред)
Неподредени (но не по-малко интересни) статии от Интернет
Курсове и лекции
Източник: www.habr.com