Model perhitungan secara ketat antara klasik dan kuantum dalam hal kompleksitas kueri

18

Sudah dikenal komputer kuantum benar-benar lebih kuat daripada rekan-rekan klasik mereka dalam hal kompleksitas permintaan .

Apakah ada model lain (alami atau buatan) yang secara ketat antara kuantum dan klasik dalam hal kompleksitas kueri?

Pemisahan bisa dimulai

masalah spesifik: model X menghitung fungsi dengan kueri yang lebih ketat dari kuantum, tetapi kueri lebih sedikit dari batas bawah pada klasik, atau $f$
masalah yang berbeda: model X menghitung fungsi dengan kueri yang lebih ketat dari kuantum, tetapi menghitung fungsi dengan kueri yang lebih sedikit daripada klasik. $f_1$ $f_2$

Dalam kedua kasus, kami ingin agar setiap fungsi memiliki untuk menghindari contoh-contoh yang sulit dibandingkan dengan kuantum (seperti kompleksitas sertifikat kueri non-deterministik). Di sini (dan ) adalah kompleksitas kueri kuantum -sisi (dan acak klasik) dua sisi dan ketidaksetaraan berada dalam faktor konstan. $f$ $Q_2(f) \leq X(f) \leq R_2(f)$ $Q_2(f)$ $R_2(f)$ $1/3$

cc.complexity-theory quantum-computing query-complexity Artem Kaznatcheev
sumber

8

Salah satu cara mudah untuk membuat model seperti itu adalah pertama-tama membuat model komputasi kuantum terbatas yang masih bisa melakukan sesuatu yang non-klasik, dan kemudian hanya memberikannya komputasi klasik secara gratis.

Contoh dari strategi ini adalah model qubit yang bersih (bersama dengan mesin BPP). Beberapa referensi: Tentang Kekuatan Satu Bit Informasi Quantum , Perhitungan dengan Unitarian dan Satu Qubit Murni dan Perkiraan polinomial Jones adalah masalah lengkap untuk satu qubit bersih .

Contoh lain adalah memiliki rangkaian kuantum kedalaman log (atau kedalaman polylog) dengan akses ke komputer klasik. Ini akan menghasilkan sesuatu seperti . $BPP^{BQNC}$

Robin Kothari
sumber

Ini tentu saja berfungsi untuk kompleksitas komputasi, tetapi apakah itu berfungsi untuk kompleksitas kueri? Saya tidak segera melihat masalah yang model qubit bersih + BPP menghasilkan kompleksitas kueri yang lebih baik daripada mesin klasik. Juga, secara umum teknik ini bisa gagal, karena memberikan kelompok Clifford atau komputer gerbang yang sesuai perhitungan klasik mendorong mereka untuk perhitungan kuantum universal.

Joe Fitzsimons

@JoeFitzsimons: Saya tidak bisa memikirkan masalah dari atas kepala saya, tapi saya pikir Dan Shepherd menunjukkan pemisahan oracle antara BPP dan model qubit yang bersih di kertasnya. Poin kedua Anda valid, tentu saja.

Robin Kothari

Tetapi tentunya pemisahan oracle tidak selalu menyiratkan pemisahan kompleksitas kueri.

Joe Fitzsimons

Saya setuju dengan @JoeFitzsimons, walaupun model DQC1 menarik, saya belum melihat pemisahan kompleksitas kueri untuknya. Masalah alami seperti estimasi jejak atau varian Peter polor dari masalah polinomial Jones tampaknya sulit disajikan dalam model kueri.

Artem Kaznatcheev

7

$X(f)\leq D(f)$ $R_2(f)$

Joe Fitzsimons
sumber

2

P

$\mathsf P$

\oplus L

$\oplus L$

P

$\mathsf P$

L

$\mathsf L$

2

Mungkin contoh yang lebih jelas dari model komputasi semacam ini adalah DQC1 yang dijelaskan oleh @RobinKothari dalam jawabannya. Lihat referensi dalam jawabannya untuk pengantar model yang bagus.

Juga, agak baru-baru ini, ada artikel bagus di majalah Nature tentang Quantum Discord. Perselisihan Quantum adalah ukuran informasi-teoretis dari korelasi non-klasik, generalisasi keterjeratan. Inilah tautannya . Anda akan melihat di sana bahwa ada contoh perhitungan di mana keterjeratan tidak memainkan peran mendasar, yaitu, korelasi non-klasik lainnya adalah yang mengurus mempercepat perhitungan. Ini terjadi di DQC1 untuk menghitung jejak matriks (lihat kertas oleh Datta, Shaji, dan Caves ). Apa yang menarik dalam artikel ini adalah ia membuka pertanyaan tentang "algoritma berbasis Quantum Discord", yaitu, algoritma di mana Anda tidak memerlukan keterikatan untuk mempercepat kuantum. Itu sesuatu antara komputasi kuantum penuh dan klasik.

Model lain yang mungkin termasuk dalam kategori ini (antara kuantum penuh dan klasik) adalah Model Optik Linier oleh Arkhipov dan Aaronson. Lihat pertanyaan ini untuk penjelasan yang bagus.

Saya tidak tahu di mana model ini cocok dalam hal kompleksitas kueri, tetapi bisa menjadi titik awal yang baik.

Marcos Villagra
sumber

Model perhitungan secara ketat antara klasik dan kuantum dalam hal kompleksitas kueri

Jawaban: