Hem Förberedelser inför vintern Kvantberäkning. En kort introduktion till Quantum Computing (gästinlägg av Roman Dushkin) Quantum Computing Algoritmer

Förberedelser inför vintern

Kvantberäkning. En kort introduktion till Quantum Computing (gästinlägg av Roman Dushkin) Quantum Computing Algoritmer

RYSKA FEDERATIONENS UTBILDNINGSMINISTERIE

STATLIG UTBILDNINGSINSTITUT

Uppsats

Kvantberäkning

Introduktion

Kapitel I. Grundläggande begrepp inom kvantmekanik

Kapitel II. Grundläggande begrepp och principer för kvantberäkning

Kapitel III. Grovers algoritm

Slutsats

Bibliografi

Introduktion

Föreställ dig en dator vars minne är exponentiellt större än dess fysiska storlek skulle få dig att förvänta dig; en dator som kan hantera en exponentiellt större uppsättning indata samtidigt; en dator som utför beräkningar i Hilbert-rymden, vilket är disigt för de flesta av oss.

Då tänker man på en kvantdator.

Idén med en datorenhet baserad på kvantmekanik övervägdes först i början av 1970-talet och början av 1980-talet av fysiker och datavetare som Charles H. Bennett från IBM Thomas J. Watson Research Center och Paul A. Benioff från Argonne National Laboratoriet i Illinois, David Deutsch från Oxford University och senare Richard P. Feynman från California Institute of Technology (Caltech). Idén uppstod när forskare blev intresserade av de grundläggande begränsningarna av datoranvändning. De insåg att om tekniken fortsatte att gradvis minska storleken på datornätverk packade i kiselchips, skulle det leda till att enskilda grundämnen inte blev fler än ett fåtal atomer. Sedan uppstod ett problem, eftersom kvantfysikens lagar fungerar på atomnivå, inte klassiska. Detta väckte frågan om det var möjligt att konstruera en dator utifrån kvantfysikens principer.

Feynman var en av de första som försökte svara på denna fråga. År 1982 han föreslog en modell av ett abstrakt kvantsystem lämpligt för beräkning. Han förklarade också hur ett sådant system skulle kunna vara en simulator inom kvantfysik. Med andra ord skulle fysiker kunna utföra beräkningsexperiment på en sådan kvantdator.

Senare, 1985, insåg Deutsch att Feynmans påstående så småningom kunde leda till en kvantdator för allmänt bruk, och han publicerade ett rikt teoretiskt arbete som visade att vilken fysisk process som helst i princip kunde simuleras på en kvantdator.

Tyvärr var allt de kunde komma på vid den tiden några ganska långsökta matematiska problem, tills Shor släppte sitt arbete 1994, där han presenterade en algoritm för att lösa ett viktigt problem från talteorin på en kvantdator, nämligen, sönderdelning till primära faktorer. Han visade hur en uppsättning matematiska operationer utformade specifikt för en kvantdator kunde faktorisera(faktorisera) enorma siffror fantastiskt snabbt, mycket snabbare än konventionella datorer. Detta var ett genombrott som flyttade kvantdatorn från ett akademiskt intresse till ett problem av intresse för hela världen.

Kapitel jag . Grundläggande begrepp inom kvantmekanik

I slutet av 1800-talet fanns det en utbredd åsikt bland forskare att fysiken var en "nästan komplett" vetenskap och att det fanns mycket lite kvar för dess fullständiga "fullständighet": att förklara strukturen optiska spektra av atomer och spektralfördelning värmestrålning . Optiska spektra av en atom erhålls genom emission eller absorption av ljus (elektromagnetiska vågor) av fria eller svagt bundna atomer; Monatomiska gaser och ångor, i synnerhet, har sådana spektra.

Värmestrålningär en mekanism för att överföra värme mellan rumsligt åtskilda delar av kroppen på grund av elektromagnetisk strålning.

I början av 1900-talet ledde dock till förståelsen att det inte kunde vara tal om någon "fullständighet". Det blev tydligt att för att förklara dessa och många andra fenomen var det nödvändigt att radikalt revidera de begrepp som ligger till grund för fysikalisk vetenskap.

Till exempel, baserat på vågteorin om ljus, visade det sig vara omöjligt att ge en uttömmande förklaring av hela uppsättningen av optiska fenomen.

När man löste problemet med strålningens spektrala sammansättning, föreslog den tyske fysikern Max Planck 1900 att emission och absorption av ljus av materia sker i ändliga delar, eller kvanta. Samtidigt energin foton - kvant av elektromagnetisk strålning(i snäv mening - ljus) bestäms av uttrycket

Var är frekvensen av emitterat (eller absorberat) ljus, och är den universella konstanten, nu kallad Plancks konstant.

Dirac-konstanten används ofta

Då uttrycks kvantenergin som , där

Cirkulär frekvens av strålning.

Motsättningarna mellan att se ljus som en ström av laddade partiklar och som vågor ledde till konceptet våg-partikeldualitet.

Å ena sidan demonstrerar fotonen egenskaperna hos en elektromagnetisk våg i fenomenen diffraktion(vågor böjer sig runt hinder jämförbara med våglängden) och interferens(överlagring av vågor med samma frekvens och samma initialfas) på skalor jämförbara med fotonens våglängd. Till exempel skapar enkla fotoner som passerar genom en dubbel slits ett interferensmönster på skärmen som kan beskrivas Maxwells ekvationer. Experimentet visar dock att fotoner emitteras och absorberas helt och hållet av objekt vars dimensioner är mycket mindre än fotonvåglängden (till exempel atomer), eller i allmänhet, till någon approximation, kan anses vara punktliknande (till exempel en elektron). det vill säga de beter sig som partiklar - blodkroppar. I makrokosmos omkring oss finns det två grundläggande sätt att överföra energi och momentum mellan två punkter i rymden: den direkta rörelsen av materia från en punkt till en annan och vågprocessen att överföra energi utan att överföra materia. Alla energibärare här är strikt uppdelade i corpuscular och wave. Tvärtom, i mikrovärlden existerar inte en sådan uppdelning. Alla partiklar, och i synnerhet fotoner, tillskrivs både korpuskulära och vågegenskaper. Läget är oklart. Detta är en objektiv egenskap hos kvantmodeller.

Den nästan monokromatiska frekvensstrålningen som sänds ut av en ljuskälla kan ses som att den består av "strålningspaket" som vi kallar fotoner. Monokromatisk strålning – med en mycket liten frekvensspridning, helst en våglängd.

Utbredningen av fotoner i rymden beskrivs korrekt av de klassiska Maxwell-ekvationerna. I det här fallet anses varje foton vara klassisk i ett tåg vågor, definieras av två vektorfält - den elektrostatiska fältstyrkan och magnetfältsinduktionen. Ett vågtåg är en serie av störningar med pauser mellan dem. Strålningen från en enskild atom kan inte vara monokromatisk, eftersom strålningen varar en begränsad tidsperiod, med perioder av uppgång och fall.

Det är felaktigt att tolka summan av amplitudernas kvadrater som energitätheten i det utrymme där fotonen rör sig; istället bör varje storhet som beror kvadratiskt på vågamplituden tolkas som en kvantitet proportionell mot sannolikheten för någon process. Låt oss säga att det inte är lika med energin som fotonen bidrar med till denna region, utan är proportionell mot sannolikheten att detektera en foton i denna region.

Energin som överförs till vilken plats som helst i rymden av en foton är alltid lika med . Därigenom var är sannolikheten att hitta en foton i ett givet område, och är antalet fotoner.

1921 bekräftade Stern-Gerlach-experimentet närvaron av atomer tillbaka och faktumet av rumslig kvantisering av riktningen för deras magnetiska moment (från engelska spin - att rotera, snurra.). Snurra- elementarpartiklarnas inneboende rörelsemängd, som har en kvantnatur och inte är associerad med partikelns rörelse som helhet. När begreppet spin introducerades antogs det att elektronen kunde betraktas som en "roterande topp", och dess spin som ett kännetecken för sådan rotation. Spin är också namnet som ges till det inneboende vinkelmomentet för en atomkärna eller atom; i det här fallet definieras spinn som vektorsumman (beräknad enligt reglerna för att addera moment i kvantmekaniken) av spinnen av de elementarpartiklar som bildar systemet, och orbitalmomenten för dessa partiklar, på grund av deras rörelse inom systemet.

Spin mäts i enheter (reducerade Planck-konstanter eller Dirac-konstanter) och är lika med , där J- ett heltal (inklusive noll) eller ett halvheltal positivt tal som är karakteristiskt för varje typ av partikel - spin kvantnummer, som brukar kallas helt enkelt spin (ett av kvanttalen). I detta avseende talar de om ett helt eller halvt heltals spinn av en partikel. Begreppen spin och spin quantum number bör dock inte blandas ihop. Ett spinnkvanttal är ett kvanttal som bestämmer spinnvärdet för ett kvantsystem (atom, jon, atomkärna, molekyl), d.v.s. dess eget (inre) rörelsemängd. Projektionen av spinnet i valfri fast riktning z i rymden kan anta värdena J , J-1, ..., -J. Alltså en partikel med spin J kan vara med 2J+1 spinntillstånd (kl J= 1 / 2 - i två tillstånd), vilket motsvarar närvaron av en ytterligare intern frihetsgrad.

Nyckelelementet i kvantmekaniken är Heisenbergs osäkerhetsprincip, som säger att det är omöjligt att samtidigt exakt bestämma positionen för en partikel i rymden och dess rörelsemängd. Denna princip förklarar kvantiseringen av ljus, såväl som fotonenergins proportionella beroende av dess frekvens.

En fotons rörelse kan beskrivas av Maxwells ekvationssystem, medan rörelseekvationen för alla andra elementarpartiklar som en elektron beskrivs av Schrödinger-ekvationen, som är mer generell.

Maxwells ekvationssystem är invariant under Lorentz-transformationen. Lorentz förvandlingar i den speciella relativitetsteorin kallas transformationer som rum-tidskoordinater utsätts för (x,y,z,t) varje händelse under övergången från en tröghetsreferensram till en annan. I grund och botten är dessa transformationer transformationer inte bara i rymden, som Galileos transformationer, utan också i tiden.

Kapitel II . Grundläggande begrepp och principer för kvantberäkning

Även om datorer har blivit mindre och mycket snabbare på sin uppgift än tidigare, förblir själva uppgiften densamma: manipulera en sekvens av bitar och tolka den sekvensen som ett användbart beräkningsresultat. En bit är en grundläggande informationsenhet, vanligtvis representerad som en 0 eller 1 i din digitala dator. Varje klassisk bit realiseras fysiskt av ett makroskopiskt fysiskt system, såsom magnetiseringen på en hårddisk eller laddningen på en kondensator. Till exempel en text som består av n tecken, och lagrade på en typisk dators hårddisk, beskrivs av en sträng av 8n nollor och ettor. Det är här den grundläggande skillnaden mellan din klassiska dator och en kvantdator ligger. Medan en klassisk dator följer den klassiska fysikens välförstådda lagar, är en kvantdator en enhet som utnyttjar kvantmekaniska fenomen (särskilt kvantinterferens) för att implementera ett helt nytt sätt att behandla information.

I en kvantdator är den grundläggande informationsenheten (kallad en kvantbit eller qubit), är inte binär, utan snarare kvartär till sin natur. Denna egenskap hos qubit uppstår som en direkt konsekvens av dess underkastelse av kvantmekanikens lagar, som är radikalt olika från den klassiska fysikens lagar. En qubit kan existera inte bara i ett tillstånd som motsvarar logisk 0 eller 1, som en klassisk bit, utan också i tillstånd som motsvarar blandat eller superpositioner dessa klassiska tillstånd. Med andra ord kan en qubit existera som en nolla, som en etta och som både 0 och 1. I det här fallet kan du ange en viss numerisk koefficient som representerar sannolikheten att vara i varje tillstånd.

Idéer om möjligheten att bygga en kvantdator går tillbaka till R. Feynmans arbete 1982-1986. Med tanke på frågan om att beräkna utvecklingen av kvantsystem på en digital dator, upptäckte Feynman "olösbarheten" av detta problem: det visar sig att minnesresurserna och hastigheten hos klassiska maskiner är otillräckliga för att lösa kvantproblem. Till exempel ett system med n kvantpartiklar med två tillstånd (snurr 1/2 ) Det har 2 n grundläggande tillstånd; för att beskriva det är det nödvändigt att specificera (och skriva in i datorns minne) 2 n amplituder för dessa tillstånd. Baserat på detta negativa resultat föreslog Feynman att det är troligt att en "kvantdator" kommer att ha egenskaper som gör att den kan lösa kvantproblem.

"Klassiska" datorer är byggda på transistorkretsar som har olinjära samband mellan ingångs- och utgångsspänningar. De är i huvudsak bistabila element; till exempel, när ingångsspänningen är låg (logisk "0"), är inspänningen hög (logisk "1") och vice versa. I kvantvärlden kan en sådan bistabil transistorkrets jämföras med en två-nivå kvantpartikel: vi tilldelar logiska värden till tillståndet, tillståndet, - booleskt värde. Övergångar i en bistabil transistorkrets kommer här att motsvara övergångar från nivå till nivå: . Men ett kvantbistabilt element, kallat qubit, har en ny, jämfört med den klassiska, egenskapen för superposition av tillstånd: det kan vara i vilket superpositionstillstånd som helst, där är komplexa tal, . Tillstånd i ett kvantsystem från P tvånivåpartiklar har i allmänhet formen av en superposition 2 n grundförutsättning . I slutändan gör kvantprincipen för överlagring av stater det möjligt att ge en kvantdator fundamentalt nya "förmågor".

Det har bevisats att en kvantdator kan byggas av bara två element (gates): ett en-qubit-element och ett två-qubit-kontrollerat NOT-element (CNOT). Matris 2x2 element har formen:

(1)

Grinden beskriver rotationen av qubit-tillståndsvektorn från z-axeln till den polära axeln som anges av vinklarna . Om det är irrationella tal, kan tillståndsvektorn genom upprepad användning ges vilken som helst förutbestämd orientering. Detta är just "universaliteten" för en enkel-qubit-grind i formen (1). I ett särskilt fall får vi ett logiskt element med en qubit NOT (NOT): NOT=, NOT=. När man fysiskt implementerar ett element är det INTE nödvändigt att påverka en kvantpartikel (qubit) med en extern puls som överför kvantbiten från ett tillstånd till ett annat. Den kontrollerade NOT-grinden exekveras genom att påverka två interagerande qubits: i detta fall, genom interaktion, styr en qubit utvecklingen av den andra. Övergångar under påverkan av externa pulser är välkända inom pulsad magnetisk resonansspektroskopi. Ventilen motsvarar INTE en spin flip under påverkan av en impuls (rotation av magnetiseringen runt axeln med en vinkel) . CNOT-porten exekveras på två snurr 1/2 med Hamiltonian (snurrkontroller ). CNOT utförs i tre steg: impuls + fri precession över tid - impuls. Om (den styrande qubiten är i tillståndet), gör den kontrollerade qubiten under de specificerade influenserna övergångar (eller ). Om (den styrande qubiten är i tillståndet), kommer resultatet av utvecklingen av den kontrollerade qubiten att vara annorlunda: (). Således utvecklas spinn annorlunda kl : här är tillståndet för den styrande qubiten.

När man överväger frågan om att implementera en kvantdator på vissa kvantsystem, undersöks först och främst genomförbarheten och egenskaperna hos elementära NOT- och kontrollerade NOT-grindar.

För vad som följer är det också användbart att introducera en-qubit Hadamard-transformen:

I magnetisk resonansteknik utförs dessa ventiler av pulser:

Diagrammet för en kvantdator visas i figuren. Innan datorn börjar fungera måste alla qubits (kvantpartiklar) föras in i tillståndet, d.v.s. till grundtillståndet. Detta tillstånd i sig är inte trivialt.

Det kräver antingen djupkylning (till temperaturer i storleksordningen millikelvin) eller användning av polariseringsmetoder. systemet P qubits i ett tillstånd kan betraktas som ett minnesregister förberett för att registrera indata och utföra beräkningar. Utöver detta register antas vanligtvis att det finns ytterligare (hjälp)register som är nödvändiga för att registrera mellanliggande resultat av beräkningar. Data registreras genom att påverka varje qubit i datorn på ett eller annat sätt. Låt oss till exempel anta att en Hadamard-transformation utförs på varje qubit i registret:

Som ett resultat gick systemet i ett tillstånd av superposition från 2 sid bastillstånd med amplitud 2 - n /2 . Varje grundtillstånd är ett binärt tal från till . De horisontella linjerna i figuren anger tidsaxlarna.

Exekveringen av algoritmen åstadkommes genom en enhetlig superpositionstransformation. är en enhetlig dimensionsmatris 2 sid. När den är fysiskt implementerad genom pulsad påverkan på qubits utifrån, måste matrisen representeras som en vektorprodukt av matriser av dimension 2 och . Det senare kan utföras genom att sekventiellt påverka enstaka qubits eller par av qubits :

Antalet faktorer i denna expansion bestämmer varaktigheten (och komplexiteten) för beräkningarna. Allt i (3) utförs med hjälp av operationerna NOT, CNOT, H (eller deras variationer).

Det är anmärkningsvärt att den linjära enhetsoperatorn verkar samtidigt på alla villkor för superpositionen

Resultaten av beräkningen skrivs i reservregistret, som var i tillståndet före användning. I en körning av beräkningsprocessen får vi värdena för den önskade funktionen f för alla värden i argumentet X = 0,..., 2 p - 1 . Detta fenomen kallas kvantparallellism.

Att mäta resultatet av beräkningar reduceras till att projicera superpositionsvektorn i (4) på vektorn för ett av grundtillstånden :

(5)

Här dyker en av de svaga punkterna i en kvantdator upp: siffran "faller ut" under mätprocessen enligt slumpens lag. Att hitta för en given , det är nödvändigt att utföra beräkningar och mätningar många gånger tills det faller ut av misstag .

När man analyserar den enhetliga utvecklingen av ett kvantsystem som utför en beräkningsprocess, avslöjas vikten av fysiska processer såsom interferens. Enhetstransformationer äger rum i komplexa tals rymd, och tillägget av faserna för dessa tal har karaktären av interferens. Produktiviteten hos Fourier-transformationer i fenomenen interferens och spektroskopi är känd. Det visade sig att kvantalgoritmer alltid innehåller Fourier-transformer. Hadamard-transformen är den enklaste diskreta Fourier-transformen. Gates av NOT- och CNOT-typerna kan implementeras direkt på Mach-Zehnder-interferometern med hjälp av fenomenet fotoninterferens och rotation av dess polarisationsvektor.

Olika sätt att fysiskt implementera kvantdatorer undersöks. Modellexperiment på kvantberäkning utfördes på en pulsad kärnmagnetisk resonansspektrometer. I dessa modeller fungerade två eller tre snurr (qubits), till exempel två snurr av 13 C-kärnor och ett snurr av en proton i en trikloretylenmolekyl

Men i dessa experiment var kvantdatorn "ensemble": datorns utsignaler är sammansatta av ett stort antal molekyler i en flytande lösning (~ 10 20).

Hittills har förslag lagts fram för att implementera kvantdatorer på joner och molekyler i fällor i vakuum, på kärnsnurr i vätskor (se ovan), på kärnsnurr av 31 P-atomer i kristallint kisel, på elektronspin i kvant. prickar skapade i tvådimensionell elektronisk gas i GaAs-heterostrukturer, vid Josephson-korsningar. Som vi ser kan en kvantdator i princip byggas på atomära partiklar i vakuum, vätska eller kristaller. I varje fall måste vissa hinder övervinnas, men bland dem finns det flera vanliga, som bestäms av principerna för drift av qubits i en kvantdator. Låt oss sätta uppgiften att skapa en fullskalig kvantdator som innehåller, säg, 10 3 qubits (om än vid n = 100 en kvantdator kan vara ett användbart verktyg).

1. Vi måste hitta sätt att "initiera" datorns qubits till tillståndet. För spinnsystem i kristaller är användningen av ultralåga temperaturer och ultrastarka magnetfält uppenbar. Användningen av spinnpolarisering genom pumpning kan vara användbar när kylning och höga magnetiska fält appliceras samtidigt.

För joner i vakuumfällor uppnås ultralåg kylning av joner (atomer) med lasermetoder. Behovet av kallt och ultrahögt vakuum är också uppenbart.

2. Det är nödvändigt att ha en teknologi för selektiv påverkan av pulser på valfri vald qubit. Inom området radiofrekvenser och spinresonans innebär detta att varje snurr måste ha sin egen resonansfrekvens (när det gäller spektroskopisk upplösning). Skillnader i resonansfrekvenser för spinn i molekyler beror på kemiska förskjutningar för spinnen av en isotop och ett element; de nödvändiga frekvensskillnaderna finns för spinn av kärnor av olika element. Men sunt förnuft dikterar att dessa naturligt förekommande skillnader i resonansfrekvenser sannolikt inte är tillräckliga för att fungera med 10 3 snurrar

Mer lovande tillvägagångssätt verkar vara de där resonansfrekvensen för varje qubit kan styras externt. I förslaget till en kvantdator av kisel är qubit kärnspinnet för en föroreningsatom 31 R. Resonansfrekvensen bestäms av konstanten A hyperfin växelverkan mellan kärn- och elektronspin i 31 R-atomen. Det elektriska fältet på nanoelektroden som ligger ovanför 31 R-atomen polariserar atomen och ändrar konstanten. A(resonansfrekvensen för kärnspinnet). Således bäddar närvaron av en elektrod in en qubit i en elektronisk krets och ställer in dess resonansfrekvens.

3. För att utföra CNOT-operationen (kontrollerad INTE) krävs interaktion mellan qubits och formen . Sådan växelverkan sker mellan spinn av kärnor i en molekyl om kärnorna är separerade av en kemisk bindning. I princip är det nödvändigt att kunna utföra operationen på vilket par av qubits som helst . Det är knappast möjligt att ha fysisk interaktion av qubits av samma storleksskala och enligt "allt med allt"-principen i den naturliga miljön. Det finns ett uppenbart behov av ett sätt att trimma miljön mellan qubits utifrån genom att introducera elektroder med en kontrollerad potential. På detta sätt är det möjligt att till exempel skapa en överlappning av vågfunktionerna hos elektroner i angränsande kvantprickar och uppkomsten av en interaktion av formen mellan elektronspin [. Överlappningen av vågfunktionerna för elektronerna i angränsande 31 P-atomer orsakar uppkomsten av en interaktion av typen mellan kärnspinn.

För att tillhandahålla operationen , där och är avlägsna qubits mellan vilka det inte finns någon interaktion av formen, är det nödvändigt att i datorn tillämpa operationen för att utbyta tillstånd längs en kedja så att operationen säkerställs eftersom tillståndet sammanfaller med tillståndet.

4. Under exekveringen av en enhetlig transformation som motsvarar den valda algoritmen, utsätts datorns qubits för påverkan från omgivningen; som ett resultat upplever amplituden och fasen av qubit-tillståndsvektorn slumpmässiga förändringar - dekoherens. I huvudsak är dekoherens avslappningen av de frihetsgrader för partikeln som används i qubiten. Dekoherenstiden är lika med avslappningstiden. Vid kärnmagnetisk resonans i vätskor är relaxationstiderna 1-10 s. För joner i fällor med optiska övergångar mellan nivåer E 0 Och E 1 Dekoherenstiden är tiden för spontan emission och tidpunkten för kollisioner med kvarvarande atomer. Det är uppenbart att dekoherens är ett allvarligt hinder för kvantberäkning: den påbörjade beräkningsprocessen får egenskaperna av slumpmässighet efter att dekoherenstiden har förflutit. Det är dock möjligt att uppnå en stabil kvantberäkningsprocess under en godtyckligt lång tid m > ma om kvantkodning och felkorrigeringsmetoder (fas och amplitud) används systematiskt. Det har bevisats att med relativt låga krav för felfri exekvering av elementära operationer som NOT och CNOT (felsannolikhet inte mer än 10 -5), säkerställer kvantfelskorrigering (QEC) metoder stabil drift av en kvantdator.

Det är också möjligt att aktivt undertrycka dekoherensprocessen om periodiska mätningar utförs på systemet av qubits. Mätningen kommer med största sannolikhet att hitta partikeln i "korrekt" tillstånd, och små slumpmässiga förändringar i tillståndsvektorn kommer att kollapsa under mätningen (quantum Zeno-effekt). Det är dock svårt att säga ännu hur användbar en sådan teknik kan vara, eftersom sådana mätningar i sig kan påverka beräkningsprocessen och störa den.

5. Tillstånden för qubitarna efter slutförandet av beräkningsprocessen måste mätas för att bestämma resultatet av beräkningen. Idag finns det ingen behärskad teknik för sådana mätningar. Vägen till att söka efter en sådan teknik är dock uppenbar: det är nödvändigt att använda amplifieringsmetoder vid kvantmätning. Till exempel överförs kärnspinntillståndet till elektronspinnet; orbitalvågsfunktionen beror på den senare; genom att känna till orbitalvågsfunktionen är det möjligt att organisera laddningsöverföring (jonisering); närvaron eller frånvaron av laddning på en enda elektron kan detekteras med klassiska elektrometriska metoder. Sondkraftsmikroskopimetoder kommer sannolikt att spela en stor roll i dessa mätningar.

Hittills har kvantalgoritmer upptäckts som leder till exponentiell acceleration av beräkningar jämfört med beräkningar på en klassisk dator. Dessa inkluderar Shors algoritm för att bestämma primtalsfaktorer för stora (flersiffriga) tal. Detta rent matematiska problem är nära relaterat till samhällets liv, eftersom moderna krypteringskoder bygger på "icke-beräknebarheten" hos sådana faktorer. Det var denna omständighet som orsakade en sensation när Shors algoritm upptäcktes. Det är viktigt för fysiker att lösningen av kvantproblem (att lösa Schrödinger-ekvationen för många-partikelsystem) accelereras exponentiellt om en kvantdator används.

Slutligen är det mycket viktigt att under forskningen om kvantberäkningsproblem utsätts kvantfysikens huvudproblem för ny analys och experimentell verifiering: problem med lokalitet, verklighet, komplementaritet, dolda parametrar, vågfunktionskollaps.

Idéerna om kvantberäkning och kvantkommunikation uppstod hundra år efter födelsen av kvantfysikens ursprungliga idéer. Möjligheten att bygga kvantdatorer och kommunikationssystem har visats genom teoretiska och experimentella studier som hittills genomförts. Kvantfysiken är "tillräcklig" för design av kvantdatorer baserade på olika "elementbaser". Kvantdatorer, om de kan byggas, kommer att vara 2000-talets teknik. Deras tillverkning kommer att kräva skapandet och utvecklingen av ny teknik på nanometer- och atomnivå. Detta arbete kan sannolikt ta flera decennier. Konstruktionen av kvantdatorer skulle vara ytterligare en bekräftelse på principen om naturens outtömlighet: naturen har medel att utföra vilken uppgift som helst korrekt formulerad av människan.

I en konventionell dator kodas information som en sekvens av bitar, och dessa bitar bearbetas sekventiellt av booleska logiska grindar för att producera det önskade resultatet. På liknande sätt bearbetar en kvantdator qubits genom att utföra en sekvens av operationer på kvantlogiska grindar, som var och en representerar en enhetlig transformation som verkar på en enda qubit eller ett par qubits. Genom att sekventiellt utföra dessa transformationer kan en kvantdator utföra en komplex enhetlig transformation över hela uppsättningen av qubits som förbereds i något initialt tillstånd. Efter detta kan du göra mätningar på qubits, vilket kommer att ge det slutliga resultatet av beräkningarna. Dessa likheter i beräkningen mellan en kvantdator och en klassisk dator tyder på att, åtminstone i teorin, en klassisk dator kan exakt replikera driften av en kvantdator. Med andra ord kan en klassisk dator göra allt en kvantdator kan göra. Varför då allt detta krångel med en kvantdator? Poängen är att, även om en klassisk dator teoretiskt sett kan simulera en kvantdator, är den väldigt ineffektiv, så ineffektiv att praktiskt taget en klassisk dator inte kan lösa många problem som en kvantdator kan göra. Att simulera en kvantdator på en klassisk dator är ett beräkningsmässigt svårt problem eftersom korrelationerna mellan kvantbitar är kvalitativt olika från korrelationerna mellan klassiska bitar, som först visades av John Bell. Till exempel kan vi ta ett system med bara några hundra qubits. Den finns i Hilberts rymd med dimension ~10 90 , vilket skulle kräva, vid modellering med en klassisk dator, användning av exponentiellt stora matriser (för att utföra beräkningar för varje enskilt tillstånd som också beskrivs av matrisen). Detta innebär att en klassisk dator kommer att ta exponentiellt mer tid jämfört med även en primitiv kvantdator.

Richard Feynman var bland de första som insåg potentialen med kvantsuperposition för att lösa sådana problem mycket snabbare. Till exempel är ett system med 500 qubits, vilket är nästan omöjligt att modellera klassiskt, en kvantöverlagring av 2 500 stater. Varje värde på en sådan överlagring motsvarar klassiskt en lista med 500 ettor och nollor. Varje kvantoperation på ett sådant system, till exempel en avstämd puls av radiovågor som kan utföra en kontrollerad NOT-operation på till exempel den 100:e och 101:e qubiten, kommer samtidigt att påverka 2 500 stater. Således, i en tick på datorklockan, beräknar kvantoperationen inte ett maskintillstånd, som konventionella datorer, utan 2 500 konstaterar omedelbart! Men så småningom görs en mätning på systemet av kvantbitar, och systemet kollapsar till ett enda kvanttillstånd som motsvarar en enda lösning på problemet, en enda uppsättning av 500 ettor och nollor, som dikteras av kvantmekanikens mätaxiom. Detta är ett verkligt spännande resultat, eftersom denna lösning, hittad av en kollektiv process av kvantparallellberäkning med dess ursprung i superposition, motsvarar att utföra samma operation på en klassisk superdator med ~ 10 150 separata processorer (vilket naturligtvis är omöjligt)!! De första forskarna inom detta område inspirerades förstås av sådana gigantiska möjligheter, och därför började jakten på lämpliga problem för sådan datorkraft snart. Peter Shor, en forskare och datavetare vid AT&T's Bell Laboratories i New Jersey, föreslog ett problem som skulle kunna lösas på en kvantdator och med hjälp av en kvantalgoritm använder sig av kraften i kvantsuperposition för att faktorisera stora tal (i storleksordningen av. ~10 200 bitar eller mer) i faktorer på några sekunder. som enkelt löser detta problem, är naturligtvis av stort intresse för de många statliga organisationer som använder RSA, som hittills ansetts vara "unhackable", och för alla som är intresserade av säkerheten för deras data.

Kryptering är dock bara en möjlig tillämpning av en kvantdator. Shor har utvecklat en hel uppsättning matematiska operationer som uteslutande kan utföras på en kvantdator. Några av dessa operationer används i hans faktoriseringsalgoritm. Vidare hävdade Feynman att en kvantdator skulle kunna fungera som en simuleringsenhet för kvantfysik, vilket potentiellt öppnar dörren för många upptäckter inom området. För närvarande är kraften och kapaciteten hos en kvantdator huvudsakligen en fråga om teoretisk spekulation; tillkomsten av den första verkligt funktionella kvantdatorn kommer utan tvekan att ge många nya och spännande praktiska tillämpningar.

Kapitel III . Grovers algoritm

Sökproblemet är som följer: det finns en oordnad databas som består av N-element, varav endast ett uppfyller de givna villkoren - det är detta element som måste hittas. Om ett element kan inspekteras är det en enstegsprocess att avgöra om det uppfyller kraven eller inte. Databasen är dock sådan att det inte finns någon beställning på plats för att hjälpa till att välja ett objekt. Den mest effektiva klassiska algoritmen för denna uppgift är att kontrollera objekten från databasen en efter en. Om elementet uppfyller villkoren är sökningen över. Om inte, läggs elementet åt sidan så att det inte kontrolleras igen. Uppenbarligen kräver denna algoritm att ett medelvärde av element kontrolleras innan den önskade hittas.

När du implementerar denna algoritm kan du använda samma utrustning som i det klassiska fallet, men specificera ingången och utdata i formuläret superpositioner stater kan du hitta ett objekt för O () kvantmekaniska steg istället för HANDLA OM( N )) klassiska steg. Varje kvantmekaniskt steg består av en elementär enhetlig operation, som vi kommer att överväga nedan.

För att implementera denna algoritm behöver vi följande tre elementära operationer. Den första är förberedelsen av ett tillstånd där systemet är med lika sannolikhet i något av dess N grundtillstånd; den andra är Hadamard-transformen och den tredje är den selektiva fasrotationen av tillstånd.

Som bekant är huvudoperationen för kvantberäkning operationen M, som verkar per bit, vilket representeras av följande matris:

det vill säga en bit i tillstånd 0 förvandlas till en överlagring av två tillstånd: (1/, 1/). På liknande sätt omvandlas en bit i tillstånd 1 till (1/, -1/,), d.v.s. amplitudvärdet för varje tillstånd är 1/, men fasen i tillstånd 1 är omvänd. Fasen har ingen analog i klassiska probabilistiska algoritmer. Det uppstår inom kvantmekaniken, där sannolikhetsamplituden är komplex. I ett system där tillståndet beskrivs P bitar (dvs det finns N = 2 p möjliga tillstånd) kan vi utföra omvandlingen M på varje bit oberoende, sekventiellt ändra systemets tillstånd. I fallet där den ursprungliga konfigurationen var en konfiguration med P bitar i det första tillståndet kommer den resulterande konfigurationen att ha lika amplituder för varje tillstånd. Detta är sättet att skapa en superposition med samma amplitud för alla tillstånd.

Den tredje transformationen vi behöver är att selektivt rotera amplitudfasen i vissa tillstånd. Transformationen som presenteras här för ett tvåtillståndssystem är av formen:

Var j = Och - godtyckliga reella tal. Observera att, till skillnad från Hadamard-transformationen och andra tillståndstransformationsmatriser, förblir sannolikheten för varje tillstånd densamma, eftersom kvadraten på den absoluta storleken på amplituden i varje tillstånd förblir densamma.

Låt oss betrakta problemet i abstrakt form.

Låt systemet ha det N = 2 p stater, som betecknas som ,..., . Dessa 2 sid tillstånd representeras som n-bitars strängar. Låt det finnas ett enda tillstånd, säg , som uppfyller villkoret C() = 1, medan för alla andra tillstånd S, MED( ,) = 0 (det antas att för vilket tillstånd S som helst tillståndet utvärderas per tidsenhet). Uppgiften är att erkänna staten

Låt oss gå vidare till själva algoritmen

Steg (1) och (2) är en sekvens av elementära enhetsoperationer som beskrivits tidigare. Steg (3) är den slutliga mätningen som utförs av det externa systemet.

(1) Vi för systemet i ett tillstånd av superposition:

med identiska amplituder för vart och ett av de N tillstånden. Denna överlagring kan erhållas i steg.

(2) Låt oss upprepa följande enhetsoperation HANDLA OM( ) en gång:

a. Låt systemet vara i något tillstånd S:

När MED( S ) = 1, rotera fasen med radian;

När С(S) = 0, lämna systemet oförändrat.

b . Tillämpa diffusionstransformation D som bestäms av matrisen D enligt följande: om ;" och . D kan implementeras som sekventiell exekvering av enhetliga transformationer: , där W– Hadamard transformationsmatris, R – fasrotationsmatris.

(3) Mät det resulterande tillståndet. Denna stat kommer att vara staten MED( )„ (dvs det önskade tillståndet som uppfyller villkoret (C() = 1) med en sannolikhet på åtminstone inte mindre än 0,5. Observera att steg (2a) är en fasrotation. Dess implementering måste inkludera ett igenkänningsprocedurtillstånd och den efterföljande bestämning av huruvida fasrotationen ska utföras eller inte Den måste utföras på ett sådant sätt att det inte lämnar ett spår på systemets tillstånd, så att det finns förtroende för att vägarna som leder till samma slutliga tillstånd inte kan särskiljas. och kan störa Inte inkluderar klassiska mått.

Denna kvantsökningsalgoritm kommer sannolikt att vara enklare att implementera jämfört med många andra kända kvantmekaniska algoritmer, eftersom de nödvändiga operationerna endast är Walsh-Hadamard-transformen och den villkorade fasförskjutningsoperationen, som var och en är relativt enkel jämfört med de operationer som används av de andra kvantmekaniska algoritmerna.

Slutsats

För närvarande är kvantdatorer och kvantinformationsteknologier fortfarande i banbrytande utveckling. Att lösa de svårigheter som dessa teknologier för närvarande står inför kommer att säkerställa att kvantdatorer kommer att avancera till sin rättmätiga plats som de snabbaste datorerna som är fysiskt möjliga. Vid det här laget har felkorrigeringen avancerat avsevärt, vilket för oss närmare den punkt där vi kan bygga datorer som är tillräckligt robusta för att motstå effekterna av dekoherens. Å andra sidan är skapandet av kvantutrustning fortfarande bara en framväxande industri; men det arbete som gjorts hittills övertygar oss om att det bara är en tidsfråga innan vi kan bygga maskiner som är tillräckligt stora för att köra seriösa algoritmer som Shors algoritm. Kvantdatorer kommer alltså definitivt att dyka upp. Åtminstone kommer dessa att vara de mest avancerade datorenheterna, och de datorer vi har idag kommer att bli föråldrade. Quantum computing har sitt ursprung i mycket specifika områden av teoretisk fysik, men dess framtid kommer utan tvekan att ha en enorm inverkan på hela mänsklighetens liv.

Bibliografi

1. Quantum computing: för- och nackdelar. Ed. V.A. Sadovnichigo. – Izhevsk: Udmurt University Publishing House, 1999. – 212 s.

2. Belonuchkin V.E., Zaikin D.A., Tsypenyuk Yu.M., Fundamentals of Physics. Allmän fysikkurs: Lärobok. I 2 vol. T. 2. Kvant- och statistisk fysik. – M.: FIZMATLIT, 2001. – 504 sid.

3. Valiev K.A. "Kvantdatorer: kan de göras "stora"?", Advances in Physical Sciences, vol. 169, nr 6, 1999.

4. Valiev K.A. "Kvantinformationsvetenskap: datorer, kommunikation och kryptografi", BULLETIN OF THE RUSSIAN ACADEMY OF SCIENCES, volym 70, nr 8, sid. 688-695, 2000

5. Maslov. D. "Quantum computing and communication: reality and prospects", Computerra, nr 46, 2004.

6. Khalfin L.A. "Quantum Zeno effect", Advances in Physical Sciences, v. 160, nr 10, 1990.

7. Kholevo A. "Kvantinformationsvetenskap: dåtid, nutid, framtid,"

IN THE WORLD OF SCIENCE, nr 7, 2008.

8. Center for Quantum Technologies, National University of Singapore www.quantumlah.org

Historisk referens

Kvantberäkning är otänkbar utan kontroll över kvanttillståndet hos enskilda elementarpartiklar. Två fysiker – fransmannen Serge Lroche och amerikanen David Wineland – lyckades. Lrosh fångade enstaka fotoner i resonatorn och "hakade av" dem från omvärlden under lång tid. Wineland fångade enskilda joner med specifika kvanttillstånd och isolerade dem från yttre påverkan. Harosh använde atomer för att observera fotonens tillstånd. Wineland använde fotoner för att ändra jonernas tillstånd. De lyckades göra framsteg i att studera förhållandet mellan kvantvärlden och den klassiska världen. De tilldelades 2012 Nobelpriset i fysik för "banebrytande experimentella tekniker som gjorde det möjligt att mäta och kontrollera individuella kvantsystem."

Funktionen av kvantdatorer är baserad på egenskaperna hos en kvantbit av information. Om datorprocesser använder P qubits, då har Hilbert-tillståndsrummet i ett kvantsystem en dimension lika med 2". Under Hilbert utrymme vi kommer att förstå ett dimensionellt vektorrum där den skalära produkten definieras under förutsättning att värdet tenderar att P till oändligheten.

I vårt fall betyder detta att det finns 2" bastillstånd, och datorn kan arbeta på en överlagring av dessa 2" bastillstånd.

Observera att en påverkan på valfri qubit omedelbart leder till en samtidig förändring av alla 2” bastillstånd. Denna egenskap kallas "kvantparallellism».

Kvantberäkning är en enhetlig transformation. Detta innebär att en linjär transformation utförs med komplexa koefficienter, vilket håller summan av kvadraterna av de transformerade variablerna oförändrad. En enhetlig transformation är en ortogonal transformation där koefficienterna bildar en enhetlig matris.

Under enhetlig matris vi kommer att förstå den kvadratiska matrisen ||aj|, vars produkt av den komplexa konjugatet och transponerade matrisen || aJI ger identitetsmatrisen. Tal ajk Och en ki komplex. Om siffrorna ett ikär reella tal, kommer den enhetliga matrisen att vara ortogonal. Ett visst antal qubits bildar en dators kvantregister. I en sådan kedja av kvantbitar kan en- och tvåbitars logiska operationer utföras på samma sätt som operationerna NOT, NAND, 2 OR-HE, etc. utförs i ett klassiskt register. (Fig. 5.49).

Specifikt nummer N register bildar i huvudsak en kvantdator. Driften av en kvantdator sker i enlighet med utvecklade beräkningsalgoritmer.

Ris. 5,49.

NOT - boolesk INTE; CNOT - kontrolleras INTE

Qubits som informationsbärare har ett antal intressanta egenskaper som helt skiljer dem från klassiska bitar. En av de viktigaste teserna inom kvantinformationsteorin är statens förveckling. Anta att det finns två två-nivå qubits A Och I, realiseras i form av en atom med ett elektroniskt eller nukleärt spinn, en molekyl med två kärnspinn. På grund av samverkan mellan två delsystem A Och I en icke-lokal korrelation uppstår som är rent kvantmässigt till sin natur. Denna korrelation kan beskrivas av densitetsmatrisen med blandat tillstånd

Var p i- befolkning eller sannolikhet jag- stat, alltså R ( + p 2 + p 3 + + Ra = 1-

Egenskapen hos koherenta kvanttillstånd att ha en summa av sannolikheter som är lika med en kallas förtrassling, eller koppling, av tillstånd. Intrasslade, eller intrasslade, kvantobjekt är kopplade till varandra oavsett hur långt de är placerade från varandra. Om tillståndet för ett av de länkade objekten mäts, erhålls information om tillståndet för andra objekt omedelbart.

Om två kvantbitar är sammankopplade saknar de individuella kvanttillstånd. De är beroende av varandra på ett sådant sätt att mätningen för en typ ger "O", och för den andra - "1" och vice versa (Fig. 5.50). I detta fall sägs det maximalt länkade paret bära en e-bit sammanhållning.

Entangled states är en resurs i kvantberäkningsenheter, och metoder för att tillförlitligt generera intrasslade qubits måste utvecklas för att fylla på antalet intrasslade tillstånd. En av metoderna

Ris. 5,50. Det maximalt intrasslade paret av qubits-schemat är ett algoritmiskt sätt att erhålla intrasslade qubits på joner i fällor, kärnspinn eller ett par fotoner. Processen att sönderfalla en partikel i ett singletttillstånd till två partiklar kan vara mycket effektiv. I det här fallet genereras partikelpar som är intrasslade i koordinater, momentum eller spinn.

Att utveckla en heltäckande teori om intrassling är ett nyckelmål för kvantinformationsteorin. Med dess hjälp kommer det att vara möjligt att komma närmare att lösa problemen med teleportering, ultratät kodning, kryptografi och datakomprimering. För detta ändamål utvecklas kvantalgoritmer, inklusive kvantfouriertransformer.

Beräkningsschemat på en kvantdator har följande algoritm: ett system av qubits bildas, på vilket det initiala tillståndet registreras. Genom enhetliga transformationer förändras systemets och dess delsystems tillstånd när logiska operationer utförs. Processen avslutas med mätning av nya qubit-värden. Rollen för att ansluta ledare för en klassisk dator spelas av qubits, och de logiska blocken i en klassisk dator spelas av enhetliga transformationer. Detta koncept med en kvantprocessor och kvantlogiska grindar formulerades 1989 av David Deutsch. Han föreslog sedan ett universellt logikblock som kunde användas för att utföra vilken kvantberäkning som helst.

Doina-Jozhi algoritm låter dig bestämma "i en beräkning" om en funktion av en binär variabel /(/?) är konstant (f x (ri)= Åh, f 2 (ri) = 1 oavsett P) eller "balanserad" (f 3 ( 0) = 0,/ 3 (1) = 1;/ 4 (0) = 1, / 4 (1) = 0).

Det visade sig att för att konstruera någon beräkning räcker det med två grundläggande operationer. Kvantsystemet ger ett resultat som är korrekt endast med viss sannolikhet. Men genom att öka operationerna i algoritmen något kan du föra sannolikheten att få det korrekta resultatet så nära ett som möjligt. Med hjälp av grundläggande kvantoperationer är det möjligt att simulera driften av vanliga logiska grindar som utgör vanliga datorer.

Grovers algoritm gör att vi kan hitta en lösning på ekvationen f(x) = 1 för 0 x i O(VN) tid och är avsedd för databassökning. Grovers kvantalgoritm är uppenbarligen mer effektiv än någon algoritm för oordnad sökning på en klassisk dator.

Shors faktoriseringsalgoritm låter dig bestämma för primtalsfaktorer aub givet heltal M= a"Xb genom att använda en lämplig kvantkrets. Denna algoritm låter dig hitta faktorerna för ett A-siffrigt heltal. Den kan användas för att uppskatta beräkningsprocesstiden. Samtidigt kan Shors algoritm tolkas som ett exempel på en procedur för att bestämma energinivåerna i ett kvantberäkningssystem.

Zalka-Wiesner algoritm låter dig simulera den enhetliga utvecklingen av ett kvantsystem P partiklar i nästan linjär tid med användning På) qubits.

Simons algoritm löser black box-problemet exponentiellt snabbare än någon klassisk algoritm, inklusive probabilistiska algoritmer.

Felkorrigeringsalgoritm gör det möjligt att öka brusimmuniteten hos ett kvantberäkningssystem som är känsligt för förstörelse av ömtåliga kvanttillstånd. Kärnan i denna algoritm är att den inte kräver kloning av qubits och bestämning av deras tillstånd. En kvantlogisk krets bildas som är kapabel att detektera ett fel i vilken kvantbit som helst utan att faktiskt läsa det individuella tillståndet. Till exempel detekterar tripletten 010 som passerar genom en sådan anordning en felaktig mittbit. Enheten vänder på den utan att bestämma de specifika värdena för någon av de tre bitarna. Så, baserat på informationsteori och kvantmekanik, uppstod en av de grundläggande algoritmerna - kvantfelskorrigering.

De angivna problemen är viktiga för att skapa en kvantdator, men de faller inom kvantprogrammerares kompetens.

En kvantdator är mer progressiv än en klassisk i ett antal indikatorer. De flesta moderna datorer fungerar enligt von Neumann- eller Harvard-schemat: P minnesbitar lagrar tillstånd och ändras av processorn varje gång tick. I en kvantdator, ett system av P qubits är i ett tillstånd som är en överlagring av alla bastillstånd, så en förändring i systemet påverkar alla 2" grundläggande tillstånd samtidigt. Teoretiskt kan det nya schemat fungera exponentiellt snabbare än det klassiska. En nästan kvantdatabassökningsalgoritm visar en kvadratisk ökning av effekt jämfört med klassiska algoritmer.

Innehållet i begreppet "kvantparallellism" kan avslöjas på följande sätt: "Datan i beräkningsprocessen representerar kvantinformation, som i slutet av processen omvandlas till klassisk information genom att mäta sluttillståndet i kvantregistret. Vinsten i kvantalgoritmer uppnås på grund av det faktum att när man tillämpar en kvantoperation, transformeras ett stort antal superpositionskoefficienter för kvanttillstånd, som innehåller klassisk information i virtuell form, samtidigt."

Kvantintrassling, även kallad "kvantsuperposition", betyder vanligtvis följande: "Föreställ dig en atom som kan genomgå radioaktivt sönderfall under en viss tidsperiod. Eller så kan vi inte förvänta oss att denna atom bara har två möjliga tillstånd: "förfall ” och ”inte sönderfall”, /.../ men i kvantmekaniken kan en atom ha något slags enhetligt tillstånd – ”förfall – inte sönderfall”, det vill säga varken det ena eller det andra, utan så att säga mellan detta tillstånd kallas "superposition".

De grundläggande egenskaperna hos kvantdatorer i teorin tillåter dem att övervinna några av de begränsningar som möter i driften av klassiska datorer.

Teori

Qubits

Idén med quantum computing, först uttryckt av Yu I. Manin och R. Feynman, är att ett kvantsystem av L två-nivå kvantelement (qubits) har 2 L linjärt oberoende stater, och därför, på grund av principen om kvantöverlagring, 2 L-dimensionellt Hilbert tillståndsrum. En operation i kvantberäkning motsvarar en rotation i detta utrymme. Alltså en kvantberäkningsenhet av storlek L en qubit kan exekvera 2 parallellt L operationer.

Låt oss anta att det finns en qubit. I det här fallet, efter mätning, i den så kallade klassiska formen, blir resultatet 0 eller 1. I verkligheten är en qubit ett kvantobjekt och därför kan den, på grund av osäkerhetsprincipen, vara både 0 och 1 med en viss sannolikhet. Om en qubit är 0 (eller 1) med hundra procent sannolikhet, betecknas dess tillstånd med symbolen |0> (eller |1>) - i Dirac-notation. |0> och |1> är grundtillstånden. I det allmänna fallet är kvanttillståndet för en qubit mellan basen och skrivs på formen , där | a|² och | b|² - sannolikheter för att mäta 0 respektive 1; ; | a|² + | b|² = 1. Dessutom, omedelbart efter mätningen, går qubiten in i det grundläggande kvanttillståndet, liknande det klassiska resultatet.

Det finns en qubit i ett kvanttillstånd I det här fallet, sannolikheten att få vid mätning. I det här fallet, vid mätning, fick vi 0 med en sannolikhet på 64 %. Sedan hoppar qubiten till ett nytt kvanttillstånd 1*|0>+0*|1>=|0>, det vill säga nästa gång vi mäter denna qubit får vi 0 med hundra procents sannolikhet. Detta beror på det faktum att Dirac-tillståndsvektorn inte är beroende av tid, det vill säga den bryts upp i en summa av vektorer av bastillstånd med tidsoberoende koefficienter.

För att förklara, låt oss ge två exempel från kvantmekaniken: 1) fotonen är i ett tillstånd av överlagring av två polarisationer; mätningen en gång för alla kollapsar fotonens tillstånd till ett med en viss polarisation; 2) en radioaktiv atom har en viss halveringstid; en mätning kan avslöja att den ännu inte har förfallit, men det betyder inte att den aldrig kommer att förfalla.

Låt oss gå vidare till ett system med två qubits. Att mäta var och en av dem kan ge 0 eller 1. Därför har systemet 4 klassiska tillstånd: 00, 01, 10 och 11. De grundläggande kvanttillstånden liknar dem: |00>, |01>, |10> och |11 >. Och slutligen har systemets allmänna kvanttillstånd formen . Nu | a|² - sannolikhet att mäta 00, etc. Observera att | a|²+| b|²+| c|²+| d|²=1 som total sannolikhet.

I allmänhet system från L den har 2 qubits L klassiska tillstånd (00000...(L-nollor),...00001(L-siffror),..., 11111...(L-enheter)), som var och en kan mätas med sannolikheter på 0-100 %.

Således påverkar en operation på en grupp av qubits alla värden som den kan ta, till skillnad från en klassisk bit. Detta säkerställer en aldrig tidigare skådad parallellitet mellan beräkningar.

Beräkning

Ett förenklat beräkningsschema på en kvantdator ser ut så här: ett system med qubits tas, på vilket det initiala tillståndet registreras. Systemets eller dess delsystems tillstånd ändras sedan genom grundläggande kvantoperationer. I slutet mäts värdet och detta är resultatet av datorn.

Det visar sig att för att konstruera någon beräkning räcker det med två grundläggande operationer. Kvantsystemet ger ett resultat som är korrekt endast med viss sannolikhet. Men genom att öka operationerna i algoritmen något kan du föra sannolikheten att få det korrekta resultatet så nära ett som möjligt.

Med hjälp av grundläggande kvantoperationer är det möjligt att simulera driften av vanliga logiska grindar som utgör vanliga datorer. Därför kommer alla problem som är lösta nu att lösas av en kvantdator, och det på nästan samma tid. Följaktligen kommer det nya beräkningssystemet inte att vara svagare än det nuvarande.

Varför är en kvantdator bättre än en klassisk? De flesta moderna datorer fungerar enligt samma schema: n bitar av minneslagringstillstånd och ändras av processorn varje tidscykel. I kvantfallet är ett system med n kvantbitar i ett tillstånd som är en överlagring av alla bastillstånd, så en förändring i systemet gäller alla 2 n grundläggande tillstånd samtidigt. Teoretiskt kan det nya schemat fungera mycket (exponentiellt många gånger) snabbare än det klassiska. I praktiken visar Grovers (kvant) databassökningsalgoritm en kvadratisk ökning av effekt jämfört med klassiska algoritmer. Än så länge finns de inte i naturen.

Algoritmer

Det visades att "kvantacceleration" inte är möjlig för alla algoritmer.

Kvantteleportering

Teleporteringsalgoritmen implementerar den exakta överföringen av tillståndet för en qubit (eller system) till en annan. Det enklaste schemat använder 4 qubits: en källa, en mottagare och två extra. Observera att som ett resultat av algoritmen kommer det initiala tillståndet för källan att förstöras - detta är ett exempel på åtgärden av den allmänna principen om omöjlighet för kloning- det är omöjligt att skapa en exakt kopia av ett kvanttillstånd utan att förstöra originalet. Det är faktiskt ganska lätt att skapa identiska tillstånd på qubits. Till exempel, efter att ha mätt 3 qubits, kommer vi att överföra var och en av dem till grundtillstånden (0 eller 1) och på minst två av dem kommer de att sammanfalla. Kan inte kopiera slumpmässig tillstånd, och teleportering är en ersättning för denna operation.

Teleportering låter dig överföra kvanttillståndet för ett system med hjälp av vanliga klassiska kommunikationskanaler. Således är det särskilt möjligt att erhålla det bundna tillståndet för ett system som består av delsystem belägna på stort avstånd.

Tillämpningar av kvantdatorer

Applikationsspecifikationer

Det kan tyckas att en kvantdator är en typ av analog dator. Men detta är inte sant: i sin kärna är det en digital enhet, men med en analog karaktär.

De huvudsakliga problemen i samband med skapandet och användningen av kvantdatorer:

det är nödvändigt att säkerställa hög mätnoggrannhet;
yttre påverkan kan förstöra kvantsystemet eller införa förvrängningar i det.

Tillämpningar på kryptografi

Tack vare den enorma hastigheten för nedbrytning till primära faktorer kommer en kvantdator att göra det möjligt att dekryptera meddelanden krypterade med en populär asymmetrisk kryptografisk algoritm, vilket öppnar upp för nya möjligheter inom meddelandeöverföring. Prototyper av system av detta slag är på utvecklingsstadiet.

Genomföranden

Det kanadensiska företaget D-Wave tillkännagav i februari 2007 skapandet av en provkvantdator bestående av 16 qubits (enheten kallades Orion). Information om denna enhet uppfyllde dock inte de strikta kraven på korrekt vetenskaplig rapportering; nyheterna fick inte vetenskapligt erkännande. Dessutom väckte företagets ytterligare planer (att skapa en 1024-qubit-dator inom en snar framtid) skepsis bland medlemmar av expertgemenskapen.

I november 2007 demonstrerade samma företag, D-Wave, driften av ett exempel på en 28-qubit-dator online vid en konferens om superdatorer. Denna demonstration orsakade också en viss form av skepsis.

I december 2008 organiserade företaget Distributed Computing-projektet AQUA@home( A diabatisk Q.U. antum A lgorithms), som testar algoritmer som optimerar beräkningar på D-Wave adiabatiska supraledande kvantdatorer.

se även

Anteckningar

Litteratur

Kilin S.Ya. Kvanta och information / Framsteg inom optik. - 2001. - Vol. 42. - S. 1-90.
Kilin S. Ya. Kvantinformation / Framsteg inom fysikaliska vetenskaper. - 1999. - T. 169. - P. 507-527.
Quantum computing för- och nackdelar. Ed. Sadovnichy V. A.
Kvantdator och kvantberäkning. Ed. Sadovnichy V. A.
Valiev K. A., Kokin A. A. Kvantdatorer: hopp och verklighet. Moskva, Izhevsk: Regular and Chaotic Dynamics, 2004. 320 s. ISBN 5-93972-024-2

Länkar

Kvantdator och dess elementära halvledarbas
Kitaev, A., Shen, A., Vyalyi, M. Klassisk och kvantberäkning
QWiki (engelska) och Quantiki (engelska) - Wikiresurser för kvantinformationsvetenskap
QCL programmeringsspråk för kvantdatorer
Kurs "Modern problem of theoretical data science" (föreläsningar om kvantberäkning: introduktion, supertät kodning, kvantteleportation, Simon och Shor-algoritmer)
InFuture.ru: Kvantdatorernas framtid ligger i ternär beräkning
Valiev K. A. "Quantum computers and quantum computing" UFN 175 3 (2005)

Wikimedia Foundation. 2010.

Kvantstorlekseffekt
Kvantdimensionella effekter

Se vad "Quantum computing" är i andra ordböcker:

Kvantdatorer- 3 qubits av ett kvantregister kontra 3 bitar av ett konventionellt en kvantdator är en hypotetisk beräkningsenhet som, genom att exekvera kvantalgoritmer, avsevärt använder kvantmekaniska effekter i sin funktion, som ... ... Wikipedia.

TOPOLOGISKA KVANTFÄLTTEORIER- kvantmekanisk eller kvantfältteorier, alla korrelationsfunktioner där inte är beroende av valet av koordinater och mått både i rymdtid och i andra rum som är involverade i att definiera teorin. Detta gör att du kan använda... ... Fysisk uppslagsverk

Kvantdator- 3 qubits av ett kvantregister kontra 3 bitar av ett konventionellt register. En kvantdator skiljer sig fundamentalt från klassiska datorer baserade på ... Wikipedia

På grund av den allmänna boomen av blockchain och alla typer av stordata har ett annat lovande ämne släppts från toppen av tekniska nyheter - kvantberäkning. Och de är förresten kapabla att revolutionera flera IT-områden samtidigt, börja med den ökända blockkedjan och sluta med informationssäkerhet. I de följande två artiklarna kommer Sberbank och Sberbank Technologies att berätta varför kvantdatorer är coolt och vad de gör med det nu.

Klassiska beräkningar: OCH, ELLER, INTE

För att förstå quantum computing bör du först fräscha upp klassisk datoranvändning. Här är enheten för bearbetad information lite. Varje bit kan endast vara i ett av två möjliga tillstånd - 0 eller 1. Ett register med N bitar kan innehålla en av 2 N möjliga kombinationer av tillstånd och representeras som en sekvens av dem.

För att bearbeta och transformera information används bitvisa operationer som kommer från boolesk algebra. De grundläggande operationerna är enbitars NOT och tvåbitars OCH och ELLER. Bitoperationer beskrivs genom sanningstabeller. De visar överensstämmelsen mellan inmatningsargumenten och det resulterande värdet.

En klassisk beräkningsalgoritm är en uppsättning sekventiella bitoperationer. Det är mest bekvämt att reproducera det grafiskt, i form av ett diagram av funktionella element (SFE), där varje operation har sin egen beteckning. Här är ett exempel på SFE för att kontrollera två bitar för ekvivalens.

Kvantberäkning. Fysisk grund

Låt oss nu gå vidare till ett nytt ämne. Kvantberäkning är ett alternativ till klassiska algoritmer baserade på kvantfysikens processer. Den säger att utan växelverkan med andra partiklar (det vill säga fram till mätögonblicket) har elektronen inte entydiga koordinater i atomens omloppsbana, utan är samtidigt lokaliserad i alla punkter i omloppsbanan. Området där elektronen befinner sig kallas elektronmolnet. I det berömda dubbelslitsexperimentet passerar en elektron genom båda slitsarna samtidigt och stör sig själv. Först under mätning kollapsar denna osäkerhet och elektronkoordinaterna blir entydiga.

Den probabilistiska karaktären hos mätningar som är inneboende i kvantberäkning ligger bakom många algoritmer - till exempel sökning i en ostrukturerad databas. Algoritmer av denna typ ökar steg för steg amplituden för det korrekta resultatet, vilket gör att det kan erhållas vid utgången med maximal sannolikhet.

Qubits

Inom kvantberäkning implementeras de fysiska egenskaperna hos kvantobjekt i så kallade qubits (q-bitar). En klassisk bit kan bara vara i ett tillstånd – 0 eller 1. Före mätning kan en qubit vara i båda tillstånden samtidigt, så den betecknas vanligtvis med uttrycket a|0⟩ + b|1⟩, där A och B är komplexa siffror som uppfyller villkoret |A | 2 +|B| 2 = 1. Att mäta en qubit "kollapser" omedelbart dess tillstånd till ett av de grundläggande - 0 eller 1. I det här fallet kollapsar "molnet" till en punkt, det ursprungliga tillståndet förstörs och all information om det går oåterkalleligt förlorad.

En tillämpning av denna egenskap är Schrödingers katt som en sann slumptalsgenerator. Qubiten införs i ett tillstånd där resultatet av mätningen kan vara 1 eller 0 med lika stor sannolikhet. Detta tillstånd beskrivs enligt följande:

Kvant- och klassisk datoranvändning. Första omgången

Låt oss börja med grunderna. Det finns en uppsättning initiala data för beräkningar, representerade i binärt format av vektorer med längden N.

I klassiska beräkningar laddas endast ett av 2 n dataalternativ in i datorns minne och värdet på funktionen beräknas för detta alternativ. Som ett resultat endast ett av 2 n möjliga datamängder.

Alla 2n kombinationer av källdata representeras samtidigt i minnet på en kvantdator. Transformationer tillämpas på alla dessa kombinationer på en gång. Som ett resultat beräknar vi funktionen i en operation för alla 2 n möjliga varianter av datamängden (mätning ger fortfarande bara en lösning i slutändan, men mer om det senare).

Både klassisk och kvantberäkning använder logiska transformationer - grindar. I klassisk beräkning lagras in- och utvärden i olika bitar, vilket innebär att antalet ingångar i grindar kan skilja sig från antalet utgångar:

Låt oss överväga ett verkligt problem. Vi måste avgöra om två bitar är ekvivalenta.

Om vi under klassiska beräkningar får en vid utgången, är de likvärdiga, annars inte:

Låt oss nu föreställa oss detta problem med hjälp av kvantberäkning. I dem har alla transformationsgrindar samma antal utgångar som ingångar. Detta beror på det faktum att resultatet av omvandlingen inte är ett nytt värde, utan en förändring i tillståndet för de nuvarande.

I exemplet jämför vi värdena för den första och andra qubiten. Resultatet kommer att vara i noll qubit - flaggan qubit. Denna algoritm är endast tillämplig på de grundläggande tillstånden - 0 eller 1. Här är ordningen för kvantomvandlingar.

Vi påverkar qubit-flaggan med "Not"-porten och sätter den till 1.
Vi använder två-qubit "Controlled Not"-porten två gånger. Denna grind vänder endast om värdet på flaggqubiten om den andra qubiten som är involverad i transformationen är i tillstånd 1.
Vi mäter noll qubit. Om resultatet är 1, är både den första och andra qubiten antingen både i tillstånd 1 (flaggan qubit ändrade sitt värde två gånger) eller i tillstånd 0 (flaggan qubit förblev i tillstånd 1). Annars är qubitarna i olika tillstånd.

Nästa nivå. Quantum single-qubit Pauli-grindar

Låt oss försöka jämföra klassisk och kvantberäkning i mer allvarliga problem. För detta behöver vi lite mer teoretisk kunskap.

Vid kvantberäkning kodas informationen som bearbetas i kvantbitar – så kallade kvantbitar. I det enklaste fallet kan en qubit, som en klassisk bit, vara i ett av två grundläggande tillstånd: |0⟩ (kort notation för vektorn 1|0⟩ + 0|1⟩) och |1⟩ (för vektorn 0) |0⟩ + 1 |1⟩). Ett kvantregister är en tensorprodukt av kvantbitsvektorer. I det enklaste fallet, när varje kvantbit är i ett av grundtillstånden, är kvantregistret ekvivalent med det klassiska. Ett register med två qubits i tillståndet |0> kan skrivas på följande sätt:

(1|0⟩ + 0|1⟩)*(1|0⟩ + 0|1⟩) = 1|00⟩ + 0|01⟩ + 0|10⟩ + 0|11⟩ = |00⟩.

För att bearbeta och transformera information i kvantalgoritmer används så kallade kvantportar. De representeras i form av en matris. För att få resultatet av att applicera grinden måste vi multiplicera vektorn som karakteriserar qubiten med grindmatrisen. Den första koordinaten för vektorn är multiplikatorn före |0⟩, den andra koordinaten är multiplikatorn före |1⟩. Matriserna för de huvudsakliga enkel-qubit-grindarna ser ut så här:

Här är ett exempel på användning av Not-porten:

X * |0⟩ = X * (1|0⟩ + 0|1⟩) = 0|0⟩ + 1|1⟩ = |1⟩

Faktorerna framför bastillstånden kallas amplituder och är komplexa tal. Modulen för ett komplext tal är lika med roten av summan av kvadraterna av de reella och imaginära delarna. Kvadraten på storleken på amplituden framför bastillståndet är lika med sannolikheten för att erhålla detta bastillstånd när man mäter en qubit, så summan av kvadraterna på amplitudernas storlek är alltid lika med 1. Vi skulle kunna använda godtyckliga matriser för transformationer över qubits, men på grund av att norm (längd) vektorn alltid måste vara lika med 1 (summan av sannolikheterna för alla utfall är alltid lika med 1), måste vår transformation bevara vektorns norm . Detta innebär att transformationen måste vara enhetlig och motsvarande matris måste vara enhetlig. Kom ihåg att den enhetliga transformationen är inverterbar och UU † =I.

För att tydligare arbeta med qubits är de avbildade som vektorer på Bloch-sfären. I denna tolkning representerar en-qubit-grindar rotationen av qubit-vektorn runt en av axlarna. Till exempel roterar Not(X)-grinden qubit-vektorn med Pi relativt X-axeln. Således går tillståndet |0>, representerat av en vektor som pekar rakt upp, in i tillståndet |1> som pekar rakt ned. Tillståndet för qubiten på Bloch-sfären bestäms av formeln cos(θ/2)|0⟩+e iϕ sin(θ/2)|1⟩

Quantum två-qubit grindar

För att bygga algoritmer räcker inte bara en-qubit-grindar för oss. Det behövs grindar som utför transformationer beroende på vissa förutsättningar. Det huvudsakliga verktyget för detta är två-qubit-grinden CNOT. Denna grind appliceras på två qubits och inverterar den andra qubiten endast om den första qubiten är i tillståndet |1⟩. CNOT-portmatrisen ser ut så här:

Här är ett applikationsexempel:

CNOT *|10⟩ = CNOT * (0|00⟩ + 0|01⟩ + 1|10⟩ + 0|11⟩) = 0|00⟩ + 0|01⟩ + 1|11⟩ + 0|10⟩ = |11⟩

Att använda en CNOT-grind motsvarar att utföra en klassisk XOR-operation och skriva resultatet till den andra qubiten. Faktum är att om vi tittar på sanningstabellen för XOR- och CNOT-operatörerna, kommer vi att se korrespondensen:

XOR			CNOT
0	0	0	00	00
0	1	1	01	01
1	0	1	10	11
1	1	0	11	10

CNOT-grinden har en intressant egenskap - efter dess applicering blir qubitarna intrasslade eller lossnade, beroende på initialtillståndet. Detta kommer att visas i nästa artikel, i avsnittet om kvantparallellism.

Konstruktion av algoritmen - klassisk och kvantimplementering

Med en full arsenal av kvantportar kan vi börja utveckla kvantalgoritmer. I en grafisk representation representeras qubits av raka linjer - "strängar" på vilka grindar är överlagrade. En-qubit Pauli-grindar betecknas med vanliga kvadrater, inuti vilka rotationsaxeln är avbildad. CNOT-porten ser lite mer komplicerad ut:

Exempel på användning av CNOT-porten:

En av de viktigaste åtgärderna i algoritmen är att mäta det erhållna resultatet. Måttet anges vanligtvis med en bågskala med en pil och en beteckning på vilken axel som mätningen görs.

Så låt oss försöka bygga en klassisk och kvantalgoritm som lägger till 3 till argumentet.

Att summera vanliga siffror i en kolumn innebär att man utför två åtgärder på varje siffra - summan av siffrorna i själva siffran och summan av resultatet med en överföring från föregående operation, om det fanns en sådan överföring.

I den binära representationen av tal kommer summeringsoperationen att bestå av samma åtgärder. Här är koden i python:

Arg = #ställ in argumentresultatet = #initiera resultatet carry1 = arg & 0x1 #add med 0b11, så att carry från den låga biten visas om argumentet har låg bit = 1 resultat = arg ^ 0x1 #lägg till de låga bitarna bära2 = bära1 | arg #add med 0b11, så carry från den höga biten kommer att visas om argumentet har den höga biten = 1 eller om det fanns en carry från lågbitresultatet = arg ^ 0x1 #add the high bits result ^= carry1 #apply carry från lågbitresultatet ^= carry2 #apply carry från den mest signifikanta biten utskrift(resultat)
Låt oss nu försöka utveckla ett liknande program för en kvantdator:

I detta schema är de två första qubitarna argumentet, de två nästa är överföringarna och de återstående 3 är resultatet. Så här fungerar algoritmen.

Det första steget till barriären är att ställa argumentet till samma tillstånd som i det klassiska fallet - 0b11.
Med hjälp av CNOT-operatorn beräknar vi värdet av den första bäringen - resultatet av operationen arg & 1 är lika med ett endast när arg är lika med 1, i vilket fall vi inverterar den andra qubiten.
De nästa 2 grindarna implementerar tillägget av de minst signifikanta bitarna - vi överför qubit 4 till |1⟩-tillståndet och skriver XOR-resultatet in i det.
Den stora rektangeln representerar CCNOT-porten, en förlängning av CNOT-grinden. Denna grind har två kontroll-qubits och den tredje inverteras endast om de två första är i tillstånd |1. Kombinationen av 2 CNOT-grindar och en CCNOT-grind ger oss resultatet av den klassiska operationen carry2 = carry1 | arg. De två första grindarna överförs till en om en av dem är 1, och CCNOT-grinden hanterar fallet när de båda är lika med en.
Vi lägger till de högsta qubitarna och överföringsqubitarna.

Interimistiska slutsatser

Om vi kör båda exemplen får vi samma resultat. På en kvantdator kommer detta att ta längre tid eftersom ytterligare kompilering till kvantmonteringskod måste utföras och skickas till molnet för exekvering. Användningen av kvantberäkning skulle vara vettig om hastigheten för att utföra deras elementära operationer - grindar - skulle vara många gånger mindre än i den klassiska modellen.

Expertmätningar visar att utförandet av en gate tar cirka 1 nanosekund. Algoritmer för en kvantdator bör alltså inte kopiera klassiska, utan utnyttja kvantmekanikens unika egenskaper maximalt. I nästa artikel kommer vi att titta på en av de viktigaste egenskaperna - kvantparallellism - och prata om kvantoptimering i allmänhet. Sedan kommer vi att identifiera de mest lämpliga områdena för kvantberäkning och beskriva deras tillämpningar.

Baserat på material