Randomness är en grundläggande egenskap i naturen och en värdefull resurs för tillämpningar som sträcker sig från kryptografi och spelande till numeriska simuleringar av fysiska och biologiska system. Slumpmässiga tal är dock svåra att karakterisera matematiskt [1], och deras generation måste förlita sig på en oförutsägbar fysisk process [2, 3, 4, 5, 6]. Brister i den teoretiska modelleringen av sådana processer eller fel på anordningarna, eventuellt på grund av kontradiktoriska attacker, begränsar tillförlitligheten hos slumptalsgeneratorer på sätt som är svåra att kontrollera och upptäcka. Här, inspirerad av tidigare arbete på nonlocality baserade [7, 8, 9] och enhet oberoende [10, 11, 12, 13, 14] kvantinformation bearbetning, visar vi att icke-lokala korrelationer av insnärjda kvantpartiklar kan användas för att certifiera förekomsten av äkta slumpmässighet. Det är därmed möjligt att utforma en ny typ av kryptografiskt säker slumptalsgenerator som inte kräver något antagande om den interna funktionen hos enheterna. Denna starka form av slumpmässighet generation är omöjligt klassiskt och möjligt i kvantsystem endast om certifierade av en Bell ojämlikhet överträdelse [15]. Vi utför en proof-of-concept demonstration av detta förslag i ett system med två insnärjda atomer åtskilda med cirka 1 meter. Den observerade Bell ojämlikhet överträdelse, med nästan perfekt detektion effektivitet, garanterar att 42 nya slumpmässiga tal genereras med 99% förtroende. Våra resultat lägger grunden för framtida enhetsoberoende kvantinformationsexperiment och för att ta itu med grundläggande frågor som uppstår genom kvantteorins inneboende slumpmässighet. * Dessa författare bidrog lika mycket till detta arbete. 1 arXiv:0911.3427v3 [quant-ph] 19 okt 2010 Karaktäriseringen av sann slumpmässighet är svårfångad. Det finns statistiska tester som används för att kontrollera frånvaron av vissa mönster i en ström av siffror [16, 17], men ingen ändlig uppsättning tester kan någonsin anses vara fullständig, eftersom det kan finnas mönster som inte omfattas av sådana tester. Till exempel är vissa pseudo-random nummergeneratorer deterministiska till sin natur, men ändå ger resultat som uppfyller alla slumpmässiga tester [18]. På en mer grundläggande nivå finns det inget sådant som sann slumpmässighet i den klassiska världen: varje klassiskt system medger i princip en deterministisk beskrivning och framstår därför slumpmässigt för oss som en följd av bristande kunskap om dess grundläggande beskrivning. Kvantteorin är å andra sidan i grunden slumpmässig; ändå är i varje verkligt experiment kvantsystemens inneboende slumpmässighet nödvändigtvis förväxlad med en skenbar slumpmässighet som är ett resultat av buller eller brist på kontroll över experimentet. Det är därför oklart hur man entydigt certifierar eller kvantifierar det observerade slumpmässiga beteendet även i en kvantprocess. Dessa överväganden är av direkt betydelse för tillämpningar av slumpmässighet, särskilt kryptografiska tillämpningar. Imperfektioner i slumptalsgeneratorer [2, 3, 4, 5, 6] (RNG) kan införa mönster oupptäckta av statistiska tester men kända för en motståndare. Dessutom, om enheten inte är betrodd men betraktas som en svart låda som utarbetats av en motståndare, inga befintliga RNGs kan fastställa förekomsten av privat slumpmässighet. I själva verket kan man aldrig utesluta att talen genererades i förväg av motståndaren och kopierades till ett minne som finns inuti enheten. Här etablerar vi en grundläggande koppling mellan kränkningen av Bells ojämlikheter och den oförutsägbara karaktären hos resultaten av kvantmätningar och visar, som Colbeck [14] ursprungligen föreslog, att de icke-lokala korrelationerna mellan kvanttillstånd kan användas för att generera certifierad privat slumpmässighet. Överträdelsen av en Bell ojämlikhet [15] garanterar att de observerade outputs inte är förutbestämda och att de uppstår från insnärjda kvantsystem som har inneboende slumpmässighet. För enkelhetens skull anser vi att Clauser-Horn-Shimony-Holt (CHSH) form av Bell ojämlikhet [19], men vår strategi är allmän och gäller alla Bell ojämlikhet. Vi överväger alltså två separata system som var och en kan mätas på två olika sätt, med en mätning på varje system som resulterar i ett av två värden (Figur 1 ). De binära variablerna x och y beskriver den typ av mätning som utförs på varje system, vilket resulterar i respektive binära mätresultat a och b. Vi kvantifierar Bell ojämlikhet överträdelse genom CHSH korrelation funktion [19] där P (a = b-xy) är sannolikheten att a = b givna inställningar (x, y) och P (a = b-xy) definieras analogt. System som medger en lokal, därav deterministisk [20], beskrivning uppfyller I ≤ 2. Vissa mätningar som utförs på insnärjda stater, dock, kan bryta denna ojämlikhet. För att uppskatta Bell-överträdelsen upprepas experimentet n gånger i följd. Mätval (x, y) för varje försök genereras av en identisk och oberoende sannolikhetsfördelning P (xy). Vi betecknar den slutliga utdatasträngen efter n körningar r = (a 1, b 1 ;. . ; a n, b n ) och ingångssträngen s = (x 1, y 1 ;. . ; ; x n, y n ).... ;.................................................................................................. En uppskattning av CHSH-uttrycket(1) som bestämts utifrån de observerade uppgifterna ges b och där N (a = b, xy) är antalet gånger som mätningarna x, y utfördes och att resultaten a och b hittades lika efter n-realiseringar, och där N (a = b, xy) definieras analogt. Utmatningssträngens slumpmässighet r kan kvantifieras av min-entropin [21] H ∞ (R-S) = − log 2 [max r P (r-s)], där P (r-s) är den villkorliga sannolikheten för att få resultaten r när mätningarna görs. Vi visar (se bilaga A) att min-entropin för utgångarna r begränsas med sannolikhet större än 1 − δ, där = O( − log δ/(q 2 n)) är en statistisk parameter och q = min x,y P (xy) är sannolikheten för det minst sannolika inmatningsparet. Funktionen f (I) erhålls med semidefinit programmering [22, 23] och presenteras i figur 2. För att härleda den bundna (3), gör vi följande antaganden: 1) de två observerade systemen uppfyller lagarna i kvantteori; 2) de separeras och icke-interaktion under varje mätsteg i; 3) ingångarna x i, y i genereras av slumpmässiga processer som är oberoende och okorrelerade från systemen och deras värde visas för systemen endast i steg i (se figur 1 ). Förutom dessa antaganden införs inga begränsningar för staterna, mätningarna eller Hilbert-rymdens dimension. Vi antar inte ens att systemet beter sig identiskt och självständigt för varje försök; till exempel, enheterna kan ha ett internt minne (eventuellt kvantum), så att i th mätningen kan bero på tidigare i‐1 resultat och mätinställningar. Alla värden av min-entropin mindre än (3) är oförenliga med kvantteorin. Den observerade CHSH-mängden ger således en gräns (se figur 3 ) på den slumpmässighet som produceras av kvantenheter, oberoende av någon uppenbar slumpmässighet som kan uppstå från buller eller begränsad kontroll över experimentet. Detta resultat kan utnyttjas för att konstruera en ny RNG där kränkningen av en Bell ojämlikhet garanterar att produktionen är slumpmässig och privat från alla motståndare, även i en enhet-oberoende scenario [12, 13] där de interna fungerar av de två kvantenheter är okända eller inte betrodda (se bilaga B). En viss mängd slumpmässighet vid indata är nödvändigt för att utföra de statistiska tester som används för att uppskatta Bell ojämlikhet överträdelse. Därför beskriver vi här ett slumpmässig expansionsprogram [14] där ett litet privat slumpmässigt frö expanderas till en längre privat slumpmässig sträng. Den slumpmässighet som används för att välja indata behöver inte avslöjas och kan därefter användas för en annan uppgift. Den slutliga slumpmässiga strängen, konkateneringen av in- och utgående slumpmässiga strängar, är således uppenbart längre än den ursprungliga. När n blir tillräckligt stor är det dock möjligt med en katalyseffekt där en frösträng av längd O ( ε n log ε n) producerar en mycket längre slumpmässig utmatningssträng av entropi O(n), vilket illustreras i figur 3 (se tillägg B). Detta är möjligt eftersom jag kan uppskattas tillräckligt utan att konsumera mycket slumpmässighet genom att använda samma inmatning par för det mesta [t.ex., (x, y) = (0, 0)] medan endast sällan provtagning från andra möjligheter, i vilket fall q 1. Detta följer av det faktum att CHSH-uttrycket endast beror på de villkorliga sannolikheterna P (ab-xy), som kan uppskattas även om x, y inte är jämnt fördelade. Även om den slutliga utdatasträngen kanske inte är jämnt slumpmässig (den kanske inte ens klarar ett av de vanliga statistiska testerna [16, 17] av slumpmässighet), är vi garanterade att dess entropi begränsas av (3). Med hjälp av en liten privat slumpmässig frö, kan utdatasträngen sedan klassiskt bearbetas med hjälp av en slumpmässig utsugare [24] för att omvandla den till en sträng av storlek nf (ί − ) som är nästan enhetlig och okorrelerad med information från en motståndare. Den bundna (3) etablerar säkerheten i vår slumpmässighet expansion protokoll mot en motståndare som mäter sin sida-information innan slumpmässigheten extraktion steg, t.ex., mot en motståndare som bara har en kortlivad eller avgränsad kvantum minne. Detta beror på att det gäller när det är betingat på varje mätning som utförs av motståndaren. Men vårt protokoll är ännu inte bevisat att vara universellt-komposerbar mot en full kvant motståndare, det vill säga, säkra mot en motståndare som lagrar sin sida-information i en 3 Ingångar Rotationer N (0, 0; x, y) N (0, 1; x, y) N (1, 0; x, y) N (1, 1; x, y) Tabell 1 : Observerat antal händelser N (a, b; x, y) för vilka mätningen på en atom gav resultat a och mätningen på den andra atomen gav resultat b, med tanke på binära val av mätbaser (x, y) motsvarande π/2 qubit rotationer med fasvinklar (en x,  och y ) på ekvatorn av Bloch sfären. Den sista kolumnen anger andelen händelser där a = b anger varje inmatning. Om försöket tolkas som att det består av identiska och oberoende insikter (ett antagande som inte görs någon annanstans i detta dokument), anger data därefter en CHSH observerbar av α = x,y (−1) xy [P (a = b påxy) − P (a = b påxy)] = 2.414 ± 0,058, betydligt bortom den lokala deterministiska tröskeln för I = 2. kvantumminne som kan mätas i ett senare skede. Ett universellt sammansatt bevis skulle också täcka den situation där motståndaren försöker uppskatta de slumpmässiga talen efter att ha fått partiell information om dem. Att bevisa universellt-komponerbar säkerhet av vårt protokoll skulle förmodligen också leda till mycket effektivare slumpmässig expansion system. Observera att det faktum att den bundna (3) innehar för enheter som har ett internt minne är ett betydande framsteg jämfört med de enhetsoberoende protokoll [9, 12, 13] som hittills föreslagits. Det är det avgörande som gör vårt protokoll praktiskt. Det experimentella förverkligandet av detta system kräver observation av en Bell ojämlikhet med detektion kryphål stängd (nära perfekt upptäckt av varje händelse), så att utgångarna r inte kan deterministiskt reproduceras. De två enskilda systemen bör också vara tillräckligt åtskilda så att de inte interagerar, men det är inte nödvändigt att de två delsystemen är rymdliknande åtskilda (se bilaga C). Vi inser denna situation med två 171 Yb + atomiska jon kvantbitar (qubits) [25] instängda i två oberoende vakuumkammare åtskilda med cirka 1 meter. Kvbitnivåerna inom varje atom är insnärjda genom en probabilistisk process där varje atom snärjs med utsända fotoner och interferensen och den samtidiga upptäckten av de två fotonerna förebådar en framgångsrik förberedelse av ett nära-maximalt insnärjd tillstånd av de två avlägsna atomerna genom swapning [26], såsom beskrivs i bild. 1 och tillägg D. De binära värdena a och b motsvarar efterföljande mätresultat för varje qubit som erhålls genom standard atomiska fluorescenstekniker (detektionsfel < 3%) [25], och varje händelse registreras. De respektive binära mätbaserna x och y väljs slumpmässigt och ställs in genom sammanhängande qubit rotationsoperationer före mätning. Direkt interaktion mellan atomerna är försumbar och klassiska mikrovågs- och optiska fält används för att utföra rotationer och mätningar på en atom har ingen inverkan på den andra atomen (vi utför statistiska tester för att verifiera att mätdata är förenliga med denna hypotes, se bilaga D.4). För att uppskatta värdet av CHSH ojämlikhet vi ackumulera n = 3, 016 på varandra följande trassling händelser under perioden på ungefär en månad, sammanfattas i bilaga D.1 och tabell I. Den observerade CHSH-kränkningen av på = 2,414 innebär en betydande förbättring jämfört med tidigare resultat [27, 26]. Sannolikheten för att en lokal teori, eventuellt med ett internt minne av tidigare händelser [28], skulle kunna ge upphov till en sådan överträdelse är P (ί ≥ 2.414) ≤ 0.00077 (se Appedendix D.3). I 4 experimentet valde vi en enhetlig slumpmässig fördelning av de initiala mätbaserna ingångar [P (x, y) = 1/4] för att minimera antalet körningar som krävs för att erhålla en meningsfull gräns på produktionen entropi (se figur 3). Den observerade CHSH-överträdelsen innebär att minst H(R) > 42 nya slumpmässiga bitar genereras i experimentet med 99% konfidensnivå. Detta är första gången som man kan intyga att ny slumpmässighet produceras i ett experiment utan en detaljerad modell av anordningarna. Vi förlitar oss endast på en högnivåbeskrivning (atomer begränsade till oberoende vakuumkammare åtskilda med en meter) för att säkerställa frånvaron av interaktion mellan de två delsystemen när mätningarna utförs. Eftersom inga aktiva åtgärder vidtas i vårt experiment för att kontrollera denna interaktion, kan dessa nya slumpmässiga bitar inte betraktas som privata i det starkaste kontradiktoriska enhetsoberoende scenariot. Den säkerhetsnivå som vårt experiment ger kommer dock att vara tillräcklig för många tillämpningar, eftersom det garanterar att nästan alla fellägen hos anordningarna kommer att upptäckas. Det nuvarande experimentet når inte den katalysregim som nämns ovan, på grund av den låga sannolikheten för framgång av förebådad snärjning generation (2 × 10 −8 ) [26]. Det bör dock vara möjligt att överskrida katalyströskeln genom att förbättra fotoninsamlingens effektivitet genom användning av närliggande optiska samlingselement eller optiska hål [29]. Att gå tillbaka till den mer konceptuella nivån, notera att Eq. (3) relaterar kvantteorins slumpmässiga karaktär till kränkningen av Bells ojämlikheter. Denna gräns kan ändras för en situation där vi endast utgår från nollsignalprincipen i stället för hela kvantformalismen (se figur 2 och 3 och Appedenix A.3). En sådan gräns lägger grunden för att på ett statistiskt signifikant sätt ta itu med en av de mest grundläggande frågorna i kvantteorin: om vår värld är förenlig med determinism (men då nödvändigtvis signalering), eller i sig slumpmässig (om signalering anses omöjlig). Tack Vi tackar Roger Colbeck för att han delar sin doktorsavhandling med oss. Detta arbete stöddes av den schweiziska NCCR Quantum Photonics, den europeiska ERC-AG QORE, den europeiska QAP, COMPAS-projekt och ERC Starting Grant PERCENT, den spanska MEC FIS2007-60182 och Consolider-Ingenio QOIT-projekt, Generalitat de Catalunya och Caixa Manresa, Interuniversity Attraction Poles Photonics@be-programmet (Belgian Science Policy), den amerikanska Army Research Office med medel från IARPA, National Science Foundation (NSF) Fysik vid Information Frontier Program, och NSF Physics Frontier Center vid JQI. Experimentellt förverkligande av privat slumptalsgenerator med hjälp av två 171 Yb + qubits instängda i oberoende vakuumkammare. Varje atom avger en enda foton (till vänster) som är insnärjd med sin värd atomkvadrat och kopplad till optiska fibrer; interferensen av fotonerna på strålsplittern (BS) och efterföljande slumpdetektering på fotomultiplikatorrören (PMT) förebådar insnärjningen av atomkvadrerna [26]. Efter att qubits är insnärjda, binära slumpmässiga ingångar (x, y) matas till mikrovåg (μ-våg) oscillatorer som konsekvent roterar varje qubit på ett av två sätt före mätning [26]. Varje qubit mäts slutligen genom fluorescens som samlas in på PMT [25], vilket resulterar i binära utgångar (a, b). Abstractly, kan vi se detta system som består av två svarta lådor som tar emot ingångar x, y och producera utgångar a, b. I vår teoretiska analys görs ingen hypotes om apparatens interna funktion, men den klassiska och kvantinformation som flödar in och ut ur lådorna är begränsad (doterade linjer). Framför allt är de två rutorna fria att kommunicera innan indata införs (för att etablera delad insnärjning), men de får inte längre interagera under mätningsprocessen. Dessutom visas ingångarnas värden för rutorna endast i början av mätningsprocessen. I försöket vidtas inga aktiva åtgärder för att kontrollera informationsflödet in och ut ur systemen. Men när atomerna är insnärjda är den direkta interaktionen mellan dem försumbar. Dessutom är det osannolikt att värdet av de valda mätbaserna (x, y), som erhålls genom att man kombinerar resultaten från flera slumptalsgeneratorer, kommer att vara korrelerat till atomernas tillstånd innan mätningen av mikrovågspulser tillämpas, vilket uppfyller villkoren för bundet (3) på utgångarnas entropi. Figur 2 : Tomt för funktionen f (I). Funktionen f (I) kan tolkas som en gräns på min-entropi per användning av systemet för en given CHSH förväntan I, i den asymptotiska gränsen av stora n där ändliga statistiska effekter (parametern i (3)) kan försummas. Funktionen f (I) (kurva a) härleds genom semidefinit programmering med hjälp av teknikerna i [22,23] (semidefinit programmering är en numerisk metod som garanteras att konvergera till det exakta resultatet). Kurv b motsvarar den analytiska nedre gränsen f (I) ≥ - log 2 1 - log 2 1 + 2 - I 2 4. Kurv c motsvarar det minimala värdet f (I) = − log 2 (3/2 − I/4) av min-entropin underförstått enbart av nollsignalprincipen. Funktionen f (I) börjar vid noll vid det lokala tröskelvärdet I = 2. System som bryter mot den CHSH ojämlikhet (I > 2), å andra sidan, uppfyller f (I) > 0, dvs., har en positiv min-entropi. Figur 3: Gränsvärde nf (I) för den minsta entropi som produceras jämfört med antalet prövningar n för en observerad CHSH-överträdelse av β = 2.414, och en konfidensnivå 1 − δ = 99 %. Mängden slumpmässighet som ges av den bundna (3) beror på sannolikheten för att indata från varje försök (x i, y i ) väljs genom parametern q = min x,y [P (x, y)], där P (x, y) är sannolikheten fördelning av indata. Vi har ritat gränserna på entropin underförstått av kvantteorin för ett enhetligt val av ingångar [P (x, y) = 1/4] (kurva a) och för ett partiskt val av ingångar som ges av P SOS alarm = 1 − 3q, P (01) = P (10) = P (11) = q, där q = αn −1/2 med α = 11 (kurva b). För ett givet antal n användningsområden för anordningarna leder det enhetliga valet av ingångar till mer slumpmässighet i utgångarna. Å andra sidan kräver partiska indata mindre slumpmässighet att genereras, och den nettomängd slumpmässighet som erhålls genom skillnaden mellan utdata och indata entropi blir positiv för tillräckligt stor n. Curve c representerar den bundna på entropin underförstått av nollsignalprincipen ensam för ett enhetligt val av indata. Observera att i samtliga fall krävs ett minimalt antal användningar av anordningarna (ett par tusen) för att garantera att viss slumpmässighet har producerats på konfidensnivå 1 − δ = 99% Insatsen visar nettomängden producerad entropi (outputentropi minus inmatad entropi) för det partiska valet av indata med den observerade CHSH-överträdelsen.
Ur ett praktiskt perspektiv, en annan skillnad mellan vår strategi och enhet-oberoende slumpmässighet expansion är att genomförandet av de senare är mycket utmanande med state-of-the-art teknik och deras effektivitet är låg (vi vet att endast 42 nummer genereras på detta sätt REF ).
Random Numbers Certified by Bell's Theorem
{'venue': 'Nature 464, 1021 (2010)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Medicine', 'Physics']}