Գնահատել նախագիծը
← Բոլոր հրապարակումները

Քվանտային հաշվարկները զբաղված ծրագրավորողի համար. մաս 1

Քվանտային հաշվարկների կարճ ներածություն, որը դրանք համեմատում է GPU-ի և վեկտորիզացիայի նման հայտնի գաղափարների հետ՝ ցույց տալու համար, թե ինչ կարող և ինչ չի կարող անել քվանտային համակարգիչը և ինչպես կարելի է քվանտային տեխնոլոգիայով լուծել օպտիմալացման սեփական խնդիրները։

8 րոպե
Քվանտային հաշվարկներԶուգահեռ հաշվարկներՎեկտորիզացիաՀաշվողական բարդություն

Մոտիվացիա

Քվանտային համակարգիչները առաջարկում են զուգահեռության առանձնահատուկ տեսակ։ Դրա շնորհիվ քվանտային համակարգիչը պետք է կարողանա հաշվարկներ կատարել դասական մեքենայից ավելի արագ։ Սակայն դրանից օգտվելու համար խնդիրներին պետք է մոտենալ այլ կերպ՝ հատուկ դրա համար նախագծված ալգորիթմներով։

«Ավելի արագ» այստեղ նշանակում է, որ որոշ խնդիրներ իսկապես կարող են լուծվել ավելի լավ հաշվողական բարդությամբ։ Որոշ դեպքերում տարբերությունը կտրուկ է. խնդիրներ, որոնք դասական համակարգչի վրա պահանջում են էքսպոնենցիալ ժամանակ, քվանտայինի վրա կարող են լուծվել պոլինոմային ժամանակում։ (Հայտնի օրինակներ են Դոյչ-Յոզսայի ալգորիթմը և հայտնի Շորի ալգորիթմը։)

Սակայն սրանք հատուկ խնդիրներ են, որոնք պատահաբար առանձնապես լավ են համապատասխանում այս պլատֆորմին։ Որպես ծրագրավորող՝ ես ուզում եմ պարզել, կարելի՞ է այդ ձևով լուծել նաև ավելի ընդհանուր տեսակի խնդիրներ։

Այս կարճ շարքում ես ցույց կտամ, թե ինչպես սեփական խնդիրը տանել քվանտային համակարգչի վրա և կառուցել դրա լուծումը։

Պլան

Շարքը բաժանված է չորս մասի, որոնցից յուրաքանչյուրը քվանտային համակարգիչը քննում է փոքր-ինչ տարբեր տեսանկյունից.

  • Մաս 1. տալիս է քվանտային համակարգչի բարձր մակարդակի պատկերը՝ համեմատելով այն ավելի ծանոթ գաղափարների հետ, ինչպիսիք են GPU-ն և վեկտորիզացիան։
  • Մաս 2. ներկայացնում է քյուբիթները և այդ բարձր մակարդակի պատկերի հետևում կանգնած մյուս բաղադրիչները։
  • Մաս 3. ցույց է տալիս, թե իրականում ինչ տեսք ունի քվանտային համակարգչի ծրագրավորումը։
  • Մաս 4. քայլ առ քայլ անցնում է աշխատող կոդի օրինակի միջով։

Քվանտային համակարգիչը մի հայացքով

Օրինակ խնդիր

Քննարկումը կոնկրետ պահելու համար եկեք կենտրոնանանք խնդրի մեկ տեսակի վրա՝ դիսկրետ օպտիմալացման։ Մենք ունենք մուտքերի բազմություն և ուզում ենք գտնել այն մեկը, որը լավագույնս բավարարում է ինչ-որ չափանիշների (օրինակ՝ ճանապարհորդ վաճառականի խնդիրը, կարճ՝ TSP, որտեղ փնտրում ենք տրված գրաֆի բոլոր հանգույցներով ամենակարճ երթուղին)։ Ավելի ձևական ասած՝ մենք ունենք արժեքի ֆունկցիա և ուզում ենք գտնել նրա նվազագույնը։

Հաճախ սա կարելի է անել թվային մեթոդներով, բայց միայն եթե արժեքի ֆունկցիան բավարարում է որոշակի պահանջների։ Ընդհանուր դեպքում մենք, ըստ էության, պետք է հաշվենք և համեմատենք արդյունքները յուրաքանչյուր հնարավոր արգումենտի համար։

Նախքան առաջ գնալը՝ ուզում եմ ներմուծել երկու լրացուցիչ ենթադրություն.

  • Պարզության համար ենթադրում ենք, որ արժեքի ֆունկցիան և՛ ընդունում, և՛ վերադարձնում է մեկական ամբողջ թիվ տրված {0…N} միջակայքից։ Ավելի բարդ մուտքերով խնդիրների համար կարող ենք փորձել դրանք կոդավորել որպես թվեր (TSP-ի դեպքում, ասենք, գրաֆի յուրաքանչյուր երթուղուն տալով իր եզակի համարը)։

1

Մեկ արգումենտով արժեքի ֆունկցիա

  • Մենք օպտիմալացման խնդիրը կվերածենք որոշման խնդրի։ Ենթադրենք, մեզ խիստ անհրաժեշտ չէ ամենալավ արդյունքը, այլ միայն բավականաչափ լավը, այսինքն՝ այնպիսին, որը բավարարում է նախապես սահմանված չափանիշներին (TSP-ի դեպքում կարող է բավարար լինել տրված սահմանից կարճ ցանկացած երթուղի)։ Այդ դեպքում արժեքի ֆունկցիան կարելի է փոխարինել պրեդիկատով, որը լավ մուտքերի համար վերադարձնում է 1, իսկ մնացած բոլորի համար՝ 0։

2

Մեկ արգումենտով պրեդիկատ

Երկրորդ ենթադրության շնորհիվ մենք այլևս պետք չէ մուտքերի միջև արդյունքները համեմատել, ինչը օգտակար կլինի, երբ փորձենք հաշվարկը զուգահեռացնել։

Այժմ, բախտի դեպքում, ֆունկցիայի մեկ կանչը արդեն կարող է լավ արդյունք տալ։ Բայց եթե լավ արդյունքները հազվադեպ են, կանչերի սպասվող քանակը դեռ կմասշտաբավորվի արգումենտների ընդհանուր քանակի հետ։

Ֆունկցիան յուրաքանչյուր հնարավոր արգումենտի համար հաշվարկելը շուտով կարող է անիրագործելի դառնալ, և հենց այստեղ քվանտային համակարգիչները կարող են օգնել։

Ինչո՞ւ օգտագործել քվանտային համակարգիչ

Վերը նկարագրված օպտիմալացման խնդիրը մեզ կստիպի անցնել արժեքի ֆունկցիայի բոլոր հնարավոր արդյունքների միջով։ Դասական համակարգչի վրա այս խնդիրն ունի O(n) բարդություն, որտեղ n-ը հնարավոր արգումենտների ընդհանուր քանակն է։ Նշում. այստեղ մենք ֆունկցիան դիտարկում ենք որպես սև արկղ, և բարդությունը սահմանվում է որպես ֆունկցիայի կանչերի քանակին համաչափ։

Մաս 4-ում մենք այս օրինակ խնդիրը կլուծենք քվանտային համակարգչի վրա՝ քվանտային որոնման ալգորիթմով, որը լուծում գտնելու բարդությունը իջեցնում է O(√n)-ի։ Սա էքսպոնենցիալ արագացում չէ, բայց դեռ ուշագրավ է, և մոտեցումը բավական ընդհանուր է։

Ինչպե՞ս է դա հնարավոր։

Ուրեմն ի՞նչ է քվանտային համակարգիչը

Պարզ ասած՝ քվանտային համակարգիչը մեքենա է, որը հաշվարկներ է կատարում քվանտային էֆեկտների միջոցով։ Այս էֆեկտներն ունեն մի յուրահատուկ հատկություն. երբեմն նրանք իրենց պահում են այնպես, կարծես միաժամանակ շատ բան են անում։ Դուք կարող եք հիշել, օրինակ, թե ինչպես է էլեկտրոնը միաժամանակ մի քանի ճանապարհ ուսումնասիրում կրկնակի ճեղքի փորձում։ Այս հատկությունը խելացի օգտագործելը թույլ է տալիս քվանտային հաշվարկը կատարել զուգահեռ։

Որոշ առումներով սա նման է GPU-ի վրա հաշվարկներ կատարելուն։

GPU-ն որպես համապրոցեսոր

GPU-ն կարող է գործել որպես համապրոցեսոր հատկապես հաշվարկատար խնդիրների համար։ Օրինակ՝ Machine Learning pipeline-ները հաճախ հետևում են մի օրինակի, երբ հաշվարկի ամենածանր մասերը տեղափոխվում են GPU։

3

GPU-ն որպես համապրոցեսոր

Ավելի թեթև խնդիրները, ինչպիսիք են տվյալների պատրաստումը և հետմշակումը, սովորաբար կատարվում են GPU-ից դուրս։ Կարելի է պատկերացնել նման կառուցվածք, որտեղ որոշ հստակ սահմանված խնդիրներ հանձնվում են քվանտային համակարգչին, իսկ տվյալների պատրաստումը և հետմշակումը տեղի են ունենում դասական համակարգչի վրա։

Համեմատությունը սակայն ավելի հեռու է գնում. պարզվում է, որ քվանտային համակարգչի վրա հաշվարկը նման է վեկտորիզացիային։

Վեկտորիզացիան GPU-ի վրա

4

Զուգահեռ հաշվարկ վեկտորիզացիայով

Վեկտորիզացիան տեխնիկա է GPU-ն արդյունավետ օգտագործելու համար՝ հաշվարկները զուգահեռացնելու նպատակով։ Այն կիրառելու համար մեր ֆունկցիան սովորաբար պետք է արտահայտված լինի պարզ թվաբանական գործողություններով և պետք է խուսափի տարամիտող ճյուղավորումից։

Այդ դեպքում ֆունկցիային կարող ենք փոխանցել բոլոր արգումենտները պարունակող մեկ վեկտոր, և GPU-ն աշխատանքը զուգահեռացնում է։ Բնականաբար, զուգահեռ կատարվող գործողությունների քանակը սահմանափակվում է հասանելի միջուկների քանակով։

Իդեալականում, սակայն, ամբողջ հաշվարկը կարելի է արտահայտել որպես քայլերի շարք։ Յուրաքանչյուր քայլում մուտքային վեկտորի բոլոր տարրերը մշակվում են զուգահեռ, և յուրաքանչյուր քայլ տալիս է նոր վեկտոր։ Քանի որ յուրաքանչյուր տարր մշակվում է անկախ, ելքային վեկտորն ունի նույն երկարությունը։ (Ելքային վեկտորի յուրաքանչյուր տարր համապատասխանում է մուտքային վեկտորի մեկ տարրի։)

Քվանտային համակարգչի վրա հաշվարկը որոշ չափով այսպիսի տեսք ունի։

Վեկտորիզացիան քվանտային համակարգչի վրա

պատկեր6

Զուգահեռ հաշվարկ քվանտային համակարգչի վրա

Սա նույն պատկերն է, ինչ նախորդը, միայն թե n-ը՝ վեկտորի երկարությունը, կարող է հասնել 2ᵏ-ի, որտեղ k-ն քյուբիթների քանակն է (քյուբիթները ավելի մանրամասն քննարկվում են Մաս 2-ում)։

Այստեղ նույնպես ֆունկցիան պետք է բավարարի որոշակի պահանջների։ Որոշները նման են GPU-ի վեկտորիզացիայի պահանջներին, իսկ մյուսները բնորոշ են միայն քվանտային համակարգիչներին։

Ամենակարևորը՝ ֆունկցիայի կոդը չպետք է ճյուղավորվի. հաշվարկը պետք է յուրաքանչյուր արգումենտի նկատմամբ կիրառի նույն գործողությունների շարքը։ Այդպիսի ֆունկցիան կարող է զուգահեռ մշակել իր արգումենտների ամբողջ վեկտորը։ Տարբերությունն այն է, որ քվանտային համակարգչի վրա արգումենտների առավելագույն քանակը կախված է քյուբիթների քանակից, և յուրաքանչյուր ավելացված քյուբիթ կրկնապատկում է այդ սահմանը։ Այս աճը էքսպոնենցիալ է, այնպես որ նույնիսկ միայն մի քանի քյուբիթով այն շուտով գերազանցում է GPU-ի միջուկների քանակը։

Միաժամանակ պետք է հաշվի առնենք որոշ լրացուցիչ, հատուկ սահմանափակումներ.

  • GPU-ի վեկտորիզացիայի դեպքում վեկտորի տարրերը կարող էին լինել ցանկացած թվեր։ Այստեղ՝ k քյուբիթով, վեկտորի տարրերը կարող են լինել միայն առավելագույնը k թվանշան ունեցող եզակի երկուական ամբողջ թվեր։
  • GPU-ի վեկտորիզացիայից տարբերվելով՝ վեկտորի երկարությունը կարող է փոխվել։ Սա հնարավոր է, քանի որ զուգահեռ մուտքերի հաշվարկները միշտ չէ, որ իրարից անկախ են։
  • Վերջապես, ամբողջ վեկտորի վրա հաշվարկը տալիս է ընդամենը մեկ թիվ։

պատկեր3

Զուգահեռ հաշվարկ՝ մեկ թվով որպես արդյունք

Վերադառնալով մեր օրինակին

Այս սահմանափակումներն ինչ են նշանակում և որտեղից են գալիս, ավելի մոտիկից կքննենք հետո։ Առայժմ եկեք արագ ստուգենք, արդյոք դրանք հարմար են մեր օրինակ խնդրի համար։

Մեր օրինակ արժեքի ֆունկցիան ընդունում է մուտքեր ամբողջ թվերի սահմանափակ բազմությունից՝ {0…N}։ Մեզ անհրաժեշտ են բավարար քյուբիթներ՝ յուրաքանչյուր հնարավոր մուտք ներկայացնելու համար (այսինքն՝ N < 2ᵏ)։ Մենք կկառուցենք բոլոր մուտքերը պարունակող վեկտոր և կապավինենք քվանտային համակարգչի այն հնարավորությանը, որ նա կարող է ֆունկցիան զուգահեռ հաշվարկել դրանք բոլորի համար։ Մեզ նաև որոշ լրացուցիչ քյուբիթներ կպետք գան հաշվարկի միջանկյալ արդյունքները պահելու համար։

Օրինակ՝ մուտքի k բիթ և միջանկյալ արդյունքների համար մի քանի լրացուցիչ բիթ

Յուրաքանչյուր մուտքին (k երկուական թվանշանով ամբողջ թիվ) կցվում են որոշ լրացուցիչ բիթեր։ Մեր դեպքում մուտքի մասը մնում է անփոփոխ, իսկ լրացուցիչ բիթերը փոխվում են հաշվարկի ընթացքում։ Անփոփոխ մասը և լրացուցիչ բիթերը միասին կազմում են վեկտորի մեկ տարր։

Յուրաքանչյուր տարրը կարելի է պատկերացնել որպես բանալի-արժեք զույգ, որտեղ անփոփոխ մասը բանալին է, իսկ մնացածը՝ փոփոխվող արժեքը։ Քանի որ բանալին եզակի է և միշտ առկա, յուրաքանչյուր տարր ամբողջ հաշվարկի ընթացքում մնում է եզակի։

Վերջում մենք քվանտային համակարգչին կստիպենք վերադարձնել որոնման չափանիշներին բավարարող միակ մուտքը։ Հասկանալու համար, թե ինչպես, պետք է մի փոքր ավելի խորանալ, ինչին էլ հաջորդում ենք հիմա։

Ամփոփում

Շարքի այս մասը քվանտային համակարգչի համառոտ ակնարկ տվեց։ Ես այն համեմատեցի ավելի ծանոթ գաղափարների հետ, ինչպիսիք են GPU-ն և վեկտորիզացիան՝ նշելով ինչպես նմանությունները, այնպես էլ այն առանձնահատուկ սահմանափակումները, որոնք քվանտային համակարգիչը պարտադրում է։ Ես նաև ուրվագծեցի, թե ինչպես կարելի է օպտիմալացման սեփական խնդիրը տանել քվանտային համակարգչի վրա։

Մաս 2-ում կբացատրեմ, թե որտեղից են գալիս այս առանձնահատուկ սահմանափակումները, ինչը նշանակում է քննարկել քյուբիթները և քվանտային համակարգչի մյուս շինանյութերը։

Մաս 3-ում և Մաս 4-ում կվերադառնամ օպտիմալացման օրինակին և այն ավելի մոտիկից կքննեմ՝ աշխատող կոդի օրինակի հետ միասին։