Səyyar satıcı problemi kombinator optimallaşdırma probleminin əsas nümunəsi hesab olunur. İndi Berlin Freie Universität Berlin və HZB-dən nəzəri fizik Prof. Dr. Jens Eisertin rəhbərlik etdiyi Berlin komandası göstərdi ki, bu cür problemlərin müəyyən sinfi əslində adi üsullarla müqayisədə kvant kompüterləri ilə daha yaxşı və daha sürətli həll edilə bilər.

Komandanın işi Science Advances jurnalında dərc olunub .

Kvant kompüterləri adi məntiq dövrələrində olduğu kimi nə sıfır, nə də bir olmayan, lakin aralarındakı istənilən dəyəri qəbul edə bilən qubit adlananlardan istifadə edirlər. Bu kubitlər yüksək dərəcədə soyudulmuş atomlar, ionlar və ya superkeçirici sxemlər tərəfindən həyata keçirilir və bir çox kubitli kvant kompüteri qurmaq hələ də fiziki cəhətdən çox mürəkkəbdir. Bununla belə, riyazi üsullar artıq səhvlərə dözümlü kvant kompüterlərinin gələcəkdə nəyə nail ola biləcəyini araşdırmaq üçün istifadə edilə bilər.

“Bununla bağlı çoxlu miflər, bəzən də müəyyən qədər qaynar hava və ajiotaj var. Amma biz məsələyə ciddi yanaşdıq, riyazi metodlardan istifadə etdik və mövzu ilə bağlı tutarlı nəticələr verdik. Hər şeydən əvvəl hansı mənada aydınlıq gətirdik. ümumiyyətlə hər hansı üstünlüklər ola bilər,” Freie Universität Berlin və Helmholtz-Zentrum Berlində birgə tədqiqat qrupuna rəhbərlik edən Prof. Dr. Eisert deyir.

Səyyar satıcının məşhur problemi buna əsas nümunə kimi xidmət edir: Səyyah bir sıra şəhərləri gəzməli və sonra öz doğma şəhərinə qayıtmalıdır. Ən qısa yol hansıdır? Bu problemi başa düşmək asan olsa da, şəhərlərin sayı artdıqca və hesablama vaxtı partladıqca getdikcə mürəkkəbləşir. Səyahətçi satıcı problemi dəmir yolu şəbəkələri, logistika və ya resursların optimallaşdırılması ilə bağlı böyük iqtisadi əhəmiyyət kəsb edən bir qrup optimallaşdırma problemini ifadə edir. Kifayət qədər yaxşı həllər yaxınlaşma metodlarından istifadə etməklə tapıla bilər.

https://googleads.g.doubleclick.net/pagead/ads?client=ca-pub-0536483524803400&output=html&h=135&slotname=8188791252&adk=2329133447&adf=780081655&pi=t.ma~as.8188791252&w=540&fwrn=4&lmt=1711911340&rafmt=11&format=540×135&url=https%3A%2F%2Fphys.org%2Fnews%2F2024-03-quantum-combinatorial-optimization-problems-easily.html&wgl=1&uach=WyJXaW5kb3dzIiwiMTAuMC4wIiwieDg2IiwiIiwiMTIzLjAuNjMxMi44NiIsbnVsbCwwLG51bGwsIjY0IixbWyJHb29nbGUgQ2hyb21lIiwiMTIzLjAuNjMxMi44NiJdLFsiTm90OkEtQnJhbmQiLCI4LjAuMC4wIl0sWyJDaHJvbWl1bSIsIjEyMy4wLjYzMTIuODYiXV0sMF0.&dt=1711911340023&bpp=3&bdt=545&idt=427&shv=r20240327&mjsv=m202403250101&ptt=9&saldr=aa&abxe=1&cookie=ID%3D5d346f5e5cc96c83%3AT%3D1711816817%3ART%3D1711911207%3AS%3DALNI_MZdbuKX3JkLTYIASzwYTqXQsnfO5g&gpic=UID%3D00000d8601a1b778%3AT%3D1711816817%3ART%3D1711911207%3AS%3DALNI_MaQelh7liNnsBkMosJkThXBNbKuJw&eo_id_str=ID%3D3c61c6284063652a%3AT%3D1711816817%3ART%3D1711911207%3AS%3DAA-AfjZTZ5YTcMfFebI4RXZlGycf&prev_fmts=0x0&nras=1&correlator=6596096957847&frm=20&pv=1&ga_vid=1802142616.1711809852&ga_sid=1711911340&ga_hid=1719023486&ga_fc=1&rplot=4&u_tz=240&u_his=1&u_h=900&u_w=1440&u_ah=860&u_aw=1440&u_cd=24&u_sd=1&dmc=8&adx=347&ady=1977&biw=1423&bih=739&scr_x=0&scr_y=0&eid=44759875%2C44759926%2C44759842%2C42532243%2C44798934%2C95321963%2C95321867%2C95328825%2C21065725%2C31078663%2C31078665%2C31078668%2C31078670&oid=2&pvsid=2697265349341309&tmod=751381899&uas=3&nvt=3&ref=https%3A%2F%2Fphys.org%2Fweekly-news%2Fpage2.html&fc=1920&brdim=0%2C0%2C0%2C0%2C1440%2C0%2C1440%2C860%2C1440%2C739&vis=1&rsz=%7C%7CpeEbr%7C&abl=CS&pfx=0&fu=128&bc=31&bz=1&td=1&psd=W251bGwsbnVsbCwibGFiZWxfb25seV80IiwxXQ..&nt=1&ifi=2&uci=a!2&btvi=1&fsb=1&dtd=440

Eisert və onun həmkarı Jean-Pierre Seifert-in rəhbərlik etdiyi qrup indi kubitli kvant kompüterinin bu sinif problemləri, qələm və kağız ilə klassik düşüncə təcrübəsi və çoxlu təcrübəni necə həll edə biləcəyini qiymətləndirmək üçün sırf analitik üsullardan istifadə etdi.

“Fiziki dərk etməsindən asılı olmayaraq, biz sadəcə olaraq güman edirik ki, kifayət qədər kubitlər var və onlarla hesablama əməliyyatlarını yerinə yetirmək imkanlarına baxırıq”, – Ph.D Vincent Ulitzsch izah edir. Berlin Texniki Universitetinin tələbəsi.

Bununla da, komanda kriptoqrafiyanın məşhur problemi, yəni məlumatların şifrələnməsi ilə oxşarlıqlar açıb.

“Biz başa düşdük ki, bu optimallaşdırma problemlərinin alt sinfini həll etmək üçün Shor alqoritmindən istifadə edə bilərik” dedi Ulitzsch. Bu o deməkdir ki, hesablama vaxtı artıq şəhərlərin sayı ilə (eksponensial, 2 ^N ) “partlatılmır”, ancaq çoxhədli, yəni N ^x ilə artır , burada x sabitdir. Bu yolla əldə edilən həll həm də adi alqoritmdən istifadə edərək təxmini həlldən keyfiyyətcə xeyli yaxşıdır.

“Biz göstərdik ki, kombinator optimallaşdırma problemlərinin xüsusi, lakin çox vacib və praktiki olaraq müvafiq sinfi üçün kvant kompüterləri problemin müəyyən nümunələri üçün klassik kompüterlərdən əsas üstünlüyə malikdir” dedi Eisert.

Daha çox məlumat: Niklas Pirnay və digərləri, Hesablamalı öyrənmə nəzəriyyəsi vasitəsilə kombinatorial optimallaşdırma problemlərini yaxınlaşdırmaq üçün prinsipial super polinom kvant üstünlüyü, Science Advances (2024). DOI: 10.1126/sciadv.adj5170

Alman Araşdırma Mərkəzlərinin Helmholtz Assosiasiyası tərəfindən təmin edilmişdir