Hur fungerar en kvantdator egentligen

Det är steget att hitta ett element a i Z_n sådant att a^r=1 (mod n) som kvantdatorn är bättre på, polynomiellt i n ist. exponentiellt. Har man ett sådant a^r går man enkelt vidare med r till att hitta en delare till n. (Det bygger på att a och n är relativt prima, (så man kan få testa ett antal kandidater innan man finner ett sådant a) vilket ger att det finns en invers till a i Z_n, det är också viktigt för få en unitär operation i det kvantmekaniska). Har man r får man en delare till n genom att hitta största gemensamma delare för n och (a^(r/2)-1), det är som du säger ganska lätt.


När det gäller det tillämpade kvantmekaniska så vet jag ingenting.

Men det finns enorma förhoppningar om det här och det pumpas in otroliga resurser i olika projekt. IBM har nu en variant med 125 qbits. Man kan ansöka om att få köra på den...

Det finns en svensk expert på det här Martin Ekerå som nu jobbar åt försvarsmakten....

Här är en intressant artikel som visar dels en simulation av Shors algoritm och dels en körning av samma fall (faktorisera 15 resp. 21) på IBMs kvantdator med 128 qbits.
Det lyckas men knappt på kvantdatorn.

Where Are We with Shor’s Algorithm?
A deep dive into the implementation of Shor's algorithm and an analysis of quantum runs on IBM quantum hardware

Benjamin Assel
Jul 7, 2025


Slutsatsen är:


Vägen framåt verkar vara att sätta ihop en massa qbits i ett kluster med felkorrigering, ett sådant kluster med tusentals faktiska qbits bildar då en logisk qbit.
+En en massa annat mumbo jumbo som nog ligger några år framåt. Men ibland går det ju snabbare än man tror. Dagens datorchips är en bit från Eniac som nämndes i tråden.

Satsa pengar i det??

Nä, antingen fungerar det inte eller så har banksystemet kollapsat när du skall hämta ut vinsten. Spelteoretiskt en garanterad felsatsning.

Såhär fungerar i princip en kvantdator: En qubit är motsvarigheten till en klassisk bit, men istället för att bara kunna vara 0 eller 1 kan den vara i en superposition av båda, beskriven som |ψ⟩ = a|0⟩ + b|1⟩, där a och b är komplexa amplituder och ∣a∣^2 respektive ∣b∣^2 är sannolikheterna att mäta 0 eller 1. Kvantoperationer manipulerar dessa amplituder och därmed kvanttillståndet, till skillnad från klassiska operationer som bara växlar mellan 0 eller 1.

Med N klassiska bits finns 2^N möjliga tillstånd, men bara ett kan finnas åt gången. N qubits däremot kan vara i en superposition av alla 2^N tillstånd samtidigt. Detta betyder dock inte att man får ut alla dessa värden vid mätning – superpositionen används för att skapa interferens, inte för att läsa av alla svar. En klassisk dator bearbetar normalt ett tillstånd åt gången, medan en kvantdator låter många möjliga lösningar existera parallellt och använder interferens för att förstärka sannolikheten för rätt lösning och minska sannolikheten för felaktiga innan mätningen sker. När mätningen väl görs kollapsar kvanttillståndet till ett enda klassiskt utfall, och hela beräkningen måste därför konstrueras så att rätt svar har hög sannolikhet just vid mättillfället.

Skillnaden mellan kvant- och klassiska datorer ligger alltså i hur beräkningarna utförs. Det betyder inte att kvantdatorer är överlägsna i alla situationer. Hittills finns bara ett fåtal välkända områden där de teoretiskt erbjuder tydliga fördelar, t.ex.:
- faktorisering av stora tal (Shor’s algoritm),
- sökning i oorganiserade datamängder (Grover’s algoritm, som ger en kvadratisk hastighetsvinst),
- kvantsimulering av kemi och material.
Gemensamt för dessa problem är att de har en struktur som kan utnyttjas av kvantinterferens; utan en sådan struktur finns ingen generell kvantfördel.

Däremot finns idag inga exempel där kvantdatorer entydigt överträffar klassiska datorer* inom t.ex. vanlig deep learning, grafik eller generella optimeringsproblem – även om forskningen är aktiv. Och vad gäller ditt exempel: att bara testa primtal i en lista är faktiskt ett problem där klassiska datorer redan är väldigt effektiva på stora tal (t.ex. Miller–Rabin-testet), så där finns ingen tydlig kvantfördel idag.

Låt oss ta en annan konkret uppgift. Låt oss säga att vi har en osorterad databas med N poster och vi vill hitta en specifik post. En klassisk dator måste i värsta fall kontrollera alla poster, och i genomsnitt ungefär N/2 poster. En kvantdator kan istället använda Grover’s algoritm. Den lägger alla möjliga index i superposition och använder kvantinterferens för att gradvis minska sannolikheten för fel svar och öka sannolikheten för rätt svar. Efter ungefär kvadratroten av N iterationer är rätt post mycket sannolik att dyka upp vid mätning. Om databasen innehåller en biljon poster behöver en klassisk dator i genomsnitt runt 500 miljarder iterationer, medan en kvantdator bara runt en miljon – alltså ungefär 500 000 gånger färre sökningar.
_____

* Det finns en intressant intervju med Ewin Tang, som forskar kring kvantdatorer. Hon påvisade att vissa algoritmer som man tidigare trodde att kvantdatorer var teoretiskt sett var överlägsna kunde med vissa förändringar göras så att klassiska datorer blev lika bra. Så hur användbar en kvantdator kommer att bli i framtiden är en intressant frågeställning. Du kan lyssna på denna 37 minuter långa intervju här: What Is the True Promise of Quantum Computing? | PODCAST: The Joy of Why.

Tack för ditt insiktsfulla inlägg! Ett av många dessutom, men här i linje med ditt användarnamn. Ser gärna mer av dig om detta, och kanske ännu mer detaljerat om fysiken i det, eller med fler referenser.

Vad säger du t ex om möjligheterna att testa detta själv, t ex som det beskrivs här?
https://www.jonvet.com/blog/using-a-real-quantum-computer
Ska jag göra detta behöver jag steppa upp lite i mina Python skills, som just nu är rätt rudimentära. Vad händer där egentligen? Python som sådan är ju för en klassisk dator, men i något kritiskt steg skickar man alltså iväg någon indata (kvantamplituder antar jag) till en kvantator, som ger någon output (kvantamplituder igen). Men isf är nog den kvantdatorn uppsatt för EN speciell sorts kvantberäkning (dvs med EN hamiltonian som bestämmer kvanttillståndets tidsutveckling)? Eller kan den ändras utifrån på något sätt?

Ursäkta mitt svammel, men säg gärna något klokt.

Vet inte om jag köper just den här jämförelsen då den tycks utgå från att den klassiska datorn har konstant mängd transistorer medan kvantdatorn behöver en mängd qubits som växer med N. En klassisk dator vars mängd transistorer fick lov att växa på motsvarande sätt skulle enkelt kunna lösa ovanstående problem i O(log N) vilket är mycket bättre än kvantdatorns O(√N). Eller missar jag något?

Tack för dessa vänliga ord 😊 Om du vill fördjupa dig i kvantdatorer och kvantinformation så kan jag rekommendera följande böcker*:

1. Quantum Computation and Quantum Information – Nielsen & Chuang.
Går igenom grunderna kring kvantinformation, kvantgrindar och kvantkretsar, samt algoritmer (såsom Grover och Shor). Det är en bok jag rekommenderar om du är intresserad av kvantprogrammering.

2. Quantum Information Theory – Wilde.
Är en bok om kvantentropi och kvantkommunikation, om du vill bättre förstå teorin bakom kvantinformation.

_______________
* Som jag förstått av dina inlägg så har du fysikbakgrund, därför ger jag dig denna rekommendation som jag gör, vilket jag inte hade gjort till någon som saknar denna bakgrund och bara vill ha en populärvetenskaplig variant. Dessa böcker bygger på att man kan sådant som formalismen i kvantmekanik och linjär algebra, men har man en kandidat i fysik ska dessa böcker inte vara ett problem.


Huruvida jag har något klokt att säga vet jag inte. Däremot kan jag säga några ord om möjligheterna att testa själv. Qiskit är ett bibliotek i Python som möjliggör att skapa en kvantkrets med kvantgrindar. Om du vill lära dig hur man programmerar en kvantkrets kan du välja att simulera kvantkretsen i Python (klassiskt). Men i bloggen kan du registrera dig hos IBM och få tillgång till deras kvantdator. Vad du gör är att skicka instruktionerna till själva kvantkretsen och vilka kvantgrindar du använt, som du skriver i Qiskit, inte amplituderna. Sen kör du själva programmet på IBM’s kvantdator, där görs en mätning och du får tillbaks mätresultatet i klassiska bits.

Och exemplet på bloggen på instruktioner som du skickar till kvantdatorn är följande:

qc = QuantumCircuit(1) – här skapar du en kvantkrets med plats för en qubit.
qc.h(0) – här appliceras Hadamard-grinden på qubit, som försätter den i en superposition |ψ⟩ = a|0⟩ + b|1⟩.
qc.measure_all() – gör en mätning av qubit och kollapsar den till en klassisk bit.

Här så ställer du inte in Hamiltonian direkt, utan du manipulerar systemet genom olika grindar. De flesta hårdvaruplattformar som jag förstår det är programmerbara för många olika kretsar, inte bara en statisk Hamiltonian. Och vill du ändra beräkningen, så adderar/subtraherar du grindar eller ändrar ordningen på dem.

Om jag förstår din invändning korrekt så bygger detta på att man tillåter hårdvaran i den klassiska datorn att antingen genom massiv parallell åtkomst eller ett sorterat minne/sökträd så kan man lösa problemet i O(log N). Men det scenario jag beskrev var en osorterad databas och endast åtkomligt via jämförelser (oracle-frågor av typen: ”är detta index som jag söker?” - Ja/Nej). Och då kan den klassiska datorn endast lösa detta inom O(N).

Kan man lösa problemet genom en massiv parallell åtkomst eller ett sorterat minne/sökträd så är det för närvarande i praktiken givetvis ett smartare sätt att lösa detta på än genom Grovers algoritm. Men det var inte det scenario som jag beskrev. Det scenario jag beskrev var klassisk vs kvantalgoritm med samma typ av tillgång till data.

Tack för det långa svaret. Det jag fick ut av det var att Qbitsen skickar ut många ettor och nollor samtidigt och vissa kombinationer av ettor och nollor förekommer oftare. Så tror jag att jag ska tolka att sannolikheten för en del lösningar är högre än andra. Det är dom kombinationerna och så småningom en kombination, som ska vaskas fram, så att säga.

Undrar ibland om det går det att förklara med ett vardagligare språk? Det är nödvändigt om åtminstone alla som är intresserade ska kunna förstå. Kvantfysik och kvantdatorer beskrivs även mer populärt med uttryck som bara en liten del av befolkningen känner till. Som tur är har jag genomgått en civilingenjörsutbildning även om det var längesen. Så jag hänger med i språket, vilket är en absolut förutsättning för att förstå någonting. Annars är det inte många andra, förutom utbildade inom fysik och matematik, som ens vet vad komplexa tal är, eller interferens.. Bara en sån sak.

Vi kan ta vanliga RAM-minnen som ett vardagligt exempel. För att besvara frågan "vilket värde finns på adressen X" så låter vi inte en central processor löpa igenom allt minne sekventiellt tills den hittar en minnescell med adressen X (vilket skulle vara O(N) i tid), utan vi delegerar frågan till minneskretsarnas adressavkodare som det finns många av. Den minnescell som har adressen X lägger sedan ut sitt värde på bussen så att den centrala processorn kan läsa av den medan de andra minnescellerna håller tyst.

I det generella fallet kan vi besvara mer komplexa ja/nej-frågor genom att bygga ett nätverk där varje minnescell representeras av en egen dator så att vi får N orakel istället för att använda bara ett.

Hur mycket hårdvara kräver då en kvantalgoritm för att lösa motsvarande uppgift? Jag är lite osäker på exakt vilken algoritm som syftas på i just det här fallet, men en snabb AI-sökning visar att det finns en algoritm vid namn "Grover search" som kräver O(N * 2^{N/2}) antal grindar, alltså en exponentiell hårdvarukostnad för att lösa problemet på en kvantdator, medan exampelvis Shor's algoritm bara kräver O(N^3 log N) grindar. Vet inte var vi landar i det här fallet, men för att göra en rättvis jämförelse så behöver vi jämföra med en klassisk dator som har tillgång till samma mängd hårdvara.

Jag uppfattade det som att du ville ge exempel på problem där en tänkt kvantdator överträffar en klassisk dator. Eftersom vi då måste konstruera en ny kvantdator för ändamålet så måste vi rimligen jämföra med en klassisk dator optimalt konstruerad för samma ändamål, annars kan vi ju bevisa vad som helst.

Ibland kan man ju undra om inte oförmåga att förklara så att folk förstår rent av skulle kunna vara en förutsättning för att alltid beviljas nya anslag för projekt som aldrig visar sig fungera? I vilka andra sammanhang accepteras ständigt brutna löften om framgångar som alltid ligger bara några år fram i tiden och har gjort så i decennier?

Det var lite orättvist. Det är inte en bro eller väg vi talar om, utan något som inte gjorts förut eller en variant som inte gjorts förut. Sånt är väldigt svårt och beräkna när det blir klart, vilket projektledningen borde vara ärligare om.