Akhirnya, ada masalah yang hanya bisa diselesaikan oleh komputer kuantum

Selama bertahun-tahun, para ilmuwan komputer telah mencari tugas dari jenis tertentu yang hanya dapat diselesaikan oleh komputer kuantum, tetapi bukan komputer klasik, bahkan dari generasi mendatang. Maka mereka menemukan salah satunya.

Pada tahap awal studi komputer kuantum, para ilmuwan komputer mengajukan pertanyaan, jawaban yang menurut pendapat mereka, seharusnya mengungkapkan beberapa kebenaran yang mendalam tentang kemampuan mesin-mesin futuristik ini. 25 tahun kemudian, jawaban untuk itu ditemukan. Dalam sebuah makalah yang diterbitkan pada Mei 2018, ilmuwan komputer Ren Rez dan Avishai Tal menawarkan bukti kuat bahwa kekuatan komputasi komputer kuantum melampaui apa pun yang dapat dicapai oleh komputer klasik.

Rez, seorang profesor di Universitas Princeton dan Wiseman Institute of Science, serta Tal, seorang postdoc dari Universitas Stanford, mengidentifikasi jenis masalah komputasi tertentu. Mereka membuktikan, dengan satu peringatan, bahwa komputer kuantum dapat secara efektif menyelesaikan masalah, dan komputer tradisional akan macet selamanya, mencoba melakukannya. Ilmuwan komputer telah mencari masalah seperti itu sejak tahun 1993, ketika mereka pertama kali mengidentifikasi kelas tugas BQP , yang mencakup semua tugas yang dapat diselesaikan oleh komputer kuantum.

Sejak itu, mereka berharap untuk membedakan kelas tugas BQP yang dikenal sebagai PH, yang mencakup semua tugas yang dapat dilakukan pada komputer klasik apa pun, bahkan yang sangat canggih yang dikembangkan oleh beberapa peradaban masa depan. Kemungkinan kontras seperti itu tergantung pada menemukan masalah yang dimiliki kelas BQP, tetapi tidak untuk kelas PH. Dan sekarang Rez dan Tal telah melakukannya.

Hasil ini tidak membuat komputer kuantum lebih baik daripada klasik dari sudut pandang praktis. Pertama, para ilmuwan komputer teoritis sudah tahu bahwa komputer kuantum mampu menyelesaikan tugas apa pun yang mampu dilakukan komputer klasik. Dan insinyur sedang berjuang untuk memecahkan masalah menciptakan mesin kuantum yang berguna. Tetapi karya Reza dan Tal menunjukkan perbedaan dalam kategori di mana komputer kuantum dan klasik berada - dan bahwa bahkan di dunia di mana komputer klasik telah melampaui batas mimpi, komputer kuantum masih dapat mengungguli mereka.

Kelas kuantum

Tugas dasar informatika teoretis adalah membagi tugas ke dalam kelas kompleksitas. Kelas kompleksitas berisi semua tugas yang dapat diselesaikan dengan sumber daya tertentu, seperti waktu atau memori.

Para ilmuwan, misalnya, telah menemukan algoritma yang efektif yang memeriksa apakah suatu bilangan prima. Namun, mereka tidak dapat menemukan algoritma yang efektif untuk menemukan faktor utama dalam jumlah besar. Oleh karena itu, mereka percaya (walaupun mereka tidak dapat membuktikannya) bahwa kedua masalah ini termasuk kelas kompleksitas yang berbeda.

Dua kelas kesulitan yang terkenal adalah P dan NP. P adalah semua tugas yang bisa diselesaikan dengan cepat oleh komputer klasik. (Masalahnya "adalah bilangan prima?" Milik P). NP mencakup semua tugas yang tidak harus diselesaikan oleh komputer klasik dengan cepat, tetapi kebenaran dari solusi yang ada, yang mana dapat dengan cepat diperiksa. ("Apa faktor utama angka?" Milik NP). Para ilmuwan percaya bahwa kelas P dan NP berbeda, tetapi tugas untuk membuktikan perbedaan ini adalah yang paling sulit dan paling penting dari masalah terbuka di bidang ini.


PH berisi NP yang berisi P. Apakah kelas BQP terpisah dari PH?

Pada tahun 1993, ilmuwan komputer Ethan Bernstein dan Umesh Wazirani mendefinisikan kelas kompleksitas baru, yang mereka sebut BQP, atau "waktu kuantum-polinomial dengan batasan probabilitas kesalahan." Mereka mendefinisikan kelas sebagai berisi semua tugas pengambilan keputusan - tugas dengan jawaban "ya" atau "tidak" - yang dapat diselesaikan komputer kuantum secara efektif. Sekitar waktu yang sama, mereka membuktikan bahwa komputer kuantum mampu menyelesaikan semua tugas yang mampu dilakukan oleh komputer klasik. Artinya, BQP berisi semua tugas yang terkandung dalam P.

Contoh lain dari kelas tugas individu. Masalah penjual bertanya apakah jalur yang melewati kota-kota tertentu lebih pendek dari jarak yang diberikan. Tugas seperti itu ada di NP. Tugas yang lebih sulit bertanya apakah jarak ini adalah jalur terpendek melalui kota-kota ini. Tugas seperti itu ada di PH.

Namun, mereka tidak dapat menentukan apakah BQP berisi tugas yang tidak ada dalam kelas tugas penting lainnya, yang dikenal sebagai PH atau "hierarki polinomial". PH adalah generalisasi dari NP. Ini berisi semua tugas yang bisa diperoleh dengan memulai dengan tugas dari NP, dan menyulitkannya, menambahkan pernyataan klarifikasi seperti "apakah" dan "untuk semua orang". Komputer klasik masih tidak dapat menyelesaikan sebagian besar masalah dari PH, tetapi kelas ini dapat dianggap sebagai kelas masalah yang dapat diselesaikan oleh komputer klasik jika ternyata P setara dengan NP. Dengan kata lain, untuk membandingkan BQP dan PH, perlu untuk menentukan apakah komputer kuantum memiliki keunggulan dibandingkan komputer klasik, yang akan tetap ada bahkan jika komputer klasik tiba-tiba belajar untuk memecahkan lebih banyak masalah daripada yang dapat mereka pecahkan saat ini.

"PH adalah salah satu kelas kompleksitas paling sederhana yang ada," kata Scott Aaronson , seorang spesialis IT di University of Texas di Austin. "Jadi kami agak ingin tahu tempat komputasi kuantum dalam dunia kompleksitas klasik."

Cara terbaik untuk memisahkan dua kelas kesulitan adalah menemukan masalah yang terbukti termasuk dalam salah satu dari mereka dan tidak termasuk dalam yang lain. Namun, karena kombinasi kendala mendasar dan teknis, tugas seperti itu sangat sulit ditemukan.

Untuk menemukan tugas yang dimiliki BQP, tetapi tidak untuk PH, Anda perlu mendefinisikan sesuatu yang "komputer klasik, menurut definisi, bahkan tidak dapat memeriksa jawabannya secara efektif, belum lagi menemukannya," kata Aaronson. "Ini menghilangkan banyak tugas yang kami kerjakan dalam ilmu komputer."

Tanya oracle

Tantangan. Misalkan kita memiliki dua generator bilangan acak, yang masing-masing menghasilkan urutan angka. Pertanyaan ke komputer: apakah kedua sekuens ini benar-benar independen satu sama lain, atau mereka entah bagaimana terhubung secara tidak kasat mata (misalnya, apakah satu urutan diperoleh oleh transformasi Fourier yang lain)? Aaronson memperkenalkan tugas “furrelation” ini pada tahun 2009 dan membuktikan bahwa itu adalah milik BQP. Langkah kedua, yang lebih sulit tetap - untuk membuktikan bahwa furrelation tidak termasuk dalam PH.


Ran rez

Dalam arti tertentu, inilah yang dilakukan oleh Resu dan Talu. Pekerjaan mereka memisahkan BQP dan PH dengan bantuan yang disebut " oracle " atau "kotak hitam". Ini adalah hasil yang umum dalam ilmu komputer, yang digunakan para peneliti ketika apa yang ingin mereka buktikan tidak diberikan kepada mereka dengan cara apa pun.

Cara terbaik untuk memisahkan kelas kompleksitas BQP dan PH adalah dengan mengukur waktu komputasi yang diperlukan untuk menyelesaikan masalah dari masing-masing kelas. Tetapi ilmu komputer tidak memiliki "pemahaman mendalam tentang waktu komputasi nyata atau kemampuan untuk mengukurnya," kata Henry Youn, seorang ilmuwan komputer di University of Toronto.

Sebaliknya, sesuatu yang lain sedang diukur dalam ilmu komputer, yang dianggap memberikan pemahaman tentang waktu komputasi yang tidak dapat diukur secara langsung. Para ilmuwan menghitung jumlah panggilan komputer ke "oracle" untuk memberikan jawaban atas pertanyaan itu. Nubuat itu tampaknya memberi petunjuk. Kita tidak tahu bagaimana dia menerimanya, tetapi kita tahu bahwa mereka dapat diandalkan.

Jika tugas Anda adalah untuk mengetahui apakah ada koneksi rahasia antara dua generator bilangan acak, Anda dapat mengajukan pertanyaan oracle seperti "apa yang akan menjadi bilangan keenam dari setiap generator?" Maka Anda perlu membandingkan daya komputasi berdasarkan jumlah permintaan yang dibutuhkan oleh setiap komputer untuk memecahkan masalah. Komputer yang membutuhkan lebih banyak petunjuk berjalan lebih lambat.

“Dalam arti tertentu, kami memahami model ini jauh lebih baik. Dia berbicara lebih banyak tentang informasi daripada tentang komputasi, ”kata Tal.


Avishai Tal

Karya baru Reza dan Tal membuktikan bahwa komputer kuantum akan membutuhkan petunjuk yang jauh lebih sedikit untuk menyelesaikan masalah furrelation daripada yang klasik. Selain itu, komputer kuantum hanya membutuhkan satu petunjuk, meskipun faktanya PH tidak memiliki algoritma untuk menyelesaikan masalah seperti itu, bahkan dengan jumlah petunjuk yang tidak terbatas. "Ini berarti bahwa ada algoritma kuantum yang sangat efisien yang memecahkan masalah seperti itu," kata Rez. "Tetapi jika kita hanya mempertimbangkan algoritma klasik, maka bahkan jika kita sampai ke kelas paling atas dari algoritma klasik, mereka tidak akan mampu mengatasinya." Ini membuktikan bahwa dengan oracle, furrelation mengacu pada tugas-tugas milik BQP, tetapi tidak untuk PH.

Rez dan Tal hampir mencapai hasil ini sekitar empat tahun yang lalu, tetapi tidak dapat mengambil satu langkah dalam bukti di masa depan. Dan kemudian, hanya sebulan sebelum publikasi, Tal mendengar tentang karya baru tentang generator bilangan acak semu, dan menyadari bahwa teknologi dari artikel itu hanya memberikan apa yang ia dan Rez butuhkan untuk menyelesaikannya sendiri. "Itu adalah bagian yang hilang," kata Tal.

Berita tentang pemisahan kelas BQP dan PH menyebar dengan cepat. "Dunia kompleksitas kuantum sedang ramai," tulis Lance Fortnau, seorang spesialis IT di Universitas Teknologi Georgia sehari setelah publikasi karya tersebut.

Karya ini memberikan keyakinan yang kuat bahwa komputer kuantum ada di dunia komputasi yang terpisah dari dunia klasik (setidaknya menurut definisi dengan oracle). Bahkan di dunia di mana P setara dengan NP - di mana menyelesaikan masalah salesman keliling adalah semudah menemukan garis yang paling cocok di spreadsheet - buktinya oleh Reza dan Tal menunjukkan bahwa ada masalah yang hanya bisa diselesaikan oleh komputer kuantum.

"Bahkan jika P setara dengan NP, bahkan dengan asumsi yang kuat," kata Fortnau, "komputer kuantum masih tidak akan menyusul."