Untuk menyelesaikan tugas optimasi yang paling sulit, cukup tambahkan laser

Perangkat aneh yang dikenal sebagai Ising Optical Machine mampu mengendalikan lalu lintas udara dan membantu jadwal pertandingan NFL.

Tahun lalu, kegagalan dalam sistem distribusi antara karyawan American Airlines dapat menyebabkan terganggunya jadwal ribuan penerbangan selama musim liburan. Kesalahan memungkinkan pilot untuk menolak penerbangan tanpa digantikan oleh pilot lain, dan sekitar 15.000 penerbangan terancam. Dan meskipun maskapai berhasil melacak masalah dalam waktu dan mendistribusikan karyawan , kekacauan ini menjadi pengingat betapa kita bergantung pada komputer dalam mengatur jadwal kerja sejumlah besar layanan dan fungsi, di mana komunitas kita sekarang sepenuhnya bergantung.

Misalnya, semua maskapai besar memiliki algoritma optimisasi grafik canggih yang membandingkan pilot dan penerbangan. Dan meskipun insiden dengan American Airlines tidak terjadi secara langsung melalui kesalahan algoritme, hasilnya bisa serupa. Penolakan semacam itu akan menyebabkan ratusan ribu orang dalam situasi yang sulit atau sangat tidak nyaman saat maskapai mencari jalan keluar dari situasi tersebut.

Kemenangan sains algoritmik dan hukum Moore adalah bahwa kita sekarang dapat mendekati banyak tugas optimasi yang kompleks, termasuk bidang-bidang seperti transportasi, logistik, dan penjadwalan. Sebagian besar dunia modern tidak akan dapat berfungsi secara normal tanpa algoritma ini: setiap tahun 50.000 kapal barang mengangkut barang, 25.000 TWh listrik dihasilkan, dan router membawa 1 Zettabyte lalu lintas melalui diri mereka sendiri. Semua ini akan bekerja jauh lebih efisien. Namun, organisasi sering bekerja dengan solusi suboptimal karena tenggat waktu yang ketat dan kurangnya sumber daya komputer yang tersedia. Selain itu, masih ada banyak peluang untuk meningkatkan metode yang kami gunakan untuk membantu menyelesaikan sebagian besar masalah pengoptimalan.

Mengingat pentingnya optimasi dan fakta bahwa era peningkatan stabil dan utama dalam kecepatan prosesor tampaknya akan segera berakhir, para peneliti mulai mempelajari pertanyaan apakah mesin yang dirancang khusus untuk optimasi dapat secara signifikan meningkatkan kemampuan kita untuk memecahkan masalah yang kompleks.

Salah satu pendekatan yang menjanjikan adalah pengembangan mesin optik yang dirancang untuk optimisasi. Sekelompok ilmuwan dari Universitas Stanford (yang termasuk penulis artikel), yang dipimpin oleh Yoshihik Yamamoto, memulai studi ini tujuh tahun lalu. Sekarang topik ini sedang dipelajari oleh beberapa kelompok ilmuwan, serta para peneliti dari laboratorium HP dan NTT . Setelah bertahun-tahun bekerja, ada kepercayaan yang tumbuh bahwa setidaknya satu dari kelompok-kelompok ini suatu hari nanti akan dapat menciptakan mesin yang dapat membantu kita mendekati beberapa masalah optimasi yang paling sulit yang dibutuhkan industri modern untuk menyelesaikannya.


Tugas wiraniaga: kompleksitas tugas seperti menemukan jalur terpendek antara beberapa titik meningkat dengan jumlah titik. Memodelkan mereka dengan kedok Ising masalah optimasi dapat membantu menyelesaikannya lebih cepat.

Ingat masalah salesman klasik, di mana salesman bergerak dari kota ke kota, menjual barang. Dia tidak ingin membuang waktu dan uang untuk bensin. Ini adalah tugas pengoptimalan, yang tujuannya adalah untuk menemukan jalan terpendek bagi penjual, mengingat bahwa ia perlu mencapai setiap titik satu kali, dan pada akhir perjalanan ia ingin kembali ke tempat ia mulai.

Untuk lima kota, masalahnya diselesaikan dengan sederhana. Ini dapat dihitung hanya dengan mempertimbangkan semua 12 jalur . Namun, jika pekerja keras-penjual berniat mengunjungi 50 kota, maka metode pencarian yang menganggap semua jalur yang mungkin ada akan tak tertahankan - akan ada lebih banyak jalur ini daripada jumlah yang baru , atau 10 ⁶⁰ - satu dan 60 nol.

Solusi yang mungkin untuk masalah ini dapat diberikan kepada kami oleh algoritma yang menggunakan jalur pintas yang berbeda dan perkiraan yang masuk akal. Tetapi bahkan yang terbaik dari mereka dapat membuat komputer yang paling kuat berpikir. Dalam sebuah contoh baru-baru ini, Universitas Waterloo dari Kanada berusaha menemukan jalur terpendek antara hampir 50.000 kota di Amerika Serikat yang ada dalam daftar nasional tempat-tempat bersejarah dan membuktikan kebenaran keputusannya. Untuk melakukan ini, ia menggunakan 310 prosesor kuat yang bekerja tanpa henti selama 9 bulan.

Tetapi optimasi melibatkan lebih banyak tugas daripada hanya tugas salesman. Tantangan lain adalah penjadwalan. Misalnya, Liga Sepak Bola Nasional di Amerika Serikat setiap tahun harus menjadwalkan beberapa ratus pertandingan, sambil berusaha mematuhi ribuan peraturan, yang, misalnya, melarang tim bermain lebih dari tiga pertandingan di bidang mereka sendiri secara berturut-turut. Untuk mengatasi masalah ini, pada 2017, NFL menggunakan sekelompok 400 komputer .


Ising Optimization : dalam masalah Ising ini, energi dari sistem lebih rendah ketika spin elektron diarahkan ke arah yang berlawanan dengan spin tetangga. Sistem yang dapat menemukan keadaan dengan energi minimal dalam model Ising dapat membantu mempercepat solusi masalah optimisasi yang kompleks.

Perusahaan manufaktur perlu merencanakan perawatan mesin. Universitas membutuhkan jadwal. Layanan surat perlu merencanakan rute pengiriman. Kota-kota besar, seperti Beijing atau Tokyo, akan senang belajar bagaimana mengelola secara efektif arus jutaan mobil yang mencoba melaju di jalan-jalan mereka selama jam-jam sibuk. Tugas-tugas ini dapat mencakup ratusan atau ribuan acara yang perlu direncanakan, dan dalam banyak kasus, solusi praktis masih belum tersedia, karena mereka memerlukan terlalu banyak waktu komputer atau terlalu banyak komputer.

Selama bertahun-tahun, para peneliti telah mencoba membuat mesin khusus untuk menyelesaikan masalah optimisasi. Pada pertengahan 1980-an, David Tank, kemudian bekerja di AT&T Bell labs, dan John Hopfield, keduanya bekerja di AT&T Bell dan Caltech, menyarankan menggunakan sirkuit elektronik analog yang mewakili jaringan saraf untuk menyelesaikan masalah optimisasi seperti masalah salesman keliling. Pekerjaan mereka memunculkan penelitian puluhan tahun di bidang ini. Kemudian, pada 1994, Leonard Edleman dari University of Southern California, menemukan bahwa secara teori, DNA dapat digunakan untuk menyelesaikan masalah jenis ini. Idenya memunculkan kesibukan penelitian yang serupa. Namun, upaya ini untuk mengembangkan pendekatan yang baru dan efektif secara radikal untuk menyelesaikan masalah optimisasi telah mengarah pada alternatif praktis untuk komputer dan teknologi konvensional, yang hingga kini tetap menjadi alat utama untuk memecahkan masalah tersebut.

Upaya untuk membuat mesin optik khusus yang mampu menyelesaikan masalah optimisasi terkonsentrasi pada salah satu masalah ini, yang dikenal sebagai Ising optimisasi. Dia dinamai sesuai dengan fisikawan Ernst Ising, karya terkenal pada model momen magnetik dan penjelasannya tentang transisi antara berbagai kondisi magnetik. Ternyata banyak masalah optimisasi umum, termasuk jalur penjadwalan dan pencarian, dapat dengan mudah diubah menjadi Mengatasi masalah optimisasi.

Untuk memahami bagaimana model Ising terkait dengan optimasi, Anda harus mulai dengan menggunakannya dalam fisika untuk memahami magnet. Pertimbangkan batang magnet konvensional. Dengan menggunakan model Ising, orang dapat membayangkan sebuah batang magnet, sebagai kisi atom tiga dimensi, di mana masing-masing atom itu sendiri adalah batang magnet. Elektron dalam atom memiliki sifat yang disebut spin. Putaran elektron valensi - terletak di kulit terluar atom - diarahkan ke atas atau ke bawah. Arah putaran menentukan magnetisasi material. Jika semua punggung diarahkan ke atas, material akan termagnetisasi. Jika turun, materialnya juga bermagnet - hanya dengan polaritas yang berlawanan. Jika punggungnya dicampur, bahannya tidak termagnetisasi.

Putaran ini juga saling berinteraksi. Dalam bilah magnet, " energi total " dari dua elektron yang berdekatan lebih rendah jika spinnya sejajar - yaitu, mereka diarahkan ke arah yang sama. Sebaliknya, energi totalnya lebih tinggi jika putarannya multidireksional.


Mesin Ising Optik: osilator parametrik optik (OPO) dengan umpan balik pengukuran dapat menyelesaikan masalah optimisasi yang dinyatakan dalam bentuk model Ising - satu set putaran elektron dan pengaruhnya satu sama lain. Fase pulsa optik dalam OPO mewakili putaran, dan efeknya dimasukkan ke dalam array gerbang yang dapat diprogram pengguna ( PPM ). Diperlukan untuk menyelesaikan sekitar seratus melewati sistem sebelum impuls dalam OPO menjadi cukup kuat untuk menghasilkan solusi untuk masalah tersebut.

Dalam model Ising, kami merangkum energi interaksi antara spin masing-masing pasangan elektron dalam satu set atom. Karena jumlah energi tergantung pada apakah putaran disejajarkan atau tidak, energi total himpunan tergantung pada arah semua putaran sistem. Dengan demikian, tugas umum dari optimasi Ising adalah untuk menentukan dalam keadaan apa putaran harus dalam rangka untuk meminimalkan energi sistem.

Dalam model paling sederhana, diyakini bahwa hanya putaran yang berdekatan berinteraksi. Namun, dalam masalah umum Ising optimasi, setiap putaran dapat berinteraksi dengan yang lain, terlepas dari jarak, dan tanda dan kekuatan interaksi ini dapat menjadi unik untuk setiap pasangan punggung. Dalam formulasi umum seperti itu, masalah ini sangat sulit dipecahkan - seperti halnya memecahkan masalah seorang penjual yang mengunjungi ratusan ribu pembeli potensial. Jika kita dapat menemukan cara untuk dengan cepat menyelesaikan masalah optimasi Ising, dan cara untuk berbicara tentang masalah salesman keliling dan masalah serupa dengan cara yang sama seperti masalah Ising, kita mungkin dapat menyelesaikan masalah ini dengan cepat juga. Energi sistem minimum dalam masalah Ising akan mewakili rute tercepat antar kota, solusi paling efektif untuk mengemas kapal kargo, atau masalah optimasi lainnya yang kami butuhkan.

Jadi, bagaimana Anda mengubah jalur salesman keliling menjadi punggung? Tugas utama adalah membangun kepatuhan: kita perlu menyajikan masalah optimisasi kita dalam bentuk di mana mesin yang dirancang untuk menyelesaikan Ising masalah optimasi dapat menyelesaikannya. Pertama, Anda perlu membandingkan masalah optimasi awal - misalnya, menemukan cara untuk penjual penyedot debu - dengan satu set putaran, dan menentukan bagaimana putaran mempengaruhi satu sama lain. Berkat studi yang dilakukan dalam beberapa dekade terakhir dalam ilmu komputer dan riset operasi , perbandingan berbagai masalah optimisasi dengan formulir Ising secara umum diketahui .

Namun, sulit untuk bekerja dengan masing-masing atom dan putaran elektronnya, jadi kami berkonsentrasi pada pembuatan mesin yang mengimplementasikan model Ising menggunakan pulsa cahaya alih-alih putaran elektron. Masalah Ising dibandingkan dengan momenta dan interaksi di antara mereka. Hasilnya dievaluasi dalam hal energi total masalah, dan keadaan dengan energi minimal dianggap sebagai solusi optimal. Kemudian keputusan ini diterjemahkan ke dalam bahasa yang masuk akal untuk tugas asli - misalnya, dengan cara terpendek seorang salesman.

Kunci kemampuan prototipe kami untuk mencocokkan putaran dengan pulsa cahaya adalah OPO, perangkat seperti laser. Tetapi OPO, tidak seperti laser konvensional, menghasilkan cahaya yang persis dalam fase, atau tepatnya dalam antiphase, untuk beberapa cahaya dasar. Ini adalah persis apa yang diperlukan untuk mewakili keadaan biner dari putaran, naik dan turun. Kita dapat membayangkan putaran yang diarahkan ke atas sebagai keadaan di mana cahaya OPO berada dalam fase dengan basisnya, dan sebaliknya, putaran yang diarahkan ke bawah berhubungan dengan cahaya dalam antiphase.

Ada beberapa cara untuk membuat mesin Ising menggunakan OPO. Kelompok-kelompok dari NTT, Caltech, Cornell, dan Columbia, antara lain, memiliki pendekatan yang berbeda. Prototipe mesin Ising, pertama kali ditampilkan di Stanford dalam percobaan yang dipimpin oleh Alireza Marandi (yang sekarang bekerja di Caltech), menggunakan teknologi yang kami terus bekerja dengan lebih jauh: multiplexing time-division multiplexing dan koneksi optik.

Mari kita lihat istilah yang sulit ini. Kami mulai dengan sumber laser berdenyut. Sumber mengirimkan pulsa cahaya simultan yang berlangsung beberapa picoseconds dalam dua arah. Impuls pertama menjadi dasar; ia terbelah, dan berjalan di sepanjang dua jalan yang berbeda.

Yang kedua digunakan sebagai sumber energi untuk OPO: itu merangsang kristal dalam OPO, yang memancarkan pulsa foton. Setiap pulsa ditransmisikan ke koil kabel loop optik beberapa ratus meter, tergantung pada jumlah pulsa yang kita butuhkan. Ada ratusan atau bahkan ribuan pulsa OPO di cincin ini, dan mereka akan mengejar satu per satu lingkaran, melewati kristal itu berulang-ulang.


Atas: Penulis artikel dan mantan rekan laboratoriumnya, Alireza Marandi, sedang melihat prototipe komputer optik Ising.
Bawah: sebagian besar peristiwa terjadi di dalam gulungan kabel optik

Fase dari pulsa-pulsa ini akan memainkan peran spin dari model Ising. Tetapi segera setelah penciptaan mereka, sebelum mereka melewati loop beberapa kali, mereka sangat lemah sehingga fase mereka tidak didefinisikan dengan baik. Cara kita membuat mereka berinteraksi pada akhirnya akan memberi mereka fase akhir dan memberi kita solusi untuk masalah Ising kita.

Ingat cahaya dasar dari deskripsi percobaan? Pada satu titik dalam loop adalah pembagi yang memilih sebagian kecil dari setiap pulsa, yang dibandingkan dengan pulsa dasar di detektor homodyne. Tegangan keluaran detektor berisi informasi tentang fase dan amplitudo detektor. Sinyal ini didigitalkan dan dimasukkan ke dalam PPVM. Di dalamnya, masalah Ising itu sendiri disajikan.

Ingatlah bahwa untuk menyelesaikan masalah Ising berarti menemukan keadaan energi minimum untuk satu set spin di mana spin berinteraksi dengan cara yang berbeda, dan interaksi ini menambah energi tambahan ke energi total sistem. Dalam HME, setiap impuls menunjukkan putaran. Oleh karena itu, untuk setiap pulsa - dan dalam pengaturan kami kami menggunakan 100 - PPMM melakukan perhitungan, yang mencakup pengukuran rekaman semua pulsa lainnya, yang, menurut masalah Ising, harus memengaruhi putaran yang dipertimbangkan. Prosesor kemudian menerapkan perhitungan ke pengaturan modulator intensitas dan modulator fase yang terletak di salah satu jalur pulsa basis. Denyut nadi termodifikasi dimasukkan ke dalam cincin kabel serat optik, di mana pulsa OPO mengintip.

Sangat penting untuk memilih momen yang tepat - kita membutuhkan pulsa basis gabungan untuk bergabung dengan pulsa OPO yang tepat. Jika dilakukan dengan benar, kedua pulsa akan bercampur. Tergantung pada apakah mereka dalam fase atau tidak, impuls yang dimasukkan ke dalam sistem cenderung impuls OPO untuk mewakili putaran diarahkan baik ke atas atau ke bawah.

Untuk setiap pulsa OPO dalam loop, kami mengulangi seluruh proses ini, dan untuk mencapai tahap fase terakhir, pulsa dapat melakukan perjalanan puluhan ribu kali sepanjang seluruh panjang loop. Setelah itu, komputer yang terpisah membaca serangkaian fase, menafsirkannya sebagai elektron dari masalah Ising dengan berputar menunjuk ke atas atau ke bawah, dan kemudian mengubahnya menjadi solusi yang berarti untuk masalah pengoptimalan awal yang perlu Anda pecahkan.

Dalam percobaan kami, pertama-tama kami membuat sistem dengan empat putaran, dan kemudian dengan 16 putaran. Parameter tugas didasarkan pada perangkat keras dalam instalasi dalam bentuk segmen bercabang dari kabel optik dengan panjang tertentu. Dalam percobaan ini, kami berhasil menemukan keadaan energi minimum, dan ini memberi kami motivasi untuk mengembangkan pendekatan ini. Pada tahun 2016, kami menciptakan mesin umpan balik berbasis PPVM yang mampu menyelesaikan masalah Ising dengan 100 putaran. Perbandingan kecepatan fasilitas kami dengan sistem khusus, termasuk peralatan " quantum annealing " NASA, memberi kami keyakinan bahwa mesin OPO Ising dapat menjadi pengoptimal yang efisien.

Hasilnya cukup menjanjikan, tetapi kami masih harus banyak belajar sebelum kami memahami apakah pendekatan optik semacam itu bahkan dapat mengungguli prosesor konvensional dalam menyelesaikan masalah optimasi praktis. Ada kemungkinan bahwa kemampuan mesin untuk memecahkan masalah dapat ditingkatkan dengan menggunakan status cahaya kuantum, yang sangat sulit untuk disimulasikan. Kami hanya mendekati solusi dari banyak pertanyaan seperti itu, dan kami berencana dalam beberapa tahun ke depan untuk mempelajari interaksi yang sangat menarik antara teori dan eksperimen, mengembangkan jenis komputer baru ini.