Adakah contoh kasus di mana simulasi klasik suatu algoritma kuantum untuk suatu masalah mengungguli algoritma klasik yang paling dikenal sebelumnya untuk masalah ini? "Outperforms" tidak harus berarti kelas kompleksitas yang berbeda, itu bisa saja lebih baik skala. Pertanyaan ini terinspirasi oleh...
Baru-baru ini saya berpikir tentang "mengimpor" beberapa pertanyaan terkait fisika ke dalam kuantum CS: Gagasan fenomena hukum-daerah dalam sistem Hamilton biasanya merupakan singkatan dari Hamiltonian lokal pada beberapa kisi, yang groundstate menunjukkan properti di mana keterjeratan suatu...
Dalam kompleksitas pohon keputusan fungsi boolean, metode batas bawah yang sangat diketahui adalah untuk menemukan (perkiraan) polinomial yang mewakili fungsi. Paturi memberikan karakterisasi untuk fungsi simetris boolean (parsial dan total) dalam hal kuantitas yang dilambangkan :ΓΓ\Gamma...
Pertimbangkan ruang Hilbert . Dasar Produk Yang Tidak Dapat Diubah (UPB) adalah sekumpulan vektor produk sedemikian rupa sehingga:H= H1⊗ ⋯ ⊗ HnH=H1⊗⋯⊗HnH = H_1 \otimes \dots \otimes H_n| vsaya⟩ = | v1saya⟩ ⊗ ⋯ ⊗ | vnsaya⟩|vsaya⟩=|vsaya1⟩⊗⋯⊗|vsayan⟩\vert v_i \rangle = \vert v_i^1 \rangle \otimes...
Tentukan model komputasi MPostBQP agar identik dengan PostBQP kecuali kami mengizinkan pengukuran qubit secara polinomial banyak sebelum pengukuran pasca-seleksi dan akhir. Bisakah kita memberikan bukti yang menunjukkan bahwa MPostBQP lebih kuat daripada PostBQP? Tentukan MPostBQP [k] untuk...
Karena tidak ada jawaban yang diberikan, bendera telah ditetapkan yang meminta agar pertanyaan ini dikonversi ke wiki komunitas. Komentar oleh Aaron Sterling, Sasho Nikolov, dan Vor telah disintesis menjadi resolusi berikut, yang terbuka untuk diskusi wiki komunitas: Terselesaikan: ...
Diketahui bahwa kompleksitas query quantum error terbatas dari fungsi adalah Θ ( √O R ( x1, x2, ... , xn)OR(x1,x2,…,xn)OR(x_1,x_2,\ldots, x_n). Sekarang pertanyaannya adalah bagaimana jika kita ingin algoritma quantum kami berhasil untuk setiap input dengan probabilitas1-εdaripada biasa2/3....
Apakah ada keluarga aksi kelompok yang diketahui dengan elemen yang ditunjuk dalam set yang sedang ditindaklanjuti, di mana diketahui cara efisien \: sampel (pada dasarnya seragam) dari kelompok, menghitung operasi terbalik, \: hitung operasi grup, dan hitung aksi grup dan tidak ada algoritma...
Banyak literatur komputasi kuantum berfokus pada model rangkaian. Komputasi kuantum adiabatik tidak didasarkan pada penerapan urutan operator kesatuan, tetapi pada perubahan Hamiltonian yang bergantung waktu. Saya mencari wawasan tentang hal-hal berikut. Apakah komputasi kuantum adiabatik sekuat...
Konteks : Ada beberapa makalah yang mempelajari implikasi dari kurva timelike tertutup (CTL) terhadap kompleksitas kuantum. Pada tahun 2008, Aaronson dan Watrous menerbitkan makalah terkenal mereka tentang topik ini yang menunjukkan bahwa bentuk perjalanan waktu tertentu dapat membuat komputasi...
Saya mencoba untuk memperjelas pemahaman saya dalam contoh yang disajikan dalam Bagian 2.2 dari Quantum Finite Automata 1-arah: Kekuatan Kelemahan dan Generalisasi ( tautan alternatif ini juga mungkin berguna). Contoh ini memberikan contoh 1-QFA yang sangat terbuka dengan aturan transisi...
Apa set terbesar yang mengakui algoritma pencarian kuantum deterministik, untuk elemen bertanda tunggal, yang beroperasi hanya dengan satu panggilan ke oracle? Pertanyaannya menarik karena algoritma Grover, yang untuk pencarian tidak terstruktur pada set elemen membutuhkan O ( √NNNpanggilan ke...
Model Standar fisika (model matematika yang memprediksi bos Higg), sejauh yang saya mengerti, model alam semesta kita yang paling lengkap. Dengan kata lain, ini adalah deskripsi terbaik dari permainan matematika yang akan dimainkan untuk membuat prediksi tentang hasil percobaan yang dilakukan di...
Saya membaca koran Ahmed Younes, " Algoritma Waktu Polinomial Kuantum-Kesalahan Terbatasi untuk Dua Masalah Dua Grafik ", 2015. doi: 10.1007 / s11128-015-1069-y yang diterbitkan dalam jurnal Springer's Quantum Information Processing. Makalah ini tampaknya mengklaim bahwa ia menyediakan...
Dari Wikipedia : VPVP\mathsf{VP} : Kelas VP adalah analog aljabar dari P; itu adalah kelas polinomialfff derajat polinomial yang memiliki sirkuit ukuran polinomial atas lapangan tetapKKK . VNPVNP\mathsf{VNP} : Kelas VNP adalah analog dari NP. VNP dapat dianggap sebagai kelas polinomfff untuk...