Algoritma kuantum berdasarkan transformasi selain transformasi Fourier

19

Dalam Komputasi Quantum dan Informasi Quantum oleh Nielsen dan Chuang, mereka mengatakan bahwa banyak algoritma yang didasarkan pada transformasi Fourier kuantum bergantung pada properti Coset Invariance dari transformasi Fourier dan menunjukkan bahwa properti invarian dari transformasi lain mungkin menghasilkan algoritma baru.

Apakah ada penelitian yang bermanfaat tentang transformasi lain?

quantum-computing quantum-information Sam Burville
sumber
10
Iya. Yi-Kai Liu, Shelby Kimmel, dan lainnya telah mengembangkan algoritma kuantum berdasarkan transformasi wavelet, dan Stephen Jordan telah mengembangkan algoritma kuantum berdasarkan transformasi Clebsch-Gordan. Anda dapat google untuk referensi, atau orang lain mungkin datang untuk memberikan beberapa. Tentu saja, masalah yang dipecahkan oleh algoritma ini tidak setinggi profil anjak dan diskrit (jika tidak Anda pasti sudah pernah mendengarnya).
Scott Aaronson
5
@ScottAaronson komentar -> answer
Alessandro Cosentino
@ScottAaronson Hebat, saya akan memeriksa mereka. Terima kasih!
Sam Burville
Oracle Hamiltonian?
vzn
Yi-Kai Liu telah mengembangkan algoritma kuantum menggunakan transformasi curvelet (lihat versi lengkap tentang arXiv atau versi pendek dari FOCS).
Māris Ozols

Jawaban:

16

Saya ingin menambahkan beberapa referensi untuk komentar Scott:

Memang, transformasi Clebsch-Gordan (yang dapat Anda anggap sebagai multi-register Transformasi Fourier register) adalah alat yang berguna dalam desain algoritma kuantum untuk masalah subkelompok tersembunyi non-Abelian (HSP).

  • Transformasi Clebsch-Gordan digunakan oleh Greg Kuperberg dan Oded Regev untuk menyelesaikan HSP dihedral dalam waktu subeksponensial (belum superpolinomial). Algoritma kuantum ini tidak efisien, tetapi mereka memiliki kompleksitas kueri yang lebih baik daripada algoritma klasik.

  • Dave Bacon juga menggunakan transformasi Clebsch-Gordan untuk memecahkan masalah subkelompok tersembunyi (HSP) selama kelompok Heisenberg dalam waktu polinomial. Saya dapat merekomendasikan kertas itu karena cukup jelas.Zhal2⋊Zhal

Saya juga menulis untuk menambahkan bahwa kita tidak boleh lupa bahwa baik transformasi kuantum Fourier dan transformasi Clebsch-Gordan tidak selalu diperlukan, bahkan jika mereka bisa sangat berguna.

  • Dalam algoritma Shor (atau bahkan dalam estimasi fase kuantum) transformasi Fourier dapat diganti dengan tes Hadamard , oleh karena itu hanya menggunakan gerbang Hadamard alih-alih transformasi Fourier: trik ini adalah karena Kitaev dan Anda dapat membacanya di sini .

  • Ada lagi algoritma efisien untuk HSP lebih dari , oleh Bacon, Childs, Van Dam, yang tidak menggunakan transformasi Clebsch-Gordan. Alih-alih, algoritma menggunakan jenis POVM kuat tertentu yang dikenal sebagai Pengukuran Cukup Baik.Zhal2⋊Zhal

Tentu saja, daftar ini mungkin tidak lengkap. Saya harap seseorang akan menunjukkan hasil lain yang belum disebutkan.

Juan Bermejo Vega
sumber
HSP = masalah subkelompok tersembunyi
vzn
Terima kasih telah menunjukkannya. Saya menjelaskan akronim di edit terakhir.
Juan Bermejo Vega
4

Tidak yakin apakah ini terkait langsung dengan pertanyaan Anda, tetapi membacanya membuat saya berpikir tentang sebuah artikel oleh Peter Høyer yang saya baca beberapa tahun yang lalu. Di dalamnya, ia menunjukkan bagaimana algoritma kuantum paling populer seperti Grover atau Shor mengikuti pola yang sama dalam menerapkan apa yang ia sebut "operator terkonjugasi" dan ia membangun algoritma baru juga berdasarkan pada pola yang sama.

Seperti yang saya katakan, sudah beberapa tahun sejak saya membacanya sehingga deskripsi saya agak ceroboh, tapi inilah tautannya jika Anda ingin memeriksanya.

http://journals.aps.org/pra/abstract/10.1103/PhysRevA.59.3280

Philippe Lamontagne
sumber