Квантни рачунари и квантно рачунарство - ново , који је додат у наш информациони простор заједно са , и други високотехнолошки појмови. У исто време, никада нисам успео да пронађем материјал на интернету који би сложио слагалицу у мојој глави тзв "како раде квантни рачунари". Да, има много одличних радова, укључујући и на Хабру (види. ), коментари на које су, како то обично бива, још информативнији и кориснији, али се слика у мојој глави, како кажу, није слагала.
А недавно су ми колеге пришле и питале: „Да ли разумете како функционише квантни рачунар? Можете ли нам рећи?" А онда сам схватио да нисам једини који има проблем да саставим кохерентну слику у својој глави.
В результате была сделана попытка скомпилировать информацию о квантовых компьютерах в непротиворечивую логическую схему, в которой бы на основни ниво, без дубоког урањања у математику и структуру квантног света, објашњено је шта је квантни рачунар, на којим принципима функционише и са каквим се проблемима суочавају научници при стварању и руковању њиме.
Преглед садржаја
Одрицање од одговорности
Аутор није стручњак за квантно рачунање, и Циљна публика чланка су исти ИТ људи, а не квантни стручњаци, који такође желе да саставе слику у својим главама под називом „Како функционишу квантни рачунари“. Због тога су многи концепти у чланку намерно поједностављени да би се боље разумеле квантне технологије на „основном“ нивоу, али без .
Чланак на неким местима користи материјале из других извора, . Где год је то могуће, убацују се директне везе и индикације на оригинални текст, табелу или слику. Ако сам негде заборавио (или некога) напиши и исправићу.
Увод
У овом поглављу ћемо укратко погледати како је почела квантна ера, шта је био мотивациони разлог за идеју о квантном рачунару, ко су (које земље и корпорације) тренутно водећи играчи у овој области, а такође ћемо укратко говорити о главним правцима развоја квантног рачунарства.
Како је све почело
Почетном тачком квантне ере сматра се 1900. година, када је М. Планцк први пут изнео та енергија се емитује и апсорбује не непрекидно, већ у одвојеним квантима (порцијама). Идеју су преузели и развили многи истакнути научници тог времена - Бор, Ајнштајн, Хајзенберг, Шредингер, што је на крају довело до стварања и развоја такве науке као што је . На интернету постоји много добрих материјала о формирању квантне физике као науке, у овом чланку се нећемо детаљније задржавати на томе, али је било потребно назначити датум када смо ушли у нову квантну еру.
Квантна физика је у наш свакодневни живот донела многе изуме и технологије без којих је сада тешко замислити свет око нас. На пример, ласер, који се сада користи свуда, од кућних апарата (ласерски нивои итд.) до високотехнолошких система (ласери за корекцију вида, здраво ). Логично би било претпоставити да ће пре или касније неко доћи на идеју зашто не користити квантне системе за рачунарство. А онда се то догодило 1980. године.
Википедија указује да је прву идеју о квантном рачунарству изнео 1980. наш научник Јуриј Манин. Али о томе су заиста почели да говоре тек 1981. када је познати Р. Фејнман , приметио је да је немогуће симулирати еволуцију квантног система на класичном рачунару на ефикасан начин. Предложио је елементарни модел , који ће моћи да спроведе такво моделовање.
Има , у чему разматра се академски и детаљније, али ћемо укратко прећи:
Главне прекретнице у историји стварања квантних рачунара:
- [1994]. П. Схоре. Дизајнирао
- [1998]. Цреатед
- [2001]. ИБМ је увео извршење за проширење броја 15
- [КСНУМКС-КСНУМКС]. креира и развија рачунар са 128-2000 кубита
- [2012]. Имплементирано на Универзитету Калифорније
- [2016]. Гоогле на рачунару од 9 кубита
- [КСНУМКС]. (три атома)
- [КСНУМКС]. . 20-кубитни рачунар у облаку
- [КСНУМКС]. . 53 кубит рачунар. ?
Као што видите, прошло је 17 година (од 1981. до 1998.) од тренутка настанка идеје до њене прве имплементације у рачунару са 2 кубита и 21 година (од 1998. до 2019.) док се број кубита није повећао на 53. Било је потребно 11 година (од 2001. до 2012.) да се резултат Шоровог алгоритма (погледаћемо га детаљније мало касније) са броја 15 на 21. Такође, пре само три године дошли смо до тога да имплементирајући оно о чему је Фејнман говорио, и научите да моделујете најједноставније физичке системе.
Развој квантног рачунарства је спор. Научници и инжењери су суочени са веома тешким задацима, квантна стања су веома кратког века и крхка, а да би их очували довољно дуго за обављање прорачуна, морају да граде саркофаге за десетине милиона долара, у којима се одржава температура. непосредно изнад апсолутне нуле, а који су максимално заштићени од спољашњих утицаја. Затим ћемо детаљније говорити о овим задацима и проблемима.
Водећи играчи
Слајдови за овај одељак су преузети из чланка , од истраживача Алексеј Федоров. Дозволите ми да вам дам директне цитате:
Све технолошки успешне земље тренутно активно развијају квантне технологије. У ово истраживање се улаже огроман новац, а стварају се и посебни програми подршке квантним технологијама.
У квантној трци учествују не само државе, већ и приватне компаније. Укупно, Гугл, ИБМ, Интел и Мајкрософт су недавно уложили око 0,5 милијарди долара у развој квантних рачунара и створили велике лабораторије и истраживачке центре.
Постоји много чланака на Хабреу и на Интернету, нпр. , и , у коме се детаљније испитује тренутно стање са развојем квантних технологија у различитим земљама. За нас је сада најважније да све водеће технолошки развијене земље и играчи улажу огромне количине новца у истраживања у овом правцу, што даје наду за излаз из садашњег технолошког ћорсокака.
Правци развоја
Тренутно (могу да грешим, исправите ме) главни напори (и мање-више значајни резултати) свих водећих играча су концентрисани у две области:
- Специјализовани квантни рачунари, који су усмерени на решавање једног специфичног проблема, на пример, проблема оптимизације. Пример производа су Д-Ваве квантни рачунари.
- Универзални квантни рачунари — који су способни да имплементирају произвољне квантне алгоритме (Схор, Гровер, итд.). Имплементације од ИБМ-а, Гоогле-а.
Други вектори развоја које нам даје квантна физика, као што су:
- као основа за
- и много више
Наравно, и он је на листи области за истраживање, али за сада се чини да нема више или мање значајних резултата.
Додатно можете читати , па, гуглај“", На пример, , и .
Основе. Квантни објекат и квантни системи
Најважнија ствар коју треба разумети из овог одељка је да
Квантни компјутер (за разлику од уобичајених) користи као носиоце информација квантни објекти, а да би се извршили прорачуни, квантни објекти морају бити повезани квантни систем.
Шта је квантни објекат?
Квантни објекат - објекат микросвета (квантног света) који показује квантна својства:
- Има дефинисано стање са два гранична нивоа
- Налази се у суперпозицији свог стања до тренутка мерења
- Преплиће се са другим објектима да би створио квантне системе
- Задовољава теорему без клонирања (стање објекта се не може копирати)
Разберем каждое свойство более подробно:
Има дефинисано стање са два гранична нивоа (крајње стање)
Класичан пример из стварног света је новчић. Има „бочно“ стање, које има два гранична нивоа – „главе“ и „репове“.
Налази се у суперпозицији свог стања до тренутка мерења
Бацили су новчић, он лети и врти се. Док се ротира, немогуће је рећи у ком се од граничних нивоа налази његово „бочно“ стање. Али чим га залупимо и погледамо резултат, суперпозиција држава се одмах сруши у једно од два гранична стања – „главе“ и „репове“. Шамарање новчића у нашем случају је мерење.
Преплиће се са другим објектима да би створио квантне системе
Тешко је са новчићем, али хајде да покушамо. Замислите да смо бацили три новчића тако да се ротирају држећи се један за другог, ово је жонглирање са новчићима. У сваком тренутку времена, не само да је свако од њих у суперпозицији стања, већ та стања међусобно утичу једно на друго (кованице се сударају).
Задовољава теорему без клонирања (стање објекта се не може копирати)
Док новчићи лете и окрећу се, не постоји начин да креирамо копију стања окретања било ког новчића, одвојено од система. Систем живи у себи и веома је љубоморан на објављивање било какве информације у спољни свет.
Још неколико речи о самом концепту "суперпозиције", у скоро свим чланцима суперпозиција се објашњава као „је у свим државама у исто време“, што је, наравно, тачно, али понекад непотребно збуњујуће. Суперпозиција стања се такође може замислити као чињеница да у сваком тренутку времена квантни објекат има постоје одређене вероватноће колапса у сваки од његових граничних нивоа, а укупно су ове вероватноће природно једнаке 1. Касније, када разматрамо кубит, детаљније ћемо се задржати на томе.
За новчиће, ово се може визуализовати - у зависности од почетне брзине, угла бацања, стања средине у којој новчић лети, у сваком тренутку је вероватноћа добијања „глава“ или „репа“ различита. И, као што је раније поменуто, стање таквог летећег новчића може се замислити као „да се истовремено налази у свим својим граничним стањима, али са различитим вероватноћама њихове примене“.
Било који објекат за који су испуњена наведена својства и који можемо да креирамо и контролишемо може се користити као носилац информација у квантном рачунару.
Мало даље ћемо говорити о тренутном стању ствари са физичком имплементацијом кубита као квантних објеката, ио томе шта научници сада користе у овом својству.
Дакле, треће својство каже да се квантни објекти могу заплести да би створили квантне системе. Шта је квантни систем?
Квантни систем — систем заплетених квантних објеката са следећим својствима:
- Квантни систем је у суперпозицији свих могућих стања објеката од којих се састоји
- Немогуће је знати стање система до тренутка мерења
- У тренутку мерења систем имплементира једну од могућих варијанти својих граничних стања
(и гледајући мало унапред)
Последица за квантне програме:
- Квантни програм има дато стање система на улазу, суперпозицију унутра, суперпозицију на излазу
- На излазу програма након мерења имамо вероватну имплементацију једног од могућих коначних стања система (плус могуће грешке)
- Сваки квантни програм има архитектуру димњака (улаз -> излаз. Нема петљи, не можете видети стање система усред процеса.)
Поређење квантног рачунара и конвенционалног
Хајде сада да упоредимо конвенционални рачунар и квантни рачунар.
| обичан рачунар | Квантни компјутер | |
|
Логицс
|
КСНУМКС / КСНУМКС | `а|0> + б|1>, а^2+б^2=1` |
|
Пхисицс
|
Полупроводнички транзистор | Квантни објекат |
|
Носилац информација
|
Нивои напона | Поларизација, окретање,… |
|
Операције
|
НОТ, АНД, ОР, КСОР преко битова | Вентили: ЦНОТ, Адамард,… |
|
Однос
|
Полупроводнички чип | Забуна једни с другима |
|
Алгоритми
|
Стандардно (погледајте бич) | Посебне понуде (Схоре, Гровер) |
|
Принцип
|
Дигитално, детерминистичко | Аналогно, вероватно |
Логички ниво
У обичном рачунару ово је мало. Нама добро познат кроз и низ детерминистички бит. Може да има вредности од 0 или 1. Добро се носи са улогом логичка јединица за обичан рачунар, али је потпуно неприкладан за описивање стања квантни објекат, који се, као што смо већ рекли, у дивљини налази усуперпозиције њихових граничних стања.
Ово су они смислили . У својим граничним стањима остварује стања слична 0 и 1 , а у суперпозицији представља расподела вероватноће преко њених граничних стања |0> и |1>:
a|0> + b|1>, такое, что a^2+b^2=1а и б представљају , а квадрати њихових модула су стварне вероватноће добијања управо таквих вредности граничних стања |0> и |1>, ако сада срушите кубит мерењем.
Физички слој
На садашњем технолошком нивоу развоја, физичка имплементација бита за конвенционални рачунар је полупроводнички транзистор, за квант, као што смо већ рекли, било ког квантног објекта. У следећем одељку ћемо говорити о томе шта се тренутно користи као физички медиј за кубите.
Средство за складиштење
За обичан рачунар ово је електрична енергија - нивои напона, присуство или одсуство струје и сл., за квантне - исто стање квантног објекта (правац поларизације, спин, итд.), који може бити у стању суперпозиције.
Операције
За имплементацију логичких кола на обичном рачунару користимо добро познате , за операције над кубитима је било потребно осмислити потпуно другачији систем операција, тзв . Гејтови могу бити једнокубитни или двокубитни, у зависности од тога колико се кубита конвертује.
Примери квантних капија:
Постоји концепт универзални сет вентила, који су довољни за обављање било каквог квантног прорачуна. На пример, универзални сет укључује Адамардову капију, капију фазног померања, ЦНОТ капију и π⁄8 капију. Уз њихову помоћ, можете извршити било који квантни прорачун на произвољном скупу кубита.
У овом чланку нећемо се детаљно задржавати на систему квантних капија; можете прочитати више о њима и логичким операцијама на кубитима, на пример, . Главна ствар коју треба запамтити:
- Операције на квантним објектима захтевају креирање нових логичких оператора (квантних капија)
- Квантне капије долазе у једнокубитним и двокубитним типовима.
- Постоје универзални сетови капија који се могу користити за извођење било ког квантног прорачуна
Однос
Један транзистор нам је потпуно бескористан; да бисмо извршили прорачуне потребно је да повежемо много транзистора један са другим, односно да од милиона транзистора направимо полупроводнички чип на коме ћемо градити логичка кола, и, на крају, добити модеран процесор у његовом класичном облику.
Један кубит нам је такође потпуно бескористан (па, ако само у академском смислу),
за извођење прорачуна потребан нам је систем кубита (квантних објеката)
који, као што смо већ рекли, настаје преплитањем кубита један са другим тако да се промене у њиховим стањима дешавају на координисан начин.
Алгоритми
Стандардни алгоритми које је човечанство акумулирало до данас потпуно су неприкладни за имплементацију на квантном рачунару. Да, генерално нема потребе. Квантни рачунари засновани на логици капије преко кубита захтевају креирање потпуно различитих алгоритама, квантних алгоритама. Од најпознатијих квантних алгоритама, могу се разликовати три:
- (факторизација)
- (брза претрага у неуређеној бази података)
- (одговор на питање, константна или уравнотежена функција)
Принцип
А најважнија разлика је принцип рада. За стандардни рачунар ово је дигитални, строго детерминистички принцип, на основу чињенице да ако поставимо неко почетно стање система и прођемо га кроз дати алгоритам, онда ће резултат прорачуна бити исти, без обзира колико пута извршимо овај прорачун. Заправо, овакво понашање је управо оно што очекујемо од рачунара.
Квантни рачунар ради аналогни, пробабилистички принцип. Резултат датог алгоритма у датом почетном стању је узорак из дистрибуције вероватноће коначне имплементације алгоритма плус могуће грешке.
Оваква вероватноћа природа квантног рачунарства је последица саме вероватноће суштине квантног света. "Бог се не игра коцкицама са универзумом.", рекао је стари Ајнштајн, али сви досадашњи експерименти и запажања (у садашњој научној парадигми) потврђују супротно.
Физичке имплементације кубита
Као што смо већ рекли, кубит се може представити квантним објектом, односно физичким објектом који имплементира квантна својства описана горе. То јест, грубо говорећи, сваки физички објекат у коме постоје два стања и ова два стања су у стању суперпозиције може се користити за изградњу квантног рачунара.
„Ако можемо да ставимо атом на два различита нивоа и да их контролишемо, онда имате кубит. Ако ово можемо да урадимо са јоном, то је кубит. Исто је и са струјом. Ако га покренемо у смеру казаљке на сату и супротно од казаљке на сату у исто време, имате кубит."
Ту је к , у којем се детаљније разматра тренутна разноликост физичких имплементација кубита, једноставно ћемо навести најпознатије и најчешће:
- и многе друге егзотичне идеје (ањони, итд.)
Од све ове разноликости, најразвијенији је први метод добијања кубита, заснован на . , , а други водећи играчи га користе за изградњу својих система.
Па, прочитајте више могуће кубита из .
Основе. Како функционише квантни рачунар
Материјали за овај одељак (задатак и слике) преузети су из чланка .
Дакле, замислите да имамо следећи задатак:
Постоји група од три особе: (А)ндреј, (Б)олођа и (Ц)ережа. Постоје два таксија (0 и 1).
Такође је познато да:
- (А)ндреи, (Б)олодиа су пријатељи
- (А)ндреј, (Ц)ережа су непријатељи
- (Б)олођа и (Ц)ережа су непријатељи
Задатак: Поставите људе у таксије тако да Макс (пријатељи) и Мин (непријатељи)
Оцена: Л = (број пријатеља) - (број непријатеља) за сваку опцију смештаја
ВАЖНО: Под претпоставком да не постоје хеуристика, не постоји ни оптимално решење. У овом случају, проблем се може решити само потпуним претраживањем опција.
Решење на обичном рачунару
Како решити овај проблем на обичном (супер) рачунару (или кластеру) - то је јасно морате проћи кроз све могуће опције. Ако имамо вишепроцесорски систем, онда можемо паралелизирати израчунавање рјешења на неколико процесора и затим прикупити резултате.
Имамо 2 могуће опције смештаја (такси 0 и такси 1) и 3 особе. Простор за решење 2^3 = 8. Можете чак и да прођете кроз 8 опција користећи калкулатор, то није проблем. Сада да закомпликујемо проблем - имамо 20 људи и два аутобуса, простор за решење 2^20 = 1. Ни ништа компликовано. Хајде да повећамо број људи за 2.5 пута - узми 50 људи и два воза, простор за решење је сада 2^50 = 1.12 к 10^15. Обичан (супер) рачунар већ почиње да има озбиљне проблеме. Хајде да повећамо број људи за 2 пута, 100 људи ће нам већ дати 1.2 к 10^30 могуће опције.
То је то, овај задатак се не може израчунати за разумно време.
Повезивање суперкомпјутера
Најмоћнији рачунар тренутно је број 1 Она , продуктивност 122 . Претпоставимо да нам је потребно 100 операција да израчунамо једну опцију, а затим да решимо проблем за 100 људи биће нам потребно:
(1.2 к 10^30 100) / 122×10^15 / (606024365) = 3 к 10^37 година.
Као што видимо како се димензија почетних података повећава, простор решења расте према закону степена, у општем случају, за Н битова имамо 2^Н могућих опција решења, што нам за релативно мало Н (100) даје непрорачунат (на тренутном технолошком нивоу) простор решења.
Да ли постоје алтернативе? Као што сте можда претпоставили, да, постоји.
Али пре него што уђемо у то како и зашто квантни рачунари могу ефикасно да решавају проблеме попут ових, хајде да одвојимо тренутак да поновимо шта су они. расподела. Не брините, ово је прегледни чланак, овде неће бити тешке математике, задовољићемо се класичним примером са кесом и лоптом.
Совсем немного комбинаторики, теории вероятностей и странного экспериментатора
Узмимо торбу и ставимо је у њу 1000 белих и 1000 црних лоптица. Спровешћемо експеримент - извадимо лопту, запишемо боју, вратимо лоптицу у кесу и мешамо лоптице у кеси.
Експеримент је изведен 10 пута, извукао 10 црних лоптица. Можда? Прилично. Да ли нам овај узорак даје разумну представу о правој дистрибуцији у торби? Очигледно не. Шта треба да се уради – тачно, стрпоновите експеримент милион пута и израчунајте фреквенције црних и белих куглица. Добијамо нпр 49.95% црне и 50.05% беле. У овом случају, структура дистрибуције из које узоркујемо (вадимо једну куглицу) је већ мање-више јасна.
Главна ствар је да се то разуме сам експеримент има вероватносну природу, са једним узорком (лоптом) нећемо знати праву структуру дистрибуције, треба да поновимо експеримент много пута и просечне резултате.
Хајде да га додамо у нашу торбу 10 црвених и 10 зелених лоптица (грешке). Поновимо експеримент 10 пута. ИНизвукао 5 црвених и 5 зелених. Можда? Да. Можемо рећи нешто о правој дистрибуцији - Не. Шта треба да се уради - добро, разумете.
Да би се стекло разумевање структуре дистрибуције вероватноће, потребно је више пута узорковати појединачне исходе из ове дистрибуције и усредсредити резултате.
Повезивање теорије са праксом
Сада уместо црно-белих лопти, узмимо куглице за билијар и ставимо их у кесу 1000 лоптица са бројем 2, 1000 са бројем 7 и 10 лоптица са другим бројевима. Замислимо експериментатора који је обучен у најједноставније радње (вади лопту, записује број, враћа лоптицу у кесу, меша лоптице у кеси) и то ради за 150 микросекунди. Па такав експериментатор на брзини (не реклама за дрогу!!!). Тада ће за 150 секунди моћи да изведе наш експеримент милион пута и дајте нам резултате усредњавања.
Посјели су експериментатора, дали му торбу, окренули се, чекали 150 секунди и добили:
број 2 - 49.5%, број 7 - 49.5%, преостали бројеви укупно - 1%.
Да то је тачно, наша торба је квантни компјутер са алгоритмом који решава наш проблем, а лоптице су могућа решења. Пошто постоје два тачна решења, онда квантни компјутер ће нам дати било које од ових могућих решења са једнаком вероватноћом и грешкама од 0.5% (10/2000), о чему ћемо касније.
Да бисте добили резултат квантног рачунара, потребно је да покренете квантни алгоритам више пута на истом скупу улазних података и добијете просечни резултат.
Скалабилност квантног рачунара
Сада замислите то за задатак који укључује 100 људи (простор за решење 2^100 памтимо ово), такође постоје само две исправне одлуке. Затим, ако узмемо 100 кубита и напишемо алгоритам који израчунава нашу циљну функцију (Л, види горе) преко ових кубита, онда ћемо добити врећу у којој ће бити 1000 куглица са бројем првог тачног одговора, 1000 са број другог тачног одговора и 10 лоптица са другим бројевима. И за истих 150 секунди наш експериментатор ће нам дати процену дистрибуције вероватноће тачних одговора.
Време извршења квантног алгоритма (уз неке претпоставке) може се сматрати константним О(1) у односу на димензију простора решења (2^Н).
А ово је управо својство квантног компјутера - константност времена извршавања у односу на све већи закон степена сложеност простора решења је кључна.
Кубит и паралелни светови
Како се ово дешава? Шта омогућава квантном рачунару да изводи прорачуне тако брзо? Све је у квантној природи кубита.
Видите, рекли смо да је кубит као квантни објекат остварује једно од своја два стања када се посматра, али у „дивљој природи“ је у суперпозиције држава, односно налази се у оба своја гранична стања истовремено (са извесном вероватноћом).
Узми (А)ндреиа и замислите његово стање (у ком возилу је - 0 или 1) као кубит. Тада имамо (у квантном простору) два паралелна света, у једном (АЛИ) седи у таксију 0, у другом свету - у таксију 1. У два таксија у исто време, али са извесном вероватноћом да се нађе у сваком од њих током посматрања.
Узми (Б) млад и замислимо његово стање као кубит. Настају још два паралелна света. Али за сада ови парови светова (АЛИ) и (АТ) не комуницирајте уопште. Шта треба учинити да се створи повезан систем? Тако је, требају нам ови кубити везати (збунити). Узимамо и збуњујемо (А) са (Б) — добијамо квантни систем од два кубита (А, Б), реализујући у себи четири међузависне паралелни светови. Додати (С)ергеи и добијамо систем од три кубита (АБЦ), спровођење осам међузависне паралелни светови.
Суштина квантног рачунарства (имплементација ланца квантних капија преко система повезаних кубита) је чињеница да се израчунавање одвија у свим паралелним световима истовремено.
И није важно колико их имамо, 2^3 или 2^100, квантни алгоритам ће се извршавати у коначном времену у свим овим паралелним световима и даће нам резултат, који је узорак из дистрибуције вероватноће одговора алгоритма.
За боље разумевање, то се може замислити квантовый компьютер на квантовом уровне запускает 2^N параллельных процессов решения, од којих сваки ради на једној могућој опцији, затим прикупља резултате рада - и даје нам одговор у виду суперпозиције решења (дистрибуција вероватноће одговора), из које узоркујемо по један сваки пут (за сваки експеримент).
Запамтите време потребно нашем експериментатору (150 µс) да спроведемо експеримент, ово ће нам бити од користи мало даље, када говоримо о главним проблемима квантних рачунара и времену декохеренције.
Квантни алгоритми
Као што је већ поменуто, конвенционални алгоритми засновани на бинарној логици нису применљиви на квантни рачунар који користи квантну логику (квантне капије). За њега је било неопходно осмислити нове које у потпуности искоришћавају потенцијал својствен квантној природи рачунарства.
Најпознатији алгоритми данас су:
В отличие от классических, квантовые компьютеры не универсальны.
До сада је пронађен само мали број квантних алгоритама.
захвалити за везу до , место где је, према речима аутора (), прикупљени су и настављају да се окупљају најбољи представници квантно-алгоритамског света.
У овом чланку нећемо детаљно анализирати квантне алгоритме; на Интернету постоји много одличних материјала за било који ниво сложености, али ипак морамо укратко да пређемо на три најпознатија.
Шоров алгоритам.
Најпознатији квантни алгоритам је (измислио је енглески математичар 1994 ), који има за циљ решавање проблема разлагања бројева у просте чиниоце (проблем факторизације, дискретни логаритам).
Управо овај алгоритам се наводи као пример када пишу да ће вам ускоро бити хаковани банкарски системи и лозинке. С обзиром да је дужина кључева који се данас користе није мања од 2048 бита, време за ограничење још није дошло.
До сада више него скроман. Најбољи резултати факторизације са Шоровим алгоритмом – бројеви и , што је много мање од 2048 бита. За преостале резултате из табеле, другачије прорачуна, али чак и најбољи резултат према овом алгоритму (291311) је веома далеко од стварне примене.
Можете прочитати више о Шоровом алгоритму, на пример,. О практичној примени - .
Један од сложеност и потребна снага за факторисање 2048-битног броја је рачунар са . Спавамо мирно.
Гроверов алгоритам
- решавање задатка набрајања, односно налажење решења једначине F(X) = 1, где је Ф из n Променљиве. Предложио га је амерички математичар в .
Гроверов алгоритам се може користити за проналажење и бројевне серије. Поред тога, може се користити за решавање проблема кроз исцрпну претрагу међу многим могућим решењима. Ово може довести до значајног повећања брзине у поређењу са класичним алгоритмима, иако без обезбеђивања "" генерално.
Можете прочитати вишеИли . Још Постоји добро објашњење алгоритма на примеру кутија и лопте, али, нажалост, из разлога који су ван било чије контроле, овај сајт ми се не отвара из Русије. Ако имате је такође блокиран, па ево кратког резимеа:
Гроверов алгоритам. Замислите да имате Н комада нумерисаних затворених кутија. Све су празне осим једне, која садржи лопту. Ваш задатак: сазнајте број кутије у којој се налази лопта (овај непознати број се често означава словом в).
Како решити овај проблем? Најглупљи начин је да наизменично отварате кутије и пре или касније ћете наићи на кутију са лоптом. У просеку, колико кутија треба да се провери пре него што се пронађе кутија са лоптом? У просеку, потребно је да отворите око половине Н/2 кутија. Овде је најважније да ако повећамо број кутија за 100 пута, онда ће се просечан број кутија које треба отворити пре него што се пронађе кутија са лоптом такође повећати за истих 100 пута.
Теперь сделаем ещё одно уточнение. Пусть мы не сами открываем коробки руками и проверяем наличие мячика в каждой, а имеется некий посредник, назовем его Оракул (Oracle). Мы говорим Оракулу — «проверь коробку номер 732», и Оракул честно проверяет и отвечает «в коробке номер 732 мячика нет». Теперь вместо слов о том, сколько коробок нам нужно в среднем открыть, мы говорим «сколько раз в среднем мы должны обратиться к Оракулу для того, чтобы найти номер коробки с мячиком»
Испоставило се да ако овај проблем са кутијама, лоптом и Орацлеом преведемо на квантни језик, добијамо изванредан резултат: да бисмо пронашли број кутије са лоптом међу Н кутија, морамо да пореметимо Орацле само око СКРТ (Н) пута!
То јест, сложеност задатка претраживања помоћу Гроверовог алгоритма је смањена за квадратни корен пута.
Деутсцх-Јози алгоритам
Деутсцх-Јозса алгоритам (такође познат као Деутсцх-Јозса алгоритам) - [квантни алгоритам](%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC), предложенный и в , и постао је један од првих примера алгоритама дизајнираних да се на њима извршавају . _
Проблем Деутсцх-Јозсија је да се утврди да ли је функција неколико бинарних променљивих Ф(к1, к2, ... кн) константна (за било који аргумент узима вредност 0 или 1) или уравнотежена (за половину домена која је потребна вредност 0, за другу половину 1). У овом случају се сматра да је а приори познато да је функција или константна или уравнотежена.
Још увек можете читати . Једноставније објашњење:
Алгоритам Деутсцх (Деутсцх-Јозси) заснован је на грубој сили, али омогућава да се то уради брже него иначе. Замислите да се на столу налази новчић и треба да сазнате да ли је лажан или не. Да бисте то урадили, морате двапут погледати новчић и одредити: „главе“ и „репови“ су стварне, две „главе“, два „репа“ су лажне. Дакле, ако користите Деутсцх квантни алгоритам, онда се ово одређивање може извршити једним погледом - мерењем.
Проблеми квантних рачунара
Приликом пројектовања и рада квантних рачунара, научници и инжењери се суочавају са огромним бројем проблема, који су до данас решени са различитим степеном успеха. Према () може се идентификовати следећи низ проблема:
- Осетљивост на околину и интеракција са околином
- Акумулација грешака током прорачуна
- Потешкоће са почетним иницијализацијом стања кубита
- Потешкоће у креирању мултикубит система
Топло препоручујем да прочитате чланак "“, посебно коментари на њега.
Хајде да организујемо све главне проблеме у три велике групе и детаљније погледамо сваки од њих:
Декохеренција
.
Квантовое состояние веома крхка стваркубити у заплетеном стању су изузетно нестабилни, сваки спољни утицај може (и заиста) уништи ову везу. Промена температуре за најмањи део степена, притисак, случајни фотон који лети у близини - све то дестабилизује наш систем.
За решавање овог проблема уграђују се нискотемпературни саркофази у којима је температура (-273.14 степени Целзијуса) нешто изнад апсолутне нуле, уз максималну изолацију унутрашње коморе са процесором од свих (могућих) утицаја спољашње средине.
Максимални животни век квантног система од неколико заплетених кубита, током којег он задржава своја квантна својства и може се користити за прорачуне, назива се време декохеренције.
Тренутно је време декохеренције у најбољим квантним решењима реда десетине и стотине микросекунди.
Постоји диван где можете погледати свих створених квантних система. Овај чланак укључује само два врхунска процесора као примере - из ИБМ-а И од . Као што видимо, време декохеренције (Т2) не прелази 200 μс.
Нисам нашао тачне податке о платану, али у већини дата су два броја - 1 милион прорачуна за 200 секунди, другде - за 130 секунди без губитка контролних сигнала итд.. У сваком случају, ово нам даје време декохеренције је око 150 μс. Сетите се наших експериментатор са торбом? Па, ево га.
| Име рачунара | Н Кубитс | Макс упарен | Т2 (µс) |
| ИБМ К Систем Оне | 20 | 6 | 70 |
| Гоогле Сицаморе | 53 | 4 | ~ 150-200 |
Чиме нам прети декохеренција?
Главни проблем је у томе што ће после 150 μс наш рачунарски систем од Н замршених кубита почети да емитује вероватни бели шум уместо вероватноће расподеле тачних решења.
То јест, потребно нам је:
- Иницијализујте кубит систем
- Извршите прорачун (ланац операција капије)
- Прочитајте резултат
И урадите све ово за 150 микросекунди. Нисам имао времена - резултат се претворио у бундеву.
Али то није све…
Грешке
Као што смо рекли, квантни процеси и квантно рачунање су по природи вероватноће, не можемо бити 100% сигурни ни у шта, али само са извесном вероватноћом. Ситуацију додатно отежава чињеница да квантно рачунарство је склоно грешкама. Главне врсте грешака у квантном рачунарству су:
- Грешке декохеренције су узроковане сложеношћу система и интеракцијом са спољашњим окружењем
- Рачунске грешке гејта (због квантне природе израчунавања)
- Грешке у читању коначног стања (резултат)
Грешке повезане са декохеренцијом, појављују се чим уплетемо своје кубите и почнемо да радимо прорачуне. Што више кубита уплетемо, систем је сложенији, и то је лакше уништити. Нискотемпературни саркофази, заштићене коморе, сви ови технолошки трикови су управо усмерени на смањење броја грешака и продужење времена декохеренције.
Рачунске грешке капије - свака операција (гејт) на кубитима може, са извесном вероватноћом, да се заврши грешком, а за имплементацију алгоритма потребно је да извршимо стотине капија, па замислите шта добијамо на крају извршавања нашег алгоритма. Класичан одговор на питање је „Колика је вероватноћа да ћете срести диносауруса у лифту?“ - 50к50, или ћеш се срести или не.
Проблем је додатно отежан чињеницом да стандардне методе исправљања грешака (дуплирање прорачуна и усредњавање) не функционишу у квантном свету због теореме без клонирања. За у квантном рачунарству је морало бити измишљено . Грубо говорећи, узимамо Н обичних кубита и правимо 1 од њих логички кубит са мањом стопом грешке.
Али овде се јавља још један проблем - укупан број кубита. Гледајте, рецимо да имамо процесор са 100 кубита, од којих се 80 кубита користи за исправљање грешака, онда нам је остало само 20 за прорачуне.
Грешке у читању коначног резултата — као што се сећамо, резултат квантних прорачуна нам је представљен у облику расподела вероватноће одговора. Али читање коначног стања такође може пропасти уз грешку.
На истој Постоје упоредне табеле процесора по нивоима грешке. За поређење, узмимо исте процесоре као у претходном примеру - ИБМ и :
| рачунар | 1-Кубит Гате Фиделити | 2-Кубит Гате Фиделити | Реадоут Фиделити |
| ИБМ К Систем Оне | 100% | 100% | - |
| Гоогле Сицаморе | 100% | 100% | 100% |
Овде је мера сличности два квантна стања. Величина грешке се може грубо изразити као 1-Фиделити. Као што видимо, грешке на 2-кубитним гејтовима и грешке очитавања су главна препрека извршавању сложених и дугих алгоритама на постојећим квантним рачунарима.
Још увек можете читати године од да реши проблем исправљања грешака.
Архитектура процесора
У теорији ми градимо и послујемо кола од десетина заплетених кубита, у стварности је све компликованије. Сви постојећи квантни чипови (процесори) су изграђени тако да обезбеђују безболност преплитање једног кубита само са суседима, којих нема више од шест.
Ако треба да запетљамо 1. кубит, рецимо, са 12., онда ћемо морати изградити ланац додатних квантних операција, укључују додатне кубите, итд., што повећава укупан ниво грешке. Да, и не заборавите на време декохеренције, можда ће се време завршити и цео коло ће се претворити у леп генератор беле буке.
Такође не заборавите то Архитектура свих квантних процесора је различита, а програм написан у емулатору у режиму повезивања „све на све“ ће морати да се „прекомпајлира“ у архитектуру одређеног чипа. Постоје чак да изврши ову операцију.
Максимална повезаност и максималан број кубита за исте врхунске чипове:
| Име рачунара | Н Кубитс | Макс упарен | Т2 (µс) |
| ИБМ К Систем Оне | 20 | 6 | 70 |
| Гоогле Сицаморе | 53 | 4 | ~ 150-200 |
И, за поређење, табела са подацима из претходне генерације процесора. Упоредите број кубита, време декохеренције и стопу грешке са оним што сада имамо са новом генерацијом. Ипак, напредак је спор, али се креће.
Дакле:
- Тренутно не постоје потпуно повезане архитектуре са > 6 кубита
- Да би се кубит 0 с уплео на прави процесор, на пример, кубит 15 може захтевати неколико десетина додатних операција
- Више операција -> више грешака -> јачи утицај декохеренције
Резултати
Декохеренција је прокрустово лежиште модерног квантног рачунарства. Морамо све уклопити у 150 μс:
- Иницијализација почетног стања кубита
- Рачунање проблема помоћу квантних капија
- Исправите грешке да бисте добили значајне резултате
- Прочитајте резултат
Међутим, за сада су резултати разочаравајући тврди да постиже време задржавања кохерентности од 0.5с на квантном рачунару заснованом на :
Ми меримо време кохерентности кубита веће од 0.5 с, а са магнетном заштитом очекујемо да ће се ово побољшати дуже од 1000 с
Такође можете прочитати о овој технологији или на пример .
Ситуацију додатно компликује чињеница да је при извођењу сложених прорачуна потребно користити квантна кола за корекцију грешака, што такође троши и време и доступне кубите.
И коначно, модерне архитектуре не дозвољавају примену шема заплетања бољих од 1 у 4 или 1 у 6 уз минималне трошкове.
Начини решавања проблема
За решавање наведених проблема тренутно се користе следећи приступи и методе:
- Коришћење криокомора са ниским температурама (10 мК (–273,14°Ц))
- Коришћење процесорских јединица које су максимално заштићене од спољашњих утицаја
- Коришћење квантних система за исправљање грешака (логички кубит)
- Коришћење оптимизатора приликом програмирања кола за одређени процесор
Такође се спроводе истраживања у циљу повећања времена декохеренције, тражења нових (и побољшања познатих) физичких имплементација квантних објеката, оптимизације кола корекције итд, итд. Има напретка (погледајте горе карактеристике ранијих и данашњих врхунских чипова), али до сада је спор, веома, веома спор.
Д-талас
Д-Ваве 2000К 2000-кубит рачунар. Извор:
Усред Гооглеове најаве о постизању квантне надмоћи користећи процесор од 53 кубита, и из компаније Д-Ваве, у којој је број кубита у хиљадама, донекле збуњује. Па, заиста, ако је 53 кубита било у стању да постигне квантну надмоћ, за шта је онда способан рачунар са 2048 кубита? Али није све тако добро...
Укратко (преузето са вики-ја):
Компјутери рад на принципу (), могу решити веома ограничену подкласу проблема оптимизације и нису погодни за имплементацију традиционалних квантних алгоритама и квантних капија.
За више детаља можете прочитати, нпр. , (пажљиво, можда се не отвара из Русије), или в од његовог . Иначе, топло препоручујем читање његовог блога уопште, тамо има доста доброг материјала
Генерално, од самог почетка најава, научна заједница је имала питања о Д-Ваве рачунарима. На пример, ИБМ је 2014. довео у питање чињеницу да је Д-Ваве Дошло је до тога да је 2015. Гугл заједно са НАСА-ом купио један од ових квантних компјутера и након истраживања , да да, рачунар ради и израчунава проблем брже од обичног. Више о Гугловој изјави можете прочитати и, на пример, .
Главна ствар је да Д-Ваве рачунари, са својим стотинама и хиљадама кубита, не могу да се користе за израчунавање и покретање квантних алгоритама. На њима, на пример, не можете покренути Шоров алгоритам. Све што могу да ураде је да користе одређене квантне механизме да реше одређени проблем оптимизације. Можемо сматрати да је Д-Ваве квантни АСИЦ за одређени задатак.
Мало о емулацији квантног рачунара
Квантно рачунарство се може емулирати на обичном рачунару. Заиста, :
- Стање кубита може бити комплексни број, који заузимају од 2к32 до 2к64 бита (8-16 бајтова) у зависности од архитектуре процесора
- Стање Н повезаних кубита може се представити као 2^Н комплексних бројева, тј. 2^(3+Н) за 32-битну архитектуру и 2^(4+Н) за 64-битну.
- Квантна операција на Н кубита може бити представљена матрицом 2^Н к 2^Н
Онда:
- За складиштење емулираних стања од 10 кубита потребно је 8 КБ
- За складиштење стања од 20 кубита потребно вам је 8 МБ
- Для хранения состояний 30 кубитов нужны 8 ГБ
- За складиштење стања од 40 кубита потребно је 8 терабајта
- За складиштење стања од 50 кубита потребно је 8 петабајта итд.
За поређење, () носи само 2.8 петабајта меморије.
— 49 кубит поставленный в прошлом году на крупнейшем китайском суперкомпьютере ()
Граница симулације квантног рачунара на класичним системима одређена је количином РАМ меморије потребне за чување стања кубита.
Такође препоручујем читање . Одатле:
По раду - за тачну емулацију 49-кубитног кола које се састоји од неких 39 "циклуса" (независних слојева капија) 2^63 комплексна множења - 4 Пфлопса суперкомпјутера за 4 сата
Емулација квантног рачунара од 50+ кубита на класичним системима сматра се немогућим у разумном времену. Ово је такође разлог зашто је Гоогле користио процесор од 53 кубита за свој експеримент квантне надмоћи.
Надмоћ у квантном рачунарству.
Википедија нам даје следећу дефиницију надмоћи квантног рачунарства:
Квантна надмоћ – способност уређаја за решавање проблема које класични рачунари практично не могу да реше.
У ствари, постизање квантне надмоћи значи да, на пример, факторизација великих бројева коришћењем Шоровог алгоритма може да се реши у одговарајућем времену, или да се сложени хемијски молекули могу емулирати на квантном нивоу и тако даље. Односно, наступила је нова ера.
Али постоји нека рупа у формулацији дефиниције, „које класични рачунари практично не могу да реше" У ствари, то значи да ако креирате квантни рачунар од 50+ кубита и покренете неко квантно коло на њему, онда, као што смо горе расправљали, резултат овог кола не може се емулирати на обичном рачунару. То је класични рачунар неће моћи да поново створи резултат таквог кола.
Да ли такав резултат представља стварну квантну надмоћ или не, пре је филозофско питање. Али схватите шта је Гоогле урадио и на чему се заснива неопходно.
Гоогле-ова изјава о квантној надмоћи
Сицаморе 54-кубит процесор
Тако су у октобру 2019. Гоогле програмери објавили чланак у научној публикацији Натуре “" Аутори су најавили постизање квантне надмоћи по први пут у историји користећи 54-кубит Сицаморе процесор.
Чланци на мрежи Сицаморе често се односе на процесор од 54 кубита или процесор од 53 кубита. Истина је да према , процесор се физички састоји од 54 кубита, али један од њих није у функцији и избачен је из употребе. Дакле, у стварности имамо процесор од 53 кубита.
На вебу управо тамо материјала на ову тему чији је степен варирао од до .
ИБМ-ов тим за квантно рачунарство је то касније изјавио . Компанија тврди да ће се конвенционални рачунар у најгорем случају носити са овим задатком за 2,5 дана, а резултат ће бити тачнији од квантног рачунара. Овај закључак је донесен на основу резултата теоријске анализе неколико метода оптимизације.
И наравно, у његовој Нисам могао да игноришем ову изјаву. Његово заједно са свим везама и као и обично, вреди потрошити своје време на њих. На чворишту ова ФАК, и обавезно прочитајте коментаре, постоје везе до прелиминарних докумената који су процурили на мрежи пре званичног саопштења.
Шта је Гоогле заправо урадио? За детаљније разумевање прочитајте Аронсона, али укратко овде:
Могу, наравно, да вам кажем, али осећам се прилично глупо. Прорачун је следећи: експериментатор генерише насумично квантно коло Ц (тј. насумични низ капија од 1 кубита и 2 кубита између најближих суседа, са дубином од, на пример, 20, који делује на 2Д мрежу од н = 50-60 кубита). Експериментатор затим шаље Ц квантном рачунару и тражи од њега да примени Ц на почетно стање 0, измери резултат на бази {0,1}, пошаље назад н-битну посматрану секвенцу (стринг) и понови неколико хиљаду или милионе пута. Коначно, користећи своје знање о Ц, експериментатор изводи статистички тест да види да ли се резултат поклапа са очекиваним излазом из квантног рачунара.
Врло кратко:
- Насумично коло дужине 20 од 53 кубита се креира помоћу капија
- Коло почиње са почетним стањем [0…0] за извршење
- Излаз кола је насумични низ битова (узорак)
- Расподела резултата није случајна (сметња)
- Расподела добијених узорака упоређује се са очекиваном
- Закључује квантну надмоћ
То јест, Гоогле је имплементирао синтетички проблем на процесор од 53 кубита и заснива своју тврдњу о постизању квантне надмоћи на чињеници да је немогуће емулирати такав процесор на стандардним системима у разумном времену.
За разумевање - Овај одељак ни на који начин не умањује Гоогле-ово достигнуће, инжењери су заиста сјајни, а питање да ли се то може сматрати стварном квантном супериорношћу или не, као што је раније поменуто, више је филозофско него инжењерско. Али морамо разумети да, пошто смо постигли такву супериорност у рачунању, нисмо напредовали ни корак ка могућности покретања Шоровог алгоритма на 2048-битним бројевима.
Резиме
Квантни рачунари и квантно рачунарство су веома перспективна, веома млада и до сада мало индустријски применљива област информационе технологије.
Развој квантног рачунарства ће нам (једног дана) омогућити да решимо проблеме:
- Моделирање сложених физичких система на квантном нивоу
- Нерешиво на обичном рачунару због рачунске сложености
Главни проблеми у стварању и раду квантних рачунара:
- Декохеренција
- Грешке (декохеренција и капија)
- Архитектура процесора (потпуно повезана кубит кола)
Тренутно стање ствари:
- У ствари – сам почетак .
- Још увек нема ПРАВЕ комерцијалне експлоатације (и није јасно када ће бити)
Шта може помоћи:
- Нека врста физичког открића које смањује трошкове ожичења и рада процесора
- Откривање нечега што ће повећати време декохеренције за ред величине и/или смањити број грешака
По мом мишљењу (чисто лично мишљење), У садашњој научној парадигми знања нећемо постићи значајније успехе у развоју квантних технологија, овде нам је потребан квалитативни продор у некој области фундаменталне или примењене науке, који ће дати подстицај новим идејама и методама.
У међувремену стичемо искуство у квантном програмирању, прикупљању и креирању квантних алгоритама, тестирању идеја итд, итд. Чекамо искорак.
Закључак
У овом чланку прошли смо кроз главне прекретнице у развоју квантног рачунарства и квантних рачунара, испитали принцип њиховог рада, испитали главне проблеме са којима се суочавају инжењери у развоју и раду квантних процесора, а такође смо погледали шта је мулти-кубит. Д-рачунари заправо јесу.. Ваве и Гоогле-ова недавна најава о постизању квантне надмоћи.
Иза кулиса су остала питања програмирања квантних рачунара (језици, приступи, методе итд.) и питања везана за специфичну физичку имплементацију процесора, како се управљају кубитима, повезују их, читају итд. Можда ће ово бити тема следећег чланка или чланака.
Хвала вам на пажњи, надам се да ће овај чланак некоме бити користан.
(Ц)
Захвалнице
за лектуру и коментаре на изворни текст, као и за чланак
за информативно богате коментаре на , и не само њој, што ми је у великој мери помогло да одгонетнем ову загонетку.
Свим ауторима чланака и публикација чији су материјали коришћени при писању овог чланка.
Списак ресурса
Актуелни чланци из [Тхе Натионал Ацадемиес Пресс]
Чланци са Хабра (насумичним редоследом)
Неразврстани (али не мање занимљиви) чланци са Интернета
Курсеви и предавања
Извор: ввв.хабр.цом