Paglutas ng ‘Traveling Salesman Problem’ Gamit ang Quantum Computing

Isang klasikong problemang algorithmiko sa larangan ng agham ng kompyuter na kilala bilang Traveling Salesman Problem (TSP) ay isang pangunahing halimbawa ng problemang kombinatoryal na optimisasyon.

Ano nga ba ang TSP? Ang klasikong matematika na ito ay naglalaman ng paghahanap ng pinakamaikling posibleng ruta upang bisitahin ang N na bilang ng mga lungsod nang eksaktong isang beses bago bumalik sa pinagmulan. Gayunpaman, habang tumataas ang bilang ng mga lungsod, tumataas din ang posibleng mga ruta at ang oras ng pagkompyut upang mahanap ang pinakamainam na solusyon. Bagaman maaaring lutasin ang problemang ito gamit ang mga pamamaraan ng aproksimasyon, maaaring magbigay ang mga quantum computer ng mas magagandang solusyon at mas mabilis pa.

Ito ay eksaktong ipinakita ng koponan ni Prof. Dr. Jens Eisert: na ang mga ganitong problema ay maaaring malutas nang mas mahusay at mas mabilis gamit ang mga quantum computer.

Ang quantum computing ay gumagamit ng hardware at mga algorithm na sinasamantala ang mekaniks ng quantum upang lutasin ang mga komplikadong problema na lampas sa kayang abutin ng tradisyonal, kabilang ang mga supercomputer. Sa kabila ng kanilang kapangyarihan, ang mga supercomputer—malalaking klasikong kompyuter na may libu-libong CPU at GPU cores—ay limitado ng kanilang pag-asa sa teknolohiyang transistor ng ika-20 siglo kapag nilulutas ang mga problemang may mataas na antas ng komplikasyon.

Dito pumapasok ang pisika ng quantum. Sa pagkakaiba sa mga klasikong kompyuter, na nag-encode ng impormasyon sa binary bits (0s at 1s), ang mga quantum computer ay gumagamit ng quantum bits o qubits upang patakbuhin ang multidimensiyonal na mga quantum algorithm.

Bukod pa rito, hindi tulad ng mga tradisyonal na kompyuter na gumagamit ng mga bentilador para sa paglamig, ang mga quantum computer ay nangangailangan na panatilihing napakalamig ang kanilang mga quantum processor upang mapanatili ang kanilang mga quantum state. Ito ay nakamit sa pamamagitan ng sobrang malamig na superfluid.

Ang mga superconductor ay mga materyales na nagpapakita ng kritikal na epekto ng mekaniks ng quantum, na nagpapahintulot sa mga electron na dumaloy sa kanila nang walang resistensya. Habang dumadaan ang mga electron, nagpa-pares sila upang magdala ng karga sa mga hadlang. Kapag dalawang superconductor ay inilagay sa magkabilang panig ng isang insulator, nabubuo ang isang Josephson junction, na ginagamit upang mag-conduct ng superconducting qubits.

Ang isang qubit ay kapaki-pakinabang sa mahalagang gawain ng paglalagay ng kanyang quantum na impormasyon sa isang estado ng superposisyon, isang kombinasyon ng posibleng mga konfigurasyon ng qubit. Ang mga grupo ng mga qubit sa superposisyon ay kayang lumikha ng komplikadong, multidimensiyonal na mga computational space kung saan maaaring irepresenta ang mga komplikadong problema.

Dito, sa pamamagitan ng pagkakaugnay ng dalawang qubit, ang mga pagbabago sa isa ay maaaring direktang makaapekto sa isa pa, habang kapag ang mga entangled na qubit ay inilagay sa isang estado ng superposisyon, napakaraming posibilidad ang nabubuo. Ang pagkompyut sa isang quantum computer ay gumagana sa pamamagitan ng paghahanda ng superposisyon ng lahat ng posibleng computational state, at sa pamamagitan ng interference, natatagpuan ang mga solusyon.

Siyempre, ang pagbuo ng isang quantum computer na may maraming qubit ay isang napaka-komplikadong proseso, bagaman maraming pamamaraan ang sinusuri kung ano ang maaaring magawa ng mga ganitong kompyuter.

Ayon kay Eisert, na namumuno sa isang pinagsamang pangkat ng pananaliksik sa Helmholtz-Zentrum Berlin (HZB), isang sentro ng pananaliksik para sa mga materyales ng enerhiya, at sa pampublikong unibersidad na Freie Universität Berlin:

“Maraming mito tungkol dito, at kung minsan ay may kaunting usong walang laman at hype. Gayunpaman, sinuri namin ang isyu nang mahigpit, gamit ang mga metodong matematika, at naghatid ng matibay na resulta sa paksa. Higit sa lahat, nilinaw namin kung sa anong paraan maaaring magkaroon ng anumang mga benepisyo.”

Ang Kritikal na Problema ng Traveling Salesman

Isang problemang optimisasyon, ang TSP ay may malaking kahalagahan sa ekonomiya sa industriya ng logistika at supply chain. Ito ay kabilang sa mas malawak na kategorya ng mga problemang kombinatoryal na optimisasyon, na kinabibilangan din ng job scheduling, resource allocation, portfolio optimization, at kahit protein folding, na lahat ay kritikal sa iba’t ibang sektor.

Dahil sa panlipunan at pang-ekonomiyang kahalagahan ng mga problemang ito, naging paksa ng matinding pananaliksik ang mga ito. Bilang gayon, ang paghahanap ng sagot sa mga problemang tulad ng pinakaepektibong supply chain at pinakamurang ruta ng paghahatid ay may positibong epekto sa ating pang-araw-araw na buhay.

Gayunpaman, ang pag-optimize ng mga ruta ng paghahatid para sa maraming destinasyon habang isinasaalang-alang ang iba’t ibang limitasyon tulad ng trapiko, tumataas na gastusin sa operasyon, biglaang pagbabago ng ruta, mga huling minutong appointment sa negosyo, at mga kahilingan ng customer ay nagpapahirap pa lalo sa paglutas ng TSP. Sa kabila ng mga hamong ito, ang paglutas ng TSP ay mahalaga para sa epektibong paghahatid ng mga kalakal, na nagsisiguro ng isang matatag na modelo ng negosyo.

Maraming benepisyo ang nagmumula sa paglutas ng problemang ito, kabilang ang pagbawas ng distansya at oras ng paglalakbay at pagtitipid sa paggamit ng gasolina. Ang pag-minimize ng distansyang nilakbay ay makatutulong na malaki ang bawas sa carbon footprint, na nagreresulta sa mas magandang kalidad ng hangin, pagbagal ng pagbabago ng klima, at paglago ng ekonomiya. Bukod pa rito, ang paglutas ng TSP ay makatutulong sa on-time delivery ng mga kalakal at napapanahong mga pulong sa mga kliyente, na nagpapabuti sa karanasan ng customer at mga negosyo sa field service.

Tulad ng ating nakita, ang paglutas ng problemang ito ay hindi lamang nakakatulong sa mga negosyo, kundi ang mga benepisyo ay umaabot din sa mga customer, na nagpapayaman sa karanasan ng lahat ng kasangkot.

Maraming pamamaraan ang maaaring gamitin upang lutasin ang problemang TSP. Isa sa mga ito ay ang ‘Brute-Force’ na pamamaraan, na nagkakalkula ng lahat ng posibleng permutasyon upang mahanap ang pinakamaikling ruta. Sa branch-and-bound method, hinahati ang problema sa ilang serye ng mga subproblem, kung saan ang solusyon sa bawat yugto ay nakakaapekto sa solusyon na matatagpuan sa mga susunod na yugto.

Sa dynamic programming, ang pokus ay sa pag-iwas sa mga paulit-ulit na kalkulasyon. Ang Nearest Neighbor, sa kabilang banda, ay isang approximation algorithm kung saan nagsisimula ka sa panimulang lokasyon at pagkatapos ay tumitigil sa pinakamalapit na isa. Kapag natakpan na ang lahat ng lungsod, babalik ka sa panimulang punto. Bagaman praktikal at medyo mabilis, maaaring hindi palaging magbigay ang pamamaraang ito ng epektibong ruta.

Habang umuunlad ang teknolohiya, ang pagpaplano at pag-optimize ng ruta ay maaaring gawin nang mas epektibo. Ang Artificial Intelligence (AI), partikular, ay maaari ring makatulong sa paglutas ng problema sa pamamagitan ng mabilis na pagsusuri ng napakalaking dami ng data upang matulungan ang maraming modernong negosyo na gumawa ng mga operasyonal at estratehikong desisyon.

Ang mga quantum computer ay iniimbestigahan din upang lutasin ang problema; matapos ang lahat, nag-aalok ang mga ito ng makabuluhang pagbilis ng kompyutasyon kumpara sa mga klasikong kompyuter. Matagal nang sinasabing maaaring makatulong ang mga ito sa pagpapabuti ng mga aproksimasyon sa mga problemang ito.

Paggamit ng mga Teknik sa Quantum Computing upang Lutasin ang TSP

Habang ang quantum computing ay nakakuha ng napakalaking interes at nagbibigay ng magagandang resulta para sa ilang mga problema, ang lawak ng quantum advantage na ito ay nananatiling halos hindi pa nasusuri.

Bilang resulta, ang pag-aaral ay nagbigay ng ganap na konstruktibong patunay na ang mga quantum computer ay maaaring talagang higitan ang mga tradisyonal na kompyuter sa paghahanap ng mga aproksimasyon sa mga problemang kombinatoryal na optimisasyon.

Ang pinakabagong pag-aaral, na pinamunuan nina Eisert at ng kanyang kasamahan na si Jean-Pierre Seifert, ay gumamit lamang ng mga analitikal na pamamaraan upang suriin kung paanong isang quantum computer na may mga qubit ay maaaring lutasin ang problemang TSP.

“Simple naming ipinapalagay, anuman ang pisikal na realizasyon, na may sapat na bilang ng mga qubit at tinitingnan ang mga posibilidad ng pagsasagawa ng mga operasyon sa pagkompyut gamit ang mga ito,” na nagbubunyag ng pagkakahawig sa isang karaniwang problema sa cryptography, i.e., ang encryption ng data, ipinaliwanag ni Vincent Ulitzsch, isang Ph.D. student sa Technical University of Berlin.

Pagkatapos, ginamit ng koponan ang Shor algorithm, isang quantum algorithm, upang hanapin ang mga prime factor ng isang integer at lutasin ang isang subclass ng mga problemang optimisasyon. Sa ganitong paraan, hindi na lalala ang oras ng pagkompyut habang dumarami ang bilang ng mga lungsod. Tataas lamang ito nang polynomially, i.e., sa Nx, kung saan ang x ay isang constant. Sa ganitong paraan, ang nakuha na solusyon ay qualitatively na mas mahusay kaysa sa nakuha mula sa approximate solution gamit ang tradisyonal na algorithm.

Sa pamamagitan ng paggamit ng mga konsepto ng cryptography at computational learning theory, ang pag-aaral ay nagbibigay ng “ganap na konstruktibong patunay na ang mga quantum computer ay may super-polynomial na advantage laban sa mga klasikong kompyuter sa pag-approximate ng mga problemang kombinatoryal na optimisasyon.”

Dagdag pa rito, binanggit ng pag-aaral na ang koponan ng pananaliksik ay gumawa ng makabuluhang pag-unlad sa mahalagang tanong kung ano ang potensyal na maiaambag ng mga quantum computer sa pag-approximate ng solusyon ng mga problemang kombinatoryal na optimisasyon, na may malaking panlipunan at pang-ekonomiyang epekto.

Ang pag-aaral ay pinondohan ng Einstein Research Unit, ang Berlin Mathematics Research Center (MATH+ Cluster of Excellence), ang BMBF (Hybrid), ang BMWK (EniQmA), ang Munich Quantum Valley, at ang DFG. Ang Federal Ministry of Education and Research ng Germany ay nagbigay din ng pinansyal na suporta.

Pagsusuri sa Potensyal ng Quantum Computing 

Bagaman isang malaking tagumpay, ito ay hindi unang pagkakataon na ginamit ang quantum computing upang lutasin ang traveling salesman problem. Maraming pagkakataon na ang mga entusiasta at mananaliksik ay tumitingin sa paglutas ng problema sa pamamagitan ng paggamit ng quantum computing.

Noong Disyembre 2022, isang paper ay nagmungkahi ng isang quantum algorithm para sa TSP batay sa Grover Adaptive Search (GAS). Sa ilalim ng framework ng GAS, mayroong hindi bababa sa dalawang pangunahing kahirapan—maaaring hindi praktikal ang mga solusyon, at ang bilang ng mga qubit ng kasalukuyang mga quantum computer ay napakakaunti at hindi nakakatugon sa minimum na pangangailangan, na naglilimita sa aplikasyon ng mga quantum algorithm para sa mga problemang kombinatoryal na optimisasyon.

Bilang resulta, pinino ng papel ang Hamiltonian Cycle Detection (HCD) oracle, na maaaring awtomatikong alisin ang mga hindi praktikal na solusyon habang tumatakbo ang algorithm. Dinisenyo rin nila ang estratehiyang “anchor register” upang makatipid sa paggamit ng qubit, na ganap na isinasaalang-alang ang pangangailangan ng reversibility ng quantum computing at nalampasan ang kahirapan na ang mga ginamit na qubit ay hindi basta-basta na-overwrite o nare-release. Pinahintulutan nito ang pag-aaral na gumamit lamang ng 31 qubits, at ang solusyon ay nagkaroon ng success rate na 86.71%.

Noong 2019, ang self-defined physics connoisseur na si Joseph Cammidge sumulat tungkol sa paggamit ng isang annealing quantum processor, na nagbigay-daan sa kanya upang lutasin ang traveling salesman problem para sa pitong lungsod at may teoretikal na potensyal na lutasin para sa siyam na lungsod kapag naalis na ang mga limitasyong teknolohikal.

Isang bagong pamamaraan sa kompyutasyon, ang Quantum annealing, ay nagpakita ng potensyal na lutasin ang mga problemang optimisasyon nang mas mabilis kaysa sa mga klasikong teknik. Ang teorya nito ay nagpapahiwatig na ang mga qubit ay makakamit ang optimal na low-energy state kapag super-cooled.

Gayunpaman, noong 2021, isang pag-aaral na pinondohan ng Supply Chain Digital & Data Science, Johnson & Johnson ay natuklasan na ang quantum annealer ay kayang hawakan lamang ang problem size na 8 o mas kaunti pang nodes, at ang performance nito ay mas mababa kapwa sa oras at katumpakan kumpara sa klasikong solver.

Ang paggamit ng quantum computing upang lutasin ang TSP ay nagaganap na nang ilang panahon. Mahigit dalawang dekada na ang nakalipas, noong 2001, isang pag-aaral ang nagsimulang maghanap ng isang quantum algorithm upang lutasin ang problema.

Sa papel, tiningnan ni Buckley Hopper ng University of Alabama ang mga algorithm ng Grover at Shor. Napansin niya na ang algorithm ni Grover ay nagbibigay lamang ng square root improvement, na nagpapahiwatig na hindi nito magagawang gawing tractable ang isang problemang klasikal na hindi matutugunan sa quantum computer. Tungkol naman sa algorithm ni Shor, napansin ni Hopper na, bagaman maaari nitong gawing tractable ang isang problemang prime factor na tila hindi matutugunan, ito ay angkop lamang para sa isang napakaespesipikong uri ng problema.

Sa pangkalahatan, sinabi ni Hopper na “hindi niya nahanap ang isang kasiya-siyang resulta para sa isang algorithm na nagko-compute ng approximate solutions sa traveling salesman problem.”

Ilang taon pagkatapos nito, ang Institute of Electrical and Electronics Engineers (IEEE) nagpresenta ng isang bagong algorithm para sa paglutas ng problema, na inspirasyon mula sa parehong genetic algorithms at quantum computing. Natuklasan ng IEEE na ang mga resulta mula sa aplikasyon ng iminungkahing algorithm sa ilang mga instance ng Traveling Salesman Problem ay mas makabuluhan kaysa sa mga ibinibigay ng standard genetic algorithms.

I-click dito upang matuto tungkol sa kasalukuyang kalagayan ng quantum computing.

Mga Kumpanyang Nagtatrabaho sa Quantum Computing 

Ngayon, tingnan natin ang ilang pangalan na nagtatrabaho sa pananaliksik at pag-unlad ng quantum computing:

#1. IBM

Ang International Business Machines Corporation (IBM ) ay kasangkot sa malawak na hanay ng mga sektor, kabilang ang AI, cloud services, IT, client financing, at commercial financing. Ang higanteng teknolohiya ay kasali rin sa quantum computing sa pamamagitan ng IBM Quantum Platform, na nagbibigay ng pampubliko at premium na access sa kanilang cloud-based na quantum computing services. Kabilang dito ang hanay ng prototype quantum processors ng IBM, mga tutorial sa quantum computation, at isang interactive na aklat-aralin.

Kamakailan lamang, ang mga siyentipiko ng IBM nagsabi na sila ay isa pang hakbang na mas malapit sa pagtagumpayan ng isang hadlang na magbubukas ng game-changing potential ng mga quantum computer. Para dito, ipinakilala nila ang isang bagong quantum error-correcting code, na sinasabi nilang halos sampung beses na mas epektibo kaysa sa mga nakaraang pamamaraan.

Noong huling bahagi ng nakaraang taon, inilunsad din ng kumpanya ang quantum computer na tinatawag na Condor, na may 1,121 superconducting qubits na nakaayos sa isang honeycomb pattern. Inilunsad din ng IBM ang IBM Quantum System Two, ang kanilang unang modular quantum computer at quantum-centric supercomputing architecture, na scalable at kaya nitong i-upgrade gamit ang mga chip na ilulunsad sa susunod na limang taon.

Sa market cap na $175 bilyon, ang mga shares ng IBM ay nagte-trade sa $190.86, tumaas ng 16.66% ngayong taon (YTD). Ang IBM ay nag-post ng revenue (TTM) na $61.86 bilyon habang may EPS (TTM) na 8.03, P/E (TTM) na 23.76, at ROE (TTM) na 33.36%. Ang kumpanya ay nagbabayad ng dividend yield na 3.48%.

#2. D-Wave Systems

Ang kumpanyang ito sa quantum computing ay nagde-develop at nagde-deliver ng mga kaugnay na sistema, software, at serbisyo. Kabilang sa mga produkto nito ang The Leap at The Advantage, at nagbibigay ito ng mga quantum application para sa scheduling, logistics, drug discovery, manufacturing processes, at iba pa.

Sa simula ng buwang ito, sinabi ng D-Wave na ang mga quantum machine ay maaari nang lutasin ang mga problema na may real-world applications nang mas mabilis kaysa sa anumang ordinaryong kompyuter. Noong unang bahagi ng taon, inanunsyo ng kumpanya ang isang quantum computer na may 1,200 qubits, 10,000 couplers, at 20x na mas mabilis na time-to-solution sa mahihirap na optimization problems.

Ang mga shares ng kumpanya ay kasalukuyang nagte-trade sa $1.86, tumaas ng 138.6% ngayong taon (YTD), na may market capitalization na $267 milyon. Iniulat nito ang $8.247 milyon na benta (TTM), -0.66 EPS (TTM), at -3.19 P/E (TTM), at inanunsyo ang higit sa 20% na paglago sa benta para sa parehong Q4 at year-end 2023 results, habang ang bookings ay tumaas ng 34% at 89%, ayon sa pagkakabanggit.

Kagiliw-giliw, idineklara ng CEO ng kumpanya, Dr. Alan Baratz, ang momentum ng kumpanya, na binanggit ang multi-year strategic partnership ng kumpanya sa Zapata AI, ang pagpapakilala ng 1,200+ qubit Advantage2 prototype, mga joint venture sa NEC Australia at Deloitte Canada, at ang paghirang kay dating Homeland Security Secretary Kirstjen Nielsen sa board of directors.

Konklusyon

Ang merkado para sa quantum computing ay inaasahang maabot ang $6.5 bilyon sa 2028, at ang potensyal nito na lutasin ang Traveling Salesman Problem (TSP) ay may mga implikasyon para sa ilang industriya, tulad ng manufacturing, logistics, supply chain management, e-commerce, transportation, at pananaliksik. Sa huli, maaari itong magdulot ng malalaking benepisyo, partikular na pagpapataas ng produktibidad, pagputol ng gastusin, at pagpapasigla ng inobasyon sa iba’t ibang sektor.

I-click dito para sa listahan ng limang pinakamahusay na kumpanya ng quantum computing.