EITC/QI/QIF Quantum Information Fundamentals er det europeiske IT-sertifiseringsprogrammet for teoretiske og praktiske aspekter ved kvanteinformasjon og kvanteberegning, basert på lovene til kvantefysikk i stedet for klassisk fysikk og tilbyr kvalitative fordeler i forhold til deres klassiske motstykker.
Læreplanen til EITC/QI/QIF Quantum Information Fundamentals dekker introduksjon til kvantemekanikk (inkludert vurdering av dobbeltspalteeksperimentet og materiebølgeinterferens), introduksjon til kvanteinformasjon (qubits og deres geometriske representasjon), lyspolarisering, usikkerhetsprinsipp, kvante sammenfiltring, EPR-paradoks, brudd på klokkeulikhet, forlatelse av lokal realisme, kvanteinformasjonsbehandling (inkludert enhetlig transformasjon, enkelt-qubit- og to-qubit-porter), ikke-kloningsteorem, kvanteteleportering, kvantemåling, kvanteberegning (inkludert introduksjon til multi -qubit-systemer, universell familie av porter, reversibilitet av beregninger), kvantealgoritmer (inkludert Quantum Fourier Transform, Simons algoritme, utvidet Churh-Turing-avhandling, Shor'q kvantefaktoreringsalgoritme, Grovers kvantesøkealgoritme), kvante-observerbare, kvante-observerbare, qubits-implementeringer, kvantekompleksitetsteori, adiabatisk kvanteberegning ion, BQP, introduksjon til spinn, innenfor følgende struktur, som omfatter omfattende videodidaktisk innhold som referanse for denne EITC-sertifiseringen.
Kvanteinformasjon er informasjonen om tilstanden til et kvantesystem. Det er den grunnleggende enheten for studier i kvanteinformasjonsteori, og kan manipuleres ved hjelp av kvanteinformasjonsbehandlingsteknikker. Kvanteinformasjon refererer til både den tekniske definisjonen når det gjelder Von Neumann-entropi og den generelle beregningstermen.
Kvanteinformasjon og beregning er et tverrfaglig felt som involverer kvantemekanikk, informatikk, informasjonsteori, filosofi og kryptografi blant andre felt. Studiet er også relevant for disipliner som kognitiv vitenskap, psykologi og nevrovitenskap. Hovedfokuset er å trekke ut informasjon fra materie i mikroskopisk skala. Observasjon i vitenskapen er et grunnleggende særegent kriturium for virkeligheten og en av de viktigste måtene å tilegne seg informasjon. Derfor er måling nødvendig for å kvantifisere observasjonen, noe som gjør den avgjørende for den vitenskapelige metoden. I kvantemekanikk, på grunn av usikkerhetsprinsippet, kan ikke-pendlende observerbare ikke måles nøyaktig samtidig, da en egentilstand i en basis ikke er en egentilstand i den andre basis. Siden begge variablene ikke er godt definert samtidig, kan en kvantetilstand aldri inneholde definitiv informasjon om begge variablene. På grunn av denne grunnleggende egenskapen til målingen i kvantemekanikk, kan denne teorien generelt karakteriseres som ikke-deterministisk i motsetning til klassisk mekanikk, som er fullstendig deterministisk. Indeterminismen til kvantetilstander karakteriserer informasjon definert som tilstander av kvantesystemer. I matematiske termer er disse tilstandene i superposisjoner (lineære kombinasjoner) av klassiske systems tilstander.
Siden informasjon alltid er kodet i tilstanden til et fysisk system, er den fysisk i seg selv. Mens kvantemekanikk tar for seg å undersøke egenskaper til materie på mikroskopisk nivå, fokuserer kvanteinformasjonsvitenskap på å trekke ut informasjon fra disse egenskapene, og kvanteberegning manipulerer og behandler kvanteinformasjon – utfører logiske operasjoner – ved hjelp av kvanteinformasjonsbehandlingsteknikker.
Kvanteinformasjon, som klassisk informasjon, kan behandles ved hjelp av datamaskiner, overføres fra ett sted til et annet, manipuleres med algoritmer og analyseres med informatikk og matematikk. Akkurat som den grunnleggende enheten for klassisk informasjon er biten, omhandler kvanteinformasjon qubits, som kan eksistere i superposisjon av 0 og 1 (som samtidig er noe sant og usant). Kvanteinformasjon kan også eksistere i såkalte sammenfiltrede tilstander, som manifesterer rent ikke-klassiske ikke-lokale korrelasjoner i sine målinger, noe som muliggjør applikasjoner som kvanteteleportering. Nivået av sammenfiltring kan måles ved hjelp av Von Neumann-entropi, som også er et mål på kvanteinformasjon. Nylig har feltet kvanteberegning blitt et veldig aktivt forskningsområde på grunn av muligheten for å forstyrre moderne beregning, kommunikasjon og kryptografi.
Historien om kvanteinformasjon begynte på begynnelsen av det 20. århundre da klassisk fysikk ble revolusjonert til kvantefysikk. Teoriene om klassisk fysikk var å forutsi absurditeter som den ultrafiolette katastrofen, eller elektroner som spirerer inn i kjernen. Først ble disse problemene børstet til side ved å legge ad hoc-hypoteser til klassisk fysikk. Snart ble det klart at en ny teori må skapes for å forstå disse absurditetene, og teorien om kvantemekanikk ble født.
Kvantemekanikk ble formulert av Schrödinger ved bruk av bølgemekanikk og Heisenberg ved bruk av matrisemekanikk. Ekvivalensen av disse metodene ble bevist senere. Formuleringene deres beskrev dynamikken til mikroskopiske systemer, men hadde flere utilfredsstillende aspekter i beskrivelsen av måleprosesser. Von Neumann formulerte kvanteteori ved bruk av operatoralgebra på en måte som beskrev måling så vel som dynamikk. Disse studiene la vekt på de filosofiske aspektene ved måling i stedet for en kvantitativ tilnærming til å trekke ut informasjon via målinger.
På 1960-tallet foreslo Stratonovich, Helstrom og Gordon en formulering av optisk kommunikasjon ved bruk av kvantemekanikk. Dette var den første historiske opptredenen av kvanteinformasjonsteorien. De studerte hovedsakelig feilsannsynligheter og kanalkapasiteter for kommunikasjon. Senere oppnådde Holevo en øvre grense for kommunikasjonshastighet ved overføring av en klassisk melding via en kvantekanal.
På 1970-tallet begynte teknikker for å manipulere enkeltatoms kvantetilstander, som atomfellen og skanningstunnelmikroskopet, å bli utviklet, noe som gjorde det mulig å isolere enkeltatomer og ordne dem i matriser. Før disse utviklingene var presis kontroll over enkeltkvantesystemer ikke mulig, og eksperimenter brukte grovere, samtidig kontroll over et stort antall kvantesystemer. Utviklingen av levedyktige enkeltstatsmanipulasjonsteknikker førte til økt interesse for feltet kvanteinformasjon og beregning.
På 1980-tallet oppsto interessen for om det kunne være mulig å bruke kvanteeffekter for å motbevise Einsteins relativitetsteori. Hvis det var mulig å klone en ukjent kvantetilstand, ville det vært mulig å bruke sammenfiltrede kvantetilstander for å overføre informasjon raskere enn lysets hastighet, noe som motbeviser Einsteins teori. Ikke-kloningsteoremet viste imidlertid at slik kloning er umulig. Teoremet var et av de tidligste resultatene av kvanteinformasjonsteorien.
Utvikling fra kryptografi
Til tross for all spenningen og interessen over å studere isolerte kvantesystemer og forsøke å finne en måte å omgå relativitetsteorien på, ble forskningen innen kvanteinformasjonsteori stagnerende på 1980-tallet. Omtrent samtidig begynte imidlertid en annen vei å prøve seg på kvanteinformasjon og beregning: Kryptografi. I en generell forstand er kryptografi problemet med å gjøre kommunikasjon eller beregning som involverer to eller flere parter som kanskje ikke stoler på hverandre.
Bennett og Brassard utviklet en kommunikasjonskanal som det er umulig å avlytte uten å bli oppdaget, en måte å kommunisere i hemmelighet på lange avstander ved å bruke kvantekrypteringsprotokollen BB84. Nøkkelideen var bruken av kvantemekanikkens grunnleggende prinsipp om at observasjon forstyrrer de observerte, og innføringen av en avlytter i en sikker kommunikasjonslinje vil umiddelbart la de to partene som prøver å kommunisere, vite om tilstedeværelsen av avlytteren.
Utvikling fra informatikk og matematikk
Med ankomsten av Alan Turings revolusjonerende ideer om en programmerbar datamaskin, eller Turing-maskin, viste han at enhver beregning i den virkelige verden kan oversettes til en tilsvarende beregning som involverer en Turing-maskin. Dette er kjent som Church–Turing-oppgaven.
Snart nok ble de første datamaskinene laget og maskinvaren vokste i et så raskt tempo at veksten, gjennom erfaring med produksjon, ble kodifisert til et empirisk forhold kalt Moores lov. Denne 'loven' er en projektiv trend som sier at antall transistorer i en integrert krets dobles hvert annet år. Etter hvert som transistorer begynte å bli mindre og mindre for å pakke mer kraft per overflateareal, begynte kvanteeffekter å dukke opp i elektronikken som resulterte i utilsiktet interferens. Dette førte til fremveksten av kvanteberegning, som brukte kvantemekanikk for å designe algoritmer.
På dette tidspunktet viste kvantedatamaskiner løfte om å være mye raskere enn klassiske datamaskiner for visse spesifikke problemer. Et slikt eksempelproblem ble utviklet av David Deutsch og Richard Jozsa, kjent som Deutsch–Jozsa-algoritmen. Dette problemet hadde imidlertid liten eller ingen praktiske anvendelser. Peter Shor i 1994 kom opp med et veldig viktig og praktisk problem, et med å finne hovedfaktorene til et heltall. Det diskrete logaritmeproblemet som det ble kalt, kunne løses effektivt på en kvantedatamaskin, men ikke på en klassisk datamaskin, og viser derfor at kvantedatamaskiner er kraftigere enn Turing-maskiner.
Utvikling fra informasjonsteori
Rundt den tiden informatikk gjorde en revolusjon, det samme gjorde informasjonsteori og kommunikasjon, gjennom Claude Shannon. Shannon utviklet to grunnleggende teoremer innen informasjonsteori: støyfri kanalkodingsteorem og støykanalkodingsteorem. Han viste også at feilrettingskoder kunne brukes for å beskytte informasjon som sendes.
Kvanteinformasjonsteori fulgte også en lignende bane, Ben Schumacher i 1995 laget en analog til Shannons støyløse kodeteorem ved å bruke qubit. Det ble også utviklet en teori om feilretting, som lar kvantedatamaskiner gjøre effektive beregninger uavhengig av støy, og foreta pålitelig kommunikasjon over støyende kvantekanaler.
Qubits og informasjonsteori
Kvanteinformasjon skiller seg sterkt fra klassisk informasjon, illustrert av biten, på mange slående og ukjente måter. Mens den grunnleggende enheten for klassisk informasjon er biten, er den mest grunnleggende enheten for kvanteinformasjon qubiten. Klassisk informasjon måles ved bruk av Shannon-entropi, mens den kvantemekaniske analogen er Von Neumann-entropi. Et statistisk ensemble av kvantemekaniske systemer er preget av tetthetsmatrisen. Mange entropimål i klassisk informasjonsteori kan også generaliseres til kvantetilfellet, for eksempel Holevo-entropi og den betingede kvanteentropien.
I motsetning til klassiske digitale tilstander (som er diskrete), er en qubit kontinuerlig verdsatt, som kan beskrives med en retning på Bloch-sfæren. Til tross for at den er kontinuerlig verdsatt på denne måten, er en qubit den minste mulige enheten av kvanteinformasjon, og til tross for at qubit-tilstanden er kontinuerlig verdsatt, er det umulig å måle verdien nøyaktig. Fem kjente teoremer beskriver grensene for manipulering av kvanteinformasjon:
- no-teleportation teorem, som sier at en qubit ikke kan (helt) konverteres til klassiske biter; det vil si at den ikke kan "leses" fullstendig
- ikke-kloningsteorem, som forhindrer at en vilkårlig qubit blir kopiert,
- no-deleting teorem, som forhindrer at en vilkårlig qubit blir slettet,
- no-broadcasting teorem, som forhindrer at en vilkårlig qubit blir levert til flere mottakere, selv om den kan transporteres fra sted til sted (f.eks. via kvanteteleportering),
- no-hiding teorem, som demonstrerer bevaring av kvanteinformasjon, Disse teoremene beviser at kvanteinformasjon i universet er bevart, og de åpner for unike muligheter i prosessering av kvanteinformasjon.
Kvanteinformasjon
Tilstanden til en qubit inneholder all informasjonen. Denne tilstanden uttrykkes ofte som en vektor på Bloch-sfæren. Denne tilstanden kan endres ved å bruke lineære transformasjoner eller kvanteporter på dem. Disse enhetlige transformasjonene beskrives som rotasjoner på Bloch-sfæren. Mens klassiske porter tilsvarer de kjente operasjonene til boolsk logikk, er kvanteporter fysiske enhetsoperatører.
På grunn av flyktigheten til kvantesystemer og umuligheten av å kopiere tilstander, er lagring av kvanteinformasjon mye vanskeligere enn å lagre klassisk informasjon. Likevel, med bruk av kvantefeilkorreksjon kan kvanteinformasjon i prinsippet fortsatt lagres pålitelig. Eksistensen av kvantefeilkorrigerende koder har også ført til muligheten for feiltolerant kvanteberegning.
Klassiske biter kan kodes inn i og deretter hentes fra konfigurasjoner av qubits, ved bruk av kvanteporter. I seg selv kan en enkelt qubit ikke formidle mer enn en bit med tilgjengelig klassisk informasjon om forberedelsen. Dette er Holevos teorem. I superdense koding kan imidlertid en sender, ved å handle på en av to sammenfiltrede qubits, formidle to biter med tilgjengelig informasjon om deres felles tilstand til en mottaker.
Kvanteinformasjon kan flyttes rundt, i en kvantekanal, analogt med konseptet med en klassisk kommunikasjonskanal. Kvantemeldinger har en endelig størrelse, målt i qubits; kvantekanaler har en endelig kanalkapasitet, målt i qubits per sekund.
Kvanteinformasjon, og endringer i kvanteinformasjon, kan måles kvantitativt ved å bruke en analog av Shannon-entropien, kalt von Neumann-entropien.
I noen tilfeller kan kvantealgoritmer brukes til å utføre beregninger raskere enn i noen kjent klassisk algoritme. Det mest kjente eksemplet på dette er Shor sin algoritme som kan faktorisere tall i polynomisk tid, sammenlignet med de beste klassiske algoritmene som tar sub-eksponentiell tid. Siden faktorisering er en viktig del av sikkerheten til RSA-kryptering, utløste Shors algoritme det nye feltet post-kvantekryptografi som prøver å finne krypteringsskjemaer som forblir trygge selv når kvantedatamaskiner er i spill. Andre eksempler på algoritmer som demonstrerer kvanteoverlegenhet inkluderer Grovers søkealgoritme, der kvantealgoritmen gir en kvadratisk hastighet opp over best mulig klassisk algoritme. Kompleksitetsklassen av problemer som effektivt kan løses av en kvantedatamaskin er kjent som BQP.
Quantum key distribution (QKD) tillater ubetinget sikker overføring av klassisk informasjon, i motsetning til klassisk kryptering, som alltid kan brytes i prinsippet, om ikke i praksis. Vær oppmerksom på at visse subtile punkter angående sikkerheten til QKD fortsatt diskuteres heftig.
Studiet av alle de ovennevnte emnene og forskjellene omfatter kvanteinformasjonsteori.
Relasjon til kvantemekanikk
Kvantemekanikk er studiet av hvordan mikroskopiske fysiske systemer endrer seg dynamisk i naturen. Innenfor kvanteinformasjonsteori er de studerte kvantesystemene abstrahert bort fra enhver motpart i den virkelige verden. En qubit kan for eksempel fysisk være et foton i en lineær optisk kvantedatamaskin, et ion i en fanget ion kvantedatamaskin, eller det kan være en stor samling av atomer som i en superledende kvantedatamaskin. Uavhengig av den fysiske implementeringen, holder grensene og egenskapene til qubits implisert av kvanteinformasjonsteorien, ettersom alle disse systemene er matematisk beskrevet av det samme apparatet med tetthetsmatriser over de komplekse tallene. En annen viktig forskjell med kvantemekanikk er at mens kvantemekanikk ofte studerer uendelig-dimensjonale systemer som en harmonisk oscillator, angår kvanteinformasjonsteori både med kontinuerlige variable systemer og endelig-dimensjonale systemer.
Kvanteberegning
Kvanteberegning er en type beregning som utnytter de kollektive egenskapene til kvantetilstander, som superposisjon, interferens og sammenfiltring, for å utføre beregninger. Enhetene som utfører kvanteberegninger er kjent som kvantedatamaskiner.: I-5 Selv om nåværende kvantedatamaskiner er for små til å utkonkurrere vanlige (klassiske) datamaskiner for praktiske applikasjoner, antas de å være i stand til å løse visse beregningsproblemer, for eksempel heltallsfaktorisering (som ligger til grunn for RSA-kryptering), vesentlig raskere enn klassiske datamaskiner. Studiet av kvanteberegning er et underfelt av kvanteinformasjonsvitenskap.
Kvanteberegning begynte i 1980 da fysikeren Paul Benioff foreslo en kvantemekanisk modell av Turing-maskinen. Richard Feynman og Yuri Manin antydet senere at en kvantedatamaskin hadde potensialet til å simulere ting en klassisk datamaskin ikke kunne gjøre. I 1994 utviklet Peter Shor en kvantealgoritme for faktorisering av heltall med potensial til å dekryptere RSA-kryptert kommunikasjon. I 1998 skapte Isaac Chuang, Neil Gershenfeld og Mark Kubinec den første to-qubit kvantedatamaskinen som kunne utføre beregninger. Til tross for pågående eksperimentell fremgang siden slutten av 1990-tallet, mener de fleste forskere at «feiltolerant kvanteberegning [er] fortsatt en ganske fjern drøm». De siste årene har investeringene i kvanteberegningsforskning økt i offentlig og privat sektor. 23. oktober 2019 hevdet Google AI, i samarbeid med US National Aeronautics and Space Administration (NASA), å ha utført en kvanteberegning som var umulig på noen klassisk datamaskin, men hvorvidt denne påstanden var eller fortsatt er gyldig er et tema om aktiv forskning.
Det finnes flere typer kvantedatamaskiner (også kjent som kvantedatamaskiner), inkludert kvantekretsmodellen, kvanteturingmaskinen, adiabatisk kvantedatamaskin, enveis kvantedatamaskin og ulike kvantecellulære automater. Den mest brukte modellen er kvantekretsen, basert på kvantebiten, eller "qubit", som er noe analog med biten i klassisk beregning. En qubit kan være i en 1- eller 0-kvantetilstand, eller i en superposisjon av 1- og 0-tilstandene. Når den måles, er den imidlertid alltid 0 eller 1; sannsynligheten for begge utfall avhenger av qubitens kvantetilstand umiddelbart før måling.
Arbeidet med å bygge en fysisk kvantedatamaskin fokuserer på teknologier som transmons, ionefeller og topologiske kvantedatamaskiner, som tar sikte på å lage qubits av høy kvalitet.: 2–13 Disse qubitene kan utformes annerledes, avhengig av fullkvantedatamaskinens datamodell, enten det er kvantelogiske porter, kvanteutglødning eller adiabatisk kvanteberegning. Det er for tiden en rekke betydelige hindringer for å konstruere nyttige kvantedatamaskiner. Det er spesielt vanskelig å opprettholde qubits' kvantetilstander, siden de lider av kvantedekoherens og statstroskap. Kvantedatamaskiner krever derfor feilretting.
Ethvert beregningsproblem som kan løses av en klassisk datamaskin kan også løses av en kvantedatamaskin. Omvendt kan ethvert problem som kan løses av en kvantedatamaskin også løses av en klassisk datamaskin, i det minste i prinsippet gitt nok tid. Kvantedatamaskiner adlyder med andre ord Kirken-Turing-avhandlingen. Dette betyr at mens kvantedatamaskiner ikke gir noen ekstra fordeler i forhold til klassiske datamaskiner når det gjelder beregnbarhet, har kvantealgoritmer for visse problemer betydelig lavere tidskompleksitet enn tilsvarende kjente klassiske algoritmer. Spesielt antas kvantedatamaskiner å være i stand til raskt å løse visse problemer som ingen klassisk datamaskin kunne løse på noen mulig tid - en bragd kjent som "kvanteoverherredømme". Studiet av den beregningsmessige kompleksiteten til problemer med hensyn til kvantedatamaskiner er kjent som kvantekompleksitetsteori.
Den rådende modellen for kvanteberegning beskriver beregningen i form av et nettverk av kvantelogiske porter. Denne modellen kan betraktes som en abstrakt lineær-algebraisk generalisering av en klassisk krets. Siden denne kretsmodellen adlyder kvantemekanikk, antas en kvantedatamaskin som er i stand til effektivt å kjøre disse kretsene å være fysisk realiserbar.
Et minne som består av n informasjonsbiter har 2^n mulige tilstander. En vektor som representerer alle minnetilstander har dermed 2^n oppføringer (en for hver tilstand). Denne vektoren blir sett på som en sannsynlighetsvektor og representerer det faktum at minnet er å finne i en bestemt tilstand.
I den klassiske visningen vil én oppføring ha en verdi på 1 (dvs. en 100 % sannsynlighet for å være i denne tilstanden) og alle andre oppføringer vil være null.
I kvantemekanikk kan sannsynlighetsvektorer generaliseres til tetthetsoperatorer. Kvantetilstandsvektorformalismen introduseres vanligvis først fordi den er konseptuelt enklere, og fordi den kan brukes i stedet for tetthetsmatriseformalismen for rene tilstander, hvor hele kvantesystemet er kjent.
en kvanteberegning kan beskrives som et nettverk av kvantelogiske porter og målinger. Imidlertid kan enhver måling utsettes til slutten av kvanteberegningen, selv om denne utsettelsen kan komme til en beregningskostnad, så de fleste kvantekretser viser et nettverk som bare består av kvantelogiske porter og ingen målinger.
Enhver kvanteberegning (som i formalismen ovenfor er enhver enhetlig matrise over n qubits) kan representeres som et nettverk av kvantelogiske porter fra en ganske liten familie av porter. Et valg av portfamilie som muliggjør denne konstruksjonen er kjent som et universelt portsett, siden en datamaskin som kan kjøre slike kretser er en universell kvantedatamaskin. Et vanlig slikt sett inkluderer alle enkelt-qubit-porter så vel som CNOT-porten ovenfra. Dette betyr at enhver kvanteberegning kan utføres ved å utføre en sekvens av enkelt-qubit-porter sammen med CNOT-porter. Selv om dette portsettet er uendelig, kan det erstattes med et begrenset portsett ved å appellere til Solovay-Kitaev-teoremet.
Kvantealgoritmer
Fremgang i å finne kvantealgoritmer fokuserer vanligvis på denne kvantekretsmodellen, selv om unntak som den kvanteadiabatiske algoritmen eksisterer. Kvantealgoritmer kan grovt kategoriseres etter typen speedup oppnådd over tilsvarende klassiske algoritmer.
Kvantealgoritmer som tilbyr mer enn en polynomhastighet i forhold til den best kjente klassiske algoritmen inkluderer Shors algoritme for faktorisering og de relaterte kvantealgoritmene for å beregne diskrete logaritmer, løse Pells ligning og mer generelt løse det skjulte undergruppeproblemet for abelske endelige grupper. Disse algoritmene er avhengige av primitivet til kvante-Fourier-transformasjonen. Det er ikke funnet noen matematiske bevis som viser at en like rask klassisk algoritme ikke kan oppdages, selv om dette anses som usannsynlig. [selvpublisert kilde?] Visse orakelproblemer som Simons problem og Bernstein-Vazirani-problemet gir beviselige hastigheter, selv om dette er i kvantespørringsmodellen, som er en begrenset modell der nedre grenser er mye lettere å bevise og ikke nødvendigvis oversettes til speedups for praktiske problemer.
Andre problemer, inkludert simulering av kvantefysiske prosesser fra kjemi og faststofffysikk, tilnærmingen til visse Jones-polynomer og kvantealgoritmen for lineære ligningssystemer har kvantealgoritmer som ser ut til å gi superpolynomiske hastigheter og er BQP-komplette. Fordi disse problemene er BQP-fullstendige, vil en like rask klassisk algoritme for dem innebære at ingen kvantealgoritme gir en superpolynomisk speedup, noe som antas å være usannsynlig.
Noen kvantealgoritmer, som Grovers algoritme og amplitudeforsterkning, gir polynomhastigheter i forhold til tilsvarende klassiske algoritmer. Selv om disse algoritmene gir en relativt beskjeden kvadratisk hastighetsøkning, er de allment anvendelige og gir dermed hastigheter for et bredt spekter av problemer. Mange eksempler på bevisbare kvantehastigheter for spørringsproblemer er relatert til Grovers algoritme, inkludert Brassard, Høyer og Tapps algoritme for å finne kollisjoner i to-til-en funksjoner, som bruker Grovers algoritme, og Farhi, Goldstone og Gutmanns algoritme for å evaluere NAND trær, som er en variant av søkeproblemet.
Kryptografiske applikasjoner
En bemerkelsesverdig anvendelse av kvanteberegning er for angrep på kryptografiske systemer som for tiden er i bruk. Heltallsfaktorisering, som underbygger sikkerheten til kryptografiske systemer med offentlig nøkkel, antas å være beregningsmessig umulig med en vanlig datamaskin for store heltall hvis de er et produkt av få primtall (f.eks. produkter av to 300-sifrede primtall). Til sammenligning kan en kvantedatamaskin effektivt løse dette problemet ved å bruke Shors algoritme for å finne dens faktorer. Denne evnen ville tillate en kvantedatamaskin å bryte mange av de kryptografiske systemene som er i bruk i dag, i den forstand at det ville være en polynomisk tidsalgoritme (i antall sifre i heltallet) for å løse problemet. Spesielt er de fleste av de populære offentlige nøkkelchifrene basert på vanskeligheten med å faktorisere heltall eller det diskrete logaritmeproblemet, som begge kan løses med Shors algoritme. Spesielt kan RSA, Diffie–Hellman og elliptiske kurve Diffie–Hellman-algoritmene bli ødelagt. Disse brukes til å beskytte sikre websider, kryptert e-post og mange andre typer data. Å bryte disse vil ha betydelige konsekvenser for elektronisk personvern og sikkerhet.
Identifisering av kryptografiske systemer som kan være sikre mot kvantealgoritmer er et aktivt forsket tema innen post-kvantekryptografi. Noen offentlige nøkkelalgoritmer er basert på andre problemer enn heltallsfaktorisering og diskrete logaritmeproblemer som Shors algoritme gjelder for, som McEliece-kryptosystemet basert på et problem i kodingsteori. Gitterbaserte kryptosystemer er heller ikke kjent for å bli ødelagt av kvantedatamaskiner, og å finne en polynomisk tidsalgoritme for å løse det dihedriske skjulte undergruppeproblemet, som ville bryte mange gitterbaserte kryptosystemer, er et godt studert åpent problem. Det har blitt bevist at bruk av Grovers algoritme for å bryte en symmetrisk (hemmelig nøkkel) algoritme med brute force krever tid lik omtrent 2n/2 påkallinger av den underliggende kryptografiske algoritmen, sammenlignet med omtrent 2n i det klassiske tilfellet, noe som betyr at symmetriske nøkkellengder er effektivt halvert: AES-256 ville ha samme sikkerhet mot et angrep ved bruk av Grovers algoritme som AES-128 har mot klassisk brute-force-søk (se Nøkkelstørrelse).
Kvantekryptografi kan potensielt oppfylle noen av funksjonene til offentlig nøkkelkryptografi. Kvantebaserte kryptografiske systemer kan derfor være sikrere enn tradisjonelle systemer mot kvantehacking.
Søkeproblemer
Det mest kjente eksemplet på et problem med å innrømme en polynomisk kvantehastighet er ustrukturert søk, å finne et markert element fra en liste med n elementer i en database. Dette kan løses av Grovers algoritme ved å bruke O(sqrt(n))-spørringer til databasen, kvadratisk færre enn Omega(n)-spørringene som kreves for klassiske algoritmer. I dette tilfellet er fordelen ikke bare bevisbar, men også optimal: det har vist seg at Grovers algoritme gir maksimalt mulig sannsynlighet for å finne det ønskede elementet for et hvilket som helst antall orakeloppslag.
Problemer som kan løses med Grovers algoritme har følgende egenskaper:
- Det er ingen søkbar struktur i samlingen av mulige svar,
- Antall mulige svar å sjekke er det samme som antall innganger til algoritmen, og
- Det finnes en boolsk funksjon som evaluerer hver inndata og bestemmer om det er riktig svar
For problemer med alle disse egenskapene skalerer kjøretiden til Grovers algoritme på en kvantedatamaskin som kvadratroten av antall innganger (eller elementer i databasen), i motsetning til den lineære skaleringen av klassiske algoritmer. En generell klasse av problemer som Grovers algoritme kan brukes på er boolsk tilfredsstillelsesproblem, der databasen som algoritmen itererer gjennom er den av alle mulige svar. Et eksempel og (mulig) anvendelse av dette er en passordknekker som forsøker å gjette et passord. Symmetriske siffer som Triple DES og AES er spesielt sårbare for denne typen angrep. Denne anvendelsen av kvantedatabehandling er en stor interesse for offentlige etater.
Simulering av kvantesystemer
Siden kjemi og nanoteknologi er avhengig av forståelse av kvantesystemer, og slike systemer er umulige å simulere på en effektiv måte klassisk, tror mange kvantesimulering vil være en av de viktigste anvendelsene av kvanteberegning. Kvantesimulering kan også brukes til å simulere oppførselen til atomer og partikler under uvanlige forhold som reaksjonene inne i en kolliderer. Kvantesimuleringer kan brukes til å forutsi fremtidige baner for partikler og protoner under superposisjon i dobbeltspalte-eksperimentet. Omtrent 2% av den årlige globale energiproduksjonen brukes til nitrogenfiksering for å produsere ammoniakk for Haber-prosessen i landbruket gjødselindustrien mens naturlig forekommende organismer også produserer ammoniakk. Kvantesimuleringer kan brukes til å forstå denne prosessen som øker produksjonen.
Kvanteutglødning og adiabatisk optimalisering
Kvanteutglødning eller adiabatisk kvanteberegning er avhengig av den adiabatiske teoremet for å utføre beregninger. Et system er plassert i grunntilstanden for en enkel Hamiltonianer, som langsomt utvikles til en mer komplisert Hamiltonianer hvis grunntilstand representerer løsningen på det aktuelle problemet. Den adiabatiske teoremet sier at hvis utviklingen er sakte nok, vil systemet holde seg i sin grunntilstand til enhver tid gjennom prosessen.
Maskinlæring
Siden kvantedatamaskiner kan produsere utdata som klassiske datamaskiner ikke kan produsere effektivt, og siden kvanteberegning er grunnleggende lineær algebraisk, uttrykker noen håp om å utvikle kvantealgoritmer som kan fremskynde maskinlæringsoppgaver. For eksempel antas kvantealgoritmen for lineære ligningssystemer, eller "HHL Algorithm", oppkalt etter oppdagerne Harrow, Hassidim og Lloyd, å gi fart i forhold til klassiske motstykker. Noen forskningsgrupper har nylig utforsket bruken av kvanteutglødningsmaskinvare for trening av Boltzmann-maskiner og dype nevrale nettverk.
Beregningsbiologi
Innen beregningsbiologi har kvanteberegning spilt en stor rolle i å løse mange biologiske problemer. Et av de velkjente eksemplene vil være i beregningsgenomikk og hvordan databehandling drastisk har redusert tiden for å sekvensere et menneskelig genom. Gitt hvordan beregningsbiologi bruker generisk datamodellering og lagring, forventes dets anvendelser til beregningsbiologi også å oppstå.
Datastøttet legemiddeldesign og generativ kjemi
Dypgenerative kjemimodeller dukker opp som kraftige verktøy for å fremskynde oppdagelsen av legemidler. Imidlertid utgjør den enorme størrelsen og kompleksiteten til det strukturelle rommet til alle mulige medikamentlignende molekyler betydelige hindringer, som kan overvinnes i fremtiden av kvantedatamaskiner. Kvantedatamaskiner er naturlig nok gode for å løse komplekse kvantemangekroppsproblemer og kan derfor være medvirkende i applikasjoner som involverer kvantekjemi. Derfor kan man forvente at kvanteforbedrede generative modeller inkludert kvante-GAN-er til slutt kan utvikles til ultimate generative kjemialgoritmer. Hybridarkitekturer som kombinerer kvantedatamaskiner med dype klassiske nettverk, som Quantum Variational Autoencoders, kan allerede trenes på kommersielt tilgjengelige annealere og brukes til å generere nye medikamentlignende molekylstrukturer.
Utvikling av fysiske kvantedatamaskiner
Utfordringer
Det er en rekke tekniske utfordringer ved å bygge en storskala kvantedatamaskin. Fysiker David DiVincenzo har listet opp disse kravene for en praktisk kvantedatamaskin:
- Fysisk skalerbar for å øke antall qubits,
- Qubits som kan initialiseres til vilkårlige verdier,
- Kvanteporter som er raskere enn dekoherenstid,
- Universal port sett,
- Qubits som lett kan leses.
Det er også veldig vanskelig å finne deler til kvantedatamaskiner. Mange kvantedatamaskiner, som de som er konstruert av Google og IBM, trenger helium-3, et kjernefysisk forskningsbiprodukt, og spesielle superledende kabler laget kun av det japanske selskapet Coax Co.
Kontrollen av multi-qubit-systemer krever generering og koordinering av et stort antall elektriske signaler med stram og deterministisk tidsoppløsning. Dette har ført til utviklingen av kvantekontrollere som muliggjør grensesnitt med qubitene. Å skalere disse systemene for å støtte et økende antall qubits er en ekstra utfordring.
Kvantedekoherens
En av de største utfordringene forbundet med å konstruere kvantedatamaskiner er å kontrollere eller fjerne kvantedekoherens. Dette betyr vanligvis å isolere systemet fra omgivelsene ettersom interaksjoner med den ytre verden får systemet til å dekohere. Det finnes imidlertid også andre kilder til dekoherens. Eksempler inkluderer kvanteportene, og gittervibrasjonene og termonukleære bakgrunnsspinn til det fysiske systemet som ble brukt til å implementere qubitene. Dekoherens er irreversibel, siden den i praksis er ikke-enhetlig, og er vanligvis noe som bør kontrolleres sterkt, hvis ikke unngås. Dekoherenstider for kandidatsystemer spesielt, tverrrelaksasjonstiden T2 (for NMR- og MR-teknologi, også kalt utfasingstiden), varierer typisk mellom nanosekunder og sekunder ved lav temperatur. For tiden krever noen kvantedatamaskiner at qubitene deres avkjøles til 20 millikelvin (vanligvis ved bruk av et fortynningskjøleskap) for å forhindre betydelig dekoherens. En studie fra 2020 argumenterer for at ioniserende stråling som kosmisk stråling likevel kan få visse systemer til å dekohere i løpet av millisekunder.
Som et resultat kan tidkrevende oppgaver gjøre noen kvantealgoritmer ubrukelige, ettersom å opprettholde tilstanden til qubits i lang nok varighet vil til slutt ødelegge superposisjonene.
Disse problemene er vanskeligere for optiske tilnærminger ettersom tidsskalaene er størrelsesordener kortere og en ofte sitert tilnærming for å overvinne dem er optisk pulsforming. Feilrater er typisk proporsjonale med forholdet mellom driftstid og dekoherenstid, og derfor må enhver operasjon fullføres mye raskere enn dekoherenstiden.
Som beskrevet i kvanteterskelteoremet, hvis feilraten er liten nok, antas det å være mulig å bruke kvantefeilkorreksjon for å undertrykke feil og dekoherens. Dette gjør at den totale beregningstiden blir lengre enn dekoherenstiden dersom feilrettingsordningen kan rette opp feil raskere enn dekoherensen innfører dem. Et ofte sitert tall for den nødvendige feilraten i hver port for feiltolerant beregning er 10−3, forutsatt at støyen er depolariserende.
Å oppfylle denne skalerbarhetsbetingelsen er mulig for et bredt spekter av systemer. Bruken av feilretting fører imidlertid med seg kostnadene for et sterkt økt antall nødvendige qubits. Tallet som kreves for å faktorisere heltall ved bruk av Shors algoritme er fortsatt polynom, og antas å være mellom L og L2, der L er antall sifre i tallet som skal faktoriseres; feilkorrigeringsalgoritmer vil blåse opp dette tallet med en ekstra faktor på L. For et 1000-bits tall innebærer dette et behov for ca. 104 biter uten feilretting. Med feilretting vil tallet stige til omtrent 107 biter. Beregningstiden er omtrent L2 eller omtrent 107 trinn og ved 1 MHz, omtrent 10 sekunder.
En helt annen tilnærming til stabilitets-dekoherens-problemet er å lage en topologisk kvantedatamaskin med anyoner, kvasipartikler brukt som tråder og basert på fletteteori for å danne stabile logiske porter.
Kvanteoverlegenhet
Quantum supremacy er et begrep laget av John Preskill som refererer til den tekniske bragden å demonstrere at en programmerbar kvanteenhet kan løse et problem utover mulighetene til toppmoderne klassiske datamaskiner. Problemet trenger ikke være nyttig, så noen ser på kvanteoverlegenhetstesten bare som en potensiell fremtidig målestokk.
I oktober 2019 ble Google AI Quantum, ved hjelp av NASA, den første til å hevde å ha oppnådd kvanteoverlegenhet ved å utføre beregninger på Sycamore kvantedatamaskinen mer enn 3,000,000 XNUMX XNUMX ganger raskere enn de kunne gjøres på Summit, generelt ansett som verdens raskeste datamaskin. Denne påstanden har senere blitt utfordret: IBM har uttalt at Summit kan utføre prøver mye raskere enn påstått, og forskere har siden utviklet bedre algoritmer for prøvetakingsproblemet som brukes til å hevde kvanteoverlegenhet, noe som gir betydelige reduksjoner til eller lukke gapet mellom Sycamore og klassiske superdatamaskiner.
I desember 2020 implementerte en gruppe ved USTC en type Boson-sampling på 76 fotoner med en fotonisk kvantedatamaskin Jiuzhang for å demonstrere kvanteoverlegenhet. Forfatterne hevder at en klassisk moderne superdatamaskin vil kreve en beregningstid på 600 millioner år for å generere antall prøver deres kvanteprosessor kan generere på 20 sekunder. 16. november 2021 på kvanteberegningstoppmøtet presenterte IBM en 127-qubit mikroprosessor kalt IBM Eagle.
Fysiske implementeringer
For fysisk implementering av en kvantedatamaskin blir mange forskjellige kandidater forfulgt, blant dem (preget av det fysiske systemet som brukes til å realisere qubits):
- Superledende kvanteberegning (qubit implementert av tilstanden til små superledende kretser, Josephson-kryss)
- Fanget ion kvantedatamaskin (qubit implementert av den interne tilstanden til fangede ioner)
- Nøytrale atomer i optiske gitter (qubit implementert av interne tilstander av nøytrale atomer fanget i et optisk gitter)
- Kvantepunktdatamaskin, spinnbasert (f.eks. Loss-DiVincenzo kvantedatamaskin) (qubit gitt av spinntilstandene til fangede elektroner)
- Kvantepunktdatamaskin, rombasert (qubit gitt av elektronposisjon i dobbel kvantepunkt)
- Kvanteberegning ved bruk av konstruerte kvantebrønner, som i prinsippet kan muliggjøre konstruksjon av kvantedatamaskiner som opererer ved romtemperatur
- Koblet kvantetråd (qubit implementert av et par kvantetråder koblet med en kvantepunktkontakt)
- Kjernemagnetisk resonans kvantedatamaskin (NMRQC) implementert med kjernemagnetisk resonans av molekyler i løsning, der qubits leveres av kjernefysiske spinn i det oppløste molekylet og sondert med radiobølger
- Solid-state NMR Kane kvantedatamaskiner (qubit realisert av den nukleære spinntilstanden til fosfordonorer i silisium)
- Elektroner-på-helium kvantedatamaskiner (qubit er elektronspinnet)
- Kavitetskvanteelektrodynamikk (CQED) (qubit levert av den indre tilstanden til fangede atomer koblet til hulrom med høy finesse)
- Molekylær magnet (qubit gitt av spinntilstander)
- Fulleren-basert ESR kvantedatamaskin (qubit basert på elektronisk spinn av atomer eller molekyler innkapslet i fullerener)
- Ikke-lineær optisk kvantedatamaskin (qubits realisert ved å behandle tilstander til forskjellige lysmoduser gjennom både lineære og ikke-lineære elementer)
- Lineær optisk kvantedatamaskin (qubits realisert ved å behandle tilstander til forskjellige lysmoduser gjennom lineære elementer, f.eks. speil, stråledelere og faseskiftere)
- Diamantbasert kvantedatamaskin (qubit realisert av elektronisk eller kjernefysisk spinn av nitrogenledige sentre i diamant)
- Bose-Einstein kondensatbasert kvantedatamaskin
- Transistorbasert kvantedatamaskin – strengkvantedatamaskiner med innføring av positive hull ved hjelp av en elektrostatisk felle
- Sjeldne-jordmetall-ion-dopet uorganiske krystallbaserte kvantedatamaskiner (qubit realisert av den interne elektroniske tilstanden til dopingmidler i optiske fibre)
- Metallisk-lignende karbon nanosfærer-baserte kvantedatamaskiner
- Det store antallet kandidater viser at kvanteberegning, til tross for rask fremgang, fortsatt er i sin spede begynnelse.
Det finnes en rekke kvanteberegningsmodeller, kjennetegnet ved de grunnleggende elementene der beregningen er dekomponert. For praktiske implementeringer er de fire relevante beregningsmodellene:
- Quantum gate array (beregning dekomponert til en sekvens av få qubit quantum gate)
- Enveis kvantedatamaskin (beregning dekomponert til en sekvens av én-qubit-målinger brukt på en svært sammenfiltret starttilstand eller klyngetilstand)
- Adiabatisk kvantedatamaskin, basert på kvanteglødning (beregning dekomponert til en langsom kontinuerlig transformasjon av en initial Hamiltonian til en endelig Hamiltonian, hvis grunntilstander inneholder løsningen)
- Topologisk kvantedatamaskin (beregning dekomponert til fletting av anyoner i et 2D-gitter)
Kvante Turing-maskinen er teoretisk viktig, men den fysiske implementeringen av denne modellen er ikke gjennomførbar. Alle fire beregningsmodeller har vist seg å være likeverdige; hver kan simulere den andre med ikke mer enn polynomisk overhead.
For å gjøre deg mer kjent med sertifiseringspensumet kan du utvide og analysere tabellen nedenfor.
EITC/QI/QIF Quantum Information Fundamentals Certification Curriculum refererer til didaktisk materiale med åpen tilgang i en videoform. Læringsprosessen er delt inn i en trinnvis struktur (programmer -> leksjoner -> emner) som dekker relevante læreplandeler. Ubegrenset rådgivning med domeneeksperter tilbys også.
Sjekk for detaljer om sertifiseringsprosedyren Hvordan det fungerer.
Hovedforelesningsnotater
U. Vazirani forelesningsnotater:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Støttende forelesningsnotater
L. Jacak et al. forelesningsnotater (med tilleggsmateriell):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Hovedstøttende lærebok
Lærebok for kvanteberegning og kvanteinformasjon (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Ekstra forelesningsnotater
J. Preskill forelesningsnotater:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
A. Childs forelesningsnotater:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
S. Aaronson forelesningsnotater:
https://scottaaronson.blog/?p=3943
R. de Wolf forelesningsnotater:
https://arxiv.org/abs/1907.09415
Andre anbefalte lærebøker
Klassisk og kvanteberegning (Kitaev, Shen, Vyalyi)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
Kvanteberegning siden Demokrit (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/
Kvanteinformasjonsteori (Wilde)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Last ned det komplette offline selvlærende forberedende materialet for EITC/QI/QIF Quantum Information Fundamentals-programmet i en PDF-fil
EITC/QI/QIF forberedende materialer – standardversjon
EITC/QI/QIF forberedende materialer – utvidet versjon med gjennomgangsspørsmål