Konsekuensi dari $MIP^\ast=RE$ Mengenai Algoritma Kuantum
Bukti (tinjauan sejawat yang menunggu keputusan) dari $MIP^\ast=RE$dalam pra-cetak ini telah dielu-elukan sebagai terobosan yang signifikan. Pentingnya hasil ini dibahas oleh Henry Yuen (salah satu penulis) dalam posting blog ini . Scott Aaronson juga mencantumkan beberapa implikasi utama dalam entri blog ini .
Untuk permainan non-lokal ($G$), tentukan supremum probabilitas keberhasilan untuk strategi produk tensor non-relativistik sebagai $\omega^\ast(G)$, dan supremum probabilitas keberhasilan untuk strategi operator komuter relativistik (QFT) sebagai $\omega^{co}(G)$. Karena QM non-relativistik adalah kasus khusus QFT, jelas bahwa strategi berbasis operator komuter yang optimal setidaknya sama baiknya dengan strategi berbasis produk tensor yang optimal,$\omega^\ast(G) \le \omega^{co}(G)$.
Pemahaman saya tentang posting Yuen adalah salah satu konsekuensi dari $MIP^\ast=RE$ adalah game non-lokal yang ada $\omega^\ast(G) < \omega^{co}(G)$. Secara khusus, katanya
Pasti ada permainan $G$, kemudian, yang nilai kuantumnya berbeda dari nilai operator komuter. Tapi ini menyiratkan masalah Tsirelson memiliki jawaban negatif, dan oleh karena itu dugaan penyematan Connes salah.
Saya memahami ini berarti bahwa ada kelas masalah yang algoritme yang menggunakan teknik dari QFT (operator komuter) memiliki probabilitas keberhasilan yang lebih tinggi daripada algoritme yang menggunakan teknik dari QM non-relativistik (produk tensor, formalisme rangkaian kuantum).
Bagian pertama dari pertanyaan saya adalah, dengan asumsi bukti ini berlaku :
- Apakah $MIP^\ast=RE$ menyiratkan bahwa ada serangkaian masalah yang dapat diselesaikan lebih efisien dengan menggunakan formalisme matematika QFT (operator komuter) daripada formalisme QM non-relativistik (sirkuit kuantum konvensional)?
Kecuali jika saya salah menafsirkan, ini sepertinya mengikuti langsung dari pernyataan Yuen. Jika demikian, mungkinkah ada sekumpulan game non-lokal yang untuknya$\omega^\ast(G) < 0.5$ dan $\omega^{co}(G) > 0.5$? Secara khusus, bagian kedua dari pertanyaan saya adalah:
- Apakah $MIP^\ast=RE$ menyiratkan bahwa ada (atau mungkin) serangkaian masalah yang dapat diselesaikan menggunakan operator komuter yang tidak dapat diselesaikan menggunakan sirkuit kuantum, atau apakah kemungkinan ini ditutup oleh universalitas model rangkaian kuantum?
EDIT: Henry Yuen telah membuat MIP * Wiki bagi mereka yang tertarik untuk lebih memahami kelas kompleksitas ini atau$MIP^\ast = RE$ hasil.
Jawaban
Saya tidak tahu apakah hasil MIP * = RE, dan khususnya klaim bahwa ada permainan nonlokal $G$ dimana $\omega^*(G) \neq \omega^{co}(G)$, memiliki implikasi algoritmik untuk komputer kuantum. Ada beberapa hal yang ingin dikatakan di sini.
Hasil MIP * = RE adalah tentang masalah komputasi apa yang dapat diverifikasi menggunakan game nonlokal, dibandingkan dengan apa yang dapat diselesaikan oleh game nonlokal (bagaimanapun, saya tidak yakin apa artinya itu!). Perbedaan antara memverifikasi dan menyelesaikan adalah karena hal berikut: dalam permainan nonlokal, kami berasumsi bahwa Alice dan Bob secara ajaib mengetahui jawaban atas masalah tersebut (jadi kami berasumsi bahwa mereka dapat menyelesaikan masalah komputasi apa pun secara instan). Tantangan mereka bukanlah untuk menyelesaikannya, tetapi untuk membuktikankepada pemverifikasi klasik waktu polinomial, mereka tahu jawabannya. Hanya mengetahui jawaban untuk sesuatu tidak berarti Anda dapat meyakinkan orang lain tentang jawabannya. Apakah Alice dan Bob dapat menggunakan korelasi dari kerangka kerja produk tensor atau kerangka kerja operator perjalanan memengaruhi apa yang dapat mereka buktikan kepada pemverifikasi. MIP * = RE menunjukkan bahwa, dengan korelasi produk tensor, Alice dan Bob dapat membuktikan bahwa mereka mengetahui bahwa Mesin Turing pada akhirnya akan berhenti. Ini adalah sesuatu yang tidak dapat dilakukan jika Alice dan Bob berbagi korelasi operator komuter; oleh karena itu model operator komuter berbeda dari model produk tensor.
Hal kedua yang ingin saya sebutkan adalah, secara terpisah, ini adalah pertanyaan menarik apakah seseorang dapat mendefinisikan model komputasi kuantum yang berbicara tentang operator komuter dan sistem dimensi tak hingga. Tampaknya Cleve, dkk telah mencoba untuk membuat model untuk ini, sesuatu yang mereka sebut model C * -circuit:https://arxiv.org/pdf/1811.12575.pdf. Anda mungkin menganggap ini menarik.