Algoritma Quantum untuk Nomor Tuhan

Nomor Allah adalah kasus terburuk dari algoritma Allah yang

gagasan yang berasal dari diskusi tentang cara-cara untuk memecahkan teka-teki Rubik's Cube, tetapi yang juga dapat diterapkan pada teka-teki kombinasi dan permainan matematika lainnya. Ini merujuk pada algoritma apa pun yang menghasilkan solusi yang memiliki gerakan sesedikit mungkin, gagasan bahwa makhluk mahatahu akan mengetahui langkah optimal dari konfigurasi yang diberikan.

Menghitung angka Tuhan menjadi 20 dengan waktu "35 CPU-tahun waktu komputer idle (klasik)."

Kecepatan macam apa yang bisa dicapai dengan pendekatan kuantum?

Kita bisa memikirkan kubus Rubik Cayley grafik dengan masing-masing (berwarna) tepi E menjadi salah satu langkah singmaster ⟨ U , U 2 , U 3 = U - 1 , D , D 2 , D 3 , ⋯ ⟩ dan setiap simpul V menjadi salah satu dari 43252003274489856000 ≈ 4.3 e 19 konfigurasi yang berbeda dari 3 × $\Gamma=(V,E)$$E$$\langle U,U^{2},U^{3}=U^{-1},D,D^{2},D^{3},\cdots\rangle$$V$$43252003274489856000\approx 4.3e{19}$ kubus.$3\times 3\times 3$

The diameter dari grafik adalah jalan terpendek terpanjang dalam grafik. Algoritma klasik untuk menentukan diameter adalah polinomial dalam ; lihat, misalnya, jawaban ini dari situs saudara.$\vert V \vert$

Seperti disebutkan di atas, angka Allah adalah (terkait dengan) diameter ini; untuk mengetahui jalur terpendek terpendek antara ke simpul untuk grafik Cayley pada suatu kelompok, cukup untuk mengetahui berapa banyak langkah menjauh dari keadaan terselesaikan yang ada. Kita tahu, terima kasih kepada Rokicki, Kociemba, Davidson, dan Dethridge, antara lain, bahwa jumlah Tuhan adalah . Algoritma yang mereka jalankan adalah polinomial dalam | V | , misalnya polinomial dalam 4.3 e 19 .$20$$\vert V\vert$$4.3e{19}$

Algoritma kuantum Heiligman untuk diameter grafik, disebutkan dalam komentar, mencapai percepatan Grover lebih algoritma Djikstra, dengan "total biaya kuantum ." Namun, saya percaya Heiligman mengkodekan grafik sebanyak algoritma klasik; misal dengan qubit O ( | V | ) . Jelas jika | V | = 4.3 e 19 maka ini tidak akan membantu.$O(|V|^{9/4})$$O(|V|)$$|V|=4.3e{19}$

Sebaliknya, cara lain untuk menyandikan kubus Rubik, seperti yang ditunjukkan dalam pertanyaan lain, tentu saja untuk mempersiapkan superposisi yang seragam di semua negara. Ini hanya membutuhkan log 4.3 e 19 qubit.$4.3e{19}$$\log 4.3e{19}$

Algoritme kuantum pandai berbicara tentang "nilai eigen" dan "vektor eigen" dan "status eigen." Menerapkan semua perpindahan Singmaster ke superposisi seragam dari semua negara tidak mengubah negara; yaitu superposisi yang seragam adalah status eigen dari rantai Markov pada grafik Cayley.$4.3e{19}$

Ada hubungan antara diameter grafik dan nilai eigen / vektor eigen dari adjacency yang sesuai / matriks Laplacian, terutama kesenjangan spektral, jarak antara dua nilai eigen terbesar ( ). Pencarian Google cepat "nilai eigen diameter" menghasilkan ini ; Saya sarankan menjelajahi pencarian Google serupa.$\lambda_1-\lambda_2$

Kesenjangan spektral adalah persis apa yang membatasi algoritma adiabatik . Jadi, mungkin dengan mengetahui seberapa cepat algoritma adiabatik perlu dijalankan untuk berevolusi dari superpositon yang seragam ke keadaan terpecahkan untuk berbagai subkelompok / subruang dari kelompok kubus Rubik, orang dapat memperkirakan celah spektral, dan menggunakannya untuk mengikat angka Tuhan. Tapi saya dengan cepat keluar dari liga saya di sini dan saya ragu rasa akurasi dapat dicapai.