Solusyon sa ‘The Travelling Salesman Problem’ sa Pamamagitan ng Quantum Computing

Isang klasikong algorithmic problem sa larangan ng agham pangkompyuter na kilala bilang ang Travelling Salesman Problem (TSP) ay isang halimbawa ng isang combinatorial optimization problem.

Ano ba ang TSP? Ang matematikal na klasiko na ito ay tumutukoy sa paghahanap ng pinakamaikling posible na ruta upang bisitahin ang N bilang ng mga lungsod nang eksaktong minsan bago bumalik sa lungsod ng pinanggalingan. Gayunpaman, habang tumataas ang bilang ng mga lungsod, dumarami rin ang mga posible na ruta at ang oras ng pagkalkula upang makahanap ng optimal na solusyon.Bagaman ang problemang ito ay maaaring malutas gamit ang mga pamamaraan ng paghahanap, ang mga quantum computer ay maaaring magbigay ng mas mabubuting solusyon at mas mabilis pa.

Ito ang eksaktong ipinakita ng team ni theoretical physicist Prof. Dr. Jens Eisert: na ang mga ganitong problemang maaaring mas mahusay at mas mabilis na malutas sa pamamagitan ng mga quantum computer.

Ang quantum computing ay gumagamit ng hardware at algorithm na nagpapapakinabang sa quantum mechanics upang malutas ang mga complex na problemang hindi makaya ng mga konbensional na computer, kabilang na ang mga supercomputer. Sa kabila ng kanilang lakas, ang mga supercomputer — mga malalaking klasikal na computer na may libu-libong CPU at GPU cores — ay limitado ng kanilang pag-asa sa teknolohiyang transistor ng ika-20 siglo sa paglutas ng mga problemang may mataas na antas ng kompleksidad.

Ito ang kinaroroonan ng quantum physics. Sa kabila ng mga klasikal na computer, na nag-eencode ng impormasyon sa binary bits (0s at 1s), ang mga quantum computer ay gumagamit ng quantum bits o qubits upang tumakbo ng multidimensional na quantum algorithm.

Bukod dito, sa kabila ng mga konbensional na computer, na gumagamit ng mga fan para sa pagpapalamig, ang mga quantum computer ay nangangailangan ng kanilang mga quantum processor na panatilihin sa napakalaking malamig na temperatura upang mapanatili ang kanilang mga quantum states. Ito ay naaabot sa pamamagitan ng super-cooled superfluids.

Ang mga superconductor ay mga materyal na nagpapakita ng isang kritikal na quantum mechanical effect, na nagpapahintulot sa mga electron na dumaraan sa kanila nang walang paglaban. Habang dumaraan ang mga electron, sila ay nagpapares upang magdala ng isang charge sa mga hadlang. Kapag inilagay ang dalawang superconductor sa magkabilang panig ng isang insulator, isang Josephson junction ang nabubuo, na ginagamit upang magdala ng superconducting qubits.

Ang isang qubit ay may kabuluhan sa mahalagang gawain ng paglalagay ng quantum information nito sa isang estado ng superposition, isang kombinasyon ng mga posible na konpigurasyon ng qubit. Ang mga grupo ng qubits sa superposition ay may kakayahan na lumikha ng mga complex, multidimensional na computational spaces kung saan ang mga complex na problemang maaaring ihayag.

Dito, sa pamamagitan ng entanglement ng dalawang qubits, ang mga pagbabago sa isa ay maaaring direktang maapektuhan ang isa pa, habang kapag ang mga entangled qubits ay inilagay sa isang estado ng superposition, maraming mga posibilidad. Ang kompyutasyon sa isang quantum computer ay gumagana sa pamamagitan ng paghahanda ng isang superposition ng lahat ng mga posible na computational states, at sa pamamagitan ng interference, ang mga solusyon ay natutuklasan.

Siyempre, ang pagbuo ng isang quantum computer na may maraming qubits ay isang napakomplikadong proseso, bagaman maraming mga pamamaraan ang sinusubukan upang malaman kung ano ang maaaring gawin ng mga computer na ito.

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

“Maraming mga alamat tungkol dito, at minsan may kaunting hangin at hype. Gayunpaman, kami ay lumapit sa isyu nang masusing, gamit ang mga pamamaraan ng matematika, at nagbigay ng mga solido at tapat na resulta sa paksa. Higit sa lahat, kami ay linawin kung saan mayroong anumang mga benepisyo.

Ang Kritikal na Travelling Salesman Problem

Isang optimization problem, ang TSP ay may malaking kahalagahan sa ekonomiya sa industriya ng logistics at supply chain. Ito ay nababahagi sa mas malawak na kategorya ng mga combinatorial optimization problem, na kinabibilangan ng job scheduling, resource allocation, portfolio optimization, at pati na rin ang protein folding, lahat ay kritikal sa iba’t ibang sektor.

Dahil sa social at ekonomikal na kahalagahan ng mga problemang ito, sila ay naging paksa ng masusing pananaliksik. Kaya, ang paghahanap ng sagot sa mga problemang tulad ng pinakamahusay na supply chain at pinakamurang ruta ng delivery ay may positibong epekto sa ating pang-araw-araw na buhay.

Gayunpaman, ang pag-optimize ng mga ruta ng delivery para sa maraming destinasyon habang isinasaalang-alang ang iba’t ibang mga limitasyon tulad ng traffic congestion, pagtaas ng operational costs, biglaang pagbabago ng ruta, huling sandali na mga pagpupulong sa negosyo, at mga kahilingan ng customer ay gumagawa ng TSP na mas mahirap malutas. Sa kabila ng mga hamon na ito, ang paglutas ng TSP ay kritikal para sa mabilis na delivery ng mga kalakal, na nagtiyak ng isang viable na modelo ng negosyo.

Mayroong maraming benepisyo sa paglutas ng problemang ito, kabilang ang pagbabawas ng distansya at oras ng pagbiyahe at pag-iwas sa paggamit ng gasolina. Ang pagbabawas ng distansya na tinatahak ay maaaring makatulong na bawasan ang carbon footprint nang malaki, na nangangahulugang mas magandang kalidad ng hangin, naabot na pagbabago ng klima, at paglago ng ekonomiya. Bukod dito, ang paglutas ng TSP ay maaaring makatulong sa on-time delivery ng mga kalakal at mga pagpupulong sa mga client, na nagpapahusay sa karanasan ng customer at mga negosyo sa field service.

Kaya, ang paglutas ng problemang ito ay hindi lamang nakatutulong sa mga negosyo, kundi ang mga benepisyo ay tumatawid rin sa mga customer, na nagpapahusay sa karanasan ng lahat ng mga kasangkot.

Maraming mga pamamaraan ang maaaring gamitin upang malutas ang problemang TSP. Ang isa sa mga pamamaraan ay ang ‘Brute-Force’ approach, na nagkalkula ng lahat ng mga posible na permutations upang makahanap ng pinakamaikling ruta. Sa pamamagitan ng branch-and-bound method, ang problemang ito ay nahahati sa maraming serye ng mga subproblem, kung saan ang solusyon sa bawat yugto ay nakakaapekto sa solusyon na natagpuan sa mga sumusunod na yugto.

Sa dynamic programming, ang pagtuon ay sa pag-iwas sa mga redundant na kalkulasyon. Ang Nearest Neighbor, samakatuwid, ay isang approximation algorithm kung saan sinisimulan mo sa starting location at pagkatapos ay tumitigil sa pinakamalapit. Kapag lahat ng mga lungsod ay natatakpan, bumabalik ka sa starting point. Bagaman praktikal at medyo mabilis, ang pamamaraan na ito ay hindi palaging nagbibigay ng isang mahusay na ruta.

Habang umuunlad ang teknolohiya, ang pagplano ng ruta at optimisasyon ay maaaring gawin nang mas mahusay. Ang Artificial Intelligence (AI), sa partikular, ay maaaring tumulong na malutas ang problemang ito sa pamamagitan ng pag-analisa ng isang malaking halaga ng data nang mabilis upang tulungan ang maraming modernong negosyo na gumawa ng mga desisyong operasyonal at estratehiko.

Ang mga quantum computer ay dinadalhan rin ng pansin upang malutas ang problemang ito; sa katunayan, sila ay nag-aalok ng makabuluhang mga pagpapabilis sa kompyutasyon kumpara sa mga klasikal na computer. Matagal nang iminungkahi na ang mga computer na ito ay maaaring tulungan na pagbutihin ang mga aproksimasyon sa mga problemang ito.

Ang Paggamit ng Mga Teknolohiya ng Quantum Computing upang Malutas ang TSP

Habang ang quantum computing ay nakakakuha ng malaking interes at nagbibigay ng mga pangako ng resulta para sa ilang mga problemang partikular, ang lawak ng quantum advantage ay nananatiling hindi gaanong napapagalaman.

Kaya, ang pag-aaral ay nagbigay ng ganap na konstruktibong patunay na ang mga quantum computer ay talagang mas mahusay kaysa sa mga konbensional na computer sa paghahanap ng mga aproksimasyon sa mga combinatorial optimization problem.

Ang pinakabagong pag-aaral, pinamunuan nina Eisert at ng kanyang kasama na si Jean-Pierre Seifert, ay gumamit lamang ng mga pamamaraan ng analitika upang subukin kung paano ang isang quantum computer na may qubits ay maaaring malutas ang problemang TSP.

“Kami ay simpleng inaasahan, anumang sa pisikal na pagpapakita, na may sapat na qubits at titingin sa mga posibilidad ng paggawa ng mga operasyon sa kompyutasyon sa kanila,” na nagpapakita ng isang pagkakaiba sa isang karaniwang problemang kriptograpiko, i.e., ang pag-encode ng data, ipinaliwanag ni Vincent Ulitzsch, isang Ph.D. student sa Technical University of Berlin.

Pagkatapos, ang team ay gumamit ng Shor algorithm, isang quantum algorithm, upang hanapin ang mga prime factors ng isang integer at malutas ang isang subclass ng mga optimization problem. Sa ganito, ang oras ng kompyutasyon ay hindi na lalaki nang husto habang tumataas ang bilang ng mga lungsod. Ito ay tataas lamang ng polynomial, i.e., kaagad ng Nx, kung saan x ay isang konstante. Sa ganitong paraan, ang solusyon na natatanggap ay mas mahusay rin kaysa sa mga naibigay ng mga aproksimadong solusyon gamit ang mga konbensional na algorithm.

Sa pamamagitan ng mga konseptong kriptograpiko at kompyutasyonal na teorya ng pag-aaral, ang pag-aaral ay nagbigay ng “ganap na konstruktibong patunay na ang mga quantum computer ay may super-polynomial na benepisyo kumpara sa mga klasikal na computer sa pag-aproksima ng mga combinatorial optimization problem.”

Ang pag-aaral ay nagpatuloy na ang team ng pananaliksik ay gumawa ng malaking pag-unlad sa mahalagang tanong kung ano ang mga potensyal na maiaambag ng mga quantum computer para sa mga aproksimasyon ng solusyon ng mga combinatorial optimization problem, na may malaking epekto sa lipunan at ekonomiya.

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 of Germany ay nagbigay rin ng pinansyal na suporta.

Ang Pagtuklas sa Potensyal ng Quantum Computing

Habang ito ay isang malaking tagumpay, ito ay hindi ang unang pagkakataon na ang quantum computing ay ginamit upang malutas ang traveling salesman problem. Mayroong maraming mga instance ng mga entusiasta at mananaliksik na tumitingin sa paglutas ng problemang ito sa pamamagitan ng quantum computing.

Noong Disyembre 2022, isang paper ay iminungkahi ang isang quantum algorithm para sa TSP batay sa Grover Adaptive Search (GAS). Sa ilalim ng framework ng GAS, mayroong dalawang pangunahing kahinaan — ang mga solusyon ay hindi maaaring magamit, at ang bilang ng qubits ng mga kasalukuyang quantum computer ay napakaliit at hindi makasasapat sa minimum na mga kinakailangan, na nagpapagbawal sa aplikasyon ng quantum algorithms para sa mga combinatorial optimization problem.

Kaya, ang paper ay pinahusay ang Hamiltonian Cycle Detection (HCD) oracle, na maaaring alisin ang mga impractical na solusyon nang awtomatiko sa panahon ng pagpapatakbo ng algorithm. Sila ay dinisenyo ng isang “anchor register” strategy upang magtipid ng paggamit ng qubit, na ganap na isinasaalang-alang ang reversibility requirement ng quantum computing at nagpapaginhawa sa kahinaan ng mga qubit na hindi maaaring simpleng ma-overwrite o ma-release. Ito ay pinayagan ang pag-aaral na magamit lamang 31 qubits, at ang solusyon ay may tagumpay na rate ng 86.71%.

Noong 2019, isang self-defined physics connoisseur na si Joseph Cammidge ay sumulat tungkol sa paggamit ng isang annealing quantum processor, na pinayagan siyang malutas ang traveling salesman problem para sa pitong lungsod at may teoretikal na potensyal na malutas para sa siyam na lungsod kapag naalis ang mga limitasyon sa teknolohiya.

Isang bagong pamamaraan ng kompyutasyon, ang Quantum annealing, ay nagpapakita ng potensyal na malutas ang mga optimization problem nang mas mabilis kaysa sa mga klasikal na pamamaraan. Ang teorya nito ay nangangahulugang ang mga qubit ay makakamit ng isang 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 nakahanap na ang quantum annealer ay maaaring malutas lamang ang isang sukat ng problemang may walong o mas mababang node, at ang pagganap nito ay subpar sa parehong oras at katumpakan kumpara sa klasikal na solver.

Ang paggamit ng quantum computing upang malutas ang TSP problem ay nagpapatuloy na. Higit sa dalawampung taon na ang nakalilipas, noong 2001, isang pag-aaral ay nagsimulang hanapin ang isang quantum algorithm upang malutas ang problemang ito.

Sa papel, si Buckley Hopper ng University of Alabama ay tumingin sa mga quantum algorithm ni Grover at Shor. Naiulat niya na ang algorithm ni Grover ay nagbibigay lamang ng isang square root improvement, na nangangahulugang ito ay hindi makakagawa ng isang klasikal na inaakala na hindi maaaring malutas sa isang quantum computer. Tungkol sa algorithm ni Shor, si Hopper ay nakahanap na ito ay makakagawa ng isang inaakalang hindi maaaring malutas na prime factor problem sa isang quantum machine, ngunit ito ay tanging angkop lamang sa isang partikular na uri ng problemang ito.

Sa kabuuan, si Hopper “ay hindi nakahanap ng isang nakapagpapasiyang resulta para sa isang algorithm para sa pagkalkula ng mga aproksimadong solusyon sa traveling salesman problem.”

Ilang taon pagkatapos nito, ang Institute of Electrical and Electronics Engineers (IEEE) ay ipinakita ng isang bagong algorithm para sa paglutas ng problemang ito, na pinag-ugnay sa mga genetic algorithm at quantum computing. Ang IEEE ay nakahanap na ang mga resulta mula sa aplikasyon ng iminungkahing algorithm sa ilang mga instance ng Traveling Salesman Problem ay mas mahusay kaysa sa mga ibinigay ng mga standard na genetic algorithm.

Pindutin ito upang malaman ang kasalukuyang estado ng quantum computing.

Mga Kompanya na Gumagawa sa Quantum Computing

Ngayon, titingnan natin ang ilang mga pangalan na gumagawa sa pananaliksik at pagbuo ng quantum computing:

#1. IBM

Ang International Business Machines Corporation ay kasangkot sa isang malawak na hanay ng mga sektor, kabilang ang AI, cloud services, IT, client financing, at commercial financing. Ang kompanya ng teknolohiya ay dinadalhan rin ng quantum computing sa pamamagitan ng IBM Quantum Platform, na nagbibigay ng pampubliko at premium na access sa mga serbisyo ng quantum computing sa cloud. Kasama rito ang isang hanay ng mga prototype quantum processor ng IBM, mga tutorial sa quantum computation, at isang interaktibong textbook.

Kamakailan, ang mga siyentipiko ng IBM ay nagsabi na sila ay isang hakbang na malapit sa pag-overcome ng isang hadlang na nagbubukas ng potensyal ng quantum computers. Sa ganito, sila ay ipinakilala ang isang bagong quantum error-correcting code, na sinasabi nilang mas mahusay ng sampung beses kaysa sa mga naunang pamamaraan.

Noong huling bahagi ng taon, ang kompanya ay din ipinakilala ang quantum computer na tinatawag na Condor, na may 1,121 superconducting qubits na inayos sa isang honeycomb pattern. Ang IBM ay din ipinakilala ang IBM Quantum System Two, ang unang modular quantum computer at quantum-centric supercomputing architecture, na maaaring pataasin ng mga chip na ilalabas sa loob ng limang taon.

Sa isang market cap ng $175 bilyon, ang mga stock ng IBM ay tumataas sa $190.86, tumaas ng 16.66% year-to-date (YTD). Ang IBM ay nag-post ng revenue (TTM) ng $61.86 bilyon habang mayroong EPS (TTM) ng 8.03, P/E (TTM) ng 23.76, at ROE (TTM) ng 33.36%. Ang kompanya ay nagbabayad ng dividend yield ng 3.48%.

#2. D-Wave Systems

Ang kompanyang ito ng quantum computing ay nagbuo at nagbigay ng mga sistema, software, at serbisyo na may kaugnayan. Ang mga produkto nito ay kinabibilangan ng The Leap at The Advantage, at nagbibigay ng mga quantum application para sa scheduling, logistics, drug discovery, manufacturing processes, at marami pa.

Noong nakaraang buwan, sinabi ng D-Wave na ang mga quantum machine ay maaaring malutas ang mga problemang may tunay na aplikasyon nang mas mabilis kaysa sa anumang ordinaryong computer. Noong simula ng taon, ang kompanya ay ipinakilala ang isang quantum computer na may 1,200 qubits, 10,000 couplers, at 20x mas mabilis na oras-sa-solusyon sa mga hard optimization problem.

Ang mga stock ng kompanya ay kasalukuyang tumataas sa $1.86, tumaas ng 138.6% year-to-date (YTD), na may market capitalization ng $267 milyon. Ito ay nag-ulat ng $8.247 milyon sa mga benta (TTM), -0.66 EPS (TTM), at -3.19 P/E (TTM), at ipinakilala ang higit sa 20% na paglago sa mga benta para sa Q4 at year-end 2023 resulta, habang ang mga booking ay tumaas ng 34% at 89%, ayon sa pagkakabanggit.

Kahanga-hanga, ang CEO ng kompanya, si Dr. Alan Baratz, ay idineklara ang momentum ng kompanya, na binanggit ang multi-year na estratehikong pakikipagtulungan sa Zapata AI, ang pagpapakilala ng 1,200+ qubit Advantage2 prototype, ang mga pinagsamang operasyon sa NEC Australia at Deloitte Canada, at ang pagtatalaga ng dating Homeland Security Secretary na si Kirstjen Nielsen sa board of directors.

Kongklusyon

Ang merkado para sa quantum computing ay inaasahang aabot sa $6.5 bilyon sa 2028, at ang potensyal nito na malutas ang Traveling Salesman Problem (TSP) ay may mga epekto sa maraming industriya, tulad ng manufacturing, logistics, supply chain management, e-commerce, transportation, at research. Sa katunayan, ito ay maaaring magdulot ng mga malalaking benepisyo, partikular sa pagtaas ng produktibidad, pagbaba ng mga gastos, at pagsulong ng inobasyon sa iba’t ibang sektor.

Pindutin ito para sa listahan ng limang pinakamahusay na kompanya ng quantum computing.