Kwantumcomputers komen eraan

Op de kleinste deeltjes kun je rekenen

De 1bit-kwantumcomputer

Wie nu al zijn eigen, betaalbare kwantumcomputer wil aanschaffen, kan daarvoor terecht bij het Zwitserse bedrijf ID Quantique. Dat verkoopt onder andere een random-nummergenerator in de vorm van een kastje met usb-aansluiting of een pci(-e)-insteekkaart. Het enige wat hun Quantis-systeem doet, is steeds een qubit in superpositie (1/2, 1/2) brengen om deze vervolgens te laten ineenstorten tot een 0 of een 1. Op die manier wordt met een snelheid van 4Mbit/s of 16Mbit/s een willekeurige stroom enen en nullen gegenereerd.

Vergis je niet, deze 1bit-kwantumcomputer heeft een heel belangrijke functie. Voor traditionele en dus deterministische computers is het genereren van een echte random reeks namelijk een schier onmogelijke opgave. Zo heeft RAND Corporation, een bekend Amerikaans militair onderzoeksinstituut, in de jaren vijftig een boek uitgegeven en heruitgegeven in 2001 met daarin een miljoen random getallen. Het fungeerde decennia lang als standaardwerk in vooral de cryptografie en de statistiek. Tegenwoordig wordt meestal speciale hardware ingezet voor het genereren, en bewaren en gebruiken, van cryptografisch sleutelmateriaal voor serieuze en grootschalige toepassingen, denk aan dnssec.

Wearables

Hoe lang het nog duurt voordat bruikbare kwantumcomputers daadwerkelijk beschikbaar zijn, durven we niet te zeggen. Afhankelijk van wetenschappelijke doorbraken op dit gebied kan dat een paar jaar zijn of nog een paar decennia, maar dat ze eraan zitten te komen is zeker. Daarmee komt dan een fundamenteel andere computertechnologie beschikbaar.

Als de geschiedenis van de deterministische computers een goede voorspeller is, gaan we daarna een nieuw tijdperk in van steeds snellere en kleinere systemen. Wie weet maakt een kwantumrekeneenheid over twintig jaar standaard deel uit van onze smartphone of anderszins draagbare computer.

Reacties (101)

[kvaruni]

Ik vind het bewonderenswaardig dat er een artikel verschijnt met een stukje over berekenbaarheid. Helaas zitten er wat haken en ogen in het verhaal.

Om te beginnen is de figuur onvolledig, terwijl ze wel juist is. Zo zijn niet alle problemen op te delen in P of NP. Er zijn tal van problemen die nog steeds in PSPACE zitten, maar die véél moeilijker zijn dan NP. Bepaalde vormen van planning zijn bijvoorbeeld moeilijker dan NP (zoals het vinden van een plan dat altijd tot de oplossing leidt, zelfs al we niet zeker zijn van de begintoestand) of het bepalen waarom bepaalde complexe elektronische circuits niet werken. Het is dus niet correct om NP problemen te beschrijven als "de moeilijkste problemen", want er zijn tal van problemen die veel moeilijker zijn. Sterker nog, er bestaat een grote zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo .

Daarnaast klopt het natuurlijk ook niet dat we enkel deterministische problemen met een huidige computer kunnen oplossen. Als dat zo was zou het onmogelijk zijn om een groot aantal interessante problemen op te lossen. Planning heb ik al vermeld, maar zelf problemen die zo triviaal zijn als het inkleuren van een landkaart zou een computer niet aankunnen, tenzij we ons beperken tot 2 kleuren: https://en.wikipedia.org/wiki/Graph_coloring#Algorithms . Er bestaan problemen in P die we amper kunnen oplossen met een computer omdat ze zo complex zijn, en er bestaan NP problemen die we alle dagen oplossen met eenvoudige computers.

Waar zit het probleem dan? Wel, het probleem is de schaling. Als een probleem één stap moeilijker wordt (denk bijvoorbeeld aan een extra foto in een map, of een extra record in een database), dan wordt een P probleem gewoon "een beetje" moeilijker, denk bijvoorbeeld aan een extra seconde. Een NP probleem wordt daarentegen exponentieel veel moeilijker. Die ene extra foto kan er bijvoorbeeld voor zorgen dat de computer 2x zo lang moet rekenen om een oplossing te vinden. Gooi je 10 extra foto's in de map, dan is je NP probleem opeens 2^10 = 1024 keer zo moeilijk om op te lossen ... . Zelf al heb je dus een héél snel NP algoritme, het probleem wordt uiteindelijk zo complex dat je onvoldoende rekenkracht hebt. Bij een P probleem volstaat het gewoon om een extra PC te kopen, bij een NP probleem moet je 2x je huidig aantal PC's kopen om één stap verder te rekenen.

Tot slot nog een leuke afsluiter: het algoritme van Shor is een voorbeeld van een NP-hard probleem (maar dus niet van een NP-compleet probleem) dat we deterministich kunnen oplossen met een quantum computer. Deze link met berekenbaarheid wordt niet vermeld in het artikel. Dankzij Shor's algoritme worden op slag alle beveiligingen op basis van factorisaties van priemgetallen achterhaald. Natuurlijk zijn er wat kanttekeningen: dit werkt enkel met een échte quantum computer met verstrengeling. Daarnaast heb je vrij veel qubits nodig. Tot nu toe blijven we dan ook steken bij een factorisatie van het getal 143, terwijl we natuurlijk in cryptographie getallen gebruiken die vele malen groter zijn. Bovendien is het algoritme van Shor geen magisch algoritme. De enige reden waarom een quantum computer hier werkt is omdat factorisatie een periodische structuur heeft. Zonder deze zwakte was het ook voor een quantum computer niet mogelijk om dit deterministisch op te lossen. Tenzij we natuurlijk plots een NP-compleet probleem kunnen oplossen, want dat zou betekenen dat we alle NP problemen kunnen oplossen. Maar ik zou er niet direct op rekenen . Sowieso wordt het tijd om van factorisatie af te stappen, en daarbij is elliptic curve cryptografie zeker en vast een aantrekkelijke optie: http://arstechnica.com/se...iptic-curve-cryptography/ .

[Reactie gewijzigd door kvaruni op 23 juli 2024 09:27]

[Meijuh]

Aan jouw verhaal zitten helaas ook haken en ogen. Een probleem is niet deterministich, of niet-deterministisch maar de oplossing ervan wel. De moeilijkheid van een probleem wordt dan niet relateerd aan het probleem zelf maar aan de oplossing ervan.
Verder als het besproken figuur juist had moeten zijn, dan had het onderverdeeld moeten zijn in twee subfiguren, namelijk in het geval dat P=NP en het geval P!=NP, waarbij het laatste geval weergegeven is. Er wordt verondersteld; "voor zover we weten" maar eerder "voor zover we denken" niemand weet namelijk of P al dan niet gelijk is aan NP maar er wordt wel vermoed dat P!=NP anders had iemand al een algoritme gevonden die een NP-probleem in P tijd had opgelost. Dat wil dus zeggen dat een niet deterministische computer deze in polynomiale tijd kon oplossen (deze computer bestaat niet!), nu ook door een deterministische computer opgelost kan worden. Nu worden NP problemen over het algemeen in exponentionele tijd opgelost door een determinischte computer door simpelweg alle mogelijkheden uit te proberen.

"Er bestaan problemen in P die we amper kunnen oplossen met een computer omdat ze zo complex zijn, en er bestaan NP problemen die we alle dagen oplossen met eenvoudige computers. " Is daarom ook appels met peren vergelijken. Het gaat bij complexiteit niet over een enkele instantie van een probleem binnen die klasse, maar het algemene geval van dat probleem binnen die klasse. Wat dat betreft is er geen enkele overlap tussen P en NP.

In deze review is er veel aandacht besteed aan de rekenkracht van een quantumcomputer in het geval P != NP. Maar zolang dit nog niet bewezen is moet er ook aandacht besteed worden aan het geval dat P = NP. Dit maakt het verhaal helemaal interessant. Want als dit zo zou zijn dan is ook een quantumcomputer niet rekenkrachtig, gezien moeilijke problemen (NP) net zo makkelijk zijn als P problemen. Dat wil dus zeggen dat nog moeilijkere problemen dan encryptie simpel op te lossen zijn door een gangbare computer. Ik ben wel benieuwd of de klasse BQP moeilijkere problemen bevat dan NP in het geval P=NP, daar lijkt het wel op in de tekening.

Degene die overigens laat zien dat P = NP, P != NP, onbeslisbaar of niet bewijsbaar is ontvangt geloof ik een miljoen dollar van een organisatie. Hier is een lijst van mensen die het proberen: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm.

[Reactie gewijzigd door Meijuh op 23 juli 2024 09:27]

[kvaruni]

De discussie die je aanhaalt over P=NP of niet is natuurlijk een interessant aspect en uiteraard is het hele verhaal gebaseerd rond het idee dat P != NP. Hoewel er geen bewijs bestaat dat P != NP zou een bewijs dat aantoont dat P = NP de computerwereld op zijn kop zetten, en dat is dan nog heel zachtjes uitgedrukt.

Verder kan je de correcte verwoording nog verder aanscherpen, en is het een algoritme dat deterministisch is (en niet het probleem of de oplossing), en beschrijven P en NP beslissingsproblemen (en dus niet algemene problemen). Net als het artikel tekortkomingen heeft ten gunste van van de leesbaarheid gaan alle commentaren ook haken en ogen vertonen.

Ik ben er wel niet mee eens dat je enkel geïnteresseerd kan zijn in de algemene instantie van een probleem. Vanuit een theoretisch oogpunt is dit uiteraard het geval, maar vanuit een praktisch oogpunt kan het perfect mogelijk zijn dat je enkel interesse hebt in één instantie of een heel kleine verzameling van de algemene instantie. Binnen NP kan je bijvoorbeeld spreken over problemen die NP zijn, maar laag in de polynomiale hierarchie vallen. Het wordt hier nogal technisch, maar voor zij die nog kunnen volgen spreken we hier bijvoorbeeld over beslissingsproblemen waarbij algoritmes bestaan die bijvoorbeeld slechts een logaritmisch aantal keer een NP orakel moeten aanspreken. (Ouch, tot zover de leesbaarheid.) Waar het in de praktijk op neerkomt is dat dit problemen zijn die heel dicht bij P liggen. Als je net geïnteresseerd bent in deze problemen, dan maakt het natuurlijk helemaal niet uit of de algemene instantie een moeilijk NP probleem is want mogelijk bestaat er voor jou een efficiënt algoritme dat toereikend is.

[Meijuh]

Yes I agree. Feit blijft dat complexiteitstheorie erg complex is en dat je inderdaad makkelijk een fout in de bewoording kan maken.

Maar nu; ik ben nog steeds benieuwd of er in dit artikel nog iets gezegd kan worden over de rekenkracht van een quantumcomputer in het geval dat P = NP. Ik ben benieuwd of BQP meer problemen bevat dan NP indien P = NP. Dat is namelijk net zo interessant totdat bewezen wordt of P != NP.

Edit: nog even naar het plaatje gekeken te hebben volgens mij wordt er gesuggereerd dat als P = NP, dat er dan als nog moeilijkere PSPACE problemen in BQP zitten.

[Reactie gewijzigd door Meijuh op 23 juli 2024 09:27]

[kvaruni]

Het probleem met P=NP is dat dit een vrij filosofische discussie is, waardoor er vrij weing aandacht voor is. Laten we er even wat dieper over nadenken.

PSPACE bestaat om te beginnen niet alleen uit P en NP, maar ook uit coNP, en daarboven Sigma-i en Pi-i (als tegenhangers van NP=Sigma-1 en coNP=Pi-1, maar telkens op een hogere laag). Dit idee wordt mooi geïllusteerd op Wikimedia, met een betere wiskundige notatie: https://en.wikipedia.org/...nomial_time_hierarchy.svg .

Wanneer equivalentie bewezen wordt tussen Sigma-k en Sigma-(k+1) of tussen Sigma-k en Pi-k, dan valt de polynomiale hierarchie ineen tot niveau k. Dit betekent dat alle problemen boven niveau k even moeilijk zijn als een probleem op niveau k. Het meest extreme geval is een bewijs voor P=NP. Hierdoor valt de volledige polynomiale hierarchie in elkaar en kan je elk probleem met een deterministisch algoritme oplossen, zelf met een gewone computer.

Je vraag of BQP meer problemen bevat dan NP indien P = NP is dus in zekere zin een verkeerde vraag: op dat moment zijn alle problemen in PSPACE problemen in P. Je hebt dus opeens dat een Sigma-k probleem ook in BQP valt en in die zin bevat BQP meer problemen dan enkel NP (maar technisch gezien is er geen NP meer).

Waar je vermoedelijk het meeste interesse in hebt is of quantum computers in dat geval nog steeds krachtiger zijn dan gewone computers. Hoewel ik geen quantum algoritmes ken die EXSPACE problemen efficiënt kunnen oplossen (bijvoorbeeld in PSPACE), zijn er wel tal van quantum algoritmes die polynomiaal sneller zijn dan klassieke algoritmes. Als P=NP zijn alle problemen deterministisch, maar in dat geval kan een quantum computer nog steeds bepaalde problemen polynomiaal sneller oplossen dan een klassieke computer. Zelf indien P=NP zal het dus nuttig zijn om een quantum computer te ontwikkelen.

Tot slot nog een disclaimer: bij alle quantum algoritmes die polynomiaal sneller zijn dan de klassieke algoritmes ontbreekt er een bewijs om aan te tonen dat we de klassieke algoritmes niet sneller kunnen maken. Er wordt alleen aangenomen, net zoals bij P!=NP, dat het zo is op basis van voorgaande pogingen. Met andere woorden: als P=NP zal de discussie vermoedelijk verschuiven naar P = BQP of P != BQP.

Ben je tevreden met deze aanvulling op het artikel?

[sirdupre]

Hoewel ik geen quantum algoritmes ken die EXSPACE problemen efficiënt kunnen oplossen (bijvoorbeeld in PSPACE), zijn er wel tal van quantum algoritmes die polynomiaal sneller zijn dan klassieke algoritmes.

Het probleem met EXPSPACE is natuurlijk dat het problemen zijn die al een exponentieel aantal geheugenplaatsen in de probleemlengte nodig hebben om slechts één mogelijk antwoord van het probleem op te schrijven. Waar je met qubits wellicht dingen in minder tijd kunt doen, omdat je meerdere oplossingen tegelijk op kunt schrijven, zul je voor EXPSPACE problemen gewoon een exponentieel aantal qubits aan ruimte nodig hebben om een enkel antwoord te representeren. Dat lijkt mij dus eigenlijk nog vele malen onwaarschijnlijker dan het instorten van PSPACE naar P of BQP.

[elleP]

Net even gecontroleerd, als ik naar mijn server ssh gebeurt de host-authenticatie als met elliptic-curve Diffie-Hellman.
Nog voor de quantum computer er is beginnen we gelukkig al minder afhankelijk te worden van factorisatie.

[Pther]

Helaas is elliptic-curve diffie-hellman (via discrete logaritmes) net zo gevoelig voor quantum-algoritmes.
Een overzichtje van wat voorlopig wel blijft werken, maar die vind je voorlopig nog niet in SSH: http://en.wikipedia.org/wiki/Post-quantum_cryptography.

[Anoniem: 532065]

Hoi Kvaruni
Nog een correctie op het deel van je post waar je schrijft: "het algoritme van Shor is een voorbeeld van een NP-hard probleem".

Een "algoritme" is geen "probleem". Het integerfactorisatie-probleem zit in de complexity-class BQP, want het kan in polytime op een quantumcomputer worden opgelost, maar is zeer waarschijnlijk niet NP-hard: http://research.microsoft...n/Thoughts/factoring.html

[kvaruni]

Je hebt natuurlijk gelijk. Een nauwkeurigere formulering is:

"het algoritme van Shor is een voorbeeld van een algoritme dat gebruikt kan worden om in polynomiale tijd een probleem, dat momenteel in de klasse NP zit, op te lossen" .

Er bestaat inderdaad geen bewijs dat het NP-hard is, m.a.w. het kan zijn dat er ook zonder een quantum computer een algoritme in polyniale tijd gevonden kan worden.
Maar er bestaat ook geen bewijs dat het niet in NP zit, en de link die je geeft is natuurlijk ook maar (beredeneerd) giswerk. Op dezelfde manier kunnen we niet zeggen dat P=NP, maar omdat nog niemand er in geslaagd is om een algoritme te vinden in P om een NP probleem op te lossen gaan we er normaal gezien van uit dat P!=NP. Factorisatie is wel een probleem dat niet stevig verankert zit in NP, aangezien het niet NP-compleet is. Dit kan inderdaad betekenen dat het in P zit, maar kan evengoed betekenen dat het in NP unie coNP zit.

bedankt voor de opmerking!

[Reactie gewijzigd door kvaruni op 23 juli 2024 09:27]

[daaf89]

Leuk artikel, ik heb zelf enkele maanden geleden een vergelijkbaar iets geschreven voor een opdracht. Wel iets korter i.v.m. een woordlimiet. Wat ik zelf alleen nogal mis is het algoritme van Grover. In mijn ogen is dit algoritme ook best iets om naar uit te kijken, zeker voor grotere instanties.

Voor degene die het algoritme niet kennen, even een klein stukje Wikipedia:

Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(log N) storage space (see big O notation). Lov Grover formulated it in 1996.

In models of classical computation, searching an unsorted database cannot be done in less than linear time (so merely searching through every item is optimal). Grover's algorithm illustrates that in the quantum model searching can be done faster than this; in fact its time complexity O(N1/2) is asymptotically the fastest possible for searching an unsorted database in the linear quantum model.[1] It provides a quadratic speedup, unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts. However, even quadratic speedup is considerable when N is large. Unsorted search speeds of up to constant time are achievable in the nonlinear quantum model.[2]

Like many quantum algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with high probability. The probability of failure can be decreased by repeating the algorithm. (An example of a deterministic quantum algorithm is the Deutsch-Jozsa algorithm, which always produces the correct answer.)

[.oisyn]

Leuk artikel, maar nu kan ik geen +3'tjes meer scoren in artikelen over quantum computing

Wel een paar opmerkingen though:

Een jaar geleden verwierf de Delftse onderzoeksgroep van Leo Kouwenhoven wereldfaam met de ontdekking van het Majoranadeeltje. Behalve voor het Standaard Model heeft dit deeltje in het bijzonder waarde voor ontwikkelaars van kwantumsystemen.

Het deeltje heeft geen enkele waarde voor het Standaard Model, om het simpele feit dat het helemaal geen echt deeltje is. Het is een denkbeeldig deeltje (zoekwoord: quasi particle of quasideeltje) gemodelleerd naar de eigenschappen van zijn omgeving. Simpel voorbeeld: een electrische stroom bestaat uit bewegende electronen langs een rij atomen. Elke keer dat er een electron bij een atoom ontsnapt om naar de andere atoom over te springen, ontstaat er een gat dat wordt opgevuld door het volgende electron. Je zou op die manier kunnen zeggen dat het gat "beweegt" in omgekeerde richting. Dat gat is positief geladen (vanwege het normaal neutrale atoom waar nu een electron mist). Eigenlijk kun je dus net doen alsof dat gat een positief geladen deeltje is (nee geen positron, die bestaat echt). Er is eigenlijk helemaal geen deeltje, maar voor het gebruikte model maakt het geen verschil.

Het onlangs ontdekte majoranadeeltje is precies zo. Het is niet een echt bestaand deeltje, het is een combinatie van bestaande deeltjes met bepaalde kwantummechanische eigenschappen dat zich als totaalsysteem exact zo gedraagt als het in theorie voorspelde majoranadeeltje. Aangezien het Standaard Model alleen fysieke deeltjes beschrijft, heeft het majoranadeeltje dus geen enkele waarden voor dat SM. Het onlangs ontdekte "deeltje" kun je ook niet beschrijven als hét majoranadeeltje, aangezien er wel meer situaties kunnen bestaan waarbij hetzelfde effect optreedt. Overigens zou de echt bestaande neutrino ook weleens een majoranadeeltje (= een fermion dat zijn eigen antideeltje is) kunnen zijn. En het bewijs daarvan zou dan weer wél van waarde zijn voor het Standaard Model

En uit de inleiding

Daarmee is de inzet van de huidige kwantumcomputers nog beperkt tot heel specifieke toepassingen, zoals cryptografie.

Kwantumcryptografie en kwantumcomputatie zijn twee compleet verschillende dingen. Voor kwantumcryptografie is geen kwamtumcomputer nodig, maar simpelweg een manier om de kwantum staat van deeltjes uit kunnen wisselen - een kwantum communicatiekanaal. Dit kan bijv. door verstrengeling of simpelweg het fysiek versturen van een deeltje in een bepaalde kwantum staat. Niet te verwarren met het kraken van traditionele encryptie, waar weer wel een kwantumcomputer voor nodig is.

[Reactie gewijzigd door .oisyn op 23 juli 2024 09:27]

[ELopesCardozo]

Een prima verhaal, dat nog maar eens laat zien dat tweakers.net zich niet tevreden stelt met het overschrijven van persberichten. Qualtum computing uitleggen is erg lastig, omdat je het moet hebben over dingen die volkomen tegen onze intuïtie en ervaring in gaan. In LAN Magazine (r.i.p.) heb ik ook eens een poging gedaan, zij het met een heel andere insteek: Hoe 'rekenen' gewone computers? Antwoord: doordat we het gedrag van elektronische schakelingen interpreteren als manipulatie van getallen, woorden, etc. De transistors zijn gewoon analoge versterkers, die we zwaar oversturen om de output vervolgens nul of één te noemen. Quantum computers zijn ook schakelingen, maar met componenten die zich volgens de wetten van de quantummechanica gedragen. En ook daar kunnen we een interpretatie op plakken, waardoor dat gedrag voor ons iets betekent, zoals het heel snel vinden van de factoren van een groot priemgetal. Voor wie het nog eens na wil lezen: http://aranea.nl/images/stories/media/almelc0910.pdf.

[JeftaDotEU]

Interessant artikel, ik dacht dat kwantumcomputers gewoon veel sneller waren maar ze hebben dus een gigantische meerwaarde!

[Anoniem: 126717]

Interessant artikel, ik dacht dat kwantumcomputers gewoon veel sneller waren maar ze hebben dus een gigantische meerwaarde!

In bepaalde omstandigheden worden ze door desktops er uitgerekend. Dit BBC artikel bericht daarover.

In some tests devised by a team of researchers, the commercial quantum computer has performed no faster than a standard desktop machine.
The team set random maths problems for the D-Wave Two machine and a regular computer with an optimised algorithm.
Google and Nasa share a D-Wave unit at a space agency facility in California.
The comparison found no evidence D-Wave's $15m (£9.1m) computer was exploiting quantum mechanics to calculate faster than a regular machine.

[Kevinp]

De desktop is natuurlijk wel erg lang uit ontwikkeld. Je vergelijkt dan appels met peren. 10 jaar na de introductie moet blijken of dit echt veel sneller is.

Overigens statements dat decrypten beter gaat en wordt lijkt me sterk. Want als evenredig zware encryptie gebruikt is dat probleem weer terug.

In de korte tijd dat de instelling zo'n ding goed werkend heeft en de rest nog desktops gebruikt misschien wel.

Maar na een paar jaar doorontwikkeling en daardoor mogelijk encryptie mbv deze dingen komt het gewoon weer terug.

[bwerg]

Overigens statements dat decrypten beter gaat en wordt lijkt me sterk. Want als evenredig zware encryptie gebruikt is dat probleem weer terug.

Het probleem is dat de complexiteit van berekeningen met cryptosystemen totaal anders is dan op een klassieke computer. Op de klassieke computer is encryptie relatief licht en snel uit te voeren (je wil geen jaar wachten voordat je over SSL kan communiceren), maar hooguit een seconde). Decryptie zonder sleutel kost echter jaren omdat het een hogere complexiteit heeft, zodat niemand mee kan lezen.

Bij quantumcomputing is het verschil tussen encryptie en decryptie veel kleiner. Als evenredig zware encryptie wordt gebruikt helpt dat helemaal niets: jij wil nog steeds hooguit 1 seconde wachten bij gebruik van een SSL-verbinding, en een aanvaller met een quantumcomputer kan dat binnen korte tijd kraken. Natuurlijk kun je een encryptie bedenken die 10 jaar kost om te kraken, maar dat zal jou dan ook 10 jaar kosten om te gebruiken. Veel plezier met internetbankieren dan.

Een quantumcomputer versnelt namelijk alleen decryptie, geen encryptie. Maar er zijn vast public-key cryptosystemen te bedenken waarin dit niet zo is, die werken op dit moment alleen nog niet zo goed...

[Reactie gewijzigd door bwerg op 23 juli 2024 09:27]

[mrlammers]

Decrypten kan heel snel; ook met heel complexe sleutels. snelheid is geen issue als je de sleutel hebt. Maar als je 'm niet hebt...

Kwantumcomputers zouden, als ze er eenmaal zijn, veel encryptie razendsnel kunnen kraken.

Dat ligt helemaal aan het type kwantumcomputer en het type encryptie.
Een kwantumcomputer met 4 qubits zal het niet sneller doen dan met 2, omdat je naar qubits moet kijken als 'geheugen' en niet als processing units. Stel, je laat een kwantumcomputer een brute-force aanval uitvoeren. Waar de klassieke computer dan O(N) trials nodig heeft, kan de kwantumcomputer het in O(√N).
De processing tijd neemt wel af als grotere sleutels in één keer in het register passen.

256-bit AES encryptie is sterk. En een brute force aanval met 50 supercomputers zouden 10^18 AES keys per seconde kunnen checken. Maar zelfs als zo'n apparaat gemaakt zou kunnen worden, duurt het nog 3×10^51 jaar om alle 256-bit key space te checken!
Een 256-bit AES sleutel zal door kwantumcomputers sneller gevonden kunnen worden, maar dat hangt dus helemaal af van de key space. Optimaal is 'de kwantumcomputer', zonder parallelle bewerkingen nog steeds ongeveer 29400000000000000000 jaar bezig om de 256-bit space door te werken.

Als het dan toch tijd wordt voor een nieuwe sleutel, hoe klinkt 1024-bit AES dan? Of misschien een heel nieuw type sleutel; kwantum encryptie. Ik zie in elk geval voldoende encryptie mogelijkheden om ook kwantumcomputers voorlopig even bezig te houden.

[.oisyn]

Jij hebt het hier over het brute force kraken. Dat kan met een QC inderdaad in O(√N) door de toepasing van Grover's Search. Echter, voor je die AES encryptie toepast zul je eerst sleutels uit moeten wisselen. Het is een symmetrische encryptie, dus voor encryptie en decryptie wordt dezelfde sleutel gebruikt. Deze sleutel is meestal random, en wordt doormiddel van public key cryptografie uitgewisseld. Dit gebeurt veelal met algoritmes zoals RSA en ECC, en nou wil het feit dat je daarvan met een kwantum computer de private key kan bepalen aan de hand van de public key in O(log³ N)[/] tijd.

O(log³ N) is véél sneller dan O(√N) (2x zoveel bits kost maar 8x zoveel tijd)

[Reactie gewijzigd door .oisyn op 23 juli 2024 09:27]

[VictordeHolland]

*Zet alu-hoedje op: dan moet de NSA geen backdoor in de standaard hebben ingebouwd.

[Rygir]

Maak daar maar een ordinaire katoenen pet van, iedereen weet onderhand wel hoe de vork aan de steel zit.

[Bonez0r]

Okee, 10 jaar wachten op een verbinding is wat veel, maar wat als je er bijvoorbeeld 1/10 seconde van maakt. Als encrypted verbindingen standaard worden (en daar gaan we dacht ik wel naartoe) en een organisatie wil alles decrypten van elke internetgebruiker, dan zijn ze alsnog lang bezig, ook met een quantumcomputer.

[MAX3400]

Ze hebben potentieel een gigantische meerwaarde; het aantal kwantumcomputers wat op dit moment grote winst levert aan technische of wetenschappelijke doelen is zo goed als 0; "de mensheid" heeft op dit moment dus nog erg weinig aan kwantumberekeningen.

Het bedrijf ID Quantique, zoals gemeld op de laatste pagina, verkoopt zeer kleine modules die worden gebruikt voor het genereren van random numbers. Nou hoeft dit niet per se met een kwantumcomputer maar het is mogelijk wel sneller en nog meer random. Neemt niet weg dat de grote afnemers allemaal in de gokwereld zitten waar de trend is om de klant zoveel mogelijk random numbers voor te schotelen teneinde een zo groot mogelijke winstmarge te halen.

/edit: zijdelings, weet iemand waarom de modules van ID Quantique alleen op 4Mbit of 16Mbit werken? Toen ik het las moest ik meteen aan token-ring snelheden denken en ik vind de snelheden wel heel erg toevallig.

[Reactie gewijzigd door MAX3400 op 23 juli 2024 09:27]

[Jefrey Lijffijt]

"Ze hebben potentieel een gigantische meerwaarde; het aantal kwantumcomputers wat op dit moment grote winst levert aan technische of wetenschappelijke doelen is zo goed als 0"

Het aantal quantumcomputers dat voor praktische doeleinden wordt gebruikt is 0, want D-Wave heeft geen general-purpose quantumcomputers. Hun machines kunnen quantum-annealing uitvoeren, en het is nog twijfelachtig of hij ook maar 1 ding sneller kan dan een cluster intel-cpu's dat veel minder geld kost.

Er zijn overigens wel general-purpose quantumcomputers, maar die hebben te weinig bits om van praktisch nut te zijn, wiskundige problemen die we daar mee kunnen oplossen kun je op een desktop ook exact oplossen via enumeratie. Voorlopig weten we dus nog steeds niet of het echt mogelijk is om een quantumcomputer te maken die grote NP-complete problemen oplost.

Oud nieuws hierover.

Nieuws van gisteren nota bene op Nu.nl.

[emnich]

Neemt niet weg dat de grote afnemers allemaal in de gokwereld zitten waar de trend is om de klant zoveel mogelijk random numbers voor te schotelen teneinde een zo groot mogelijke winstmarge te halen.

Het gaat niet om de winstmarge want die bepaal je met een (ingestelde) winkans. Het gaat om de (on)voorspelbaarheid zodat er geen fraude/misbruik kan plaats vinden.

[Epsix]

Neemt niet weg dat de grote afnemers allemaal in de gokwereld zitten waar de trend is om de klant zoveel mogelijk random numbers voor te schotelen teneinde een zo groot mogelijke winstmarge te halen.

Deze opmerking is vergelijkbaar als dat je 60 jaar geleden zou hebben gezegd: computers zijn alleen handig om snel sommetjes mee uit te voeren (aka een rekenmachine).

Toen de turing machine werd bedacht kon men ook niet bedenken dat we nu MMORPG's, pornosites, digitale valutas en rij assistentie zouden hebben.

De volledige potentie van de quantumcomputer is zelfs qua rekenkracht nog niet duidelijk. Laat staan wat voor toepassingen het mogelijk maakt.

[MPAnnihilator]

Uit het artikel : " een meting aan de een bepaalt bij de ineenstorting sneller dan het licht de waarde van de ander"

en ik die dacht dat niets sneller was dan het licht... hoe geven die dat dan aan mekaar door aan een snelheid groter dan het licht als er niets sneller is dan het licht zelf

[Goderic]

Informatie kan niet sneller dan het licht verstuurd worden, dingen die geen informatie overbrengen (zoals kwantumverstrengeling) kunnen zonder problemen sneller dan het licht gaan.

[360Degreez]

Nice! Da's een lekker snel draadloos netwerkje dan..

Mijn hoofd tolt nog een beetje. Maar denkend in de traditionele techniek zou een quantumcomputer bij het spelen van games > renderen van frames, dus parralelle rekenkracht geen noemenswaardige meerwaarde hebben tegenover de huidige (hetzij nog verder geminiaturiseerde) techniek?

[Vettigen_Dr33]

sneller dan het licht is volgens Einstein zijn theorie onmogelijk inderdaad..
maar er zouden wel mogelijkheden zijn om dit te omzeilen (wormgaten, buigen van ruimte)

is het trouwens niet zo dat elektronen die van schil verspringen 'teleporteren'? Dit op zich is sneller dan licht (correct me if I'm wrong )

[page404]

Vergelijk het met een hele felle lichtbundel, die heeft een bepaalde baansnelheid. De lichtbron kun je snel laten draaien, bijvoorbeeld 1000 rpm, waardoor de baansnelheid op een grote afstand op een gegeven moment groter is dan 300000 km/s, en dus groter dan de lichtsnelheid. Dat is op zich geen probleem, omdat het om een projectie gaat en er geen informatie overgedragen wordt.

[Anoniem: 204567]

Precies, als zo'n lichtbundel van A naar B draait beweegt er in feite niets van A naar B, maar reizen er eerst fotonen vanaf de lichtbron naar A (met lichtsnelheid) en een fractie later andere fotonen vanaf de lichtbron naar B (eveneens met lichtsnelheid).

[bed76]

Massa kan niet sneller dan het licht reizen. Massa wordt zwaarder naarmate de snelheid toeneemt, dus dan zou massa dan oneindig zwaar zou worden als de maasa de snelheid van het licht bereikt. Daarom stelt Einstein dat je conventioneel niet sneller kan reizen dan het licht. Ook in het kader van de relativiteitstheorie zou je anders inderdaad kunnen tijdreizen. Stel je kunt sneller reizen dan je naar je klok kunt kijken, dan zou je dus de tijd inhalen. (Simpele uitleg van de relativiteitstheorie)

Als ik het stukje uit het artikel goed begrijp betreft dit geen massa maar een statuswijziging.

[Reactie gewijzigd door bed76 op 23 juli 2024 09:27]

[.oisyn]

Massa kan niet sneller dan het licht reizen

Even voor de goede orde, massa kan ook niet even snel als het licht reizen. De snelheid van het licht is dus een asymptotische bovengrens voor deeltjes met massa die nooit bereikt kan worden. Daarentegen kunnen deeltjes zonder massa alleen maar met de lichtsnelheid bewegen - niet sneller en niet langzamer. En de theoretische tachyon met imaginaire massa kan alleen sneller dan het licht reizen (waarbij de lichtsnelheid dus een asymptotische ondergrens is)

[HesRuud]

Mooi en interessant artikel, maar heeft een qubit niet 3 waarden?
0,1 en alles ertussen?

Dan zou je met 3 qubits niet 8 (2^3) maar 3^3= 27 verschillende waarden hebben.

Edit:
Ok thx Marijn, het is mij nu duidelijk.

[Reactie gewijzigd door HesRuud op 23 juli 2024 09:27]

[Marijn100]

Nee, als je een qubit uitleest zal het altijd 1 of 0 worden. De superposition (alles er tussenin) is er wel maar deze verdwijnt op het moment dat het uitgelezen wordt.
Uitleg over de superposition, https://www.youtube.com/watch?v=MJZv17mW1Hg

[Reactie gewijzigd door Marijn100 op 23 juli 2024 09:27]

[rberkenpas]

Is dat niet zoiets als Schrödingers Cat?
Het beestje is niet dood en niet levend, maar zodra je de doos openmaakt weet je het zeker. m.a.w. zolang het beestje in de doos zit, en niet geopend is, weet je niet of die dood of levend is (super position), totdat je hem openmaakt (1 of 0)? Of ga ik hier nu heeel erg kort door de bocht?

http://nl.wikipedia.org/wiki/Schr%C3%B6dingers_kat

Edit: link toegevoegd.

[Reactie gewijzigd door rberkenpas op 23 juli 2024 09:27]

[maikel124]

Schrödingers Cat is een experiment dat op eenvoudige wijze duidelijk maakt wat qubits doen, dus ja, het is hetzelfde. Uiteraard verschilt dit in de details nog wel, maar dat is voor een basisbegrip van de concepten ook niet interessant.

[Rygir]

Dat was het gedachte experiment er achter en als het iets duidelijk maakt dan is het wel hoe vreemd de quantum wereld is want volgens ieders intuïtie is de kat ofwel dood ofwel levend maar niet allebei en dat is nochtans net wel wat de quantum wereld zegt.

[Wut]

De kans om het deeltje in een bepaalde toestand aan te treffen kan tussen de gekwantiseerde mogelijke waarden in liggen.
Stel je hebt de twee gekwantiseerde waarden 0 en 1, dan kan de kans om het deeltje aan te treffen tussen 0 en 1 liggen. Het is dus niet zo dat het deeltje zelf tot het gemeten werd zich tegelijkertijd in meerdere toestanden bevond. Het deeltje bevind zich altijd op één plaats in één toestand, we weten alleen niet welke het is tot we het meten.

[simlock]

Maakt niemand zich zorgen over de NSA? Ze zijn speciaal voor het doel encryptie te kraken een kwantumcomputer aan het ontwikkelen!

Dat zou volgens mij het einde van internet betekenen. Bitcoin blockchain kraken, zo gebeurd. Geen enkel paswoord is meer veilig.

[Vettigen_Dr33]

ik denk dat je voor de meeste mensen hier niets nieuw verteld
natuurlijk wilt de NSA dit gebruiken voor hun eigen doeleinden vooraleer dat de gewone mens hiervan gebruik kan maken

ik vermoed dat in de toekomst wanneer kwantumcomputers alom beschikbaar zijn er wel nieuwe encriptie technieken zullen ontwikkeld worden waardoor de situatie vergelijkbaar wordt met de huidige situatie (kraken van encriptie is mogelijk maar kost tijd)

verder vindt ik het terecht dat de praktijken van de NSA en andere overheidsinstanties in vraag worden gesteld maar om nu bij elke ontwikkeling dit onderwerp aan te zwengelen is volgens mij ook wel een beetje iets zeggen om iets te kunnen zeggen...

[angelina]

Je zou het ook in kunnen zetten voor veilige communicatie zodat niemand, inclusief NSA kan aftappen zonder dat je het merkt, want...

controleren door een deel van de zo verkregen bits met elkaar te vergelijken. Komen die bits inderdaad met elkaar overeen, dan weten de partijen zeker dat niemand anders die sleutel heeft. Een man-in-the-middle kan de waarde van een verstrengelde qubit onderweg immers niet achterhalen zonder deze te laten ineenstorten

[Jace / TBL]

Bitcoin blockchain kraken, zo gebeurd.

Bitcoin protocol aanpassen, ook zo gebeurd. Moet je bij reguliere bankprotocollen eens proberen, met al die antieke cobol troep. Dat zou een gigantische onoverzichtelijke klus worden.

[.oisyn]

Dat zou volgens mij het einde van internet betekenen. Bitcoin blockchain kraken, zo gebeurd. Geen enkel paswoord is meer veilig.

Passwords hebben er weinig mee te maken, een goede implementatie hasht de wachtwoorden en die gaat een kwantumcomputer niet ineens makkelijk omdraaien. Wat betreft encryptiealgoritmes, hoewel RSA en ECC efficient omkeerbaar is met een kwantum computer, zijn er nog tal van algoritmes die niet omkeerbaar zijn. Het lijkt me essentieel dergelijke algoritmes zo snel mogelijk op grote schaal toe te gaan passen.

[Pixeltje]

Kwaliteitsartikel, super! Wordt helder uiteengezet en hoewel er gegarandeerd onduidelijkheden of (gedeeltelijke) onjuistheden in staan heb ik het idee dat ik nu veel beter begrijp hoe kwantumcomputers in elkaar steken.

[Anoniem: 174991]

If you think you understand quantum mechanics, you don't understand quantum mechanics.

- Richard Feynman

[bobje99]

Nice one! Ik wilde eigenlijk die van futurama posten:
“Quantum physics means that anything can happen, at any time, for no reason...”
- Hubert J. Farnsworth.

Dat we er met ons verstand niet bij kunnen.. zou dat komen doordat onze technologie nog niet ver genoeg is om het te kunnen verklaren of zou het kunnen dat we Kwantummechanica nooit precies kunnen verklaren?
(bijvoorbeeld dat een deeltje meerdere vormen tegelijk aan kan nemen en dat het 'bekijken' van het deeltje de vorm van het deeltje beïnvloed)

[roel0]

Die quantis (random nummer genereren) zou alleen al de wereld rond ons kunnen veranderen. Stel je voor dat dit een basiscomponent wordt in elke smartphone en computer.
Vergeet niet dat Android bijvoorbeeld, veel moeite heeft gehad met random getallen.

En dan verzwijg ik nog maar even de mogelijkheid tot security met echte random getallen. Maar zover zijn we nog niet, €1000 voor het huidig USB kastje. Dat zie ik nog niet standaard in elke elektronische component zitten.

[Anoniem: 174991]

Een of andere blogpost is niet voldoende substantie om te claimen dat Android veel moeite zou hebben. Gelukkig legt een Android ontwikkelaar het uit.

https://code.google.com/p/android/issues/detail?id=42265

i don't know why you think this is anything to do with dalvik (or libcore). neither touches /dev/random. java.util.Random is just a PRNG seeded from the clock. java.util.SecureRandom uses /dev/urandom.

Vergeet dus maar dat Android veel moeite zou hebben met (pseudo) random nummers.

Voor de meeste toepassingen zoals SSL volstaan pseudo-random nummers prima en er is een aantal alternatieven om meer random nummers te genereren. Denk aan de achtergrond straling of radioactief verval i.c.m. een Geiger teller.