Menyelesaikan ‘Masalah Penjual Keliling’ melalui Komputasi Kuantum

Masalah algoritma klasik dalam bidang ilmu komputer yang dikenal sebagai Traveling Salesman Problem (TSP) merupakan contoh utama dari masalah optimisasi kombinatorial.

Apa sebenarnya TSP? Klasik matematika ini melibatkan pencarian rute terpendek yang memungkinkan mengunjungi N kota tepat satu kali sebelum kembali ke kota asal. Namun, seiring bertambahnya jumlah kota, jumlah rute yang mungkin juga meningkat dan waktu komputasi untuk menemukan solusi optimal menjadi lebih lama. Meskipun masalah ini dapat diselesaikan dengan metode perkiraan, komputer kuantum dapat memberikan solusi yang jauh lebih baik dan jauh lebih cepat.

Inilah yang ditunjukkan secara tepat oleh tim Prof. Dr. Jens Eisert: bahwa masalah semacam itu dapat diselesaikan dengan lebih baik dan lebih cepat menggunakan komputer kuantum.

Komputasi kuantum memanfaatkan perangkat keras dan algoritma yang memanfaatkan mekanika kuantum untuk menyelesaikan masalah kompleks yang berada di luar jangkauan komputasi konvensional, termasuk superkomputer. Meskipun memiliki kekuatan besar, superkomputer—komputer klasik raksasa dengan ribuan inti CPU dan GPU—terbatas oleh ketergantungan mereka pada teknologi transistor abad ke-20 saat menyelesaikan masalah dengan tingkat kompleksitas tinggi.

Di sinilah fisika kuantum berperan. Berbeda dengan komputer klasik yang mengkodekan informasi dalam bit biner (0 dan 1), komputer kuantum menggunakan quantum bit atau qubit untuk menjalankan algoritma kuantum multidimensi.

Selain itu, tidak seperti komputer konvensional yang menggunakan kipas untuk pendinginan, komputer kuantum memerlukan prosesor kuantumnya dipertahankan pada suhu sangat rendah agar keadaan kuantumnya tetap terjaga. Hal ini dicapai melalui superfluida yang didinginkan secara ekstrem.

Superkonduktor adalah material yang menunjukkan efek mekanika kuantum kritis, memungkinkan elektron bergerak melaluinya tanpa hambatan. Saat elektron melewati, mereka berpasangan untuk membawa muatan melintasi penghalang. Ketika dua superkonduktor ditempatkan di masing-masing sisi isolator, terbentuklah sambungan Josephson, yang digunakan untuk mengendalikan qubit superkonduktor.

Qubit berguna dalam tugas penting menempatkan informasi kuantumnya ke dalam keadaan superposisi, yaitu kombinasi dari konfigurasi qubit yang mungkin. Kelompok qubit dalam superposisi dapat menciptakan ruang komputasi kompleks multidimensi di mana masalah rumit dapat direpresentasikan.

Di sini, melalui keterikatan dua qubit, perubahan pada satu dapat memengaruhi yang lain secara langsung, sementara ketika qubit yang terikat ini ditempatkan dalam keadaan superposisi, muncul banyak probabilitas. Komputasi pada komputer kuantum bekerja dengan menyiapkan superposisi dari semua kemungkinan keadaan komputasi, dan melalui interferensi, solusi ditemukan.

Tentu saja, membangun komputer kuantum dengan banyak qubit merupakan prosedur yang sangat kompleks, meskipun beberapa metode sedang dieksplorasi untuk mengetahui apa yang dapat dicapai oleh komputer semacam itu.

Menurut Eisert, yang memimpin kelompok riset gabungan di Helmholtz-Zentrum Berlin (HZB), sebuah pusat riset material energi, dan universitas riset publik Freie Universität Berlin:

“Ada banyak mitos tentang hal ini, dan kadang-kadang ada pula sejumlah besar omong kosong dan hype. Namun, kami telah mendekati masalah ini secara ketat, menggunakan metode matematis, dan menghasilkan hasil yang solid mengenai topik tersebut. Di atas semua itu, kami telah memperjelas dalam arti apa saja keuntungan yang mungkin ada.”

Masalah Penjual Keliling yang Krusial

Sebagai masalah optimisasi, TSP memiliki pentingnya ekonomi yang besar dalam industri logistik dan rantai pasokan. Masalah ini termasuk dalam kategori lebih luas dari masalah optimisasi kombinatorial, yang juga mencakup penjadwalan pekerjaan, alokasi sumber daya, optimisasi portofolio, bahkan pelipatan protein, semuanya penting bagi berbagai sektor.

Mengingat signifikansi sosial dan ekonomi dari masalah-masalah ini, mereka telah menjadi subjek penelitian intensif. Oleh karena itu, menemukan jawaban untuk masalah seperti rantai pasokan paling efisien dan rute pengiriman termurah memberikan dampak positif pada kehidupan sehari-hari kita.

Namun, mengoptimalkan rute pengiriman untuk banyak tujuan sambil mempertimbangkan berbagai kendala seperti kemacetan lalu lintas, meningkatnya biaya operasional, perubahan rute mendadak, janji bisnis menit terakhir, dan permintaan pelanggan membuat TSP semakin menantang untuk diselesaikan. Meskipun tantangan ini, menyelesaikan TSP sangat penting untuk pengiriman barang yang efisien, yang memastikan model bisnis yang layak.

Ada banyak manfaat dari menyelesaikan masalah ini, termasuk mengurangi jarak dan jam perjalanan serta menghemat penggunaan bahan bakar. Meminimalkan jarak tempuh dapat membantu mengurangi jejak karbon secara signifikan, yang berdampak pada kualitas udara yang lebih baik, melambatnya perubahan iklim, dan pertumbuhan ekonomi. Selain itu, menyelesaikan TSP dapat membantu pengiriman barang tepat waktu dan pertemuan dengan klien tepat waktu, yang meningkatkan pengalaman pelanggan dan bisnis layanan lapangan.

Seperti yang telah kita lihat, menyelesaikan masalah ini tidak hanya membantu bisnis, tetapi manfaat tersebut juga merembes ke pelanggan, memperkaya pengalaman bagi semua pihak yang terlibat.

Beberapa metode dapat digunakan untuk menyelesaikan masalah TSP. Salah satu metode tersebut adalah pendekatan ‘Brute-Force’, yang menghitung semua kemungkinan permutasi untuk menemukan rute terpendek. Dalam metode branch-and-bound, masalah dipecah menjadi beberapa rangkaian submasalah, dengan solusi pada setiap tahap memengaruhi solusi yang ditemukan pada tahap berikutnya.

Dalam pemrograman dinamis, fokusnya adalah menghindari perhitungan berulang. Sementara itu, Nearest Neighbor adalah algoritma perkiraan di mana Anda memulai dari lokasi awal dan kemudian menuju yang terdekat. Setelah semua kota tercakup, Anda kembali ke titik awal. Meskipun praktis dan relatif cepat, metode ini tidak selalu memberikan rute yang efisien.

Seiring kemajuan teknologi, perencanaan dan optimisasi rute dapat dilakukan jauh lebih efektif. Kecerdasan Buatan (AI), khususnya, juga dapat membantu menyelesaikan masalah ini dengan menganalisis sejumlah besar data secara cepat untuk membantu banyak perusahaan modern membuat keputusan operasional dan strategis.

Komputer kuantum juga sedang diteliti untuk menyelesaikan masalah ini; bagaimanapun, mereka menawarkan percepatan komputasi yang signifikan dibandingkan komputer klasik. Sudah lama diperkirakan bahwa komputer ini dapat membantu meningkatkan perkiraan untuk masalah-masalah tersebut.

Menggunakan Teknik Komputasi Kuantum untuk Menyelesaikan TSP

Sementara komputasi kuantum menarik minat yang besar dan memberikan hasil menjanjikan untuk beberapa masalah, sejauh mana keunggulan kuantum ini masih belum banyak dieksplorasi.

Dengan demikian, studi tersebut memberikan bukti konstruktif penuh bahwa komputer kuantum sebenarnya dapat mengungguli komputer konvensional dalam menemukan perkiraan untuk masalah optimisasi kombinatorial.

Studi terbaru, yang dipimpin oleh Eisert dan rekannya Jean-Pierre Seifert, hanya menggunakan metode analitis untuk mengevaluasi sejauh mana komputer kuantum dengan qubit dapat menyelesaikan masalah TSP.

“Kami cukup mengasumsikan, terlepas dari realisasi fisik, bahwa ada cukup banyak qubit dan melihat kemungkinan melakukan operasi komputasi dengan mereka,” yang menunjukkan kemiripan dengan masalah umum dalam kriptografi, yaitu enkripsi data, jelas Vincent Ulitzsch, mahasiswa Ph.D. di Technical University of Berlin.

Kemudian, tim tersebut menggunakan algoritma Shor, sebuah algoritma kuantum, untuk menemukan faktor prima dari sebuah bilangan bulat dan menyelesaikan subkelas dari masalah optimisasi ini. Dengan itu, waktu komputasi tidak akan meledak lagi seiring bertambahnya jumlah kota. Waktu tersebut hanya akan meningkat secara polinomial, yaitu dengan Nx, di mana x adalah konstanta. Dengan cara ini, solusi yang diperoleh juga secara kualitatif jauh lebih baik daripada yang dihasilkan dari solusi perkiraan menggunakan algoritma konvensional.

Dengan menggunakan konsep kriptografi dan teori pembelajaran komputasional, studi ini memberikan “bukti konstruktif penuh bahwa komputer kuantum memiliki keunggulan super-polynomial dibandingkan komputer klasik dalam memperkirakan masalah optimisasi kombinatorial.”

Studi tersebut juga mencatat bahwa tim peneliti telah membuat kemajuan signifikan pada pertanyaan penting tentang apa yang dapat ditawarkan komputer kuantum potensial untuk memperkirakan solusi masalah optimisasi kombinatorial, yang memiliki dampak sosial dan ekonomi yang besar.

Studi ini didanai oleh Einstein Research Unit, Berlin Mathematics Research Center (MATH+ Cluster of Excellence), BMBF (Hybrid), BMWK (EniQmA), Munich Quantum Valley, dan DFG. Kementerian Federal Pendidikan dan Penelitian Jerman juga memberikan dukungan keuangan.

Menjelajahi Potensi Komputasi Kuantum 

Meskipun merupakan pencapaian besar, ini bukan pertama kalinya komputasi kuantum digunakan untuk menyelesaikan masalah penjual keliling. Telah ada banyak contoh antusias dan peneliti yang mencoba menyelesaikan masalah ini dengan memanfaatkan komputasi kuantum. 

Pada Desember 2022, sebuah paper mengusulkan algoritma kuantum untuk TSP berbasis Grover Adaptive Search (GAS). Di bawah kerangka GAS, terdapat setidaknya dua kesulitan mendasar—solusi mungkin tidak layak, dan jumlah qubit pada komputer kuantum saat ini sangat terbatas dan tidak dapat memenuhi persyaratan minimum, yang membatasi penerapan algoritma kuantum untuk masalah optimisasi kombinatorial.

Dengan demikian, paper tersebut menyempurnakan oracle Hamiltonian Cycle Detection (HCD), yang dapat secara otomatis menghapus solusi yang tidak praktis selama eksekusi algoritma. Mereka juga merancang strategi “anchor register” untuk menghemat penggunaan qubit, sepenuhnya mempertimbangkan persyaratan reversibilitas komputasi kuantum dan mengatasi kesulitan qubit yang digunakan tidak dapat sekadar ditimpa atau dilepaskan. Hal ini memungkinkan studi tersebut hanya membutuhkan 31 qubit, dan solusi tersebut memiliki tingkat keberhasilan sebesar 86,71%.

Pada 2019, seorang ahli fisika mandiri Joseph Cammidge menulis tentang penggunaan prosesor kuantum annealing, yang memungkinkannya menyelesaikan masalah penjual keliling untuk tujuh kota dan memiliki potensi teoretis untuk menyelesaikan sembilan kota setelah batasan teknologi dihilangkan.

Metode komputasi baru, Quantum annealing, telah menunjukkan potensi untuk menyelesaikan masalah optimisasi lebih cepat daripada teknik klasik. Teorinya menyiratkan bahwa qubit akan mencapai keadaan energi rendah optimal ketika didinginkan secara super.

Namun, pada 2021, sebuah studi yang didanai oleh Supply Chain Digital & Data Science, Johnson & Johnson (JNJ ) menemukan bahwa quantum annealer hanya dapat menangani ukuran masalah hingga 8 node atau kurang, dan kinerjanya kurang memuaskan baik dari segi waktu maupun akurasi dibandingkan solver klasik.

Penggunaan komputasi kuantum untuk menyelesaikan masalah TSP telah berlangsung cukup lama. Lebih dari dua dekade yang lalu, pada 2001, sebuah studi mulai mencari algoritma kuantum untuk menyelesaikan masalah tersebut.

Dalam makalah tersebut, Buckley Hopper dari University of Alabama meneliti algoritma kuantum Grover dan Shor. Ia mencatat bahwa algoritma Grover hanya memberikan perbaikan akar kuadrat, yang menyiratkan bahwa ia tidak dapat membuat masalah yang secara klasik tidak dapat dipecahkan menjadi dapat dipecahkan pada komputer kuantum. Sedangkan untuk algoritma Shor, Hopper mengamati bahwa, meskipun dapat mengubah masalah faktor prima yang dianggap tidak dapat dipecahkan menjadi dapat dipecahkan pada mesin kuantum, algoritma ini hanya cocok untuk jenis masalah yang sangat spesifik.

Secara keseluruhan, Hopper “tidak menemukan hasil yang memuaskan untuk algoritma yang menghitung solusi perkiraan untuk masalah penjual keliling.”

Beberapa tahun setelah itu, Institute of Electrical and Electronics Engineers (IEEE) memperkenalkan algoritma baru untuk menyelesaikan masalah tersebut, terinspirasi oleh algoritma genetika dan komputasi kuantum. IEEE menemukan bahwa hasil penerapan algoritma yang diusulkan pada beberapa contoh Traveling Salesman Problem jauh lebih baik dibandingkan yang diberikan oleh algoritma genetika standar.

Klik di sini untuk mempelajari keadaan terkini komputasi kuantum.

Perusahaan yang Bekerja dengan Komputasi Kuantum 

Sekarang, mari kita lihat beberapa nama yang sedang mengerjakan riset dan pengembangan komputasi kuantum:

#1. IBM

International Business Machines Corporation (IBM ) terlibat dalam berbagai sektor, termasuk AI, layanan cloud, TI, pembiayaan klien, dan pembiayaan komersial. Raksasa teknologi ini juga terlibat dalam komputasi kuantum melalui IBM Quantum Platform, yang memberikan akses publik dan premium ke layanan komputasi kuantum berbasis cloud-nya. Layanan tersebut mencakup serangkaian prototipe prosesor kuantum IBM, tutorial tentang komputasi kuantum, dan buku teks interaktif.

Baru-baru ini, ilmuwan IBM menyatakan bahwa mereka selangkah lebih dekat untuk mengatasi hambatan yang membuka potensi revolusioner komputer kuantum. Untuk itu, mereka memperkenalkan kode koreksi kesalahan kuantum baru, yang mereka katakan sekitar sepuluh kali lebih efisien dibandingkan metode sebelumnya.

Pada akhir tahun lalu, perusahaan juga meluncurkan komputer kuantum bernama Condor, dengan 1.121 qubit superkonduktor yang disusun dalam pola sarang lebah. IBM juga memperkenalkan IBM Quantum System Two, komputer kuantum modular pertama mereka dan arsitektur superkomputasi berfokus kuantum, yang dapat diskalakan sehingga dapat ditingkatkan dengan chip yang akan diluncurkan dalam lima tahun ke depan.

Dengan kapitalisasi pasar sebesar $175 miliar, saham IBM diperdagangkan pada $190,86, naik 16,66% sejak awal tahun (YTD). IBM mencatat pendapatan (TTM) sebesar $61,86 miliar dengan EPS (TTM) 8,03, P/E (TTM) 23,76, dan ROE (TTM) 33,36%. Perusahaan membayar dividen dengan hasil 3,48%.

#2. D-Wave Systems

Perusahaan komputasi kuantum ini mengembangkan dan menyediakan sistem, perangkat lunak, serta layanan terkait. Produk-produknya meliputi The Leap dan The Advantage, serta menyediakan aplikasi kuantum untuk penjadwalan, logistik, penemuan obat, proses manufaktur, dan lainnya.

Awal bulan ini, D-Wave menyatakan bahwa mesin kuantum kini dapat menyelesaikan masalah dengan aplikasi dunia nyata lebih cepat daripada komputer biasa mana pun. Pada awal tahun ini, perusahaan mengumumkan komputer kuantum dengan 1.200 qubit, 10.000 coupler, dan waktu penyelesaian 20 kali lebih cepat pada masalah optimisasi yang sulit.

Saham perusahaan saat ini diperdagangkan pada $1,86, naik 138,6% sejak awal tahun (YTD), dengan kapitalisasi pasar $267 juta. Perusahaan melaporkan penjualan sebesar $8,247 juta (TTM), EPS (TTM) -0,66, dan P/E (TTM) -3,19, serta mengumumkan pertumbuhan penjualan lebih dari 20% untuk Q4 dan hasil akhir tahun 2023, sementara pemesanan meningkat masing-masing 34% dan 89%.

Menariknya, CEO perusahaan, Dr. Alan Baratz, menyatakan momentum perusahaan, dengan menyebutkan kemitraan strategis multi-tahun dengan Zapata AI, peluncuran prototipe Advantage2 dengan lebih dari 1.200 qubit, usaha patungan dengan NEC Australia dan Deloitte Canada, serta penunjukan mantan Sekretaris Keamanan Dalam Negeri Kirstjen Nielsen ke dewan direksi.

Kesimpulan

Pasar komputasi kuantum diperkirakan akan mencapai $6,5 miliar pada 2028, dan potensinya untuk menyelesaikan Traveling Salesman Problem (TSP) memiliki implikasi bagi beberapa industri, seperti manufaktur, logistik, manajemen rantai pasokan, e‑commerce, transportasi, dan penelitian. Pada akhirnya, hal ini dapat menghasilkan manfaat yang signifikan, terutama meningkatkan produktivitas, mengurangi biaya, dan mendorong inovasi di berbagai sektor.

Klik di sini untuk daftar lima perusahaan komputasi kuantum terbaik.