Fokus i detta dokument är på kvantfördelad beräkning, där vi undersöker om kvantkommunikation kan bidra till att påskynda distribuerade nätverksalgoritmer. Vårt huvudsakliga resultat är att för vissa grundläggande nätverksproblem såsom minsta spännvidd träd, minsta klippning, och kortaste vägar, kvantkommunikation inte hjälper till att avsevärt påskynda distribuerade algoritmer för dessa problem jämfört med den klassiska inställningen. För att uppnå detta resultat utökar vi tekniken hos Das Sarma et al. [SICOMP 2012] för att få ett enhetligt tillvägagångssätt för att bevisa icke-triviala nedre gränser för kvantfördelade algoritmer för flera grafoptimering (både exakta och ungefärliga versioner) samt kontrollproblem, varav några är nya även i den klassiska inställningen, t.ex. Den fullständiga versionen av detta papper finns på http://arxiv.org/ abs/1207.5211 † och spänner över trädverifieringen, svarar på ett öppet problem med Das Sarma et al., och en lägre gräns i förhållande till viktaspekten, som motsvarar de övre gränserna för Elkin [STOC 2004]. Vårt tillvägagångssätt introducerar Servermodellen och Quantum Simulation Theorem som tillsammans ger en koppling mellan distribuerade algoritmer och kommunikations komplexitet. Servern modellen är standard tvåparts kommunikations komplexitet modell förstärkt med ytterligare kraft, men ändå är det mesta av hårdheten i tvåpartsmodellen överförs till denna nya modell. Den Quantum Simulation Theorem bär denna hårdhet vidare till kvant distribuerad dator. Våra tekniker, förutom beviset på hårdheten i Server-modellen, kräver mycket lite kunskap i kvantdator, och detta kan bidra till att övervinna ett vanligt hinder för att bevisa gränser på kvantfördelade algoritmer. I synnerhet, om man kan bevisa en lägre gräns för distribuerade algoritmer för ett visst problem med hjälp av tekniken i Das Sarma et al., är det troligt att en sådan lägre gräns kan utvidgas till kvantinställning med hjälp av verktyg som tillhandahålls i detta papper och utan behov av kunskap i kvantdator. Problem Våra resultat Ham, ST, MST-verifiering (n/B log n) deterministisk, klassisk kommunikation [13, 36 ]  och ( n/B log n) tvåsidigt fel, kvantkommunikation med insnärjning Conn och andra verifieringsproblem från [13]  och ( n/B log n) tvåsidigt fel, klassisk kommunikation [13] α-ca MST och andra optimeringsproblem från [13] (n/B log n) Monte Carlo, klassisk kommunikation för W =  och (αn) [13]
Nyligen, Elkin et al. REF visade att kvantkommunikation inte avsevärt kan påskynda algoritmer för vissa grundläggande problem, t.ex. minsta spännträd, jämfört med den klassiska inställningen.
Can quantum communication speed up distributed computation?
{'venue': "PODC '14", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}