Hur fungerar en kvantdator egentligen

Tack för återkopplingen. Tror du detta fungerar som svar för någon som saknar fysik- eller ingenjörsbakgrund?

En kvantdator fungerar ungefär så här: Tänk dig att du har ett stort antal möjliga lösningar, och i stället för att testa dem en och en bygger du ett system där alla lösningar påverkar beräkningen samtidigt, ungefär som vågor. När vågorna möts kan de släcka ut varandra (så vissa svar får låg sannolikhet) eller förstärka varandra (så andra svar blir mer sannolika). Med hjälp av kvantgrindar styr man dessa vågor så att rätt svar förstärks och fel svar försvagas. När man till slut mäter systemet får man ett enda klassiskt svar – inte för att datorn ”väljer” det, utan för att sannolikheten för just det svaret har gjorts mycket hög.

I de flesta fall är kvantdatorer inte nämnvärt bättre än klassiska datorer. De områden där man känner till verkliga kvantfördelar är till exempel kvantsimulering av kemi och material, sökning i oorganiserade datamängder och faktorisering av stora tal.

Rätta mig om jag har fel. Men jag antar att kostnaden kommer i form av O(N) minnesceller och fysisk adresslogik, som möjliggör direkt åtkomst i O(1) tid, vilket i praktiken motsvarar att bygga N parallella orakel i hårdvara. Korrekt?


Grovers algoritm kräver inte en exponentiell ökning av grindar. I det scenario jag beskrev kräver Grovers algoritm O(√N) oracle-anrop. Varje iteration kan implementeras med O((log N)^k) grindar, där k = 1 i mitt exempel med ett enkelt ja/nej-oracle (mer komplexa orakel kräver högre k). Detta ger en total grindkostnad, och därmed tidskostnad, på O(√N·log N). Antalet qubits som krävs samtidigt är O(log N), vilket räcker för att utföra dessa grindar över tid och motsvarar hårdvarukostnaden. Det innebär alltså O(log N) hårdvara för en tidskostnad på O(√N·log N).


Grovers algoritm visar en kvantfördel just när klassisk och kvantalgoritm har samma oracle-åtkomst till en osorterad databas, och jag använde detta som ett exempel i mitt första inlägg i denna tråd för att illustrera hur en kvantdator fungerar i jämförelse med en klassisk dator. Om indexet redan är känt så är givetvis inte Grovers algoritm mera effektiv än den klassiska datorn. Så Grovers algoritm är alltså effektiv just för osorterad sökning med oracle-åtkomst, inte för sorterad sökning eller direkt åtkomst. För osorterad data kan jag tänka mig att man i de flesta fall kan klassiskt välja att lösa problemet sekventiellt med en tidskostnad på O(N), eller ifall praktiskt möjligt bygga direkt åtkomst genom extra struktur med en resurskostnad på O(N). Alternativt kan man använda Grovers algoritm, som ger en grind-/tidskostnad på O(√N log N) med en hårdvarukostnad på O(log N) qubits. Valet mellan dessa alternativ är i praktiken en ekonomisk fråga.

Grover kan vara potentiellt intressant i situationer där det är opraktiskt att sortera data eller bygga index och extra struktur, och där varje test är dyrt. Samtidigt måste man komma ihåg att Grover endast ger en kvadratisk, inte exponentiell, förbättring. Även om man lyckas med att skala kvantdatorer kommer kvantresurser sannolikt att vara mycket dyra under överskådlig framtid i jämförelse med klassiska resurser, vilket lätt kan äta upp denna fördel. Den praktiska potentialen för Grovers algoritm är därför sannolikt begränsad, även om den i vissa nischade fall kan vara relevant.

Applikationer där man förväntar sig betydligt större kvantfördelar än för Grovers algoritm är kvantsimulering av kemi och material, samt faktorisering av stora tal med Shors algoritm. I dessa fall finns teoretiska resultat som pekar på exponentiella förbättringar jämfört med de bästa kända klassiska algoritmerna, med polynomisk skalning av grindar och hårdvaruresurser. Samtidigt vet man ännu inte i vilken utsträckning klassiska algoritmer, eventuellt med approximationer eller nya insikter, kan komma att minska eller helt eliminera dessa fördelar. Även om man hypotetiskt lyckas skala kvantdatorer så att de blir jämförbara med klassiska datorer i storlek och tillförlitlighet, är det därför inte självklart att de praktiska kvantfördelarna blir så stora som de teoretiska resultaten antyder.

Detta är ett aktivt forskningsområde, vilket bland annat diskuteras i en intressant intervju med Ewin Tang som är forskare inom detta fält, What Is the True Promise of Quantum Computing? | PODCAST: The Joy of Why. Hur användbara kvantdatorer faktiskt kommer att bli i framtiden vet vi därför inte. Däremot finns det sannolikt på kortare sikt potential i kvantteknologier som spin-offs från kvantdatorforskning, såsom kvantoptik och kvantsensorer. Samtidigt är det inte uteslutet att just kvantmekanisk simulering av kemi och material på längre sikt visar sig bli en mycket stor tillämpning i en skala vi inte kan föreställa oss, precis som forskningen kring kvantmekanik och halvledare under första halvan av 1900-talet lade grunden för den digitala utvecklingen vi ser idag. Men det är ett ämne för en annan tråd, eftersom denna tråd handlar om hur en kvantdator fungerar.

Ja den förklaringen är begriplig och meningsfull också för lekmannen. Bra att det går med mer vanligt språk.

Ja, precis. Det brukar framhållas som en av den moderna datorns fördelar att den kan återanvända samma hårdvara för att lösa många problem, t.ex. med en central processor som itererar över en datamängd eftersom det ofta är billigare än att skapa dedikerade processorer för varje enskilt dataelement. Men det finns inget i tekniken som kräver att vi gör så och minnesadressering är ett exempel på när vi väljer att göra tvärtom av effektivitetsskäl. (Det har experimenterats med andra varianter i datorernas barndom.)

Det är möjligt att jag helt missförstår problemet som skall lösas.

Som jag tänker mig det så beror resultatet på hela datamängden (vilken är av storleken N) och då kan inte ens en kvantdator (oberoende av algoritm) lösa problemet utan att vid något tillfälle vara preparerad med hela datamängden, annars kan datorn inte veta var den skall söka. Vi kommer alltså inte undan att preparera N stycken element, vilket sätter en absolut undre gräns för mängden arbete som krävs.

Det är möjligt att du argumenterar för att vi kan bortse från prepareringskostnaden om indatan är utdata från en tidigare beräkning, men då uppstår ju frågan om vi alls behövde organisera datan så att det inte går att göra en effektivare sökning?

👍 Tack för återkopplingen!

Jo, jag håller med dig om att en av de stora fördelarna med moderna datorer är att dess hårdvara kan återanvändas för att lösa många olika problem. Och själv tycker jag också att det finns för mycket hype då kvantdatorer och deras potential beskrivs. Jag tror aldrig att kvantdatorn någonsin kommer att ersätta klassiska datorer, utan om de kan skalas upp kan de endast operera inom mycket smala nischer.

Men som jag nämnde i tidigare inlägg kanske en potentiellt värdefull nisch är just att kvantsimulera kemiska processer och material och eventuellt ge upphov till en mängd nya technologier som inte skulle vara möjliga om vi endast använde oss av klassiska datorer, eftersom det oftast är exponentiell komplexitet i klassiska simuleringar, men polynomell komplexitet i kvantsimuleringar. Och just denna applikation tycker jag personligen är spännande med kvantdatorer. Men då krävs att man tekniskt lyckas skala upp denna teknologi.


Du missförstår inte problemet, utan pekar på en viktig poäng. Man måste läsa in N dataposter, och man måste bygga någon fysisk representation av hela datamängden, oavsett om vi pratar om en klassisk dator eller kvantdator. Kvantfördelen gäller endast söksteget, givet samma åtkomst. Grovers algoritm är snarare en pedagogisk förklaring av hur kvantintereferens kan användas snarare än att detta kommer att bli en ”killer-applikation” i jämförelse med klassiska datorer.

I de flesta praktiska fall har du rätt – om man ändå måste preparera datan är det oftast rationellt att organisera den för effektiv klassisk sökning. Exempel på scenarier där det inte är praktiskt att organisera datat för effektiv klassisk sökning är realtidsflöden, verifieringen är väldigt dyr, eller det inte finns ”data” att indexera (såsom kombinatoriska problem, vilka tenderar att vara exponentiella i sin komplexitet så kvadratisk förbättring kanske inte hjälper så mycket). Men summa kardemumma tvivlar jag på att Grover kommer att ha några större applikationer.

Kontentan, om jag förstår det rätt, blir att kvantdatorer (om vi lyckas bygga några sådana) bara tycks vara användbara för att lösa några väl utvalda problem, såsom primtalsfaktorisering och nedskalad simulering av fysikaliska processer.

När någon kvantdator lyckas knäcka några av de hittills olösta delproblemen från RSA Factoring Challenge från 1991 så kommer även jag att börja tro på quantum supremacy. Dock fortfarande långt från den populära bilden av att kvantdatorer kommer att vara som vanliga datorer men bättre på allt, som sprids av många forskare.

Stort tack för detta svar med förklaringar och boktips och allt!
Hinner inte med ett ordentligt svar just nu, men du har rätt i att jag är fysiker, som du också uppenbarligen är. Och ja, nivån är nog helt rätt för den nivå på förståelse jag faktiskt är ute efter. Har laddat ner "Mike & Ike" och börjat läsa...
Återkommer.

Tackar också för ditt svar om Qiskit. Får nog även bli en del mer om Python framöver.

Absolut är det så att ifall man lyckas skala kvantdatorer så kommer den endast att vara användbar i att lösa några väl avgränsade problem (d.v.s. problem där kvantdatorer kan reducera exponentiell komplexitet till polynomisk komplexitet i sin beräkning) och inte allmänt ersätta klassiska datorer. Om man tittar på några av tungviktarna i forskningen kring kvantdatorer, såsom Peter Shor, Lov Grover, Seth Lloyd (arbete kring kvantsimulering av reducerade/kvantmekaniska fysikaliska system), John Preskill (myntade begreppet ”quantum supremacy” för vissa avgränsade nischade problem), Scott Aaronson (forskar kring gränsen mellan kvant- och klassisk beräkningskomplexitet, inklusive s.k. dequantization), så är dessa överens om att ifall kvantdatorer kan byggas så kommer dessa att vara användbara i avgränsade specialfall, inte allmänt. Detta står i skarp kontrast till den hype man ofta ser i medier, populärvetenskap och marknadsföring från Silicon Valley.

Lycka till. 😊 Det jag personligen tycker är mest spännande med kvantdatorer (och därför började intressera mig för dem) är deras potential att simulera kvantmekaniska qudit-system, dvs. system med N frihetsgrader där varje delsystem har d nivåer (d>=2, där d = 2, 3, 4 …). Sådana system har ett tillståndsrum med d^N amplituder och kräver därför i allmänhet exponentiell skalning på klassiska datorer. Kvantdatorer, som kan representera sådana system direkt fysikaliskt, kan däremot i många fall reducera den till polynomisk komplexitet, t.ex. i simulering av lokal Hamiltonian, kortare tidsutveckling och begränsad precision (ifall det råder kaotiska dynamiker, lång tidsutveckling och höga krav på precision kan det vara svårt att simulera även på kvantdatorer). Detta möjliggör att kunna simulera sådana system inom rimlig tid, givet att man lyckas lösa de tekniska problemen med att bygga en storskalig kvantdator.

Klar nu med det första kapitlet med en introduktion till hela ämnet som ju är väldigt upplysande om alla möjliga aspekter. T ex skoj med en rätt ordentlig förklaring kvantgrindar för enstaka qbits, och om kvantteleportering! Det du säger nu berörs också ffa mot slutet på kapitlet. Kommande kapitel har djupdykningar och mer detaljer.

Har precis börjat med andra kapitlet om kvantfysik. Trevligt och stilenligt att de kör med Diracnotation.

Kul. Jo, jag tycker att Mike & Ike är upplysande. Själv gillar jag också Diracnotationer i kvantformalismen, de gör beskrivningarna mera kompakta, mer som linjär algebra och förenklar beräkningar med operatorer.