EITC/QI/QIF Quantum Information Fundamentals är det europeiska IT-certifieringsprogrammet för teoretiska och praktiska aspekter av kvantinformation och kvantberäkning, baserat på kvantfysikens lagar snarare än klassisk fysik och erbjuder kvalitativa fördelar jämfört med deras klassiska motsvarigheter.
Läroplanen för EITC/QI/QIF Quantum Information Fundamentals täcker introduktion till kvantmekanik (inklusive beaktande av dubbelslitsexperimentet och materiavågsinterferens), introduktion till kvantinformation (qubits och deras geometriska representation), ljuspolarisation, osäkerhetsprincip, kvantum entanglement, EPR paradox, Bell ojämlikhet kränkning, övergivande av lokal realism, kvantinformationsbehandling (inklusive enhetlig transformation, enkel-qubit och två-qubit grindar), no-cloning theorem, kvantteleportation, kvantmätning, kvantberäkning (inklusive introduktion till multi -qubit-system, universell familj av grindar, reversibilitet av beräkningar), kvantalgoritmer (inklusive Quantum Fourier Transform, Simons algoritm, utökad Churh-Turing-uppsats, Shor'q kvantfaktoreringsalgoritm, Grovers kvantsökningsalgoritm), kvantobservationer, quantodinger,'s qubits implementeringar, kvantkomplexitetsteori, adiabatisk kvantberäkning ion, BQP, introduktion till spin, inom följande struktur, som omfattar omfattande videodidaktiskt innehåll som referens för denna EITC-certifiering.
Kvantinformation är information om tillståndet i ett kvantsystem. Det är den grundläggande enheten för studier i kvantinformationsteori och kan manipuleras med hjälp av kvantinformationsbearbetningstekniker. Kvantinformation hänvisar till både den tekniska definitionen i termer av Von Neumann-entropi och den allmänna beräkningstermen.
Kvantinformation och beräkning är ett tvärvetenskapligt område som involverar kvantmekanik, datavetenskap, informationsteori, filosofi och kryptografi bland andra områden. Dess studie är också relevant för discipliner som kognitionsvetenskap, psykologi och neurovetenskap. Dess huvudsakliga fokus är att extrahera information från materia i mikroskopisk skala. Observation inom vetenskapen är ett grundläggande särskiljande kriturium för verkligheten och ett av de viktigaste sätten att inhämta information. Därför krävs mätning för att kvantifiera observationen, vilket gör den avgörande för den vetenskapliga metoden. Inom kvantmekaniken, på grund av osäkerhetsprincipen, kan icke-pendlande observerbara objekt inte mätas exakt samtidigt, eftersom ett egentillstånd i den ena basen inte är ett egentillstånd i den andra basen. Eftersom båda variablerna inte är väldefinierade samtidigt, kan ett kvanttillstånd aldrig innehålla definitiv information om båda variablerna. På grund av denna grundläggande egenskap hos mätningen i kvantmekanik, kan denna teori generellt karakteriseras som icke-deterministisk i motsats till klassisk mekanik, som är helt deterministisk. Kvanttillståndens indeterminism karaktäriserar information som definieras som tillstånd av kvantsystem. I matematiska termer är dessa tillstånd i superpositioner (linjära kombinationer) av klassiska systems tillstånd.
Eftersom information alltid är kodad i ett fysiskt systems tillstånd, är den fysisk i sig själv. Medan kvantmekaniken handlar om att undersöka materiens egenskaper på mikroskopisk nivå, fokuserar kvantinformationsvetenskapen på att extrahera information från dessa egenskaper, och kvantberäkningar manipulerar och bearbetar kvantinformation - utför logiska operationer - med hjälp av kvantinformationsbearbetningstekniker.
Kvantinformation, som klassisk information, kan bearbetas med hjälp av datorer, överföras från en plats till en annan, manipuleras med algoritmer och analyseras med datavetenskap och matematik. Precis som den grundläggande enheten för klassisk information är biten, handlar kvantinformation om qubits, som kan existera i superposition av 0 och 1 (samtidigt som något sant och falskt). Kvantinformation kan också existera i så kallade intrasslade tillstånd, som manifesterar rent icke-klassiska icke-lokala korrelationer i sina mätningar, vilket möjliggör tillämpningar som kvantteleportering. Nivån av intrassling kan mätas med Von Neumann-entropi, som också är ett mått på kvantinformation. På senare tid har området kvantberäkning blivit ett mycket aktivt forskningsområde på grund av möjligheten att störa modern beräkning, kommunikation och kryptografi.
Historien om kvantinformation började vid 20-talets början när klassisk fysik revolutionerades till kvantfysik. Teorierna inom klassisk fysik förutspådde absurditeter som den ultravioletta katastrofen eller elektroner som spiralerade in i kärnan. Till en början borstades dessa problem åt sidan genom att lägga till ad hoc-hypoteser till klassisk fysik. Snart blev det uppenbart att en ny teori måste skapas för att förstå dessa absurditeter, och teorin om kvantmekanik föddes.
Kvantmekaniken formulerades av Schrödinger med hjälp av vågmekanik och Heisenberg med hjälp av matrismekanik. Likvärdigheten mellan dessa metoder bevisades senare. Deras formuleringar beskrev dynamiken i mikroskopiska system men hade flera otillfredsställande aspekter i beskrivningen av mätprocesser. Von Neumann formulerade kvantteori med operatoralgebra på ett sätt som beskrev såväl mätning som dynamik. Dessa studier betonade de filosofiska aspekterna av mätning snarare än en kvantitativ metod för att extrahera information via mätningar.
På 1960-talet föreslog Stratonovich, Helstrom och Gordon en formulering av optisk kommunikation med hjälp av kvantmekanik. Detta var det första historiska framträdandet av kvantinformationsteorin. De studerade främst felsannolikheter och kanalkapacitet för kommunikation. Senare fick Holevo en övre gräns för kommunikationshastighet i överföringen av ett klassiskt meddelande via en kvantkanal.
På 1970-talet började tekniker för att manipulera enatoms kvanttillstånd, såsom atomfällan och scanning tunnelmikroskopet, utvecklas, vilket gjorde det möjligt att isolera enstaka atomer och ordna dem i arrayer. Före dessa utvecklingar var exakt kontroll över enstaka kvantsystem inte möjlig, och experiment använde grövre, samtidig kontroll över ett stort antal kvantsystem. Utvecklingen av livskraftiga entillståndsmanipulationstekniker ledde till ett ökat intresse för området kvantinformation och beräkningar.
På 1980-talet uppstod intresse för om det kunde vara möjligt att använda kvanteffekter för att motbevisa Einsteins relativitetsteori. Om det var möjligt att klona ett okänt kvanttillstånd, skulle det vara möjligt att använda intrasslade kvanttillstånd för att överföra information snabbare än ljusets hastighet, vilket motbevisar Einsteins teori. Emellertid visade no-cloning theoremet att sådan kloning är omöjlig. Satsen var ett av de tidigaste resultaten av kvantinformationsteorin.
Utveckling från kryptografi
Trots all spänning och intresse över att studera isolerade kvantsystem och försöka hitta ett sätt att kringgå relativitetsteorin, blev forskningen inom kvantinformationsteorin stillastående på 1980-talet. Men ungefär samtidigt började en annan väg ägna sig åt kvantinformation och beräkningar: Kryptografi. I en allmän mening är kryptografi problemet med att göra kommunikation eller beräkning som involverar två eller flera parter som kanske inte litar på varandra.
Bennett och Brassard utvecklade en kommunikationskanal på vilken det är omöjligt att avlyssna utan att upptäckas, ett sätt att kommunicera i hemlighet på långa avstånd med hjälp av kvantkrypteringsprotokollet BB84. Nyckelidén var användningen av kvantmekanikens grundläggande princip att observation stör de observerade, och introduktionen av en avlyssnare i en säker kommunikationslinje kommer omedelbart att låta de två parter som försöker kommunicera om avlyssnarens närvaro.
Utveckling från datavetenskap och matematik
Med tillkomsten av Alan Turings revolutionerande idéer om en programmerbar dator, eller Turing-maskin, visade han att alla verkliga beräkningar kan översättas till en likvärdig beräkning som involverar en Turing-maskin. Detta är känt som avhandlingen Church–Turing.
Snart nog tillverkades de första datorerna och datorhårdvaran växte i en så snabb takt att tillväxten, genom erfarenhet av produktion, kodifierades till ett empiriskt förhållande kallat Moores lag. Denna "lag" är en projektiv trend som säger att antalet transistorer i en integrerad krets fördubblas vartannat år. När transistorer började bli mindre och mindre för att packa mer kraft per ytarea, började kvanteffekter dyka upp i elektroniken vilket resulterade i oavsiktlig störning. Detta ledde till tillkomsten av kvantberäkningar, som använde kvantmekanik för att designa algoritmer.
Vid denna tidpunkt visade kvantdatorer löfte om att vara mycket snabbare än klassiska datorer för vissa specifika problem. Ett sådant exempel på problem utvecklades av David Deutsch och Richard Jozsa, känd som Deutsch-Jozsa-algoritmen. Detta problem hade dock få eller inga praktiska tillämpningar. Peter Shor 1994 kom med ett mycket viktigt och praktiskt problem, ett att hitta de viktigaste faktorerna för ett heltal. Det diskreta logaritmproblemet som det kallades kunde lösas effektivt på en kvantdator men inte på en klassisk dator, vilket visar att kvantdatorer är kraftfullare än Turing-maskiner.
Utveckling från informationsteori
Runt den tiden som datavetenskapen gjorde en revolution, så gjorde informationsteori och kommunikation, genom Claude Shannon. Shannon utvecklade två grundläggande informationsteorem: noiseless channel coding theorem och noisy channel coding theorem. Han visade också att felkorrigerande koder kunde användas för att skydda information som skickas.
Kvantinformationsteorin följde också en liknande bana, Ben Schumacher gjorde 1995 en analog till Shannons ljudlösa kodningssats med hjälp av qubit. En teori om felkorrigering utvecklades också, som gör det möjligt för kvantdatorer att göra effektiva beräkningar oavsett brus, och göra pålitlig kommunikation över bullriga kvantkanaler.
Qubits och informationsteori
Kvantinformation skiljer sig starkt från klassisk information, betecknad med biten, på många slående och obekanta sätt. Medan den grundläggande enheten för klassisk information är biten, är den mest grundläggande enheten för kvantinformation qubiten. Klassisk information mäts med Shannon-entropi, medan den kvantmekaniska analogen är Von Neumann-entropi. En statistisk ensemble av kvantmekaniska system kännetecknas av densitetsmatrisen. Många entropimått inom klassisk informationsteori kan också generaliseras till kvantfallet, såsom Holevo-entropin och den villkorliga kvantentropin.
Till skillnad från klassiska digitala tillstånd (som är diskreta) är en qubit kontinuerligt värderad, beskrivbar med en riktning på Bloch-sfären. Trots att den kontinuerligt värderas på detta sätt är en qubit den minsta möjliga enheten av kvantinformation, och trots att qubit-tillståndet är kontinuerligt värderat är det omöjligt att mäta värdet exakt. Fem kända satser beskriver gränserna för manipulation av kvantinformation:
- no-teleportation theorem, som säger att en qubit inte kan (helt) omvandlas till klassiska bitar; det vill säga den kan inte "läsas" helt
- no-cloning theorem, som förhindrar en godtycklig qubit från att kopieras,
- no-deleting theorem, som förhindrar att en godtycklig qubit tas bort,
- no-broadcasting theorem, som förhindrar en godtycklig qubit från att levereras till flera mottagare, även om den kan transporteras från plats till plats (t.ex. via kvantteleportering),
- no-hiding theorem, som demonstrerar bevarandet av kvantinformation, Dessa satser bevisar att kvantinformation inom universum är bevarad och de öppnar upp unika möjligheter i kvantinformationsbehandling.
Kvantinformation
Tillståndet för en qubit innehåller all dess information. Detta tillstånd uttrycks ofta som en vektor på Bloch-sfären. Detta tillstånd kan ändras genom att tillämpa linjära transformationer eller kvantportar på dem. Dessa enhetliga transformationer beskrivs som rotationer på Bloch-sfären. Medan klassiska grindar motsvarar den booleska logikens välbekanta operationer, är kvantportar fysiska enhetsoperatorer.
På grund av kvantsystemens volatilitet och omöjligheten att kopiera tillstånd är lagringen av kvantinformation mycket svårare än att lagra klassisk information. Ändå, med användning av kvantfelskorrigering kan kvantinformation fortfarande lagras på ett tillförlitligt sätt i princip. Förekomsten av kvantfelskorrigerande koder har också lett till möjligheten till feltolerant kvantberäkning.
Klassiska bitar kan kodas in i och därefter hämtas från konfigurationer av kvantbitar, genom användning av kvantgrindar. I sig själv kan en enda qubit inte förmedla mer än en bit tillgänglig klassisk information om dess beredning. Detta är Holevos sats. I superdense kodning kan emellertid en sändare, genom att agera på en av två intrasslade qubits, förmedla två bitar av tillgänglig information om deras gemensamma tillstånd till en mottagare.
Kvantinformation kan flyttas runt, i en kvantkanal, analogt med konceptet med en klassisk kommunikationskanal. Kvantmeddelanden har en ändlig storlek, mätt i qubits; kvantkanaler har en ändlig kanalkapacitet, mätt i qubits per sekund.
Kvantinformation, och förändringar i kvantinformation, kan mätas kvantitativt genom att använda en analog av Shannon-entropin, kallad von Neumann-entropin.
I vissa fall kan kvantalgoritmer användas för att utföra beräkningar snabbare än i någon känd klassisk algoritm. Det mest kända exemplet på detta är Shors algoritm som kan faktorisera tal i polynomtid, jämfört med de bästa klassiska algoritmerna som tar subexponentiell tid. Eftersom faktorisering är en viktig del av säkerheten för RSA-kryptering, utlöste Shors algoritm det nya fältet post-kvantkryptografi som försöker hitta krypteringsscheman som förblir säkra även när kvantdatorer är i spel. Andra exempel på algoritmer som visar kvantöverlägsenhet inkluderar Grovers sökalgoritm, där kvantalgoritmen ger en kvadratisk hastighet upp över bästa möjliga klassiska algoritm. Komplexitetsklassen av problem som effektivt kan lösas av en kvantdator kallas BQP.
Quantum key distribution (QKD) tillåter ovillkorligt säker överföring av klassisk information, till skillnad från klassisk kryptering, som alltid kan brytas i princip, om inte i praktiken. Observera att vissa subtila punkter angående säkerheten för QKD fortfarande diskuteras hett.
Studiet av alla ovanstående ämnen och skillnader omfattar kvantinformationsteori.
Relation till kvantmekanik
Kvantmekanik är studiet av hur mikroskopiska fysiska system förändras dynamiskt i naturen. Inom området kvantinformationsteori är de studerade kvantsystemen abstraherade bort från alla verkliga motsvarigheter. En qubit kan till exempel fysiskt vara en foton i en linjär optisk kvantdator, en jon i en fångad jonkvantdator, eller det kan vara en stor samling atomer som i en supraledande kvantdator. Oavsett den fysiska implementeringen, gäller gränserna och egenskaperna hos qubits som impliceras av kvantinformationsteorin eftersom alla dessa system är matematiskt beskrivna av samma apparat av densitetsmatriser över de komplexa talen. En annan viktig skillnad med kvantmekanik är att medan kvantmekaniken ofta studerar oändligt dimensionella system som en harmonisk oscillator, handlar kvantinformationsteorin både om kontinuerliga variabla system och ändliga dimensionella system.
Kvantberäkning
Kvantberäkning är en typ av beräkning som utnyttjar de kollektiva egenskaperna hos kvanttillstånd, såsom superposition, interferens och intrassling, för att utföra beräkningar. Enheterna som utför kvantberäkningar är kända som kvantdatorer.: I-5 Även om nuvarande kvantdatorer är för små för att överträffa vanliga (klassiska) datorer för praktiska tillämpningar, tros de vara kapabla att lösa vissa beräkningsproblem, såsom heltalsfaktorisering (som ligger till grund för RSA-kryptering), betydligt snabbare än klassiska datorer. Studiet av kvantberäkning är ett delområde av kvantinformationsvetenskap.
Kvantberäkning började 1980 när fysikern Paul Benioff föreslog en kvantmekanisk modell av Turing-maskinen. Richard Feynman och Yuri Manin föreslog senare att en kvantdator hade potentialen att simulera saker som en klassisk dator inte skulle kunna göra. 1994 utvecklade Peter Shor en kvantalgoritm för faktorisering av heltal med potential att dekryptera RSA-krypterad kommunikation. 1998 skapade Isaac Chuang, Neil Gershenfeld och Mark Kubinec den första två-qubit kvantdatorn som kunde utföra beräkningar. Trots pågående experimentella framsteg sedan slutet av 1990-talet tror de flesta forskare att "feltolerant kvantberäkning [är] fortfarande en ganska avlägsen dröm." Under de senaste åren har investeringarna i kvantberäkningsforskning ökat inom den offentliga och privata sektorn. Den 23 oktober 2019 hävdade Google AI, i samarbete med US National Aeronautics and Space Administration (NASA), att de hade utfört en kvantberäkning som var omöjlig på någon klassisk dator, men huruvida detta påstående var eller fortfarande är giltigt är en fråga om aktiv forskning.
Det finns flera typer av kvantdatorer (även kända som kvantdatorsystem), inklusive kvantkretsmodellen, kvantturingmaskinen, adiabatisk kvantdator, envägs kvantdator och olika kvantcellulära automater. Den mest använda modellen är kvantkretsen, baserad på kvantbiten, eller "qubit", som är något analog med biten i klassisk beräkning. En qubit kan vara i ett 1- eller 0-kvanttillstånd, eller i en överlagring av 1- och 0-tillstånden. När den mäts är den dock alltid 0 eller 1; sannolikheten för endera utfallet beror på qubitens kvanttillstånd omedelbart före mätning.
Arbetet med att bygga en fysisk kvantdator fokuserar på teknologier såsom transmons, jonfällor och topologiska kvantdatorer, som syftar till att skapa högkvalitativa qubits.: 2–13 Dessa qubits kan utformas annorlunda, beroende på den fullständiga kvantdatorns beräkningsmodell, oavsett om det gäller kvantlogiska grindar, kvantglödgning eller adiabatisk kvantberäkning. Det finns för närvarande ett antal betydande hinder för att konstruera användbara kvantdatorer. Det är särskilt svårt att upprätthålla qubits kvanttillstånd, eftersom de lider av kvantdekoherens och tillståndstrohet. Kvantdatorer kräver därför felkorrigering.
Alla beräkningsproblem som kan lösas av en klassisk dator kan också lösas av en kvantdator. Omvänt kan alla problem som kan lösas av en kvantdator också lösas av en klassisk dator, åtminstone i princip givet tillräckligt med tid. Kvantdatorer lyder med andra ord Church–Turings tes. Detta innebär att medan kvantdatorer inte ger några ytterligare fördelar jämfört med klassiska datorer när det gäller beräkningsbarhet, har kvantalgoritmer för vissa problem betydligt lägre tidskomplexitet än motsvarande kända klassiska algoritmer. Särskilt antas kvantdatorer snabbt kunna lösa vissa problem som ingen klassisk dator skulle kunna lösa på någon möjlig tid - en bedrift som kallas "kvantöverhöghet". Studiet av beräkningskomplexiteten hos problem med avseende på kvantdatorer är känd som kvantkomplexitetsteori.
Den rådande modellen för kvantberäkning beskriver beräkningen i termer av ett nätverk av kvantlogiska grindar. Denna modell kan ses som en abstrakt linjär-algebraisk generalisering av en klassisk krets. Eftersom denna kretsmodell lyder kvantmekaniken, tros en kvantdator som effektivt kan köra dessa kretsar vara fysiskt realiserbar.
Ett minne som består av n informationsbitar har 2^n möjliga tillstånd. En vektor som representerar alla minnestillstånd har alltså 2^n poster (en för varje tillstånd). Denna vektor ses som en sannolikhetsvektor och representerar det faktum att minnet finns i ett visst tillstånd.
I den klassiska uppfattningen skulle en post ha värdet 1 (dvs. en 100 % sannolikhet att vara i detta tillstånd) och alla andra poster skulle vara noll.
Inom kvantmekaniken kan sannolikhetsvektorer generaliseras till densitetsoperatorer. Kvanttillståndsvektorformalismen introduceras vanligtvis först eftersom den är begreppsmässigt enklare, och för att den kan användas istället för densitetsmatrisformalismen för rena tillstånd, där hela kvantsystemet är känt.
en kvantberäkning kan beskrivas som ett nätverk av kvantlogiska grindar och mätningar. Men vilken mätning som helst kan skjutas upp till slutet av kvantberäkningen, även om denna uppskjutning kan komma till en beräkningskostnad, så de flesta kvantkretsar visar ett nätverk som endast består av kvantlogiska grindar och inga mätningar.
Vilken kvantberäkning som helst (vilket är, i ovanstående formalism, vilken enhetlig matris som helst över n kvantbitar) kan representeras som ett nätverk av kvantlogiska grindar från en ganska liten familj av grindar. Ett val av grindfamilj som möjliggör denna konstruktion är känt som en universal gate set, eftersom en dator som kan köra sådana kretsar är en universell kvantdator. En vanlig sådan uppsättning inkluderar alla en-qubit-grindar såväl som CNOT-grinden från ovan. Detta innebär att vilken kvantberäkning som helst kan utföras genom att exekvera en sekvens av en-qubit-grindar tillsammans med CNOT-grindar. Även om denna portuppsättning är oändlig, kan den ersättas med en finit portuppsättning genom att appellera till Solovay-Kitaev-satsen.
Kvantealgoritmer
Framsteg med att hitta kvantalgoritmer fokuserar vanligtvis på denna kvantkretsmodell, även om undantag som den kvantadiabatiska algoritmen finns. Kvantalgoritmer kan grovt kategoriseras efter typen av hastighetsökning som uppnås jämfört med motsvarande klassiska algoritmer.
Kvantalgoritmer som erbjuder mer än en polynomhastighet över den mest kända klassiska algoritmen inkluderar Shors algoritm för factoring och de relaterade kvantalgoritmerna för att beräkna diskreta logaritmer, lösa Pells ekvation och mer allmänt lösa det dolda undergruppsproblemet för abelska ändliga grupper. Dessa algoritmer är beroende av kvantfouriertransformens primitiva. Inget matematiskt bevis har hittats som visar att en lika snabb klassisk algoritm inte kan upptäckas, även om detta anses osannolikt.[självpublicerad källa?] Vissa orakelproblem som Simons problem och Bernstein-Vazirani-problemet ger bevisbara hastigheter, även om detta finns i kvantfrågemodellen, som är en begränsad modell där lägre gränser är mycket lättare att bevisa och inte nödvändigtvis översätts till snabbare för praktiska problem.
Andra problem, inklusive simulering av kvantfysikaliska processer från kemi och fasta tillståndsfysik, approximationen av vissa Jones polynom och kvantalgoritmen för linjära ekvationssystem har kvantalgoritmer som verkar ge superpolynomiska hastigheter och är BQP-kompletta. Eftersom dessa problem är BQP-kompletta, skulle en lika snabb klassisk algoritm för dem innebära att ingen kvantalgoritm ger en superpolynomhastighet, vilket tros vara osannolikt.
Vissa kvantalgoritmer, som Grovers algoritm och amplitudförstärkning, ger polynomhastigheter jämfört med motsvarande klassiska algoritmer. Även om dessa algoritmer ger en jämförelsevis blygsam kvadratisk hastighetshöjning, är de allmänt tillämpliga och ger därmed hastigheter för ett brett spektrum av problem. Många exempel på bevisbara kvanthastigheter för frågeproblem är relaterade till Grovers algoritm, inklusive Brassard, Høyer och Tapps algoritm för att hitta kollisioner i två-till-en-funktioner, som använder Grovers algoritm, och Farhi, Goldstone och Gutmanns algoritm för att utvärdera NAND träd, vilket är en variant av sökproblemet.
Kryptografiska applikationer
En anmärkningsvärd tillämpning av kvantberäkning är för attacker på kryptografiska system som för närvarande används. Heltalsfaktorisering, som underbygger säkerheten för kryptografiska system med offentliga nyckel, tros vara beräkningsmässigt omöjlig med en vanlig dator för stora heltal om de är produkten av få primtal (t.ex. produkter av två 300-siffriga primtal). Som jämförelse kan en kvantdator effektivt lösa detta problem genom att använda Shors algoritm för att hitta dess faktorer. Denna förmåga skulle tillåta en kvantdator att bryta många av de kryptografiska systemen som används idag, i den meningen att det skulle finnas en polynomisk tidsalgoritm (i antalet siffror i heltal) för att lösa problemet. I synnerhet är de flesta av de populära publika nyckelchiffrarna baserade på svårigheten att faktorisera heltal eller det diskreta logaritmproblemet, som båda kan lösas med Shors algoritm. I synnerhet kan algoritmerna för RSA, Diffie–Hellman och den elliptiska kurvan Diffie–Hellman brytas. Dessa används för att skydda säkra webbsidor, krypterad e-post och många andra typer av data. Att bryta dessa skulle få betydande konsekvenser för elektronisk integritet och säkerhet.
Att identifiera kryptografiska system som kan vara säkra mot kvantalgoritmer är ett aktivt undersökt ämne inom området post-kvantkryptografi. Vissa publika nyckelalgoritmer är baserade på andra problem än heltalsfaktorisering och diskreta logaritmproblem som Shors algoritm gäller, som McEliece-kryptosystemet baserat på ett problem i kodningsteorin. Gitterbaserade kryptosystem är inte heller kända för att brytas av kvantdatorer, och att hitta en polynomtidsalgoritm för att lösa det dihedriska dolda undergruppsproblemet, vilket skulle bryta många gitterbaserade kryptosystem, är ett välstuderat öppet problem. Det har bevisats att användning av Grovers algoritm för att bryta en symmetrisk (hemlig nyckel) algoritm med brute force kräver tid lika med ungefär 2n/2 anrop av den underliggande kryptografiska algoritmen, jämfört med ungefär 2n i det klassiska fallet, vilket betyder att symmetriska nyckellängder är effektivt halverat: AES-256 skulle ha samma säkerhet mot en attack med Grovers algoritm som AES-128 har mot klassisk brute-force-sökning (se Nyckelstorlek).
Kvantkryptografi skulle potentiellt kunna uppfylla några av funktionerna för kryptografi med publik nyckel. Kvantbaserade kryptografiska system kan därför vara säkrare än traditionella system mot quantum hacking.
Sökproblem
Det mest välkända exemplet på ett problem med att erkänna en polynomkvanthastighetsuppgång är ostrukturerad sökning, att hitta ett markerat objekt från en lista med n objekt i en databas. Detta kan lösas med Grovers algoritm genom att använda O(sqrt(n))-frågor till databasen, kvadratiskt färre än de Omega(n)-frågor som krävs för klassiska algoritmer. I det här fallet är fördelen inte bara bevisbar utan också optimal: det har visat sig att Grovers algoritm ger maximalt möjliga sannolikhet att hitta det önskade elementet för valfritt antal orakeluppslagningar.
Problem som kan lösas med Grovers algoritm har följande egenskaper:
- Det finns ingen sökbar struktur i samlingen av möjliga svar,
- Antalet möjliga svar att kontrollera är detsamma som antalet ingångar till algoritmen, och
- Det finns en boolesk funktion som utvärderar varje ingång och avgör om det är rätt svar
För problem med alla dessa egenskaper skalas körtiden för Grovers algoritm på en kvantdator som kvadratroten av antalet ingångar (eller element i databasen), i motsats till den linjära skalningen av klassiska algoritmer. En allmän klass av problem som Grovers algoritm kan tillämpas på är booleskt tillfredsställelseproblem, där databasen genom vilken algoritmen itererar är den för alla möjliga svar. Ett exempel och (möjlig) tillämpning av detta är en lösenordsknäckare som försöker gissa ett lösenord. Symmetriska chiffer som Triple DES och AES är särskilt sårbara för denna typ av attack.[Behövs citat] Denna tillämpning av kvantberäkning är ett stort intresse för statliga myndigheter.
Simulering av kvantsystem
Eftersom kemi och nanoteknik bygger på förståelse av kvantsystem, och sådana system är omöjliga att simulera på ett effektivt sätt klassiskt, tror många att kvantsimulering kommer att vara en av de viktigaste tillämpningarna av kvantberäkning. Kvantsimulering kan också användas för att simulera beteendet hos atomer och partiklar under ovanliga förhållanden, såsom reaktionerna inuti en kolliderare. Kvantsimuleringar kan användas för att förutsäga framtida vägar för partiklar och protoner under superposition i dubbelslitsexperimentet. Cirka 2% av den årliga globala energiproduktionen används för kvävefixering för att producera ammoniak för Haber-processen i jordbruket gödselindustrin samtidigt som naturligt förekommande organismer också producerar ammoniak. Kvantsimuleringar kan användas för att förstå denna process som ökar produktionen.
Kvantglödgning och adiabatisk optimering
Kvantglödgning eller adiabatisk kvantberäkning förlitar sig på den adiabatiska teoremet för att utföra beräkningar. Ett system placeras i grundtillståndet för en enkel Hamiltonian, som långsamt utvecklas till en mer komplicerad Hamiltonian vars grundtillstånd representerar lösningen på problemet i fråga. Den adiabatiska satsen säger att om utvecklingen är tillräckligt långsam kommer systemet att hålla sig i sitt grundtillstånd hela tiden under processen.
Maskininlärning
Eftersom kvantdatorer kan producera utdata som klassiska datorer inte kan producera effektivt, och eftersom kvantberäkning i grunden är linjär algebraisk, uttrycker vissa hopp om att utveckla kvantalgoritmer som kan påskynda maskininlärningsuppgifter. Till exempel antas kvantalgoritmen för linjära ekvationssystem, eller "HHL Algorithm", uppkallad efter dess upptäckare Harrow, Hassidim och Lloyd, ge snabbare än klassiska motsvarigheter. Vissa forskargrupper har nyligen utforskat användningen av kvantglödgningshårdvara för träning av Boltzmann-maskiner och djupa neurala nätverk.
Beräkningsbiologi
Inom området beräkningsbiologi har kvantberäkning spelat en stor roll för att lösa många biologiska problem. Ett av de välkända exemplen skulle vara beräkningsgenomik och hur datoranvändning drastiskt har minskat tiden för att sekvensera ett mänskligt genom. Med tanke på hur beräkningsbiologi använder generisk datamodellering och lagring, förväntas dess tillämpningar för beräkningsbiologi också uppstå.
Datorstödd läkemedelsdesign och generativ kemi
Djupa generativa kemimodeller dyker upp som kraftfulla verktyg för att påskynda upptäckten av läkemedel. Den enorma storleken och komplexiteten hos det strukturella utrymmet för alla möjliga läkemedelsliknande molekyler utgör dock betydande hinder, som skulle kunna övervinnas i framtiden av kvantdatorer. Kvantdatorer är naturligtvis bra för att lösa komplexa kvantproblem med många kroppar och kan därför vara avgörande för tillämpningar som involverar kvantkemi. Därför kan man förvänta sig att kvantförstärkta generativa modeller inklusive kvant-GAN så småningom kan utvecklas till ultimata generativa kemialgoritmer. Hybridarkitekturer som kombinerar kvantdatorer med djupa klassiska nätverk, såsom Quantum Variational Autoencoders, kan redan tränas på kommersiellt tillgängliga annealers och användas för att generera nya läkemedelsliknande molekylära strukturer.
Utveckling av fysiska kvantdatorer
Utmaningar
Det finns ett antal tekniska utmaningar i att bygga en storskalig kvantdator. Fysikern David DiVincenzo har listat dessa krav för en praktisk kvantdator:
- Fysiskt skalbar för att öka antalet qubits,
- Qubits som kan initieras till godtyckliga värden,
- Kvantportar som är snabbare än dekoherenstiden,
- Universal gate set,
- Qubits som lätt kan läsas.
Att köpa delar till kvantdatorer är också mycket svårt. Många kvantdatorer, som de som konstruerats av Google och IBM, behöver helium-3, en kärnforskningsbiprodukt, och speciella supraledande kablar tillverkade endast av det japanska företaget Coax Co.
Styrningen av multi-qubit-system kräver generering och koordinering av ett stort antal elektriska signaler med snäv och deterministisk tidsupplösning. Detta har lett till utvecklingen av kvantkontroller som möjliggör gränssnitt med qubits. Att skala dessa system för att stödja ett växande antal qubits är en ytterligare utmaning.
Kvantdekoherens
En av de största utmaningarna med att konstruera kvantdatorer är att kontrollera eller ta bort kvantdekoherens. Detta innebär vanligtvis att man isolerar systemet från sin omgivning eftersom interaktioner med den yttre världen gör att systemet bryter samman. Men det finns också andra källor till dekoherens. Exempel inkluderar kvantgrindarna och gittervibrationerna och termonukleära bakgrundsspinn i det fysiska systemet som används för att implementera kvantbitarna. Dekoherens är oåterkallelig, eftersom den i själva verket är icke-enhetlig, och är vanligtvis något som bör kontrolleras mycket, om inte undvikas. Dekoherenstider för i synnerhet kandidatsystem, den transversella relaxationstiden T2 (för NMR- och MRI-teknik, även kallad avfasningstiden), varierar typiskt mellan nanosekunder och sekunder vid låg temperatur. För närvarande kräver vissa kvantdatorer att deras qubits kyls till 20 millikelvin (vanligtvis med utspädningskylskåp) för att förhindra betydande dekoherens. En studie från 2020 hävdar att joniserande strålning som kosmisk strålning trots allt kan få vissa system att dekohera inom millisekunder.
Som ett resultat kan tidskrävande uppgifter göra vissa kvantalgoritmer inoperabla, eftersom bibehållande av tillståndet för qubits under en tillräckligt lång varaktighet så småningom kommer att korrumpera superpositionerna.
Dessa problem är svårare för optiska tillvägagångssätt eftersom tidsskalorna är storleksordningar kortare och ett ofta citerat tillvägagångssätt för att övervinna dem är optisk pulsformning. Felfrekvenser är typiskt proportionella mot förhållandet mellan drifttid och dekoherenstid, varför varje operation måste slutföras mycket snabbare än dekoherenstiden.
Som beskrivs i kvanttröskelsatsen, om felfrekvensen är tillräckligt liten, anses det vara möjligt att använda kvantfelskorrigering för att undertrycka fel och dekoherens. Detta gör att den totala beräkningstiden blir längre än dekoherenstiden om felkorrigeringsschemat kan korrigera fel snabbare än dekoherensen introducerar dem. En ofta citerad siffra för den erforderliga felfrekvensen i varje grind för feltoleranta beräkningar är 10−3, förutsatt att bruset är depolariserande.
Att uppfylla detta skalbarhetsvillkor är möjligt för ett brett spektrum av system. Användningen av felkorrigering för med sig kostnaden för ett kraftigt ökat antal erforderliga qubits. Antalet som krävs för att faktorisera heltal med Shors algoritm är fortfarande polynom och tros vara mellan L och L2, där L är antalet siffror i talet som ska faktoriseras; felkorrigeringsalgoritmer skulle blåsa upp denna siffra med ytterligare en faktor L. För ett 1000-bitars tal innebär detta ett behov av cirka 104 bitar utan felkorrigering. Med felkorrigering skulle siffran stiga till cirka 107 bitar. Beräkningstiden är cirka L2 eller cirka 107 steg och vid 1 MHz cirka 10 sekunder.
Ett mycket annorlunda tillvägagångssätt för stabilitets-dekoherensproblemet är att skapa en topologisk kvantdator med anyoner, kvasipartiklar som används som trådar och som förlitar sig på flätteori för att bilda stabila logiska grindar.
Kvantöverträffelse
Quantum supremacy är en term som myntats av John Preskill som syftar på den tekniska bedriften att visa att en programmerbar kvantenhet kan lösa ett problem utöver kapaciteten hos toppmoderna klassiska datorer. Problemet behöver inte vara användbart, så vissa ser kvantöverhöghetstestet endast som ett potentiellt framtida riktmärke.
I oktober 2019 blev Google AI Quantum, med hjälp av NASA, den första som hävdade att ha uppnått kvantöverlägsenhet genom att utföra beräkningar på kvantdatorn Sycamore mer än 3,000,000 XNUMX XNUMX gånger snabbare än de kunde göras på Summit, allmänt ansett som världens snabbaste dator. Detta påstående har senare ifrågasatts: IBM har uttalat att Summit kan utföra prover mycket snabbare än vad som påstås, och forskare har sedan dess utvecklat bättre algoritmer för provtagningsproblemet som används för att hävda kvantöverlägsenhet, vilket ger avsevärda minskningar av eller slutande av gapet mellan Sycamore och klassiska superdatorer.
I december 2020 implementerade en grupp vid USTC en typ av bosonsampling på 76 fotoner med en fotonisk kvantdator Jiuzhang för att demonstrera kvantöverhöghet. Författarna hävdar att en klassisk samtida superdator skulle kräva en beräkningstid på 600 miljoner år för att generera antalet sampel som deras kvantprocessor kan generera på 20 sekunder. Den 16 november 2021 presenterade IBM vid kvantberäkningstoppmötet en 127-qubit mikroprocessor vid namn IBM Eagle.
Fysiska implementeringar
För att fysiskt implementera en kvantdator eftersträvas många olika kandidater, bland dem (utmärks av det fysiska systemet som används för att realisera kvantbitarna):
- Supraledande kvantberäkning (qubit implementerad av tillståndet för små supraledande kretsar, Josephson-övergångar)
- Fångad jon kvantdator (qubit implementerad av det interna tillståndet för fångade joner)
- Neutrala atomer i optiska gitter (qubit implementerad av interna tillstånd av neutrala atomer fångade i ett optiskt gitter)
- Kvantpunktsdator, spinnbaserad (t.ex. Loss-DiVincenzo kvantdator) (qubit ges av spinntillstånden för fångade elektroner)
- Kvantpunktsdator, rumsbaserad (qubit ges av elektronposition i dubbel kvantpunkt)
- Kvantberäkning med hjälp av konstruerade kvantbrunnar, som i princip skulle kunna möjliggöra konstruktion av kvantdatorer som arbetar vid rumstemperatur
- Kopplad kvanttråd (qubit implementerad av ett par kvanttrådar kopplade av en kvantpunktskontakt)
- Kärnmagnetisk resonans kvantdator (NMRQC) implementerad med kärnmagnetisk resonans av molekyler i lösning, där qubits tillhandahålls av kärnsnurr i den upplösta molekylen och sonderas med radiovågor
- Solid-state NMR Kane kvantdatorer (qubit realiserad av kärnspinntillståndet hos fosfordonatorer i kisel)
- Elektroner-på-helium kvantdatorer (qubit är elektronspinnet)
- Kavitetskvantelektrodynamik (CQED) (qubit tillhandahållen av det inre tillståndet hos fångade atomer kopplade till hålrum med hög finess)
- Molekylär magnet (qubit ges av spinntillstånd)
- Fullerenbaserad ESR kvantdator (qubit baserad på det elektroniska spinnet av atomer eller molekyler inneslutna i fullerener)
- Icke-linjär optisk kvantdator (qubits realiserade genom att bearbeta tillstånd för olika ljuslägen genom både linjära och icke-linjära element)
- Linjär optisk kvantdator (qubits realiserade genom att bearbeta tillstånd för olika ljuslägen genom linjära element, t.ex. speglar, stråldelare och fasskiftare)
- Diamantbaserad kvantdator (qubit realiserad av den elektroniska eller nukleära spinn av kvävevakanscentra i diamant)
- Bose-Einstein kondensatbaserad kvantdator
- Transistorbaserad kvantdator – strängkvantdatorer med indragning av positiva hål med hjälp av en elektrostatisk fälla
- Sällsynt jordartsmetall-jon-dopade oorganiska kristallbaserade kvantdatorer (qubit realiserad av det interna elektroniska tillståndet hos dopämnen i optiska fibrer)
- Metallisk-liknande kol nanosfärer-baserade kvantdatorer
- Det stora antalet kandidater visar att kvantberäkning, trots snabba framsteg, fortfarande är i sin linda.
Det finns ett antal kvantberäkningsmodeller som kännetecknas av de grundläggande elementen i vilka beräkningen bryts ner. För praktiska implementeringar är de fyra relevanta beräkningsmodellerna:
- Quantum gate array (beräkning uppdelad i en sekvens av få qubit quantum gate)
- Envägs kvantdator (beräkning sönderdelad i en sekvens av en-qubit-mätningar som tillämpas på ett mycket intrasslat initialtillstånd eller klustertillstånd)
- Adiabatisk kvantdator, baserad på kvantglödgning (beräkning sönderdelad till en långsam kontinuerlig omvandling av en initial Hamiltonian till en slutlig Hamiltonian, vars grundtillstånd innehåller lösningen)
- Topologisk kvantdator (beräkning sönderdelas till flätning av anyoner i ett 2D-gitter)
Kvant Turing-maskinen är teoretiskt viktig men den fysiska implementeringen av denna modell är inte genomförbar. Alla fyra beräkningsmodellerna har visat sig vara likvärdiga; var och en kan simulera den andra utan mer än polynomisk overhead.
För att bekanta dig i detalj med certifieringsläroplanen kan du utöka och analysera tabellen nedan.
EITC/QI/QIF Quantum Information Fundamentals Certification Curriculum refererar till didaktiskt material med öppen tillgång i en videoform. Lärprocessen är uppdelad i en steg-för-steg-struktur (program -> lektioner -> ämnen) som täcker relevanta läroplansdelar. Obegränsad rådgivning med domänexperter tillhandahålls också.
För detaljer om certifieringsförfarandet kontrollera Hur det fungerar.
Huvudanteckningar av föreläsningar
U. Vazirani föreläsningsanteckningar:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Stödjande föreläsningsanteckningar
L. Jacak et al. föreläsningsanteckningar (med kompletterande material):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Huvudsaklig stödjande lärobok
Quantum Computation & Quantum Information lärobok (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Ytterligare föreläsningsanteckningar
J. Preskill föreläsningsanteckningar:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
A. Childs föreläsningsanteckningar:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
S. Aaronsons föreläsningsanteckningar:
https://scottaaronson.blog/?p=3943
R. de Wolf föreläsningsanteckningar:
https://arxiv.org/abs/1907.09415
Andra rekommenderade läroböcker
Klassisk och kvantberäkning (Kitaev, Shen, Vyalyi)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
Quantum Computing Since Demokritus (Aaronson)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
Theory of Quantum Information (Watrous)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
Quantum Information Theory (Wild)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Ladda ner det fullständiga offline självlärande förberedande materialet för EITC/QI/QIF Quantum Information Fundamentals-programmet i en PDF-fil
EITC/QI/QIF förberedande material – standardversion
EITC/QI/QIF förberedande material – utökad version med granskningsfrågor