Det framväxande området för kvantmaskininlärning har potential att avsevärt bidra till problemen och omfattningen av artificiell intelligens. Detta förstärks endast av de senaste framgångarna inom klassisk maskininlärning. I detta arbete föreslår vi en metod för systematisk behandling av maskininlärning ur kvantinformationens perspektiv. Vårt tillvägagångssätt är allmänt och täcker alla tre huvudgrenar av maskininlärning: övervakat, oövervakat och förstärkande lärande. Även om kvantförbättringar i övervakat och oövervakat lärande har rapporterats, förstärkt lärande har fått mycket mindre uppmärksamhet. Inom vår strategi tar vi också itu med problemet med kvantförbättringar när det gäller att förstärka lärandet och föreslår ett systematiskt system för att tillhandahålla förbättringar. Som ett exempel visar vi att man kan uppnå andragradsförbättringar i inlärningseffektivitet och exponentiella förbättringar i prestanda under begränsade tidsperioder för en bred klass av inlärningsproblem. PAC-nummer: 03.67.-a, 03.67. Ac, 03.65.Aa, 03.67.Hk, 03.67.Lx Inledning.-området artificiell intelligens (AI) har nyligen haft anmärkningsvärda framgångar, särskilt inom området maskininlärning [1, 2]. En ny milstolpe, fram till nyligen tros vara årtionden bort - en dator slå en expert människa spelare i spelet Go [3] - tydligt illustrerar potentialen i lärande maskiner. Samtidigt bevittnar vi uppkomsten av ett nytt fält: kvantmaskininlärning (QML), som har en ytterligare, djup potential att revolutionera området AI, ungefär som kvantinformationsbehandling (QIP) har påverkat sin klassiska motsvarighet [4]. Bevisen för detta är redan underbyggda med de förbättringar som rapporterats i klassificering och klustring [5] [6] [7] [8]-problem. Sådana uppgifter är representativa för två av de tre huvudgrenarna inom maskininlärning. Den första, övervakad inlärning, överväger problemet med att lära sig den villkorliga fördelningen P (x) (t.ex., en funktion y = f (x)) som tilldelar etiketterna y till data x (dvs. klassificerar data), baserat på korrekt märkta exempel, kallas utbildningsset, tillhandahålls från en distribution P (x, y). Den andra, oövervakade inlärning, använder prover för att identifiera en struktur i en distribution P (x), t.ex., identifierar kluster. Kvantanalogen för den första uppgiften motsvarar ett tomografiliknande problem där villkorade tillstånd ρ x Y (tillstånd av en partition av ett system, med tanke på ett mätresultat av en annan partition) bör rekonstrueras från mätstatistiken för det gemensamma tillståndet ρ XY, som kodar fördelningen P (x, y). Det oövervakade fallet är liknande. Den tredje grenen, förstärkning lärande (RL) utgör ett interaktivt sätt att lära, och är mer gen- * vedran.dunjko@uibk.ac.at † jmtaylor@umd.edu  på hans.briegel@uibk.ac.at eral. Här lär sig inlärningsagenten (eller inlärningsalgoritmen) hur man beter sig korrekt genom att använda förstärkningssignaler - belöningar, eller straff. RL har undersökts mindre ur ett kvantinformationsperspektiv, även om vissa resultat har rapporterats [9, 10]. Den centrala frågan om hur kvantbehandling kan hjälpa till i lärandet kräver att vi klargör vad som utgör en bra inlärningsmodell. Detta kan vara inbegripet, men två egenskaper beaktas vanligen. Den första är algoritmens beräkningskomplexitet. Den andra, prov komplexitet, är standard för övervakad lärande, och kvantifierar hur stor utbildning uppsättningen måste vara, för algoritmen för att lära sig distributionen P (x). Det vill säga, i ett tomografi sammanhang, det räknar antalet kopior av ρ XY som krävs tills inlärningsalgoritmen kan rekonstruera staterna ρ x Y till önskat förtroende. I RL, prov komplexitet ersätts vanligtvis med lärande effektivitet - antalet interaktion steg som behövs för att agenten att lära sig att få belöningar med hög sannolikhet. De senaste resultaten i QML har fokuserat på att förbättra beräkningskomplexiteten [5] [6] [7] [8] 10], med endast ett fåtal nya arbeten med beaktande av urvalskomplexa aspekter [11] eller övervakad beräkningslärande [12, 13]. Men den bredare frågan om hur, och i vilken utsträckning, AI i slutändan kan dra nytta av kvantmekanik, i allmänna inlärningsmiljöer, förblir till stor del öppen. I detta arbete tar vi upp denna fråga, med tonvikt på den mer allmänna, och mindre utforskade, RL-inställningen. Vi föreslår ett paradigm för att överväga QML, vilket gör att vi bättre kan förstå dess gränser och dess makt. Med hjälp av detta presenterar vi ett schema för att identifiera inställningar där kvanteffekter kan hjälpa. För att illustrera hur schemat fungerar tillhandahåller vi en metod för att uppnå kvantförbättringar (polynom i det erforderliga antalet interaktionsrundor och exponentiella förbättringar i framgångsfrekvensen) i många arXiv:1610.08251v1 [quant-ph] 26 okt 2016 2 RL-inställningar. Ett paradigm för QML.-Alla tre lärande inställningar passar i paradigmet för så kallade lärande agenter [14], standard inom området artificiell intelligens. Här betraktar vi en inlärningsagent A (likvärdigt ett inlärningsprogram A) som interagerar med en okänd miljö E (den så kallade uppgiftsmiljön, eller probleminställningen) via utbyte av meddelanden, som utfärdas av A (kallas åtgärder A = {a i}) och E (kallas percepts S = {s j}). I kvantförlängningen blir dessa uppsättningar Hilbert-rymder, H A = spännvidd i}, H S = spännvidd i} och bildar ortonormala baser. Uppfattnings- och handlingstillstånden, och deras blandningar, kallas klassiska tillstånd. Varje siffra av meriter Rate(·) av resultatet av en agent A i E är en funktion av historien om interaktion H h = (a 1, s 1,. ...), samla in de utbytta uppfattningarna och åtgärderna. Interaktionens historia är alltså det centrala begreppet i lärandet. Den korrekta kvant generaliseringen av historien är inte trivial, och vi kommer att ta itu med detta ögonblickligt. Om antingen A eller E är stokastiska, beskrivs interaktionen mellan A och E av en fördelning över historia (av längd t), betecknad av A  och E. De flesta siffror av meriter sedan utvidgas till sådana fördelningar genom konvex-linjäritet. För att återhämta sig, t.ex., övervakad inlärning i detta paradigm, ta E att karakteriseras av distributionen P (x, y), där agenten ges utbildning set -n märkta datapunkter (par (x, y)) provtagna från P (x, y) -som de första n percepts. Efter detta, agenten är att svara med rätt etiketter som åtgärder (responser) till de presenterade uppfattningarna, som nu är de omärkta data-points x. Förstärkning lärande förstås som en sådan agenten environment interaktion, där percept utrymme också innehåller belöningen. Vi betecknar percept utrymme inklusive belöning status asS (t.ex., om belöningar är binära dåS = S × {0, 1}). Formellt, agent-miljö paradigm är en tvåpart interaktiv inställning, och därmed bekvämt för en kvantinformation behandling av QML. Alla befintliga resultatgrupper i fyra kategorier [15]: CC, CQ, QC och QQ, beroende på om agenset (första symbolen) eller miljön (andra symbolen) är klassiskt (C) eller kvantum (Q). Denna klassificering påminner om, men bör inte förväxlas med, klassificeringen av quantum computational universality [22] där C/Q anger om input/outputs för en kvantberäkning är klassisk. CC-scenariot omfattar klassisk maskininlärning. CQ-inställningen frågar hur klassiska inlärningsmetoder kan hjälpa i kvantuppgifter, såsom kvantkontroll [16, 17], kvantmetrologi [18], adaptiv kvantdator [19] och utformningen av kvantexperiment [20]. Här hanterar vi till exempel icke-konvexa eller icke-linjära optimeringsproblem som uppstår i kvantexperiment, hanterade med maskininlärningsteknik. QC motsvarar kvantvarianter av inlärningsalgoritmer [7, 10, 21] inför en klassisk miljö. Bildligt talat studerar detta potentialen hos en lärande robot, förstärkt med ett "quantum chip". I QQ-inställningar är fokus för detta arbete, både A och E kvantsystem. Här kan interaktionen vara helt kvant, och till och med frågan om vad det betyder "att lära sig" blir problematisk eftersom till exempel agenten och miljön kan bli insnärjda. Ramverk.-Eftersom lärande utgör en två-spelare interaktion, standard kvant förlängningar kan tillämpas: åtgärden och percept uppsättningar representeras av de ovannämnda Hilbert utrymmen H A, H S. Agenten och miljön agerar på ett gemensamt kommunikationsregister R C (i stånd att representera både percepts och åtgärder). Således, agenten (miljö) beskrivs som en sekvens av helt positiva spår-bevarande (CPTP) kartor {M t A} ( {M t E })-en för varje steg -som agerar på registret R C, men också ett privat register R A (R E ) som utgör det interna minnet av agenten (miljö). Detta illustreras i bild. 1 ovanför den streckade linjen. Det centrala objekt som kännetecknar en interaktion, nämligen dess historia, genereras för kvantfallet genom att utföra periodiska mätningar på RC i den klassiska (ofta kallade beräkningsgrunden). Generaliseringen av denna process för kvantfallet är en testad interaktion: vi definierar testaren som en sekvens av kontrollerade kartor över formen där x  på S A, och {U x t } x är enhetliga kartor som agerar på testaren registret R T, för alla steg t. Historien, i förhållande till en given testare, definieras som tillståndet i registret R T. En testad interaktion visas i bild. 1................................................................ 2 kommer Hilbert utrymmen, H A = spännvidd {a i i}, H S = spännvidd i i} och bildar ortonormala baser. Uppfattnings- och handlingstillstånden, och deras blandningar, kallas klassiska tillstånd. Varje siffra av meriter Rate(·) av resultatet av en agent A i E är en funktion av historien om interaktion H 3 h = (a 1, s 1,. ...), samla in de utbytta uppfattningarna och åtgärderna. Interaktionens historia är alltså det centrala begreppet i lärandet. Den korrekta kvant generaliseringen av historien är inte trivial, och vi kommer att ta itu med detta ögonblickligt. Om antingen A eller E är stokastiska, är interaktionen av A och E beskrivs av en fördelning över historia (av längd t), betecknad med A $ t E. De flesta siffror av meriter sedan utvidgas till sådana fördelningar genom konvex-linjäritet. För att återställa, t.ex., övervakad inlärning i detta paradigm, ta E att karakteriseras av fördelningen P (x, y), där agenten ges ett n storlek prov av (x, y) par som de första n percepts. Efter detta är agenten att svara med etiketter som åtgärder till givna percepts, nu omärkta data-points x. Denna inställning är infödd till RL om percept utrymme också innehåller förstärkningssignalen - belöningen. Vi betecknar percept mellanslag inklusive belöning status asS (t.ex., om belöningar är binära sedanS = S  till {0, 1}). Agent-environment paradigm är en tvåparts interaktiv inställning, och därmed bekvämt för en kvantinformationsbehandling av QML. Alla befintliga resultat grupp i fyra kategorier: CC, CQ, QC och QQ, beroende på om agenten (första symbolen) eller miljön (andra symbolen) är klassiska (C) eller kvant (Q) [30]. CC-scenariot omfattar klassisk maskininlärning. CQ-inställningen frågar hur klassisk ML-teknik kan hjälpa i kvantuppgifter, såsom kvantkontroll [14, 15], kvantmetrologi [16], adaptiv kvantberäkning [17] och utformningen av kvantexperiment [18]. Här har vi till exempel att göra med icke-konvexa/icke-linjära optimeringsproblem som uppstår i kvantexperiment, täppta av ML-tekniker. QC motsvarar kvantvarianter av inlärningsalgoritmer [7, 10, 19 ] inför en klassisk miljö. Bildligt talat studerar detta potentialen hos en lärande robot, förstärkt med en med ett "quantum chip". I QQ-inställningar är fokus för detta arbete, både A och E kvantsystem. Här kan interaktionen vara helt kvant, och till och med frågan om vad det betyder "att lära sig" blir problematisk eftersom till exempel agenten och miljön kan bli insnärjda. Ramverk.-Eftersom lärande utgör en tvåspelarinteraktion, kan standard quantum förlängningar tillämpas: den streckade linjen. Det centrala objekt som kännetecknar en interaktion, nämligen dess historia, återvinns för det klassiska fallet genom att utföra periodiska mätningar på RC i den klassiska (ofta kallade beräkningsgrunden). Generaliseringen av denna process för kvantfallet är en testad interaktion: vi definierar testaren som en sekvens av kontrollerade kartor över formen och {U x t } x är enhetliga kartor som agerar på testerregistret R T, för alla steg t. Historien, i förhållande till en given testare, definieras som tillståndet i registret R T. En testad interaktion visas i bild. 1................................................................ I allmänhet fungerar varje karta över testaren U T k på ett nytt delsystem i registret RT, som inte kontrolleras av miljöagenten. De korsade ledningarna representerar flera system. Begränsningen att testare är kontrollerade kartor i förhållande till den klassiska basen garanterar att, för varje val av de lokala kartorna U x T, interaktionen mellan klassisk A och E förblir oförändrad. En klassisk testare kopierar innehållet i R C i förhållande till den klassiska basen, som i stort sett har samma effekt som att mäta R C och kopiera resultatet. Med andra ord är gränssnittet mellan A och E då klassiskt. Det kan visas att det i det senare fallet finns klassisk A och E för alla kvantmedel och/eller miljöer som genererar samma historik under alla testare [20]. Med andra ord, klassiska agenter kan, i QC-inställningar och, motsvarande, i klassiskt testade QQ-inställningar, uppnå samma prestanda som kvantagenter, i termer av någon historisk-beroende siffra av meriter. Således kan de enda förbättringarna då vara i form av beräknings komplexitet. Omfattning och gränser för kvantförbättringar.-Vad är den ultimata potentialen för kvantförbättringar i lärande? I QC och klassiskt testade inställningar är vi bundna till computational komplexitet förbättringar, som har uppnåtts i vissa fall. Förbättringar i inlärning e ektivitet kräver särskild typ av tillgång till begränsningen att testare är kontrollerade kartor i förhållande till den klassiska grunden garanterar att, för varje val av lokala kartor U x T, interaktionen mellan klassisk A och E förblir oförändrad. En klassisk testare kopierar innehållet i RC i förhållande till den klassiska basen, vilket i huvudsak har samma effekt som att mäta RC och kopiera resultatet. Med andra ord är gränssnittet mellan A och E då klassiskt. Det kan visas att det i det senare fallet finns klassisk A och E för alla kvantmedel och/eller miljöer som genererar samma historik under alla testare (se tillägget för närmare uppgifter). Med andra ord, klassiska agenter kan, i QC-inställningar och, motsvarande, i klassiskt testade QQ-inställningar, uppnå samma prestanda som kvantagenter, i termer av någon historisk beroende figur av meriter. Således kan de enda förbättringarna då vara i form av beräknings komplexitet. Omfattning och gränser för kvantförbättringar.-Vad är den ultimata potentialen för kvantförbättringar i lärande? I QC och klassiskt testade inställningar är vi bundna till computational komplexitet förbättringar, som har uppnåtts i vissa fall. Förbättringar av inlärningseffektiviteten kräver en särskild typ av tillgång till miljöer, som inte är helt testad. Exakt detta görs i [6, 8], för att förbättra beräknings komplexitet, med stor framgång, eftersom förbättringen kan vara exponentiell. Där ersätts den klassiska provkällan med en kvantminnesarkitektur [25], som gör det möjligt att få tillgång till många prover i överläge. En sådan ersättning kommer naturligt i (o)övervakade inställningar, eftersom den grundläggande interaktionen endast består av två steg och är minneslös - agenten begär M prover, och miljön ger dem. Men i mer allmänna miljöer är miljöer olämpliga för sådana kvantparallella tillvägagångssätt: i allmänhet lagrar miljön alla åtgärder av agenten det i sitt minne, aldrig att återlämna dem igen. Detta bryter effektivt insnärjningen i agentens register R A, och förbjuder alla interferens effekter. För många miljömiljöer är det dock fortfarande möjligt att "dissekera" kartorna över miljön, och att tillhandahålla orakulära varianter, som vi kan använda för att hjälpa agenten att lära sig. En strategi för kvantförbättringar i förstärkning lärande.-Detta för oss till vårt schema för att förbättra RL-agenter. Först, med tanke på en klassisk miljö E, definierar vi rättvisa enhetliga orakulära motsvarigheter E q. Här är rättvis menas i samma bemärkelse som kvantorakler av booleska funktioner är rättvisa analoger av klassiska booleska funktioner -E q bör inte ge mer information än E under klassisk åtkomst, vilket garanteras, t.ex. när E q kan realiseras från en reversibel version av E. Second, eftersom tillgång till någon kvantmiljö E q inte generellt kan påskynda alla aspekter av en interaktion (t.ex., medan kvant promenader kan hitta mål hörn snabbare, priset är att den korsade vägen är odefinierad), identifierar vi särskilda miljöegenskaper som kan fastställas mer effektivt med E q, och som är relevanta för lärande. För det tredje bygger vi en förbättrad agent som använder egenskaperna från de tidigare punkterna. Vi illustrerar nu vår inställning till ett begränsat scenario, för att underlätta presentationen, och visar hur exemplen generaliseras senare. Tillämpning av ramverket.-Givet någon uppgift miljö, kan vi separat överväga kartan som anger nästa uppfattning miljön kommer att presentera-i allmänhet, en stokastisk funktion f E : H → S, kartläggning förfluten historia till nästa uppfattning - och belöning funktion. Funktion. Den senare beskrivs som kartan ι : H × S →S som också beror på historien, och kompletterar begreppet genom att fastställa sin belöning status. I miljöer som är enkla och strikt epokmässiga (vilket innebär att miljön åter sätts efter M steg och som mest en belöning ges), även om interaktionen är tur-baserad, kan den representeras som sekvenser av M-steg kartor: där "bar" på s M belyser att det inkluderar en belöning status. Dessutom är kartorna i deterministiska miljöer endast beroende av agentens agerande, eftersom perceptsvaren är fastställda. För sådana deterministiska, enkla strikt epokmässiga miljöer förenklas konstruktionen av ett lämpligt orakel dramatiskt. Åtgärderna kan returneras till agenten efter varje block av M steg, som nästa block är oberoende. Dessutom, med hjälp av fas kick-back, kan belöningskartan ändras (se tillägget för detaljer) som att påverka bara den globala fasen av returnerade åtgärder stater. Detta leder till att "fas-flipp" orakel inser En användning av denna miljöspecifika orakel kräver M interaktionssteg. Detta är det första steget i vårt föreslagna schema. Därefter fokuserar vi på steg två: att få en användbar egenskap i miljön, och identifiera inställningar där det på ett tillfredsställande sätt hjälper. Den konstruerade oraklet pekar mot användningen av Grover-typ sökning för att hitta givande åtgärder sekvenser. Enbart detta räcker för förbättringar endast i speciella miljöer där lärandet minskar till att söka. Vi kan göra bättre ifrån oss genom att kombinera snabb sökning med en klassisk inlärningsmodell. I kanoniska RL-inställningar, vad agenten lär sig (bör lära sig!) är inte en korrekt sekvens av rörelser i sig, utan snarare en korrekt association av handlingar givna begrepp. För att illustrera detta, tänk dig att navigera i en labyrint där percepten kodar rätt riktning för rörelse. Om rätt association lärs, då agenten kommer att prestera bra, även när labyrinten förändras. Men för att agenten ska lära sig den rätta associationen måste den först stöta på ett tillfälle av givande sekvenser, och här hjälper kvantåtkomst. Därför strävar vi efter att hjälpa till i prospekteringsfasen av balanseringsakten mellan prospektering (försök att hitta optima) och exploatering (att ta emot belöningar genom att använda inlärd information) som är karakteristisk för RL [26]. Denna idé kan göras helt exakt genom att ta hänsyn till den klass av miljöer där mer framgångsrika prospekteringsfaser garanterat leder till en bättre övergripande inlärningsprestanda. Om så är fallet beror dock också på agentens inlärningsmodell. Således identifierar vi agent-environment par, där sådana bättre prestanda i det förflutna (i prospektering) innebär bättre prestanda i framtiden (i genomsnitt), som vi kallar tur-favoriserande inställningar. Mer formellt, överväga miljöer E, och agenter A, sådan att om h t och h t är t-längd historia, sedan Rate(h t ) > Rate(h t ) (dvs.. h t är en historia med en bättre prestanda än h t ) innebär (3) för någon framtida period T. Här E( h) och A( h) betecknar miljön och agens, respektive, som har genomgått historien h, (observera att A( h) och A är tekniskt, olika agenser ). Vi kommer att säga A(ht ) är lyckligare än A(ht ). Sådana miljöagentpar (A, E), som uppfyller de formella villkoren ovan, är alltså lyckobringande, och vi kan dessutom ange de perioder t och T för vilka konsekvenserna (3) innehar. Detta för oss till steg tre av schemat, givet som ett teorem. Teorem 1 Låt E vara en deterministisk, strikt epokal miljö. Sedan finns det en orakulär variant E q av E, sådan att för alla klassiska lärande modell A som är tur-favoriserande i förhållande till E, och siffra av meriter Rate som är monotont ökar i antalet belöningar i historien, kan vi konstruera en kvant agent A q sådan att A q, genom att interagera med E q, överträffar A i termer av siffran av meriter Rate i förhållande till en utvald testare. Detta teorem säger att i de begränsade miljöer av deterministiska epokella miljöer, är det möjligt att generiskt förbättra inlärningseffektiviteten hos alla lärande agenter, förutsatt att miljöer är tur-favoriserande för dessa agenter. Vi noterar att de mest rimliga inlärningsmodellerna är lyckofavoriserande i förhållande till de mest typiska uppgiftsmiljöer (se bilagan för en längre diskussion). I uttalandet av Theorem 1 har vi utelämnat ytterligare specifikationer avseende t och T, men det bör förstås att om tur gynnar egendomen innehar för t och T, då den förbättrade prestanda innehar i förhållande till dessa perioder. För att bevisa Theorem 1 konstruerar vi A q, givet A. Konstruktionen illustreras steg för steg i Bild. 2, Där för illustrativa ändamål, den klassiska interaktionen av agent A kontrasteras mot kvant växelverkan av agent A q. Steg 1: A q kommer att använda kvantoraklet varianten av E ( E q oracle ) för tid t  på O (  på A till M ), där M är epoklängden, och  på A är antalet åtgärder, för att hitta en givande åtgärd sekvens en r, med Grover sökning. Under denna period är interaktionen oprövad och interaktionen testas därefter helt klassiskt. Steg 2: En q kommer att spela ut en epok genom att producera åtgärder från en r sekventiell, nu med den klassiska miljön, för att få responser av miljön (återkalla, E q oracle kan inte ge dessa), erhålla hela givande historia h r. Hittills, A q använt O (M) A till M ) interaktion steg. Steg 3: En q "trainerar" en intern simulering av A, simulerar interaktionen mellan A och E, och startar om simuleringen tills historien h r inträffar (vi antar att en sådan händelse har en icke-noll sannolikhet). Detta kan kräva många internt simulerade interaktioner, men ingen interaktion med den verkliga miljön. I steg 4, den interna simuleringen av A(hr ) motsvarar den mest lyckade agenten möjligt, och A q avstår kontrollen till det. Slutligen tänker vi på vad som händer med A under samma tidsperioder. Om inte ytterligare information om miljön ges, i O(t) steg A har endast en exponentiellt liten (O(exp(-M ln(-))/2)) sannolikhet att ha sett belöningssekvensen. Således är kvantagenten mer lyckosam än den klassiska, och i tur-favoriserande Steg 1,2 Steg 3 Steg 4 Steg 1 Steg 3: En q simulerar agenten A, och "tränar" simuleringen för att producera den givande sekvensen. I steg 4, A q använder A(hr) för återstoden av den nu klassiskt testade interaktionen, med den klassiska miljön E. inställningar, innebär detta att A q kommer att fortsätta att överträffa A efter t steg. Utlåtandet av Theorem 1 är inte kvantitativt, på grund av den allmänna definitionen av tur-favoriserande inställningar. Vi kan emellertid byta ut generalitet mot exakthet. Om en agent A använder en variant av - greedy [26] beteende - det vill säga, det ger belöningssekvensen (exploatering) med sannolikhet och utforskar med sannolikhet 1 -, Då förhållandet mellan resultaten av A q och A kommer att vara exponentiellt i M : den konstanta belöningsannolikheten för A q jämfört med exponentiellt minskande O(-M ln( en)/2)) av A i steg t. Denna exponentiella gap innehar för tidsskalan T  på O(t). Förbättringen av inlärningseffektiviteten (antal interaktionssteg) är dock kvadratisk. Våra resultat uppnår solida förbättringar med hjälp av enkla tekniker, till priset av att begränsa arbetsmiljöerna. Men vårt exempel kan ytterligare generaliseras i två riktningar. Först, så länge den re-set inträffar på steg M, flera och flervärderade belöningar kan också hanteras genom att definiera orakel som reversibelt räkna belöningarna. Mycket givande sekvenser kan sedan hittas genom kvantoptimering tekniker [27], som beskrivs i tillägget. För det andra, under starkare antaganden om E q, med hjälp av mer involverade kvant subrutiner, kan vi hantera stokastiska miljöer. Till exempel, i inställningen med en belöning per epok, oraklet  och 0 där sin 2 är sannolikheten för en belöning, med tanke på åtgärden sekvens a, kan konstrueras från en reversibel implementation av miljön där slumpmässighet representeras som ett delsystem i en insnärjd tillstånd (se tillägget för detaljer). Härifrån, genom att använda fas kick-back och fasuppskattning agenten kan förverkliga kartläggningen  på 0 →  på ett, där en är en l-bit precisionsuppskattning av belöningsannolikheten som anges av vinkeln A. Därefter amplitud förstärkning används för amplitud-amplity alla sekvenser a där belöningsannolikheten p r (a) given sekvens a, är över en tröskel p min. Med tanke på N min sådana sekvenser (ut ur N tot :=  och M sekvenser totalt), det totala antalet interaktioner steg multiplicerar M med amplitud förstärkning kostnad (O((N tot Om den minsta relevanta framgång sannolikheten är konstant för en familj av uppgift miljöer, då detta utgör en quadratic förbättring i att hitta bra åtgärd sekvenser. Detta tillvägagångssätt kan också generaliseras till en bredare kategori av inställningar (se bilagan för närmare information). I många miljöer, t.ex. robotik, tillåter de klassiska miljöerna inte "orakularisering". De konstruktioner som presenteras kan dock användas i modellbaserat lärande [14], där agenten konstruerar en intern representation av miljön för att underlätta bättre lärande genom simulering. Sedan kan "quantum chip" hjälpa till att påskynda intern bearbetning, vilket är det mest som kan göras i QC-inställningar. Ett lockande undantag från detta kan vara nanoscale-robotar (t.ex. Intelligenta versioner av in-situ sonder i [19] ) i framtida kvantexperiment, eftersom miljön på dessa skalor uppenbarligen är kvant och utsökt kontroll blir en möjlighet. Slutsatser.-I detta arbete har vi utvidgat den allmänna agent-miljö ramen för artificiell intelligens [14] till kvantområdet. Baserat på detta har vi etablerat ett schema för kvantförbättringar i lärande, bortom beräknings komplexitet. Med hjälp av detta schema har vi gett explicita konstruktioner av kvantförstärkta förstärkande inlärningsagenter, som överträffar sina klassiska motsvarigheter fyrsidigt i termer av lärande effektivitet, eller till och med exponentiellt i prestanda under begränsade perioder. Detta utgör ett viktigt steg mot en systematisk undersökning av kvantmaskininlärningens fulla potential och det första steget i samband med förstärkning av inlärningen under kvantinteraktion. ERKÄNNANDEN
En allmän ram för kvant maskininlärning presenteras i REF.
Quantum-enhanced machine learning
{'venue': 'Phys. Rev. Lett. 117, 130501 (2016)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Medicine']}