Vi använder klassen pendling kvantberäkningar som kallas IQP (Instantaneous Quantum Polynomial Time) för att stärka hypotesen att kvantdatorer är svåra att simulera klassiskt. Vi visar att om någon av två rimliga genomsnittliga fall hårdhet gissningar håller, då IQP beräkningar är svåra att simulera klassiskt upp till konstant additivt fel. En gissning avser hårdheten av att uppskatta den komplexa temperatur partition funktion för slumpmässiga fall av Ising modellen; den andra gäller approximering av antalet nollor av slumpmässiga låggradiga polynom. Vi konstaterar att båda hypoteserna kan visa sig vara giltiga när det gäller den värsta komplexiteten. Vi kommer fram till dessa antaganden genom att härleda spin-baserade generaliseringar av Bosons provtagningsproblem som undviker de så kallade permanenta antikoncentrationsförkastningarna. Kvantdatorer antas överträffa klassiska datorer för en mängd viktiga uppgifter som sträcker sig från heltal faktorisering [1] till simulering av kvantmekanik [2]. Hittills finns det dock relativt lite rigorösa bevis för detta antagande. Det är väl etablerat att kvantdatorer kan ge en exponentiell fördel i fråge- och kommunikationskomplex modeller. Men i den mer fysiskt meningsfulla modellen av tids komplexitet finns det inga bevisade separationer som är kända mellan kvant och klassisk beräkning. Detta kan ses som en följd av den extrema svårigheten att bevisa gränser på kraften i klassiska datormodeller, såsom den berömda P vs NP problem. Med tanke på denna svårighet, det mesta vi rimligen kan hoppas på är att visa att kvantberäkningar inte kan simuleras effektivt klassiskt, förutsatt att vissa allmänt trodde komplexitet-teoretiska antaganden. Till exempel ger varje uppsättning kvantkretsar som kan implementera Shors algoritm [1] ett kanoniskt exempel, med den osannolika följden av effektiv klassisk simulering av denna klass av kvantkretsar är förekomsten av en effektiv klassisk faktoralgoritm. Man kan dock hoppas på att det finns andra exempel som har mer omfattande komplexitet-teoretiska konsekvenser. Med detta i åtanke visades det i både [3] och [4] att förekomsten av en effektiv klassisk provtagare från en distribution som ligger nära utdatadistributionen av en godtycklig kvantkrets, inom ett litet multiplikativt fel i varje utdatasannolikhet, skulle innebära att postvald klassisk beräkning är likvärdig med postvald kvantifiering. Denna konsekvens anses mycket osannolik eftersom den skulle kollapsa det oändliga tornet av komplexitetsklasser som kallas polynomhierarkin [5] till sin tredje nivå. I båda verken var detta bevisat även för icke-universella kvantkrets familjer: pendla kvantkretsar i fallet med [3], och linjära-optiska nätverk i [4]. Dessa icke-universella familjer är av fysiskt intresse eftersom de är enklare att genomföra och lättare att analysera på grund av de eleganta matematiska strukturer som de är baserade på. Men i fysiskt realistiska scenar- * michael.bremner@uts.edu.au ios där kvantdatorn och dess motsvarande klassiska simulator tillåts vara korrekt upp till ett litet additivt fel, dessa resultat har liten betydelse. Ett viktigt steg nyligen för att ta itu med detta föreslogs av Aaronson och Arkhipov [4], som gav ett sofistikerat argument baserat på beräkning av komplexiteten att ungefär provtagning från utdatasannolikheten distribution av ett nätverk av icke-interaktiva fotoner (ett problem som kallas Boson Provtagning) bör vara klassiskt svårt, även upp till ett rimligt additivt fel bundet. Detta stora genombrott vilar på två frestande men ännu inte bevisade gissningar: de så kallade permanenta antikoncentrationsförkastningarna och de permanenta gaussianernas gissningar. I detta dokument föreslår vi en generalisering av Boson Provtagning argument [4] som är inhemskt att spinnsystem, särskilt för den klass av pendlande kvantkretsar som kallas IQP (Instantaneous Quantum Polynomial Time), som infördes i [6] och [3]. Enligt vår mening leder detta till en matematiskt enklare miljö, samtidigt som man uppenbarligen behåller de väsentliga komplexa-teoretiska ingredienserna. Denna enkelhet gör det möjligt för oss att bevisa IQP-analogerna i den permanenta antikoncentrationsansatsen. Det enda som återstår att bevisa är en IQP-analog av de permanenta gaussianernas gissningar, av vilka vi finner två naturliga exempel. Informellt (se [3] för den formella definitionen) är en n-qubit IQP-krets C en kvantkrets som tar som ingång det tillstånd...0  på, vars portar är diagonala i Pauli-X-basen, och vars n-qubit-utgång mäts i beräkningsgrunden. Vi säger att en klassisk provtagare av en IQP krets är korrekt upp till fel i 1 norm om dess utdata sannolikhetsfördelning har total variation avstånd som mest /2 från C. Vi kan nu ange huvudresultatet av detta papper: Theorem 1. Anta att antingen Conjecture 2 eller 3 nedan är sant. Om det är möjligt att klassiskt prov från utgången sannolikhetsfördelning av någon IQP krets C i polynom tid, upp till ett fel på 1/192 i 1 norm, då något problem i #P kan lösas i FBPP NP. Därför kollapsar polynomhierarkin till sin tredje nivå. Löst taget är komplexiteten klass #P som visas i denna sats den klass av problem reducible till räkna antalet lösningar av en NP problem [5] 2 klass av problem som kan lösas genom randomiserade klassiska polynom-tid beräkning utrustad med en orakel som kan lösa alla problem i NP. Teorem 1 är baserat på två naturliga hypoteser, av vilka en är infödd i datavetenskap, och andra vanliga i kondenserad-materia fysik. Varje gissning avser helt enkelt en familj av IQP-kretsar. I själva verket anger resultatet att om vi antar någon av våra antaganden, då finns det inget sätt att effektivt simulera dessa familjer av kvantkretsar utan en större omvärdering av den befintliga status-quo komplexitetsteori. Den första hypotesen är baserad på komplexiteten i en av de mest studerade modellerna av statistisk fysik, Ising-modellen. Betrakta partition funktion där den exponentierade summan är över den kompletta grafen på n hörn, w ij och v k är verkliga kant och vertex vikter, och A. Därefter, för alla  ska = e i på, Z( ska) uppstår okomplicerat som en amplitud av vissa IQP krets C: och [7-11]). Vår gissning är: Conjecture 2. Låt Z(en) vara partition funktion av en slumpmässig instans av Ising modellen, plockas genom att välja jämnt slumpmässiga vikter från uppsättningen {0,..., 15} på hörn och kanter av den kompletta grafen på n hörn, utvärderas vid  ska. Sedan är det #P-hård till approximation.Z(e iπ/8 ) och 2 upp till multiplicativt fel 1/4 + o(1) för en 1/24 bråkdel av fall över valet av vertex och kant vikter. Det är känt att familjen av partition funktioner Z(en) parametrised som ovan är #P-hård att beräkna i värsta fall upp till ovanstående multiplikativa fel bundna [10, 11]. Antagande 2 säger alltså att detta värsta fall hårdhet resultat kan förbättras till en genomsnittlig-fall hårdhet resultat. Vår andra gissning är baserad på hårdheten av att beräkna gapet av grad-3 polynomials över F 2, f : {0, 1} n → {0, 1}, som är uttryckliga (upp till en additiv konstant) som n. Då har vi följande gissning: Antag 3. Låt f : {0, 1} n → {0, 1} vara ett enhetligt slumpmässigt grad-3 polynom över F 2. Sedan är det #P-hård till ungefärlig ngap(f) 2 upp till ett multiplikativt fel på 1/4 + o(1) för en 1/24 bråkdel av polynom f. Det har varit känt under en tid att ngap(f) är #P-hård att beräkna exakt i värsta fall [12]. Vi visar i bilaga D, med hjälp av IQP tekniker, att denna värsta-fall hårdhet fortfarande håller för att approximera ngap(f ) 2 upp till multiplikativt fel mindre än 1/2. Precis som med Conjecture 2, vad som återstår är att lyfta denna värsta fall hårdhet resultat till genomsnittliga-fall hårdhet. Vi noterar att ytterligare ett bevis som lades fram [4] för den genomsnittliga hårdheten hos multiplikativa approximationer till Boson-provtagning (sannolikheterna för permanent-av-gaussianer) var ett direkt bevis på att exakt simulering av Bosons sannolikhetsfördelning är svår i genomsnitt. Detta baserades på genomsnittliga hårdhetsresultat för beräkning av de permanenta, för vilka vi inte känner IQP-analoger. De tekniker som för närvarande är kända verkar dock inte vara tillräckliga för att förlänga dessa exakta genomsnittliga hårdhetsresultat för Boson-provtagning till ungefärliga hårdhetsresultat [4, avsnitt 9.2]. Som i fallet med Boson-provtagning innebär den värsta hårdheten hos multiplikativa approximationer till både Z(en) och ngap(f ) ([11] och bilaga D) genom standardresultat på slumpmässig självreproducerbarhet [13] att det finns en viss fördelning över valet av dessa funktioner som är #P-hårda i genomsnitt -men inte nödvändigtvis de distributioner som vi behöver för Conjectures 2 och 3. Det finns ett antal tekniska ingredienser i Theorem 1 som kommer att diskuteras i sin helhet nedan. Den grundläggande tanken är att, för den klass av problem som ligger bakom Conjectures 2 och 3, alla klassiska sampler som är korrekt upp till en bra additiv fel bunden i värsta fall, är tvungen att också vara korrekt att inom en rimlig multiplikativ fel i genomsnitt. Detta visas genom att använda ett klassiskt resultat av komplexitetsteori, den så kallade Stockmeyer räkna algoritm [14]. En annan viktig ingrediens är antikoncentrationsresultat för ngap(f ) (för Conjecture 3) och partitionsfunktionen för den slumpmässiga Ising modellen (för Conjecture 2). Att sådana antikoncentrationsresultat kan bevisas är en följd av de eleganta matematiska strukturer på vilka IQP kretsar är baserade. Vi nämner först att den senaste tidens oberoende arbete av Fefferman och Umans [15] har utforskat ett alternativt sätt att generalisera idéerna om Aaronson och Arkhipov [4]. Detta arbete använder Quantum Fourier Provtagning för att konstruera tillstånd vars motsvarande sannolikhetsfördelningar är svåra att ta prover från klassiskt, under liknande antaganden till [4]. En tilltalande aspekt av uppförandet av [15] är att det visar att det finns specifika, och ganska enkla kvanttillstånd som är svåra att simulera klassiskt, förutsatt att en antikoncentrationssanering håller. Att bygga dessa tillstånd verkar dock kräva full effekt av kvantberäkning, till skillnad från de resultat som beskrivs här och i [4]. Vi beskriver nu våra resultat. Vi antar grundläggande kunskap om standard komplexitet klasser [5, 16] såsom P, #P och BPP. En avgörande komplexitet-teoretiska verktyg som vi kommer att använda är ett resultat av Stockmeyer på ungefärlig räkning: Det finns en FBPP NP-maskin som, för alla booleska funktion f : {0, 1} n → {0, 1}, kan approximeras till inom en multiplikativ faktor (1 + ) för alla =  och (1/ poly(n)), givet orakle tillgång till f. Vi hänvisar till [3, 6] för formella definitioner av IQP-modellen. Vi brukar överväga IQP kretsar som består av en nfold tensor produkt av en Hadamard grind H  på, en komponent 3 vars portar är diagonala i Pauli-Z bas, och en ytterligare tillämpning av H  på. För de viktigaste resultaten av detta papper kommer vi att överväga IQP kretsar vars diagonal-Z komponent består av antingen Z, CZ (kontrollerad-Z, aka styrd-fas) och CCZ (kontrollerad-kontrollerad-Z) grindar eller Z, ε CZ, och portar. Båda dessa portar skulle vara universella om vi också kunde utföra Hadamard (H) portar när som helst i kretsen - vilket vi inte kan göra i IQP eftersom denna port inte pendlar med Z-porten. Men om vi tillåter den ofysiska resursen av postval, dessa Hadamard grindar kan effektivt genomföras [3], tillåter IQP krets amplituder y-C-x att uttrycka någon kvantkrets amplitud (upp till en känd konstant). Se bilaga C för en beskrivning av denna konstruktion. En konsekvens är att exakt klassisk beräkning av sådana amplituder är #P-hård, även upp till konstant multiplikativt fel [3] eller exponentiellt litet additivt fel [9]. Tillnärmning av allmänna IQP-kretsar -Vi visar först en viktig teknisk ingrediens, som relaterar ungefärlig provtagning från utdatadistributionerna av IQP-kretsar till approximering av enskilda utdatasannolikheter. Detta är i huvudsak samma argument som användes i [4] för det permanenta, även om vi anser att det blir betydligt enklare när det gäller IQP. Intuitionen bakom detta resultat är att lägga slumpmässiga X grindar till en IQP krets slumpmässigt permuterar utdata sannolikheter. Detta gör det möjligt för användaren av en sampler som är korrekt för alla kretsar att obfusca från sampler som en av de utdata sannolikheter användaren är intresserad av. Det här är Lemma 5. Låt C vara en godtycklig IQP krets på n qubits. Låt C x, för x  ska {0, 1} n, vara den krets som produceras genom att lägga till en X grind till C för varje i sådan att x i = 1. Antag att det finns en klassisk polynom-tid algoritm A som, för alla IQP krets C, kan prov från en sannolikhetsfördelning som approximerar den utgående sannolikhetsfördelningen av C upp till additivt fel i 1 norm. Sedan, för varje δ sådan att 0 < δ < 1, det finns en FBPP NP algoritm som, givet tillgång till A, approximerar  på 0 på C x  på 2 upp till additivt fel med sannolikhet minst 1 − δ (över valet av x). Bevis. För varje x, y  till {0, 1} n, ange var i båda fallen sannolikheten tas över algoritmens interna slumpmässighet. För alla y av vårt val, kan vi tillämpa Theorem 4 till A för att uppskatta q 0y (där vi skriver 0 för 0 n ). Detta ger oss en FBPP NP-algoritm som ger en uppskattning q y sådan att  till q y − q 0y  på ≤ q 0y / poly(n). (p 0y + 0y – p 0y – p 0y – poly(n) – p 0y – p 0y – p 0y – p 0y – p 0y – poly(n) – p 0y – p 0y – poly(n) – p 0y – p 0y – p 0y – p 0y – p 0y – p 0y – p 0y – p 0y – poly(n) – p 0y – p 0y – p 0y – p 0y – p (1 + 1/ poly(n)). Som A approximerar utdatasannolikheten fördelning av C 0 upp till 1 fel, Det följer av Markovs ojämlikhet att för varje 0 < δ < 1, där y plockas jämnt på måfå. På så sätt blir det 2 n δ med en sannolikhet på minst 1 − δ, jämfört med valet av y. Men det här är beviset. Om LEMA 5-algoritmen ger en bra approximation – d.v.s. en multiplikativ approximation upp till en 1 + 1/ poly(n) faktor. Vi inkapslar detta formellt som följande följd. Sammanhang 6 Låt F vara en familj av IQP kretsar på n qubits. Välj en slumpmässig krets C genom att välja en krets från F jämnt på slumpmässigt, sedan lägga X grindar på en jämnt slumpmässig delmängd av qubits. Antag att det finns universella konstanter α, p > 0 sådana att Vidare anta att det finns en klassisk polynom-tid algoritm A som, för alla IQP krets C, kan prov från en sannolikhetsfördelning som approximerar den utgående sannolikhetsfördelningen av C upp till additivt fel = αp/8 i 1 norm. Sedan finns det en FBPP NP-algoritm som, givet tillgång till A, approximerar  på 0 och C till 2 upp till multiplikativt fel 1/4 + o(1) på minst en p/2 bråkdel av kretsar C. Bevis. Med sannolikhet minst p över valet av C,  på 0 på C0 på 2 ≥ α · 2 -n. Inställning = αp/8, δ = p/2 i Lemma 5, det finns en FBPP NP algoritm som, givet tillgång till A, approximerar  på 0 och C på 2 upp till additivt fel O((1 + o(1))α · 2 -n-2 +-0-C på 2 / poly(n)) med sannolikhet minst 1-p/2 (över val av C). Därför, med sannolikhet minst p/2, algoritmen approximerar  på 0 och C till 2 upp till multiplikativt fel 1/4 + o(1). Vi visar därefter att den första förutsättningen för Corollary 6 verkligen är nöjd för två intressanta familjer av IQP kretsar. Antikoncentrationsgränser -Fix en familj F av IQP kretsar. Vi vill visa att det är troligt att 2 kommer att vara högt för en krets C som bildas genom att välja en slumpmässig krets D från F, och sedan lägga X grindar på en jämnt slumpmässig delmängd S av qubits. Vi kommer att använda följande faktum: Fact 7 (Paley-Zygmund ojämlikhet). Om R är en icke-negativ slumpvariabel med ändlig varians, sedan för någon 0 < α < 1, Vi kommer att tillämpa Fact 7 till den slumpmässiga variabeln R =  på 0 och C, först observera att där i den andra förväntan x plockas jämnt på slumpmässigt från {0, 1} n. Detta handlar om täljaren; för att hantera nämnaren, vi behöver att övre-bundet E[ på 0 och C på 4 ]. Den första familjen av kretsar vi anser motsvarar polynom över F 2. Vi bevisar i bilaga E att för jämnt slumpmässig grad-3 polynomials f, E f [ngap (f ) 4 ] ≤ 3 · 2 −2n. Baserat på detta, och den täta anslutningen mellan IQP kretsar över grinden uppsättning {Z, CZ, CCZ} och grad-3 polynomials, har vi följande resultat: Theorem 8. Anta att det finns en klassisk polynom-tid algoritm A som, för någon IQP krets C, kan prov från en sannolikhetsfördelning som approximerar den utgående sannolikhetsfördelningen av C upp till additivt fel 1/192 i 1 norm. Sedan finns det en FBPP NP algoritm som, givet tillgång till A, approximerar ngap(f ) 2 upp till multiplicativt fel 1/4+o(1) på minst en 1/24 bråkdel av grad-3 polynomials f : {0, 1} n → {0, 1}. Bevis. Kombinera Fact 7 och den bundna på Kravet följer sedan genom att infoga dessa parametrar i Corollary 6. Vi betraktar därefter Ising-modellen, där vi är intresserade av att utvärdera partitioneringsfunktionen Z(en) för en slumpmässigt viktad graf vid  och = e iπ/8 (se (1)). Varje kant av den kompletta grafen har en vikt w ij, och varje vertex har en vikt v k, varje plockas jämnt slumpmässigt från uppsättningen {0,.., 15}. Vi visar i Appendix E att 0 till C0 = Z(en)/2 n för en IQP-krets C som består av grindar från uppsättningen {diag(1, 1, i), diag(1, e iπ/4 )}; och vidare att vi kan betrakta en slumpmässig krets av denna form som att väljas genom att välja en slumpmässig krets med hjälp av denna grinduppsättning, sedan följa den genom ett slumpmässigt val av X-portar. Dessutom, E w,v  och Z( ska) på 4 ≤ 3 · 2 2n. Detta innebär följande resultat, vars bevis i huvudsak är desamma som Theorem 8: Theorem 9. Låt Z(en) vara partition funktion av en slumpmässig instans av Ising modellen, plockas genom att välja slumpmässiga vikter från uppsättningen {0,..., 15} på hörn och kanter av den kompletta grafen på n hörn, utvärderas vid  ska. Anta att det finns en klassisk polynom-tid algoritm A som, för någon IQP krets C, kan prov från en sannolikhetsfördelning som approximerar den utgående sannolikhetsfördelningen av C upp till additivt fel 1/192 i 1 norm. Sedan finns det en FBPP NP-algoritm som, givet tillgång till A, approximerar.Z(e iπ/8 ) och 2 upp till multiplicativt fel 1/4 + o(1) med sannolikhet minst 1/24 (över val av vikter). Att kombinera teorem 8 och 9 ger vårt huvudsakliga resultat, Theorem 1. Outlook -Enligt vår åsikt, är den mest övertygande frågan hur man bäst fysiskt genomföra de klasser av IQP kretsar som diskuteras i detta papper, eftersom de är utan tvekan bland de enklaste klasserna av kvantberäkningar som sannolikt inte är klassiskt simulator. För både Ising modellen och grad-3 polynom fall de mest uppenbara experimentella implementationer kräver icke-lokala grindar, vilket är ganska utmanande. När det gäller Ising modellen fall 2-qubit interaktioner kan behöva genereras mellan två qubits i ett system. Sådana interaktioner uppstår inte naturligt i lattice geometrier och som sådan kommer att behöva konstrueras. Ur ett experimentellt perspektiv har det redan gjorts stora framsteg i dessa riktningar. Dynamiken i Ising-modellen med lokala interaktioner har digitalt simulerats i jonfällor [17, 18] och mycket nyligen har icke-lokala interaktioner utnyttjats i den digitala simuleringen av fermioniska system med supraledare [19]. Eftersom teknik som t.ex. hålrumsbussar för supraledande system [20] blir mer tillförlitlig förväntar vi oss att ett ökande antal system kommer att kunna implementera IQP-kretsar i ett system som sannolikt inte är klassiskt simulatoriskt. Teoretiskt sett finns det ett antal naturliga frågor som återstår att besvara, varav det mest uppenbara är huruvida Conjectures 2 och 3 är sanna. Såvitt vi vet finns det inga tekniker som kan lyfta de kända värsta fall hårdhet resultat för Ising modellen och luckor av grad-3 polynomials till genomsnittliga-fall resultat. De senaste genombrotten [21] [22] [23] när det gäller att kategorisera de statistiska mekaniska systemens komplexitet via de underliggande interaktionsegenskaperna ger dock en viss förhoppning om att dessa antaganden kan lösas. Förutom de anslutningar som används här mellan IQP, Ising modellen och låggradiga polynom, är det känt att IQP kretsar är nära relaterade till Tutte polynomials och vikt räknare polynomials av binära linjära koder [7]. Det är en övertygande fråga om de idéer som utvecklas här kan utvidgas till dessa modeller. Det skulle också vara mycket intressant att undersöka kopplingen mellan icke-adaptiv mätningsbaserad kvantdator och IQP [24, 25] för att hitta underklasser av IQP som är fysiskt enkla att genomföra, och för vilka man kan bevisa villkorliga hårdhetsresultat liknande dem som visas här. ERKÄNNANDEN
Även om dessa resultat inte håller för hårdhet gissningar som gjorts i REF, de är ett tydligt incitament för att avgöra i vilken utsträckning IQP provtagning argument kan tillämpas på Ising modeller på glesa grafer.
Average-case complexity versus approximate simulation of commuting quantum computations
{'venue': 'Phys. Rev. Lett. 117, 080501 (2016)', 'journal': None, 'mag_field_of_study': ['Physics', 'Medicine', 'Computer Science']}