Dapatkah algoritma kuantum dengan percepatan eksponensial direduksi menggunakan program-rentang?

12

Batas bawah musuh umum sekarang dikenal untuk mengkarakterisasi kompleksitas kueri kuantum karena karya terobosan oleh Reichardt et al. Garis pekerjaan yang sama juga membangun koneksi ke kerangka program rentang untuk merancang algoritma kuantum.

Banyak algoritma kuantum yang menarik, termasuk yang dengan kecepatan eksponensial seperti algoritma Simon dan algoritma Shor untuk pencarian periode dapat diekspresikan dalam model kueri kuantum.

Apakah ada pekerjaan yang menunjukkan batas bawah untuk algoritma ini dalam model musuh umum? Apakah ada pekerjaan yang menurunkan algoritma Simon atau Shor dalam kerangka rentang-program?

Rupanya, hanya algoritma kuantum dengan percepatan polinomial, seperti Grover, yang diturunkan menggunakan kerangka program rentang (atau grafik pembelajaran Belov).

Ada pekerjaan oleh Korian et al. menunjukkan batas bawah untuk Simon menggunakan metode polinomial, tetapi tampaknya tidak ada cara yang diketahui untuk menerjemahkan metode polinomial batas bawah ke batas bawah musuh umum.

cc.complexity-theory quantum-computing query-complexity blk
sumber
3
Saya secara tidak sengaja memilih untuk ditutup sebagai "di luar topik" karena saya pikir saya memberikan suara pada pertanyaan yang berbeda dan mengklik tab yang salah. Saya pikir ini adalah pertanyaan yang bagus dan sesuai dengan topik , tetapi sistem tidak membiarkan saya menarik suara tidak sengaja saya.
Artem Kaznatcheev

Jawaban:

8

Saya kira setidaknya ada 3 pertanyaan dalam pertanyaan Anda. Saya tidak memiliki jawaban yang memuaskan untuk semuanya, jadi ini bukan jawaban yang lengkap. Semoga akan ada lebih banyak jawaban yang menjawab semua pertanyaan Anda.

Pertanyaan dalam judul: Dapatkah algoritma kuantum dengan percepatan eksponensial direduksi menggunakan span-program?

Seperti yang Anda catat, batas musuh umum mencirikan kompleksitas kueri kuantum semua masalah keputusan, termasuk masalah janji yang memiliki percepatan eksponensial. Jadi, pada prinsipnya, ada program rentang yang memecahkan masalah subkelompok tersembunyi Abelian, yang merupakan masalah kueri yang digunakan dalam algoritma Simon dan Shor. Tetapi apakah ada program rentang eksplisit untuk ini adalah pertanyaan Anda berikutnya.

Apakah ada pekerjaan yang menurunkan algoritma Simon atau Shor dalam kerangka rentang-program?

Saya belum pernah mendengar hasil seperti itu. Saya tidak tahu program rentang untuk masalah Simon atau AHSP lainnya.

Apakah ada cara untuk menerjemahkan metode rendah polinomial ke batas bawah lawan umum?

Ya, saya yakin ada. Sepertinya saya tidak dapat menemukan kertas yang memiliki hasil ini, tetapi saya dapat memberi Anda tautan ke ceramah yang diberikan oleh Jérémie Roland . Dalam abstrak pembicaraan, ia mengatakan yang berikut:

... Lebih tepatnya, kami akan menunjukkan bahwa metode permusuhan multiplikatif, variasi dari metode permusuhan asli, menggeneralisasikan tidak hanya metode permusuhan umum, tetapi juga metode polinomial, sehingga pada dasarnya mencakup semua metode batas bawah yang diketahui. Oleh karena itu, ini memberikan pendekatan konstruktif untuk memasukkan batas bawah polinomial ke dalam kerangka metode permusuhan.

Pembaruan : Makalah ini sekarang tersedia online: Hubungan eksplisit antara semua teknik batas bawah untuk kompleksitas kueri kuantum oleh Loïck Magnin dan Jérémie Roland

Robin Kothari
sumber
2
Saya hanya ingin menunjukkan sesuatu di sini. Jika tujuannya adalah untuk mengambil batas bawah untuk algoritma Simon menggunakan metode polinomial, mengubahnya menjadi musuh, dan kemudian mengubahnya menjadi algoritma grafik pembelajaran, ini mungkin tidak akan berhasil. (Jika itu saya, saya akan menemukannya langsung dalam kerangka grafik pembelajaran). Pengurangan kami adalah dari metode polinomial ke metode musuh multiplikasi (yang lebih kuat dari aditif umum). Saya tidak mengetahui adanya koneksi dengan span-program karena metode musuh multiplikatif bukanlah SDP.
Loïck
1
@ Loïck: Benar. Bahkan jika matriks aditif yang optimal untuk masalah Simon ditemukan, tidak jelas bagaimana membangun program rentang (atau grafik pembelajaran) untuk itu.
Robin Kothari