Mengapa Montgomery modular exponentiation tidak dipertimbangkan untuk digunakan dalam factum kuantum?

Telah diketahui secara umum bahwa eksponensial modular (bagian utama dari operasi RSA) mahal secara komputasi, dan sejauh yang saya mengerti hal-hal teknik eksponensial modular Montgomery adalah metode yang lebih disukai. Eksponen modular juga menonjol dalam algoritme anjak kuantum, dan juga mahal di sana.

Jadi: mengapa eksponensial modular Montgomery tampaknya tidak hadir dalam subrutin terperinci saat ini untuk anjak piutang kuantum?

Satu-satunya hal yang dapat saya bayangkan adalah ada overhead qubit tinggi untuk beberapa alasan yang tidak jelas.

Menjalankan kuantum montgomery "eksponensial modular" melalui Google Cendekia tidak menghasilkan hasil yang berguna. Saya mengetahui pekerjaan oleh Van Meter dan lainnya tentang penambahan kuantum dan eksponensial modular, tetapi memeriksa referensi mereka (saya belum membaca karya ini) tidak menunjukkan indikasi bahwa metode Montgomery dipertimbangkan di sana.

Referensi tunggal yang saya temukan yang tampaknya membahas hal ini adalah dalam bahasa Jepang, yang sayangnya tidak dapat saya baca, meskipun tampaknya itu berasal dari proses konferensi tahun 2002. Terjemahan mesin menghasilkan nugget ditambahkan di bawah ini yang menunjukkan mungkin ada sesuatu yang berguna. Namun, saya tidak dapat menemukan indikasi bahwa ini telah ditindaklanjuti, yang membuat saya berpikir bahwa idenya telah a) dipertimbangkan dan kemudian b) dibuang.

Sirkuit kuantum dalam melakukan aritmatika Noboru Kunihiro

... Dalam penelitian ini, tetapi memerlukan qubit yang relatif besar, kami mengusulkan rangkaian kuantum modular perhitungan waktu kuantum yang singkat. Reduksi Montgomery [8] dan metode biner kanan [9] Dikombinasikan, mereka membentuk sirkuit Ru. Reduksi Montgomery, m dipilih secara acak sebagai bilangan asli, mod 2m oleh operasi, melakukan operasi sisanya Jika, mod n operasi dalam menghilangkan. Ini akan menyebabkan pengurangan waktu perhitungan ...

Aplikasi 3.2 Montgomery Reduction Montgomery Reduction [8] dirumuskan sebagai berikut ... Algoritma ini dapat mengembalikan nilai yang benar dapat dengan mudah dikonfirmasi. MR (Y) ia meminta undang-undang 2m Polinomial dengan poin 2m penting dan hanya memerlukan pembagian oleh. Selain itu, Pengurangan Montgomery dalam, ada metode perhitungan yang berbeda .... Secara umum, Pengurangan Montgomery bukan fungsi satu-ke-satu ...

... Metode yang diusulkan menggunakan metode biner yang tepat, Montgomery Reducton memiliki fitur yang diadopsi. Daripada metode konvensional, dicirikan oleh komponen kecil dari rangkaian Have. kesalahan qubit yang diperlukan untuk memiliki banyak harapan dapat dihitung dalam waktu komputasi yang kurang. Masa depan, Pengurangan Montgomery dan sirkuit kontrol khusus TIDAK dijelaskan oleh qubit benar-benar diperlukan. Mengevaluasi jumlah yang diharapkan untuk mengevaluasi waktu perhitungan. Selain itu, masing-masing memanfaatkan temuan penelitian, lebih dari eksponensial modular Non-aritmatika (divisi timbal balik Euclid, dll.) Juga berkenaan dengan konfigurasi yang direncanakan dari rangkaian kuantum yang efisien.

... [8] PL Montgomery, "Perkalian Modular Tanpa Divisi Percobaan," Matematika Komputasi, 44, 170, hlm. 519-521, 1985 ...

Bisakah Anda memposting judul / referensi asli Jepang?

Selain itu, Anda dapat mempertimbangkan untuk menulis kepada penulis - dengan anggapan bahwa ia adalah orang yang sama dengan profesor di Universitas Tokyo:

http://www.it.ku-tokyo.ac.jp/~kunihiro/

dan hampir pasti akan menjawab.

Maaf memposting ini sebagai jawaban, itu seharusnya komentar tapi saya belum punya perwakilan untuk itu ...

EDIT: Jadi, saya melihat orang Jepang asli. Sebagai kata pengantar, saya saat ini adalah mahasiswa PhD di departemen EE di U. Tokyo, berasal dari AS, dan saya melakukan terjemahan JA-> EN teknis sebagai pekerjaan paruh waktu. Namun, area topik ini jauh di luar zona nyaman saya, jadi silakan ambil pendapat saya dengan sebutir garam!

Pada dasarnya kesimpulan (4) mengatakan:

べ き 乗 剰 余 演算 を 行 う 量子 回路 を 提案 し た. 提案 方式 は, 右 向 き biner metode を 採用 し, Montgomery Pengurangan を 採用 す る と い う 特 徴 を 持 っ て い る. 従 来 の 方式 よ り も, 回路 の 構成 要素 が 少 な い と い う 特 徴 を 持 って い る 。qubit が 多 く 必要 と な る と い う う 点 は は 、 、 、 よ よ 少 少 少 な 時間 計算 が が で で き る れ れ る。。。。。。。。。

[Dalam makalah ini] Kami mengusulkan rangkaian kuantum baru untuk menghitung eksponensial modular. Metode yang diusulkan menggunakan metode biner LR, dan juga ditandai dengan penggunaan Pengurangan Montgomery. Dibandingkan dengan metode sebelumnya, metode yang diusulkan membutuhkan lebih sedikit komponen untuk membangun sirkuit. Namun, metode yang diusulkan memiliki kelemahan dalam membutuhkan sejumlah besar qubit, tetapi kami yakin bahwa itu akan efisien secara komputasi (lit: memerlukan waktu komputasi yang sangat sedikit).

Saya mencoba mencari makalah terkait dalam bahasa Inggris dan Jepang tetapi tidak berhasil. Dugaan saya adalah bahwa pendekatan itu terbukti tidak berhasil, atau profesor sibuk dengan sesuatu yang lain (sepertinya ini ada ketika dia berganti universitas).

Saya pikir bahwa taruhan terbaik Anda pada titik ini, dengan asumsi Anda ingin menindaklanjuti sisa perjalanan dan mendapatkan jawaban yang konkret, adalah menulis langsung kepada profesor Kunihiro (dalam bahasa Inggris!)

Saya juga bertanya-tanya tentang pertanyaan ini, karena pendekatan saat ini untuk perkalian modular untuk anjak kuantum menggunakan pengurangan percobaan jika ada kelebihan setelah setiap penambahan, atau pendekatan pembagian / pengurangan pada akhirnya. Keduanya tampak boros.

Saya sedang mengerjakan arsitektur kuantum untuk melakukan modexp menggunakan perkalian Montgomery sekarang. Saya tidak berpikir overhead ruang harus lebih besar dari pendekatan sebelumnya, tapi saya melihat tidak perlu menggunakan perkalian Karatsuba saat ini.

Multiplikasi Montgomery dalam biner cukup efisien (bit-shifting dan penambahan). Penambahan modulus dan jumlah bergeser tergantung pada bit paling signifikan (LSB) pada setiap langkah, jadi ini tampaknya memerlukan sebelum mereka secara seri, untuk mendapatkan waktu O (n).

Namun, Anda dapat memparalelkan ketergantungan ini pada LSB dengan menggunakan tabel fungsi dan menyusun / mempersempitnya mirip dengan pendekatan carry-lookahead atau deskripsi Kitaev tentang automata paralel paralel dalam bukunya (Kitaev, Shen, Vyalyi 2002). Langkah ini hampir pasti membutuhkan banyak ancillae, tetapi asimptotik dapat dibuat O (log n) -depth.