Get best of the week

Bagaimana ฯ€ menggabungkan blok bertabrakan dan algoritma pencarian kuantum

Seorang fisikawan yang penasaran telah menemukan hubungan yang tak terduga antara teori blok tumbukan dan algoritma pencarian kuantum yang terkenal




Apa persamaan dari ฯ€, tabrakan blok dan algoritma pencarian kuantum? Lebih dari yang bisa kamu bayangkan. Koneksi ini disediakan oleh dua karya ilmiah lucu - satu dari 2003, dan yang kedua dari Desember 2019. Bersama-sama mereka menggabungkan dunia dinamika, geometri, dan komputasi kuantum, yang menunjukkan bagaimana bahkan teka-teki matematika paling abstrak dapat secara mengejutkan mengungkapkan hubungan dengan fisika.

Mengunci


Untuk mulai memahami koneksi ini, bayangkan dua balok logam, yang masing-masing berbobot 1 kg. Mereka berada di permukaan tanpa gesekan, di sebelah kanan dinding tetap. Blok yang paling dekat dengan dinding tidak bergerak, yang kedua meluncur ke arahnya, mendekati ke kanan. Serangkaian bentrokan pasti harus terjadi; Misalkan energi kinetik tidak hilang dalam tabrakan. Dalam kondisi ideal seperti itu, proses ini akan berlangsung seperti ini:


Blok kanan mengenai kiri, memberikan seluruh dorongan. Blok kiri memantul dari dinding, kembali ke kanan untuk tabrakan lain dan transmisi impuls lengkap lainnya.

Namun, jika Anda menambah massa blok yang tepat, situasinya akan menjadi lebih menarik. Jika beratnya 100 kg, dengan masing-masing tabrakan itu akan mengirimkan hanya sebagian kecil dari momentumnya ke blok yang lebih kecil, dan bukannya jumlah tabrakan itu akan meningkat dari 3 menjadi 31.


Dengan rasio massa 10.000 banding 1, situasi akan diselesaikan setelah 314 tabrakan.


Tingkatkan perbedaan dengan mengalikan massa dengan 100, dan Anda akan dapat mengamati tren yang mengejutkan: jumlah tabrakan akan mulai mendekati angka ฯ€ semakin dekat dan semakin dekat.


Gregory Galperin, ahli matematika dari University of East Illinois, adalah orang pertama yang memperhatikan fenomena ini [pada tahun 1993]. Pada tahun 2003, ia menjelaskannya dengan memvisualisasikan pergerakan blok melalui titik bergerak, yang koordinat xnya menunjukkan lokasi satu blok dan koordinat y dari blok kedua. Lintasan suatu titik di pesawat terhubung dengan setengah lingkaran, di mana ฯ€ muncul.

Hasil yang luar biasa, bahkan jika kondisi ideal ini membuatnya tampak tidak berguna. Namun, jika Anda mengabaikan kecerobohan dunia nyata dalam matematika, Anda dapat menemukan keteraturan murni yang mengungkapkan hubungan tak terduga dengan bidang ilmu lainnya.

Pada 2019, saya menerbitkan satu set tiga videomenjelaskan hasil Halperin, dan di antara mereka yang melihatnya adalah Adam Brown, seorang peneliti dari Google dan seorang ahli fisika di Universitas Stanford. Setelah beberapa bulan di konferensi, dia membawa saya ke samping untuk membagikan pengamatannya. Yang membuatnya senang, ia menemukan bahwa matematika yang menggambarkan dinamika blok-blok ini, dari sudut pandang tertentu, menjadi identik dengan matematika yang menggambarkan salah satu algoritma kuantum paling terkenal.

Pendekatan kuantum


Ini membawa kita ke bagian kedua dari teka-teki: cara kerja pencarian kuantum.

Misalkan Anda memiliki daftar nama panjang tanpa menyortir - katakanlah, satu juta - dan Anda perlu menemukan nama tertentu. Anda tidak memiliki pilihan lain selain memeriksa satu nama demi satu sampai Anda menemukan yang benar. Rata-rata, itu akan membawa Anda setengah juta iterasi. Terkadang lebih, kadang-kadang lebih sedikit, tetapi dalam hal apapun itu akan memakan waktu Anda.

Komputer dapat melakukan pencarian ini untuk Anda, tetapi masalah dengan daftar besar adalah bahwa jumlah waktu yang dibutuhkan untuk memprosesnya akan tumbuh sebanding dengan ukurannya. Setidaknya saat menggunakan komputer klasik. Tetapi pada tahun 1996, Love Grover, yang bekerja di laboratorium Bell, menjelaskanbagaimana komputer kuantum dapat melakukan pencarian seperti itu jauh lebih cepat, dan tidak lebih dari 1000 langkah. Dalam kasus umum, komputer kuantum akan mengelola daftar panjang N dalam langkah ฯ€ / 4 โˆšN. Perhatikan bahwa seiring meningkatnya angka N, jumlah langkah yang dikembangkan komputer kuantum lebih lambat daripada yang klasik.

Efisiensi pencarian seperti itu dimungkinkan karena komputer kuantum memproses semua elemen daftar pada saat yang sama. Namun, ia tidak hanya melakukan hal yang sama dengan komputer klasik, hanya pada saat yang sama.

Komputer klasik menjawab pertanyaan: "Apakah elemen ke-21 dari daftar nama yang saya butuhkan?" Dan ia mengulanginya untuk setiap posisi daftar, dari 0 hingga 999.999. Langsung, tetapi tidak terlalu efektif.

Tetapi algoritma Grover bekerja dengan metode daftar, yang awalnya tampak aneh, tetapi pada akhirnya lebih bermanfaat. Komputer klasik hanya dapat membaca bit dari memori. Ketidakpastian hadir dalam komputasi kuantum mengarah pada fakta bahwa Anda tidak bisa langsung menarik keluar komponen vektor yang bekerja dengan Anda. Setiap posisi dalam daftar memiliki struktur probabilistik tambahan. Anda tidak melihat nama apa di posisi ini, Anda mengukur seluruh daftar, mendapatkan posisi acak - indeks - sesuai dengan probabilitas. Karena mekanika kuantum yang mendasarinya, alih-alih bekerja secara langsung dengan nilai probabilistik, kami bekerja dengan angka yang kuadratnya sesuai dengan probabilitas mendapatkan indeks yang sesuai dengan nama yang Anda cari.



Bagaimana cara membaca indeks acak berguna? Seni komputasi kuantum adalah memanipulasi daftar probabilitas yang membangun peluang untuk Anda. Dalam contoh kami, ini berarti menciptakan cara (yang dilakukan oleh algoritma Grover) untuk mendapatkan nomor yang terkait dengan indeks nama yang Anda cari, dekat dengan persatuan, sehingga semua angka lainnya mendekati nol. Kemudian, membaca daftar ini dan menerima indeks sebagai respons, Anda kemungkinan besar akan tahu bahwa itu sesuai dengan nama yang Anda cari.

Alat komputasi kuantum terdiri dari operasi yang dapat diterapkan oleh peneliti ke daftar probabilitas ini. Dalam matematika, daftar seperti itu disebut vektor. Sering kali nyaman membayangkan vektor sebagai titik dalam sistem koordinat, atau sebagai panah yang diambil dari titik asal ke titik ini.



Vektor dua komponen dapat direpresentasikan sebagai panah dalam ruang dua dimensi. Vektor dengan 1.000.000 komponen hidup dalam ruang 1.000.000 dimensi yang menakjubkan. Operasi yang dilakukan oleh komputer kuantum terlihat seperti belokan dan membalik panah ini. Secara numerik, setiap operasi ditunjukkan oleh sebuah matriks.



Komputasi kuantum sangat cepat karena setiap operasi dilakukan dengan seluruh vektor probabilitas, dan tidak lulus secara komponen. Grover menemukan cara rumit untuk memanipulasi vektor yang diberikan dengan sepasang operasi intermiten, menghasilkan vektor dengan probabilitas yang kita butuhkan. Adalah penting bahwa jumlah total operasi yang diperlukan jauh lebih kecil dari ukuran daftar.

Jika sulit bagi Anda untuk membayangkan bagaimana ini bisa berhasil, Anda bukan satu-satunya. Karena itu, Adam Brown sangat senang menemukan cara untuk membayangkan manipulasi vektor abstrak ini dalam bentuk teka-teki yang lebih dimengerti.

Tautan tersembunyi


Ternyata ketika saya menonton video saya tentang menghitung angka ฯ€ menggunakan blok bertabrakan, Brown hanya memiliki algoritma Grover di benaknya, jadi dia segera memperhatikan koneksi mereka. "Jika Anda menghabiskan sepanjang hari memikirkan pencarian kuantum, maka semuanya mulai tampak seperti pencarian kuantum," kata Brown, "dan itu terjadi secara kebetulan bahwa kasus ini ternyata terkait dengan pencarian kuantum."

Dan jika pekerjaan Galperin pada tabrakan blok menggunakan ruang yang menyandikan lokasi setiap blok, maka koneksi dengan pencarian kuantum Grover dimulai dengan vektor yang komponen x dan y menyandikan kecepatan setiap blok. Setiap tabrakan blok diterjemahkan ke dalam operasi spesifik pada vektor ini, mengubah komponennya. Misalnya, ketika blok kiri bertabrakan dengan dinding, mengubah arah ke arah yang berlawanan, ini berarti bahwa komponen vektor kita dikalikan dengan -1, dan komponen x tetap tidak berubah. Dari sudut pandang geometris, ini terlihat seperti refleksi vektor tentang sumbu x.

Demikian pula, ketika dua blok bertabrakan, perubahan kecepatan mereka mirip dengan flip lain dari vektor ini, hanya offset dari pusat. Ketika simulasi berlanjut, blok kiri akan kembali bertabrakan dengan dinding, yang akan mengarah ke giliran lain pada sumbu x. Tabrakan blok yang lain berarti revolusi lain. Akibatnya, dengan jumlah tabrakan yang cukup, vektor akan mengisi kurva yang akrab: lingkaran.


Brown mencatat bahwa jika situasi ini dijelaskan dengan benar, maka kedua operasi ini, yang berubah dalam satu arah atau yang lain, identik dengan dua operasi yang digunakan Grover dalam algoritme pencarian kuantumnya.

Untuk memahami bagaimana ini terjadi, bayangkan sebuah balok kanan besar dalam bentuk banyak kilogram yang direkatkan bersama. Kemudian, alih-alih vektor dua dimensi yang menggambarkan setiap kecepatan, kita mendapatkan vektor N-dimensi, di mana N adalah jumlah total blok kecil, termasuk blok terisolasi di sebelah kiri. Setiap blok kecil sesuai dengan nama dalam daftar yang tidak disortir, dan blok terpisah di sebelah kiri sesuai dengan nama target.

Dalam karyanya, Brown membuktikan bahwa cara tumbukan blok-blok ini mengubah vektor yang menggambarkannya benar-benar identik dengan cara algoritma Grover mengubah vektor kuantum yang menunjukkan daftar nama yang tidak disortir. Momen dalam sistem blok bertabrakan, ketika sebuah blok besar akan berbalik, dan hampir semua energi dalam sistem berada di sebuah blok kecil, sesuai dengan momen dalam algoritma Grover, ketika hampir semua probabilitas ada pada nama yang perlu Anda temukan.

Fakta bahwa angka ฯ€ muncul saat menghitung tumbukan tercermin dalam algoritma Grover: ฯ€ / 4 โˆšN langkah. Akar kuadrat dalam ekspresi juga mencerminkan seberapa jauh penghitungan digit ฯ€ (dalam derajat 10) setelah mengalikan massa blok besar dengan 10.

"Sejauh ini, itu hanya tipuan," kata Brown. "Tetapi dalam fisika, kita telah belajar bahwa semakin banyak cara kita dapat merenungkan suatu masalah, semakin banyak ide yang dapat kita lihat - jadi saya berharap fakta ini berguna pada suatu hari nanti." Kami memiliki beberapa cara alternatif yang baik untuk memvisualisasikan algoritma Grover.

Koneksi ini menekankan kemampuan bahasa universal matematika. Penggunaan vektor untuk pengkodean keadaan sistem fisik bekerja baik pada tabrakan skala besar blok dan pada skala mikro keadaan kuantum. Banyak ide mendasar dalam matematika, yang sekilas tampak tidak menyenangkan dipisahkan dari kenyataan, berubah menjadi alat yang kuat, karena jika Anda menghilangkan detail fisik di salah satu area, Anda dapat menemukan koneksi tersembunyi dengan yang lain.

More articles:


All Articles