Løsning af komplekse problemer med lysets hastighed

Mange af de mest udfordrende optimeringsproblemer, man støder på i forskellige videnskabs- og ingeniørdiscipliner, fra biologi og lægemiddelopdagelse til routing og planlægning kan reduceres til NP-komplette problemer. Intuitivt set, NP-komplette problemer er "svære at løse", fordi antallet af operationer, der skal udføres for at finde løsningen, vokser eksponentielt med problemets størrelse. Almindeligheden af ​​NP-komplette problemer har ført til udviklingen af ​​dedikeret hardware (såsom optisk annealing og kvante annealing maskiner som "D-Wave") og specielle algoritmer (heuristiske algoritmer som simuleret annealing).

For nylig, der har været en stigende interesse for at løse disse hårde kombinatoriske problemer ved at designe optiske maskiner. Disse optiske maskiner består af et sæt optiske transformationer, der overføres til et optisk signal, så det optiske signal vil kode løsningen på problemet efter en vis mængde beregning. Sådanne maskiner kunne drage fordel af de grundlæggende fordele ved optisk hardware integreret i siliciumfotonik, såsom lavt tab, parallel behandling, optisk passivitet ved lav optisk effekt og robust skalerbarhed muliggjort af industriens udvikling af fremstillingsprocesser. Imidlertid, udvikling af kompakt og hurtig fotonisk hardware med dedikerede algoritmer, som optimalt udnytter denne hardwares kapacitet, har manglet.

I dag, vejen til at løse NP-komplette problemer med integreret fotonik er åben på grund af Charles Roques-Carmes arbejde, Dr. Yichen Shen, Cristian Zanoci, Mihika Prabhu, Fadi Atieh, Dr. Li Jing, Dr. Tena Dubček, Chenkai Mao, Miles Johnson, Prof. Vladimir Čeperić, Prof. Dirk Englund, Prof. John Joannopoulos, og prof. Marin Soljačić fra MIT og Institute for Soldier Nanotechnologies, udgivet i Naturkommunikation . I dette arbejde, MIT-teamet udviklede en algoritme dedikeret til at løse det velkendte NP-komplette Ising-problem med fotonik-hardware.

Oprindeligt foreslået til at modellere magnetiske systemer, Ising-modellen beskriver et netværk af spins, der kun kan pege op eller ned. Hvert spins energi afhænger af dets interaktion med tilstødende spins - i en ferromagnet, for eksempel, den positive interaktion mellem nærmeste naboer vil tilskynde hvert spin til at tilpasse sig dets nærmeste naboer. En Ising-maskine vil have tendens til at finde den spin-konfiguration, der minimerer spinnetværkets samlede energi. Denne løsning kan derefter oversættes til løsningen af ​​et andet optimeringsproblem.

Heuristiske Ising maskiner, som den, der er udviklet af MIT-teamet, giver kun en kandidatløsning på problemet (som er, gennemsnitlig, tæt på den optimale løsning). Imidlertid, algoritmer, der altid finder den nøjagtige løsning på problemet, er svære at anvende på store problemstørrelser, da de ofte skulle løbe i timevis, hvis ikke dage, at afslutte. Derfor, heuristiske algoritmer er et alternativ til eksakte algoritmer, da de giver hurtige og billige løsninger på svære problemer.

Forskerne blev styret af deres viden om grundlæggende fotonik. Professor Marin Soljačić fra MIT forklarer:"Optisk databehandling er et meget gammelt forskningsfelt. Derfor, vi var nødt til at identificere, hvilke nyere fremskridt inden for fotonisk hardware, der kunne gøre en forskel. Med andre ord, vi var nødt til at identificere værdien af ​​moderne fotonik." Kandidatstuderende Charles Roques-Carmes tilføjer:"Vi identificerede denne værdiproposition som:(a) at udføre hurtig og billig multiplikation med fast matrix og; (b) at udføre støjende beregninger, hvilket betyder, at resultatet af beregningen varierer lidt fra den ene kørsel til den anden, lidt som at vende en mønt. Derfor, disse to elementer er byggestenene i vores arbejde."

Mens du udvikler denne algoritme og benchmarker den på forskellige problemer, forskerne opdagede en række relaterede algoritmer, der også kunne implementeres i fotonik for at finde løsninger endnu hurtigere. Postdoc associeret Dr. Yichen Shen er begejstret for udsigten til dette arbejde:"Området med at forbedre computerkapaciteten med integreret fotonik blomstrer i øjeblikket, og vi tror på, at dette arbejde kan være en del af det. Da den algoritme, vi udviklede optimalt udnytter styrkerne og svaghederne ved fotonisk hardware, vi håber, det kunne finde en kortsigtet anvendelse." MIT-forskerholdet arbejder i øjeblikket i samarbejde med andre på at realisere proof-of-concept-eksperimenter og benchmarke deres algoritme på fotonisk hardware, kontra andre fotoniske maskiner og konventionelle algoritmer, der kører på computere.