Kwantumcomputers komen eraan

Op de kleinste deeltjes kun je rekenen

Inleiding

Kwantumcomputing is een relatief jong onderwerp binnen de computerwetenschap. De eerste onderliggende concepten werden dertig jaar geleden geïntroduceerd door de beroemde natuurkundige Richard Feynman. In de tussenliggende tijd hebben we veel geleerd over het programmeren van kwantumcomputers en inmiddels kunnen we ook verstandige dingen zeggen over de theoretische rekenkracht ervan. In het afgelopen decennium hebben veel universiteiten kwantumcomputing dan ook als vak opgenomen in hun curricula.

Ondanks al die verworvenheden is er een cruciaal onderdeel op dit gebied dat we nog steeds niet onder de knie hebben: het daadwerkelijk bouwen van een kwantumcomputer. De qubits die de hardwarebasis moeten vormen onder deze nieuwe systemen, zijn nog niet in voldoende aantallen te maken en ook niet lang genoeg houdbaar om er grotere kwantumtoepassingen op te draaien. Op dit moment kan ongeveer een handvol bruikbare qubits tegelijk worden gemaakt en overleven ze niet langer dan een paar seconden. Daarmee is de inzet van de huidige kwantumcomputers nog beperkt tot heel specifieke toepassingen, zoals cryptografie.

De NSA ziet dat ook in en is begonnen met een eigen onderzoeksproject om een werkende kwantumcomputer te maken, met een budget van omgerekend 58 miljoen euro. Kwantumcomputers zouden, als ze er eenmaal zijn, veel encryptie razendsnel kunnen kraken. Maar wat is kwantumcomputing eigenlijk? In dit artikel gaan we dieper in op deze vraag.

(c) CyberHades (via Flickr)

Bits, qubits en superposities

Bits

Een qubit, kort voor quantum bit, is als bouwsteen van de kwantumcomputer vergelijkbaar met de gewone bit, die de basis vormt van al onze huidige computertechnologie. Naast de vele parallellen zijn er echter ook cruciale verschillen.

Gewone bits of binary digits kunnen alleen de waarde 0 of 1 hebben. Hoe een bit vervolgens in een computer wordt geïmplementeerd, is in principe onafhankelijk van de logische waarde ervan. Zo wordt digitale informatie in computerchips overgedragen en bewerkt door middel van signalen van verschillende spanningsniveaus, bijvoorbeeld 0 en 1,2 volt.

Ook in traditionele geheugens en op verbindingskabels wordt met verschillende spanningen gewerkt. Ouderwetse harde schijven daarentegen maken gebruik van magnetische polarisatie om dezelfde digitale informatie op te slaan. Zo zou je net zo goed een computer kunnen bouwen die met waterdruk en kleppen, met mechanische onderdelen of met knikkers, rolbanen en poortjes werkt. De logische principes van de eerste digitale computers waren ook niet anders dan die van de huidige machines, alleen werden in plaats van transistoren eerst relais (elektromagnetische schakelaars) en later vacuümbuizen, de voorlopers van de transistor, gebruikt.

In de praktijk hebben ontwerpers voor de opslag, overdracht en bewerking van digitale informatie voor elk onderdeel een implementatie gekozen die aansluit bij de toepassing, de benodigde snelheid en capaciteit, en het beschikbare budget. Al die afwegingen zien we bijvoorbeeld terug in de geheugenhiërarchie van een systeem.

Qubits

Qubits zijn fundamenteel anders dan gewone bits. Ze zijn ontwikkeld volgens de kwantummechanica, waar rekeneenheden niet alleen de waarde 0 of 1 kunnen aannemen, maar ook een beetje de ene waarde en tegelijk een beetje de andere waarde. Een qubit kan bijvoorbeeld voor de ene helft de waarde 0 hebben en voor de andere helft de waarde 1, of voor twee derde de waarde 0 en voor één derde de waarde 1.

De waarde van een qubit kan tegelijk een beetje 0 en een beetje 1 zijn

Voor wie bekend is met statistische kansverdelingen, is een qubit te vergelijken met een stochast. Ook daarvan is de waarde zelf niet exact bekend; je weet alleen iets over de kansverdeling ervan. Een cruciaal verschil tussen een stochast en een qubit is dat die eerste een probabilistisch of statistisch concept is en die laatste een kwantummechanisch concept. Dat betekent dat de waarde van een stochast weliswaar niet precies bekend is, maar dat wel voor elke mogelijke waarde vaststaat hoe groot de kans daarop is. Terwijl de waarde van een qubit tegelijk een beetje 0 kan zijn en een beetje 1. Bij kwantumcomputers spreekt men dan ook niet van kansverdelingen maar van superposities.

Superposities

De kracht van die superposities wordt duidelijker als we verschillende qubits bundelen tot een reeks, op vergelijkbare wijze als waarop in de traditionele deterministische wereld bits worden samengepakt tot bytes. Kijken we bijvoorbeeld naar een rijtje van drie gewone bits, dan kan dat een van acht verschillende waarden aannemen: 000, 001, 010, 011, 100, 101, 110, 111.

Drie gebundelde qubits hebben tegelijkertijd een beetje van elk van deze acht waarden. Hoewel de echte kwantumcomputeraars dit slordig zouden vinden, noteren we de fracties voor de acht verschillende waarden bijvoorbeeld als volgt: 1/4, 0, 0, 1/4, 0, 1/2, 0, 0. Dat betekent dat de drie qubits voor een kwart de waarde 000 hebben, voor een kwart de waarde 011 en voor de helft de waarde 101.

Zoals in de uitweiding over golffuncties op de volgende pagina wordt uitgelegd, zijn stochasten en qubits wiskundig gezien niet gelijkwaardig. In een superpositie kunnen de fracties namelijk ook negatief zijn. Juist die operaties maken berekeningen mogelijk die, zeer waarschijnlijk, niet met een klassieke machine uitgevoerd kunnen worden.

Genormaliseerde golffuncties en amplitudes

Genormaliseerde golffuncties

Hoewel de afzonderlijke kansen net als bij stochasten opgeteld een totaal van 1 moeten vormen, zijn stochasten en qubits wiskundig gezien niet gelijkwaardig. Met deze eerste beschrijving van een qubit doen we de onderliggende kwantummechanica dan ook ernstig tekort. In werkelijkheid moeten we de status van een qubit namelijk beschrijven met een zogenoemde genormaliseerde golffunctie.

Voor de natuurkundig geïnteresseerden: golffuncties beschrijven de kwantummechanische toestand van de subatomaire deeltjessystemen waarop kwantumcomputers gebouwd worden. Denk dan aan de elektronen en fotonen die we al kennen uit het atoommodel van Bohr, later verfijnd in het Standaardmodel, waarin we inmiddels tientallen verschillende smaken quarks, leptonen en bosonen aantreffen.

De toevoeging 'genormaliseerd' wil niet meer zeggen dan dat die golfvergelijking zodanig is geschaald dat het totaal van alle kansen op een specifieke waarde, oftewel de kansmassa, inderdaad gelijk is aan 1.

Amplitudes

De golffunctie specificeert voor elke afzonderlijke waarde van een qubit, 0 en 1, een complex getal, de amplitude, waaruit vervolgens weer de kans op deze waarde kan worden afgeleid. Hieronder zie je de golffunctie voor een enkele qubit staan.

Omdat de amplitudes, alfa en bèta, complexe getallen zijn, zijn er verschillende onderliggende kwantummechanische toestanden, die wel allemaal dezelfde kansverdeling hebben. Een cruciaal verschil met de stochastische wereld is dat de fracties berekend worden door de complexe amplitudes te kwadrateren en dat deze dus ook negatief kunnen zijn. Zodra we een superpositie proberen te bekijken (meten), neemt deze een van zijn niet-kwantummechanische, deterministische waarden aan. We noemen dat het ineenstorten van de superpositie. Op dat moment verandert de kwantummechanica dus in statistiek.

Rekenkracht, kansverdeling en kwantumberekening

Rekenkracht

Superposities maken het mogelijk om met een heleboel waarden tegelijk te rekenen. Voor één qubit zijn dat twee waarden: 2^1, 0 en 1, voor drie qubits zijn dat acht verschillende waarden: 2^3, en voor tien qubits zijn dat al 1024 verschillende waarden: 2^10. In wiskundige termen, het aantal verschillende waarden dat een superpositie tegelijk kan bevatten is exponentieel ten opzichte van het aantal qubits en dat is precies waar de extra rekenkracht van de kwantumcomputer zijn oorsprong vindt.

Het antwoord van een kwantumberekening kan echter meestal niet direct uitgelezen worden. Zodra je een superpositie bekijkt, stort deze immers ineen tot een van de concrete waarden binnen die superpositie. Op dat moment wordt de overgang van de kwantummechanische naar de statistische wereld gemaakt. Welke specifieke waarde die ineenstorting oplevert, kun je op voorhand niet weten. Wel is het zo dat voor elke bitwaarde de kans dat zij optreedt, overeenkomt met de grootte van zijn gekwadrateerde amplitude, wat we op de vorige pagina de fractie noemden.

Kansverdeling

Dat betekent dat je een kwantumberekening meer dan eens moet uitvoeren, waarna je de kwantummechanische waarde van de laatste superpositie terug kunt afleiden uit de onderlinge verhoudingen van alle verschillende concrete antwoorden die je hebt gemeten. Deze komen immers overeen met de kansverdeling van die superpositie. Een goed kwantumalgoritme leidt dus tot een superpositie waarin het antwoord is verborgen in de kansverdeling. Dat kan bijvoorbeeld betekenen dat op een bepaalde qubit in een derde van de gevallen de waarde 0 gemeten wordt en in twee derde van de gevallen de waarde 1. De kans dat je zo inderdaad het juiste antwoord vindt, is eenvoudig te vergroten door de kwantumberekening vaker uit te voeren.

Zodra je een superpositie bekijkt, stort deze ineen

Kwantumtheoretici hebben inmiddels slimme algoritmen ontwikkeld, waarbij alleen de juiste berekeningen en ondubbelzinnige antwoorden overblijven. Daarbij maken ze onder andere gebruik van interferentie. Op die manier hoeft een berekening nog maar één keer uitgevoerd te worden om direct het goede antwoord te geven.

Kwantumberekening

Bewerkingen op qubits verlopen ook heel anders dan de operaties die we kennen uit de deterministische wereld. Gewone bits worden steeds op logische wijze met elkaar vergeleken: 'Hebben twee bits allebei de waarde 1 (AND), heeft minstens een van de bits de waarde 1 (OR), hebben alle bits de waarde 0 (NOR)?' enzovoort. Die logische operaties worden uitgevoerd op elektrische signalen door transistors die in siliciumchips zijn vastgelegd en in een bepaald patroon met elkaar zijn verbonden. Zo worden logische poorten gecombineerd tot registers, rekeneenheden, state machines en alle andere digitale onderdelen die tezamen bijvoorbeeld een processor vormen.

Berekeningen door een kwantumcomputer worden altijd binnen dezelfde groep qubits uitgevoerd. Een superpositie kan niet worden gekopieerd of beter gezegd, bij het kopiëren gaat het origineel verloren. Een bewerking verandert dus de bestaande superpositie. Net als voor klassieke digitale systemen zijn er ook voor kwantumcomputers basisoperaties waarmee alle berekeningen uitgevoerd kunnen worden.

Modellering en berekenbaarheid

Modellering

Er zijn diverse manieren om kwantumbewerkingen te modelleren. De analytisch-wiskundige theorie is gebaseerd op de eerder beschreven golffuncties: lineaire combinaties van basiswaarden (notatie: |0> en |1>), met complexe coëfficiënten, de amplitudes.

De bol van Bloch vormt dan een meetkundige representatie van een enkele qubit. Aan de bovenkant en onderkant zijn respectievelijk de waarden |0> en |1> weergegeven. Een superpositie is een punt ergens op het oppervlak van de bol, waarbij de hoogte (de breedtecirkel) de verhouding van de amplitudes en dus de kansen van de twee basiswaarden bepaalt. Dat het superpositiepunt per se ergens op het oppervlak van de bol rond de z-as moet liggen, met een vaste afstand tot de oorsprong, is het gevolg van de randvoorwaarde dat de som van de kansen altijd 1 is. In deze modellering bestaan (eenvoudige) kwantumbewerkingen uit meetkundige rotaties, verplaatsingen van het superpositiepunt over het boloppervak.

Voor techneuten is het natuurlijk veel handiger om over kwantumbewerkingen te praten in de bekende termen van poorten en circuits. Barenco heeft symbolen ontwikkeld die gebruikt kunnen worden om bewerkingen vast te leggen in diagrammen. Hieronder zie je bijvoorbeeld een 'Controlled NOT'-poort (CNOT). De negatieoperatie (|0> wordt |1> en andersom) op de onderste qubit wordt alleen uitgevoerd als de bovenste qubit de waarde |1> heeft.

Hoewel naarstig gezocht wordt naar verschillende, natuurkundige, implementatievormen om deze kwantumoperaties daadwerkelijk te kunnen uitvoeren, is ondersteuning van de volledige reeks niet noodzakelijk. Net zoals je in de traditionele informatica aan bijvoorbeeld een AND-poort en een NOT-poort genoeg hebt om alle schakelingen te kunnen bouwen, zijn voor een kwantumcomputer drie poorten voldoende.

Berekenbaarheid

Naar aanleiding van de honderdste geboortedag van Alan Turing publiceerden we medio 2012 al een uitgebreid verhaal over Turing-machines en de theorie van berekenbaarheid en complexiteit van problemen en algoritmen. Om op een vergelijkbare manier over de rekenkracht van kwantumcomputers te kunnen praten, heeft de natuurkundige David Deutsch de Quantum Turing Machine bedacht. Op vergelijkbare wijze is er een klasse van problemen gedefinieerd die met een kwantumcomputer in een redelijke tijd op te lossen zijn. Dat wil zeggen, in polynomiale tijd ten opzichte van de lengte van de input.

De figuur hiernaast laat zien hoe deze klasse BQP of Bounded Error Quantum Polynomial Time zich verhoudt tot de traditionele complexiteitsklassen. Althans, voor zover we dat nu denken te weten.

Hoewel dat nog niet bewezen is, zoals overigens voor de meeste relaties tussen de verschillende complexiteitsklassen geldt, lijkt het erop dat kwantumcomputers inderdaad problemen kunnen oplossen die we met de huidige deterministische computers, klasse P, niet aankunnen. Sterker nog, inmiddels zijn er al diverse kwantumalgoritmen bekend voor problemen waarvoor nog niemand een deterministisch algoritme heeft kunnen bedenken. Aan de andere kant heeft nog niemand een kwantumalgoritme gevonden waarmee ook de moeilijkste problemen, in de klasse NP Compleet, in redelijke tijd oplosbaar worden. Het vermoeden is op dit moment dan ook dat kwantumcomputers fundamenteel krachtiger zijn dan gewone computers, maar ook weer niet zo krachtig dat ze de moeilijkste problemen voor ons oplossen.

Algoritme van Shor

Een van de interessantste kwantumalgoritmen die we nu kennen, is het algoritme van Shor, gebaseerd op kwantum-Fouriertransformaties. Daarmee kunnen de priemfactoren van een integer worden berekend. Deze factorisatie kan worden ingezet om een groot deel van de asymmetrische (public-key-) cryptografie die we nu op internet gebruiken, te kraken. Meest in het oog springend is de tls/ssl-beveiliging, die bij https en starttls wordt gebruikt. Hetzelfde geldt echter ook voor ssh en alle protocollen die via deze versleutelde verbindingen worden getunneld, en voor elektronische handtekeningen.

Zodra de eerste, echt bruikbare kwantumcomputer het licht ziet, zijn al deze beveiligingen in één klap waardeloos. De huidige public-key-technologie is namelijk gebaseerd op de moeilijkheid om het product van twee grote priemgetallen in zijn factoren te ontleden. Hoewel die kwantumcomputer nog niet bestaat, is het dus van cruciaal belang om nu al te werken aan de wiskundige theorie voor deze machines. Bijvoorbeeld om kwantum-proof algoritmen te vinden voor een nieuwe vorm van public-key-cryptografie, die wel bestand is tegen kwantumkrakers.

Verstrengeling

Was je al verbijsterd over superposities die tegelijk een beetje de ene waarde en een beetje de andere waarde aannemen, dan doet verstrengeling, entanglement, daar nog een schepje bovenop. Als ze eenmaal verstrengeld zijn, hoeven qubits niet meer bij elkaar in de buurt te zijn om zich toch als één superpositie te blijven gedragen. Veranderingen aan de ene qubit hebben direct consequenties voor de andere qubit. Sterker, een meting aan de een bepaalt bij de ineenstorting sneller dan het licht de waarde van de ander, in tegenstelling tot bijvoorbeeld de elektromagnetische en zwaartekrachtvelden in de klassieke mechanica, die zich met de snelheid van het licht uitbreiden.

Kwantumbeveiliging met een Nederlands tintje

Kwantumcomputers maken ook nieuwe beveiligde communicatiemethoden mogelijk. Kwantummechanische verstrengeling kan bijvoorbeeld gebruikt worden om absoluut veilige communicatiekanalen op te zetten. Informatie kan onderweg niet worden afgeluisterd door een man-in-the-middle zonder dat dit aan de uiteinden van de verbinding te zien is.

Het Majoranadeeltje zou een geschikte bouwsteen voor de qubits kunnen zijn

Hiertoe wordt eerst een serie paarsgewijs verstrengelde qubits over de twee partijen verdeeld, quantum key distribution, om die vervolgens te laten ineenstorten tot hun definitieve waarde. Beide partijen hebben nu dezelfde, of nauwkeuriger gezegd, tegenovergestelde sleutel. Ze kunnen dat 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. Op deze manier wordt het distributieprobleem voor symmetrische sleutels opgelost. Dat is waarvoor asymmetrische cryptografie vaak wordt ingezet: het veilig uitwisselen van een symmetrische sessiesleutel.

Belangrijke kanttekening hierbij is dat dergelijke kwantumsystemen wel kunnen worden gebruikt om sleutels uit te wisselen, maar niet om sneller dan het licht te communiceren. De ineenstorting aan twee zijden gebeurt inderdaad sneller dan het licht, maar doordat de concrete uitkomst door het toeval wordt bepaald, kan daarbij geen informatie worden overgedragen.

Wetenschappelijk onderzoek

In de afgelopen jaren zijn her en der bij universiteiten en andere onderzoeksinstellingen de eerste kwantumnetwerken gebouwd waarmee verstrengelde communicatiekanalen en teleportatie van kwantumtoestanden mogelijk worden. Zo lieten onderzoekers uit het Britse Cambridge vorig jaar zien dat het mogelijk is om verstrengelde fotonen via een regulier glasvezelnetwerk te verspreiden.

In Nederland wordt theoretisch onderzoek naar kwantumalgoritmen en complexiteit uitgevoerd door het CWI. Daar draait een groep onder leiding van Harry Buhrman mee met de wereldtop op dit gebied. Andere belangrijke onderzoeksgroepen bevinden zich in Zürich (ETH), Oxford en Cambridge in de UK, Cambridge in de VS (MIT), Berkeley, Waterloo (Canada), Singapore en Beijing.

Majoranadeeltjes

Ook wat de onderliggende hardware betreft is Nederland een belangrijke speler. 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 zou namelijk wel eens een geschikte bouwsteen voor de qubits kunnen zijn.

Ook elders in de wereld gebeurt van alles. Tweakers brengt regelmatig nieuws over technische en wetenschappelijke doorbraken op dit gebied. In die berichten kunnen we lezen hoe wetenschappers steeds meer en steeds stabielere qubits kunnen creëren, opslaan en transporteren. Bovendien lijkt het Canadese bedrijf D-Wave inmiddels inderdaad de eerste commerciële kwantumcomputer te kunnen aanbieden.

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.

[Verwijderd]

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!

[Verwijderd]

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.

[Verwijderd]

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.

[Verwijderd]

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.

[Verwijderd]

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.