Sonuçları $MIP^\ast=RE$ Kuantum Algoritmalarına İlişkin
(Bekleyen akran incelemesi) kanıtı $MIP^\ast=RE$içinde bu ön baskı belirgin bir atılım olarak övgü edilmiştir. Bu sonucun önemi, bu blog yazısında yazarlardan biri olan Henry Yuen tarafından ele alınmıştır . Scott Aaronson, bu blog gönderisindeki bazı önemli çıkarımları da listeliyor .
Yerel olmayan bir oyun için ($G$), göreceli olmayan tensör ürün stratejileri için başarı olasılıklarının üstünlüğünü şu şekilde tanımlayın: $\omega^\ast(G)$ve göreceli bir işe gidip gelme operatörü (QFT) stratejisi için başarı olasılıklarının üstünlüğü, $\omega^{co}(G)$. Göreli olmayan QM, QFT'nin özel bir durumu olduğu için, operatör tabanlı optimal bir işe gidip gelme stratejisinin en azından optimal tensör ürün bazlı strateji kadar iyi olduğu açıktır.$\omega^\ast(G) \le \omega^{co}(G)$.
Yuen'in gönderisinden anladığım kadarıyla, $MIP^\ast=RE$ yerel olmayan oyunların mevcut olmasıdır. $\omega^\ast(G) < \omega^{co}(G)$. Özellikle diyor ki
Bir oyun olmalı $G$, bu durumda kuantum değeri, işe gidip gelme operatörü değerinden farklıdır. Ancak bu, Tsirelson sorununun olumsuz bir cevabı olduğu anlamına gelir ve bu nedenle Connes'in gömme varsayımı yanlıştır.
Bunu, QFT (gidiş-dönüş operatörleri) tekniklerini kullanan algoritmaların, göreceli olmayan QM (tensör ürünleri, kuantum devre formalizmi) tekniklerini kullanan algoritmalardan daha yüksek başarı olasılıklarına sahip olduğu bir problem sınıfı olduğu anlamına gelmesini anlıyorum.
Sorumun ilk kısmı, bu kanıtın geçerli olduğunu varsayarsak :
- Yapar $MIP^\ast=RE$ göreli olmayan QM formalizminden (geleneksel kuantum devreleri) ziyade QFT'nin matematiksel formalizmini (gidiş-dönüş operatörleri) kullanarak daha verimli bir şekilde çözülebilecek bir dizi problem olduğunu ima eder.
Yanlış yorumlamıyorsam, bu doğrudan Yuen'in ifadelerinden kaynaklanıyor gibi görünüyor. Öyleyse, yerel olmayan oyunların olması mümkün müdür?$\omega^\ast(G) < 0.5$ ve $\omega^{co}(G) > 0.5$? Özellikle sorumun ikinci kısmı şudur:
- Yapar $MIP^\ast=RE$ kuantum devreleri kullanılarak çözülemeyen, işe gidip gelme operatörleri kullanılarak çözülebilecek bir dizi problem olduğunu (veya olabileceğini) ima eder veya bu olasılık kuantum devre modelinin evrenselliği tarafından kapatılmış mıdır?
DÜZENLEME: Henry Yuen bir yarattı MIP * Wiki daha iyi bu karmaşıklık sınıfını anlamak ilgilenen olanlar ya da$MIP^\ast = RE$ sonuç.
Yanıtlar
MIP * = RE sonucunun olup olmadığını ve özellikle yerel olmayan bir oyunun var olduğu iddiasını bilmiyorum $G$ nerede $\omega^*(G) \neq \omega^{co}(G)$, kuantum bilgisayarlar için herhangi bir algoritmik etkiye sahiptir. Burada söylenecek birkaç şey var.
MIP * = RE sonucu, yerel olmayan oyunlarla neyin çözülebileceğinin tersine, hangi hesaplama sorunlarının yerel olmayan oyunlar kullanılarak doğrulanabileceğiyle ilgilidir (bunun ne anlama geldiğinden emin değilim, yine de!). Doğrulama ve çözme arasındaki ayrım şunlardan kaynaklanmaktadır: yerel olmayan bir oyunda, Alice ve Bob'un sorunun cevabını sihirli bir şekilde bildiklerini varsayıyoruz (bu nedenle, herhangi bir hesaplama problemini anında çözebileceklerini varsayıyoruz). Zorlukları onu çözmek değil, ispat etmektir.bir polinom zaman klasik doğrulayıcıya cevabı biliyorlar. Sadece bir şeyin cevabını bilmek, başka birini cevaba ikna edebileceğiniz anlamına gelmez. Alice ve Bob'un tensör ürün çerçevesinden veya işe gidip gelme operatörü çerçevesinden korelasyonları kullanıp kullanamayacağı, doğrulayıcıya kanıtlayabileceklerini etkiler. MIP * = RE, tensör çarpım korelasyonları ile Alice ve Bob'un bir Turing Makinesinin sonunda durduğunu bildiklerini kanıtlayabileceklerini gösteriyor. Alice ve Bob, işe gidip gelme operatörü korelasyonlarını paylaşıyorsa, bu yapılamayacak bir şeydir; bu nedenle işe gidip gelme operatörü modeli tensör ürün modelinden farklıdır.
Bahsetmek istediğim ikinci şey, ayrı ayrı, işe gidip gelme operatörleri ve sonsuz boyutlu sistemlerden bahseden bir kuantum hesaplama modelinin tanımlanıp tanımlanamayacağı ilginç bir sorudur. Görünüşe göre Cleve ve diğerleri bunun için bir model bulmaya çalıştı, C * devre modeli dedikleri bir şey:https://arxiv.org/pdf/1811.12575.pdf. Bunu ilginç bulabilirsin.