Birkaç hafta önce ortak yazarlarım Zhengfeng Ji (UTS Sydney), Heny Yuen (Toronto Üniversitesi) ve Anand Natarajan ve John Wright (ikisi de Caltech'in IQIM'inde, John yakında UT Austin'e taşınıyor) ve ben el yazması başlıklı arXiv preprint sunucusunda
MIP * = RE
Tek harfli formülün büyüsü hızla etkisini gösterdi ve yayınımız blogosfer üzerinde biraz ilgi gördü (aşağıdaki bağlantılara bakın). Bilgisayar bilimlerinde karmaşıklık teorisi, birkaç harfle güçlü ifadeler yakalama yeteneğinde avantajlıdır: P, NP'nin başkanı olmayan ve bu blogun okuyucuları için BQP ve QMA? (Buna karşılık, daha açıklayıcı bir başlıktaki belirsiz girişimimin, bu satıra ulaştığınız zaman, okuyucunun hafızasından tamamen yok olduğu konusunda hiçbir yanılsamam yok.)
Ancak bu popülariteyi hesaba katarak bile, okuyucularımızın daha azının MIP * veya RE'yi duymuş olması güvenli bir bahis. Yine de, yukarıda belirtilen eşitliğin fizik (serbestlik çalışmalarında “Tsirelson problemi”) ve matematik (von Neumann cebirleri teorisinde “Connes'in gömme problemi”) için büyük sonuçları olduğuna söz veriyoruz. Nasıl yani - karmaşıklık teorik alfabe çorbasının bir yandan fiziksel gerçeklik ve diğer yandan soyut matematik için nasıl bir sonucu olabilir?
Bu yazının ve bir sonrakinin amacı, ilgili okuyucunun kuantum mekaniği için etkileşimli kanıtların (MIP * sembolleri arasında yatan) ve kararsızlığın (RE'nin arkasında yatan) önemini kavramasına yardımcı olmaktır.
Mevcut yazının büyük kısmı, benim için yazdığım bir yazının neredeyse aynı kopyası kişisel blog. Kendine intihal suçlamalarından kaçınmak için, onu küçük bir resim ve bir hikaye ile doğrulayacağım, aşağıya bakın. Yazı, yukarıda belirtilen sonuca götüren araştırmayı çok kişisel bir şekilde ele alıyor. Bir sonraki yazıda, ortak yazarım Henry Yuen, sonuca ve önemine daha bilimsel bir giriş yapmayı teklif etti.
Devam etmeden önce, bu gönderi ve bir sonraki bölümde açıklanan araştırmanın topluluk tarafından hakem edilmediğini veya kapsamlı bir şekilde incelenmediğini açıklığa kavuşturmak önemlidir. Bu süreç önümüzdeki aylarda gerçekleşecek ve sonuçlara çok fazla ağırlık koymadan önce tamamlanmasını beklemeliyiz. Bir yazar olarak işimle gurur duyuyorum; ancak iddiaların resmileştirilmesinden önce yapılması gereken bir süreç olduğunun farkındayım. Bu nedenle, bu görevler sadece benim (ve Henry'nin) fikrimi temsil eder, daha geniş bilim camiasının fikrini değil.
Sonuçlarımızla ilgili daha popüler tanıtımlar için sayfasının blog yayınlarına bakın Scott Aaronson, Dick Lipton, ve Gil Kalai ve raporlama Davide Castelvecchi Doğa ve Emily Conover Bilim için.
Şimdi kişisel gönderi ... ve vaat edilen resim için. 
Güzel değil mi Tasarım, birincisi misafir öğrenci ve ikincisi Caltech'in IQIM'inde doktora sonrası araştırmacı olan Tony Metger ve Alexandru Gheorghiu'nun izniyle yapılmıştır. Tony ve Andru fikri ortaya atarken, uygulama, özel tasarımı nezaketle uygulayan fırıncı dükkanı çalışanının izniyle yapıldı (görünüşe göre keklerin üstüne denklemler yazmak standart tekliflerin bir parçası olacak kadar yaygın değil, bu yüzden bunu yapmak zorunda kaldılar. özel seçenek için gidin). Celladın kopyaladıkları işaretlerin tüm derinliğini kavrayıp kavrayamadığı belirsiz olsa da, uygulamanın ne kadar mükemmel olduğuna dikkat edin: tek bir harf bile yersiz değildir! Tony, Andru ve lezzetli hatıra için isimsiz şefe teşekkürler.
Şimdi hikaye için. Bir önceki sonrası kişisel araştırma blogumda, son sonuç Natarajan ve Wright tarafından çok-prover interaktif kanıtların şaşırtıcı gücünü gösteren kuantum üreticileri ile dolaşıklığı paylaşıyor: harflerle, 
. Bu yazının geri kalanında Ji, Natarajan, Wright ve Yuen ile olan takip çalışmalarımızı anlatacağım. Bu yazıda, hikayenin kişisel bir bakış açısıyla, bunun ima ettiği tüm uyarılarla anlatacağım: “sert bilim” sınırlı olacak (ancak “bilim” in nasıl büyük bir kelime kullanacağına dair bir ipucu olabilir , “İlerliyor”, kötü tanımlanmış olanı kullanmak için; Henry Yuen'in daha fazla bilgi için yaklaşan gönderisine de bakın), hikaye çok uzun ve bu sadece benim için çok ilginç olabilir. Bu tek taraflı bir hikaye, ama olmalı. (Özellikle aşağıda zaman zaman “X bu fikre sahipti” şeklinde kredi atfedebilirim. Bu sadece benim anımsamam ve muhtemelen yanlış. Kesinlikle çok önemli konuları görmezden geliyorum.) Bunu yazdım çünkü hikayedeki en iyi anlardan bazılarını en zor olduğu kadar hatırlamaktan zevk aldılar; Başlangıçta bağlantısı kesilmiş görünen fikirlerde geriye dönüp bakmak anlamlıdır. Bunu, farklı çalışma çizgilerinin beklenmedik şekillerde nasıl bir araya gelebileceğinin bir örneği olarak düşünün; açık uçlu araştırma için bir durum. Kendim için hazırladığım umutsuzluğa karşı bir panzehir: ne zaman çok uzun süre bir projeye sıkıştığımı hissettiğimde, bu göreve geri döneceğim ve kendime henüz 14 yıl olup olmadığını soracağım - eğer değilse, sonra üzerine basın.
Benim için bir sürpriz olarak gelebilir, ancak artık beşikten yeni çıkmıyorum. Akademik hayatım 14 yıl önce ciddi bir şekilde başladı, 2006 baharında Bilgisayar Bilimi Yüksek Lisans tezimi Fransa'daki Orsay'da Julia Kempe'nin gözetiminde tamamladım. Bir önceki dönemde Julia ile tanışmıştım: kuantum hesaplama dersi, katıldığım Master programında açık ara en iyi öğretilen ve en heyecan verici kurstu ve beni hemen bağladı. Julia tezimi denetlemeyi kabul etti ve Stephanie Wehner tarafından kuantum mekaniğinde dolaşma ve serbestlik ile ilgili çalışmayı interaktif kanıtlama sistemleri hakkında karmaşıklık-teorik sorulara bağlayan bazı ilginç sonuçlara bakmamı önerdi (özellikle, bu Stephanie'nin kâğıt gösteren bu 
).
O zaman konu çok yeniydi. Bir önceki yıl bir güzel kağıt Cleve ve ark. (o zamandan beri birçok öğrenciye tavsiye ettim!) Benim için mükemmel bir uyumdu: lisans geçmişime bağlı karmaşıklık teorisinin ve kuantum hesaplamanın matematiksel yönleri, kuantum mekaniğinin göreceli somutluğu (sonuçta fiziksel bir teoridir) ) gerçek dünyadaki bağlantı arzumla konuştu (“etki” ya da “uygulama” değil, sadece “bağlantı”). Bir kez kendimi bölgede hızlandırdım (üç kağıttan oluşuyordu: bahsettiğim iki, bir kâğıt Kobayashi ve Matsumoto tarafından kuantum mesajları ile etkileşimli kanıtlar üzerinde çalıştıkları) Julia, “dolaşmış-prover” sınıfına bakmayı önerdi 
Cleve ve ark. Bu sınıf hakkında hiçbir şey bilinmiyordu! Tek dilimli etkileşimli provaların, IP'nin ve tüm diller içeren önemsiz sınıftaki ... TÜMÜNÜN içerilmesinin önemsiz dahil edilmesinden başka bir şey yok.
Yine de Babai ve ark. Tarafından klasik muadilinin MIP = NEXP karakterizasyonu. 1990'larda PCP teoremi ve yaklaşım sertliğinden verimli kriptografik şemalara kadar kullanımı sayesinde son birkaç on yılın karmaşıklığı içinde en verimli çalışma hatlarından birine yol açmıştı. Elbette çalışıyorum üretken bir yön olmalıydı? Klasik karmaşıklık teorisine sağlam bir şekilde bağlanmış olmasına rağmen, interaktif kanıtların biçimciliği yoluyla, bu gerçek bir kumardı. Karmaşıklık-teorik açıdan dolaşıklık çalışması tamamen yeniydi ve zorlukla dolmak zorundaydı; çok az sonuç elde edildi ve mevki dışı olmanın temellerinden, cihazdan bağımsız kriptografide daha yeni çabalara kadar mevcut çalışma hatları, en basit örneklerin bile birçok cevaplanmamış soru ile geldiğine dair güçlü kanıtlardan çok az bir başlangıç noktası sağladı. Ama akıl hocam korkusuzdu ve kuantum rastgele yürüyüşlerden adyabatik hesaplama yoluyla Hamilton karmaşıklığına kadar çeşitli alanlarda öncü çalışmalar yapmış yeni alanlara meydan okumak açısından acemi olmaktan uzaktı. Elbette bu bir şeye yol açar mı?
Kesinlikle oldu. Kağıtlardan daha uykusuz geceler, açıkça, ama sonra tersi sadece donukluğu gösterecektir. Julia'nın sorusu, o zamanlar hayal edebileceğimden çok daha beklenmedik sonuçlara yol açtı. Bu yayını, onlarca araştırmacının 15 yıllık araştırmasının son adımını kişisel bir şekilde kutlamak için yazıyorum: bugün ortak yazarlarım ve ben, gücün tam bir karakterizasyonunu düşündüğümüz miktar-ph arXiv'e yükledik eşitliği kanıtlayarak dolaşmış-prover interaktif kanıtlama sistemleri 
, özyinelemeli olarak numaralandırılabilir dillerin sınıfı (RE için tam bir sorun durma problemidir). Sonucun içine çok fazla girmeden (ilgileniyorsanız, burada kanıtlara biraz daha yaklaşan bir gönderiye bakın) ve bu daha kişisel bir yazı olduğundan, hakkında bazı kişisel düşünceler ile devam edeceğim Bizi oraya götüren yol.
Julia ve ben soru üzerinde çalışmaya başladığımızda, ana ilham kaynağımız Cleve ve arkadaşlarının sonuçlarıydı. Karmaşıklık teorisindeki etkileşimli ispat sistemleri merceğinden bakıldığında, dolanmanın yerel olmayan korelasyonlarının ilginç sonuçlar doğurduğunu göstermek. EPR makalesinden bu yana, Fizik topluluğunda, özellikle de Mermin, Peres, Bell ve son zamanlarda Acin, Pironio, Scarani ve diğerlerinin cihazdan bağımsız kuantum kriptografisinde yapılan çalışmalar olmak üzere, dolanıklığı anlamaya yönelik birçok çalışma gerçekleştirildi. , Ekert'in kuantum anahtar dağıtımı önerisi ve Mayers ve Yao'nun "cihazdan bağımsız kriptografi" fikri ile teşvik edildi. O zamana kadar, "ürkütücü bir mesafedeki eylemin" ışıktan daha hızlı bir iletişimi gerektirmediğini ve aslında ilk etapta gerçekten "uzaktan eylem" olmadığını, yalnızca "korelasyon" olduğunu kesinlikle biliyorduk. uzaktan ”. Ne Cleve ve ark. Bell'in kuantum mekaniğindeki yerel olmayışı kanıtlamak için icat ettiği araç olan "Bell eşitsizlikleri" nde yalnızca sayısal olarak farklı değerler vermekle kalmayıp, aynı zamanda bazı "ürkütücü korelasyonların" yeterince özel olduğu kabul edildi. karmaşıklık teorisinde potansiyel olarak derin sonuçlar.
Özellikle, “Sihirli Kare oyunu” gibi örnekler, sağlamlığı sadece protestocular arasında iletişimin bulunmamasına dayanan temel kanıt sistemlerini yenmek için dolaşıklıktan yeterli korelasyonun kazanılabileceğini gösterdi, o zamana kadar yanlış eşitlenmiş bir varsayım protestocular tarafından yapılan herhangi bir hesaplamanın tamamen yerel olarak modellenebileceği varsayılarak. Bu örtük varsayımın yanlışlığının, hala tamamen içselleştirmemiş olabilecek karmaşıklık teorisyenlerine bir sürpriz olarak geldiğini düşünüyorum. Yine de Magic Square oyunu için mükemmel kuantum stratejisi, 3SAT için “yan tümce-değişken” oyununun sağlamlığına çok somut bir “karşı örnek” sağlar. Gerçekten de bu oyun, Aravind ve Cleve-Mermin tarafından 1990'da Mermin ve Peres tarafından keşfedilen bir Çan Eşitsizliğinin yeniden yapılandırılması, kolayca tatmin edilemeyen 3SAT denklemler sistemi olarak yeniden tasarlanabilir ve oyuncu yan tümce vs değişken oyun mükemmel bir kuantum stratejisine sahiptir. Cleve ve ark. Tarafından makalede yapılan bu gözlem, etkileşimli prova sistemlerinde dolaşıklık kullanımının bölgedeki birçok klasik sonucun ters gidebileceğine dair ilk güçlü ipucunu verdi.
Yöresel olmama çalışmasını karmaşıklık teorisine aktararak Cleve ve ark. hemen asimptotik analiz alanına getirdi. Karmaşıklık teorisyenleri sabit nesneleri araştırmazlar, altta yatan düzgün bir yapıya sahip olan ve ilginç özellikleri kendilerini “sınırda” gösteren nesnelerin ailelerini incelerler. Bu yeni perspektifin bir sonucu olarak, tekli oyunların veya korelasyonların incelenmesinden sonsuz ailelere kaymıştır. Bu çevirinin ilk başarılarından bazıları, iletişim karmaşıklığındaki asimptotik ayrımların Bell eşitsizlikleri ve korelasyonların diline (ör. Bu kağıt). Bu ilk başarılar, vakıflarda çalışan bazı fizikçilerin yanı sıra bazı matematik fizikçilerinin de dikkatini çekti ve kuantum bilgileri, fonksiyonel analiz ve karmaşıklık teorisinden araçları birleştiren üretken bir keşfe yol açtı.
Cleve ve ark. işaret etmişti ilginç bir karmaşıklık dersi olarak Oldukça şaşırtıcı, bu konuda hiçbir şey bilinmiyordu! Doğrulayıcının yüklemine ilişkin güçlü kısıtlamalar altında (iki cevap bitinden oluşan bir XOR olmalıdır) bir çöküş meydana geldiğini göstermiştir: Hastad'ın çalışmasıyla XOR-MIP, NEXP'ye eşittir, ancak EXP'ye dahildir. Bu çok tesadüfi görünüyordu (içerme, XOR-MIP protokollerinin yapısına bağlı görünen yarı taraflı programlama ile bir bağlantı ile kanıtlanmıştır): dolaşıklık, tüm sınırsız sınıfın çökmesine neden olabilir mi? (Bu noktada Julia çoğunlukla düşündüm, çünkü hiçbir fikrim yoktu) bunun böyle olmaması gerektiğini düşündük ve bu nedenle kendimizi eşitliğin 
Babai ve arkadaşlarının MIP = NEXP karakterizasyonuna doğrudan paralel olacaktır. Bunu, dolaşıklığa karşı “bağışıklık kazandırmak” için teknikler tanıtarak göstermeye çalıştık: etkileşimli bir kanıt sistemini modifiye ederek yapısını madde-değişkeni yenmek için kullanılabilecek “yerel olmayan güçlere” karşı “dirençli” hale getirecek oyunu (Sihirli Meydan'a tanık olun). Bu kısmen başarılı oldu ve en gurur duyduğum gazetelerden birine yol açtı - bununla gurur duyuyorum çünkü temel teknikleri (Cauchy-Schwarz eşitsizliğinin kullanılması gibi - şaka içinde - daha ciddiye, temel şeyler) "atasözü değiştirme", "komütasyon testleri" vb.) artık bu alandaki rutin manipülasyonlardır. Kağıt zor bir satış oldu! Aldığımız ilk reddetmeleri hatırlamak güzel. Onlar haksız değildi: eleştirinin ana noktası, sadece üstel olarak küçük bütünlük-sağlamlık boşluğu için bir sertlik sonucu oluşturabilmemizdi. Klasik ortamda böyle küçük bir boşluk için bir sonuç, doğrudan Cook-Levin teoremine dayanan çok temel bir analizden kaynaklanmaktadır. Öyleyse neden temelde aynı sonuca ulaşmak için bu kadar çok sayfa yazdık (ve Cauchy-Schwarz'ın birçok uygulaması!) 
)?
Sonunda şanslıydık ve bildiri konferansa kabul edildi. Ama asıl sorun, sınıfta önemsiz bir alt sınır oluşturmanın sabit (veya herhangi bir paralel tekrarlama teoreminin yokluğunda, ters-polinom) bütünlük-sağlamlık boşluğu kaldı. O zamana kadar Fransa'daki bir Yüksek Lisans öğrencisinden Berkeley'deki bir yüksek lisans öğrencisine geçtim ve problem doktora derecemin en zor yıllarında beni işgal etti. İlk yılımı tamamen bunu düşünerek geçirdiğimi tamamen hatırlıyorum (oh ve eminim Berkeley gereksinimlerini karşılamak için geçmek zorunda olduğum sistem sınıfı) ve sonra ikinci yılım - yine de hiçbir yere ulaşamıyorum. (Bunu telafi etmediğimden emin olmak için arXiv'i kontrol ettim: iki tam yıl, gönderi yok.) Diğer öğrencilerim Anindya De'ye, kapımı çalarak işkence döngüsünden çıkardıkları için sonsuza dek minnettarım. çalıştığım en ilginç sorulardan biri, beni kuantum kriptografisine götürdü ve hızlı bir şekilde bir eğlenceli kağıt. Yeniden üretken hissetmek güzeldi! (Kağıdın da eğlenceli tepkileri olmasına rağmen: arXiv üzerine koyduktan sonra, alandaki uzmanlardan ilgisiz bir sorunu çözdüğümüzü ve bilgi teorisini daha iyi öğrendiğimizi daha iyi öğrendik - ki sonunda yaptık, kâğıtProjenin dikkatimi dağıtmıştı ve etkileşimli kanıtları bir kenara bıraktım; açıkça, sıkışmıştı.
Yaklaşık bir yıl sonra Waterloo'da IQC'yi ziyaret ettim. Ziyaretin hangi bağlamda gerçekleştiğini hatırlamıyorum. Hatırladığım şey, IQC'de doktora sonrası bir akademisyen olan Tsuyoshi Ito'nun ofisinde bir toplantı. Tsuyoshi benden sonuçlarımızı Julia ile açıklamamı istedi. Daha sonra çok sivri bir soru sordu: Etkileşimli prova sistemlerinin klasik analizi için temel kaya, Blum-Luby-Rubinfeld'in (BLR) “doğrusallık testi” dir. Bu testin kuantum versiyonunu tasarlamanın herhangi bir anlamı var mı?
Ne soru ama! Bu harikaydı. İlk başta sonuçsuz görünüyordu: kuantum kanıtlayıcıların “doğrusal bir işlev” uyguladıkları hangi anlamda iddia edilebilir? Elbette, kuantum mekaniği lineerdir, ama bu noktadan başka bir şey değildir. Doğrusallık, sorularının bir fonksiyonu olarak kanıtlayıcının cevaplarının bir özelliğidir. Peki kuantum durumu, doğal rastgelelik, vb.
Bunu çözmemiz birkaç ayımızı aldı. Ancak oraya vardığımızda, cevap nispeten basitti - kanıtlayıcı, doğrulayıcıya döndürülen cevabı elde etmek için sorusuna uyguladığı doğrusal bir fonksiyon döndüren sorudan bağımsız bir ölçüm yapmalı ve sonraki kâğıt NEXP'in gerçekten tutar. Tsuyoshi'nin doğrusallık testi ile ilgili sorusu PCP teknikleriyle bağlantı kurmamızı sağlamıştır; oradan MIP = NEXP'e kadar yapılacak çok bir adım vardı, bu da çok doğrusallık testini analiz etmektir. Bu adım doktora derecem tarafından önerildi. teorem büyük ölçüde eski öğrencisi Sanjeev Arora tarafından elde edildiğinden beri klasik PCP teoremine giden birçok yolun farkında olan danışman Umesh Vazirani. Çok fazla teknik çalışma gerektirdi, ancak kavramsal olarak ortak yazarımdan gelen tek bir soru beni 3 yıllık bir uykudan çıkarmak için yeterliydi.
Bu 2012 yılındaydı ve bittiğimizi sanıyordum. Bazı nedenlerden dolayı, NEXP'de çabalarımıza direniyor gibiydi, ama kesinlikle daha uzun süre dayanamadı. Navascues ve diğ. doğru cevabı vermiş gibi görünen yarı-yanlı programlar hiyerarşisini ortaya koymuştu (teknik olarak sadece gevşeme, işe gidip gelme değerine yakınsama gösterebildiler, ancak bu bir tekniklik gibi görünüyordu; özellikle, değerler sınırlı boyutlu stratejilerle sınırlı olduğunda çakışıyor, bilgisayar bilimcilerinin önem verdiği her şey budur). Hiyerarşide yakınsama sınırı yoktu, ancak aynı zamanda komütasyonel optimizasyonda çok güçlü sonuçlar elde etmek için değişmeli SDP hiyerarşileri kullanılıyordu ve birisinin analizine gelmesi sadece bir zaman meselesi gibi görünüyordu. kuantum durumu. (Yıllardır Oded Regev ile ilgili bir “boyut küçültme problemini” çözmeye çalışıyordum ve hiçbir ilerleme kaydetmedik; yine de birileri yapması gerekiyordu!)
2014 baharında açık bir soru oturumu sırasında atölye Berkeley Dorit Aharonov'daki Simons Enstitüsü'nde, QMA'nın üstel boyutlu kanıtlar analogu olan QMA-EXP'nin olası dahil edilmesi sorusunu . NEXP'in (varsayımlar altında) dahil edilmesinden daha güçlü bir sonuç, MIP = NEXP'in daha doğal bir “tam kuantum” analogu olmaz mıydı? Dorit'in önerisi, yerel Hamilton problemi alanında benzer sertlik sonuçları oluşturmayı amaçlayan “kuantum PCP teoremi” üzerine yapılan araştırmalarla motive edildi; bakınız örneğin bu Facebook post bağlantı için. Soruya nasıl yaklaşacağım hakkında hiçbir fikrim yoktu - cevabın olumlu olabileceğine gerçekten inanmadım - ama Dorit sana bir şey sorarsa ne yapabilirsin… Bu yüzden isteksizce tahtaya gittim ve soruyu sordum. Joe Fitzsimons seyirciydi ve hemen aldı! Joe, kanıtlayıcılar arasında bir kuantum kanıtı dağıtmak için kuantum hata düzeltme veya daha özel olarak gizli paylaşım kullanma konusunda harika fikirlere sahipti. Onun coşkusu şüpheciliğimin üstesinden geldi ve sonunda gösterdi istenen dahil etme. Olabilir daha büyüktü 
Bütün sonra.
Bununla birlikte, sonuçumuz, tamlık-sağlamlık boşluğunun katlanarak küçük olması nedeniyle Julia ile benzer bir eksikliğe sahipti. Sürekli bir boşlukla sonuç elde etmek, 3 yıl daha fazla çalışma ve bir doktora müthiş enerji ve anlayışını aldı. MIT, Anand Natarajan. Anand, yukarıda bahsi geçen sonuçların analizinin en teknik yönlerine dalma cesaretine sahip olduğumu bildiğim ilk kişidir, aynı zamanda Anand'ın Fizikteki arka planı tarafından desteklenen “gerçek kuantum bilgi teorisyeni” anlayışını da beraberinde getirir. ve MIT'de Aram Harrow grubunda yetiştirme. (Aksine kendimi daha çok “ham” bir matematikçi olarak düşünüyorum; kuantum durumları pozitif semidefinite matrisleri dışında gerçekten anlamıyorum… tabii ki matematiği anladığım için değil; sanırım bir buçuk pişmiş mish-mash.) Anand'ın birçok fikri vardı ama en güzel fikirlerinden biri şiirsel olarak “Pauli örgü testi” olarak adlandırdığı şeye yol açtı, BLR doğrusallık testinin iki doğrusallık testi yapmaya denk gelen “gerçekten kuantum” analogu konjugat bazlar ve sonuçları birlikte {n} -kubit dolaşıklığı için sağlam bir test haline getirmek (bu konudaki çalışmalarımız hakkında yazdım) okuyun).
Yaklaşık olarak aynı zamanda, Zhengfeng Ji'nin bir anlamda işimize dik olan başka bir harika fikri vardı. (Benim yorumum) Zhengfeng'in fikri, etkileşimli bir kanıt sistemini bir hesaplama (doğrulayıcı-kanıtlayıcı-doğrulayıcı) olarak görebilir ve tüm hesaplamayı bir “kuantum CSP” ye dönüştürmek için Kitaev'in devre-Hamiltonian yapısını kullanabilir. yerel Hamilton probleminin kendisinin bir kuantum çoklu-kanıtlamalı interaktif kanıtlama sistemi tarafından doğrulanabilen kuantum bir klasik kısıtlama memnuniyeti problemlerinin (CSP) analogu olduğunu düşünüyoruz… verimlilikte üstel kazançlarla! Zhengfeng'in sonucu, Julia ve kendimin sonucuna kıyasla karmaşıklıkta üstel bir iyileşme ima etti ve NEXP yerine NEEXP'nin . Bununla birlikte, Zhengfeng'in tekniği, sahip olduğumuzla aynı katlanarak küçük tamlık-sağlamlık boşluğundan muzdaripti, böylece en iyi alt sınır kendi başına NEXP olarak kaldı.
Her iki eser de takiplere yol açtı. Natarajan ile Pauli örgü testini “kuantum düşük dereceli test”, QMA-EXP’nin , sürekli bir boşluk ile, sonunda sorulduktan 4 yıl sonra Aharonov tarafından sorulan soruyu cevaplıyor. (Şunu da söylemeliyim ki o zamana kadar tüm sonuçlar Bavyera, Yuen ve diğerleri tarafından gösterilen bir dizi paralel tekrarlama sonucuna güvenmeye başladı; Bu kısmı atlıyorum.) Paralel olarak, Ji, Fitzsimons ve Yuen ile birlikte, Ji'nin sıkıştırma tekniğinin rasgele sayıda “yinelenebileceğini” gösterdik. Aslında, "ilk ilkelere" geri dönüp doğrulayıcıları Turing makineleri olarak eşit bir şekilde temsil ederek, sıkıştırma tekniğinin (küçük uyarılara kadar) iteratif olarak kullanılabileceğini fark ettik (ilk önce) gösterilen Sonlu olarak sunulan grup için gömme teoremi kullanarak Slofstra tarafından) durma problemini içerir. Özellikle, dolaşmış değer hesaplanamaz! Bu, hesaplanamazlığın kuantum hesaplamadaki doğal bir soruna ilk kez verdiği değildi (ör. spektral boşluk kağıdı), ancak ortaya çıktığında hala şaşırtıyor. Uncomputable! Nasıl bir şey nasıl hesaplanamaz olabilir!
Makalemizi tamamlarken Henry Yuen “interaktif prova sistemlerinin yinelenen sıkıştırılması” nın aşağıdaki anlamda muhtemelen optimal olduğunu fark etti. Sıkıştırma yoluyla tamlık-sağlamlık boşluğunun daha yavaş kapanması şeklinde tekniğin hafif bir şekilde iyileştirilmesi bile çok daha güçlü bir sonuç verecektir: sabit boşluk sınıfının kararsızlığı . Navascues ve diğerleri, Fritz ve diğerlerinin çalışmaları ile zaten böyle bir sonucun, şaşırtıcı olmasa bile, bizi derinliğimizden çıkarmış gibi görünen sonuçlara sahip olacağı zaten biliniyordu. Özellikle, herhangi bir dilin kararsızlığı Tsirelson'in probleminden Kirnes'in QWEP varsayımı yoluyla Connes'in Gömme Konjonktürüne kadar fonksiyonel analizde bir dizi eşdeğer varsayım için olumsuz bir çözüm anlamına gelecektir. Sonuçlarımızı beğendikçe, bunun fonksiyonel analizdeki herhangi bir varsayımı / çözümü çözebileceğine inandığımızı sanmıyorum.
Biz de yolumuza devam ettik. En azından devam ettim, değişiklik için biraz kriptografi yaptım. Ancak Anand Natarajan ve ortak yazarı John Wright bununla kalmadı. Bir önceki yazıda açıklanan STOC en iyi makalesinin temelini oluşturan bu hikayedeki son büyük kavrayışa sahiptiler. Kısaca, iki çalışma hattını birleştirmeyi başardılar, Natarajan ve ben düşük derece testlerinde ve Ji ve ark. mevcut olana özel olarak uyarlanmış bir sıkıştırma elde etmek için sıkıştırmada NEXP için protokol ve tamlık-sağlamlık boşluğunu azaltmadan bu protokolü sıkıştırır. Bu, Ji'nin sonucunu NEEXP içeriyor, ancak bu sefer sürekli boşluk var! Sonuç, hak ettiği dikkati çekti. Özellikle, bu çalışma dizisinde, herhangi bir uyarıdan (kapanış boşluğu veya rastgele indirimler veya modeldeki güç kazancını ilişkilendirebileceği bir tür “haksız” tweak) yaşanmayan ilk şeydir. ve MIP ile .
Sonuçlarına son dokunuşlarını yaparlarken, aniden bir şey oldu, o da çok daha büyük bir sonuca giden yolun açıldığıydı. Natarajan ve Wright'ın başardığı şey, tek adımda boşluksuz bir sıkıştırma oldu. Yinelenen sıkıştırma kağıdımızda yinelenen boşluksuz sıkıştırmanın 
söz konusu varsayımlara olumsuz cevaplar ima etmektedir. E sonra?
Sanırım biraz daha fazla çalışma gerektirdi, ancak bir şekilde tüm fikirler, kuantum interaktif kanıtlama sistemlerinin karmaşıklığında önceki 15 yıllık çalışmalarda ortaya konmuştu; sadece bir araya getirmek zorunda kaldık. Ve böylece karakterizasyondan on yıl sonra QIP = UZAY tek prover kuantum interaktif kanıtlama sistemleri, kuantum çok katlı interaktif kanıtlama sistemlerinin bir karakterizasyonuna ulaştık, . İki makale arasında ortak bir yazarla: Tebrikler Zhengfeng!
Az önce bir makale yayınlamış olsak da, bir anlamda yapacak daha çok şey var. Karmaşıklık-teorik sonucumuzun matematikçiler topluluğundan ve özellikle YSÖP'nin temel bir sorun olduğu operatör cebircilerinden yeterince ilgi çekeceğini umuyorum, bazılarının sonucu anlamak için zaman ayırmaya istekli olacakları. Ayrıca, ilk etapta erişilebilir hale getirmek için kendi tarafımızda çok çaba gerektiğini de biliyorum! Sonunda karmaşıklık teorisinin tamamen matematiksel sonuçları elde etmek için gerekli olmayacağından kuşku duymuyorum; yine de bazı fikirlerin eninde sonunda ilginç matematiksel nesnelerin (hiperlinear olmayan bir grup bilenler gibi) yapımına girebileceklerini umuyorum.
Bu iyi bir Üstatlar projesiydi… teşekkürler Julia!
