- Համայնքի արդյունավետ որոնում մեծ վերագրվող երկմաս գրաֆիկների վրա (arXiv)
Հեղինակ՝ Zongyu Xu, Yihao Zhang, Long Yuan, Yuwen Qian, Zi Chen, Mingliang Zhou, Qin Mao, Weibin Pan
Համայնքի որոնումը երկմաս գրաֆիկների վրա վերջերս զգալի հետաքրքրություն է առաջացրել: Շատ կիրառություններում, ինչպիսիք են էլեկտրոնային առևտրի օգտատեր-տարրերի երկկողմանի գրաֆիկը, ֆիլմերի վարկանիշային կայքում հաճախորդ-ֆիլմի երկակողմ գրաֆիկը, հանգույցները հակված են ունենալ ատրիբուտներ, մինչդեռ նախկին համայնքի որոնման ալգորիթմը երկկողմանի գրաֆիկների վրա անտեսում է ատրիբուտները, ինչը վերադարձված արդյունքները դարձնում է վատ համախմբվածություն: իրենց հանգույցի հատկանիշների նկատմամբ: Այս հոդվածում մենք ուսումնասիրում ենք համայնքի որոնման խնդիրը վերագրվող երկմասնական գրաֆիկների վրա: Հաշվի առնելով հարցման q գագաթը, մենք նպատակ ունենք գտնել G-ի վերագրված (α, β)-համայնքները, որտեղ համայնքի կառուցվածքի համախմբվածությունը նկարագրված է (α, β)-հիմնական մոդելով և հանգույցների երկու խմբերի հատկանիշի նմանությամբ: ենթագրաֆում առավելագույնի հասցված է: Երկկողմանի գրաֆիկներից վերագրված համայնքները վերբերելու համար մենք նախ առաջարկում ենք հիմնական ալգորիթմ, որը բաղկացած է երկու քայլից՝ թեկնածու հիմնաբառերի հավաքածուների ստեղծում և ստուգում, այնուհետև առաջարկվում են երկու բարելավված հարցումների ալգորիթմներ Inc և Dec: Inc-ն առաջարկվում է հաշվի առնելով վերագրված երկմաս գրաֆիկների հակամիօրինակության հատկությունը, այնուհետև մենք ընդունում ենք տարբեր գեներացման մեթոդ և ստուգելու թեկնածու հիմնաբառերի հավաքածուների կարգը և առաջարկում ենք Dec ալգորիթմը: Ութ մեծ գրաֆիկների վրա մեր լուծումները գնահատելուց հետո, փորձարարական արդյունքները ցույց են տալիս, որ մեր մեթոդներն արդյունավետ և արդյունավետ են երկմաս գծապատկերների վրա վերագրված համայնքների հարցումների հարցում:
2. Բարձր հավատարմության քվանտային վիճակների փոխանցման ալգորիթմ ամբողջական երկմասնական գրաֆիկի վրա (arXiv)
Հեղինակ՝ Դան Լի, Ցզյա-Նի Հուանգ, Յու-Ցյան Չժոու, Յու-Գուան Յանգ
Համառոտ. Քվանտային վիճակի բարձր հավատարմության փոխանցումը կարևոր նշանակություն ունի քվանտային հաղորդակցության և մասշտաբային քվանտային հաշվարկների համար: Ընթացիկ քվանտային վիճակների փոխանցման ալգորիթմները ամբողջական երկկողմանի գրաֆիկի վրա, որոնք հիմնված են դիսկրետ ժամանակի քվանտային քայլքի որոնման ալգորիթմների վրա, որոշ դեպքերում տառապում են ցածր հավատարմությունից: Այս խնդիրը լուծելու համար այս աշխատությունում մենք առաջարկում ենք երկաստիճան քվանտային վիճակի փոխանցման ալգորիթմ ամբողջական երկմասնական գրաֆիկի վրա: Ալգորիթմը ձեռք է բերվում ընդհանրացված Գրովերի քայլքով մեկ նշված գագաթով: Ընդհանրացված Grover walk-ի մետաղադրամների օպերատորները և հարցման օրակուլները երկուսն էլ պարամետրային միավորային մատրիցներ են, որոնք նախագծված են ճկուն կերպով՝ հիմնվելով ուղարկողի և ստացողի դիրքերի և ամբողջական երկմասնական գրաֆիկի չափի վրա: Մենք ապացուցում ենք, որ ալգորիթմի հավատարմությունը մեծ է 1−2ε1−ε2−22–√ε1ε2−−−−√ կամ 1−(2+22–√)ε1−ε2−(2+22–√)ε1ε2−−–ից։ −−√ ցանկացած կարգավորելի ε1 և ε2 պարամետրի համար, երբ ուղարկողն ու ստացողը գտնվում են նույն բաժանման մեջ կամ ամբողջական երկմաս գծապատկերի տարբեր բաժիններում։ Ալգորիթմը տրամադրում է նոր մոտեցում՝ ցանկացած դեպքում ամբողջական երկկողմանի գրաֆիկի վրա բարձր ճշգրտության քվանտային վիճակի փոխանցման հասնելու համար, որը կառաջարկի պոտենցիալ կիրառություններ քվանտային տեղեկատվության մշակման համար:
