Første kvantecomputer på en optisk chip
more_vert
close

Få de daglige nyheder fra Version2 og Ingeniøren. Læs mere om nyhedsbrevene her.

close
Ved at tilmelde dig accepterer du vores Brugerbetingelser, og du accepterer, at Teknologiens Mediehus og IDA-gruppen lejlighedsvis kan kontakte dig om arrangementer, analyser, nyheder, job og tilbud m.m. via telefon og e-mail. I nyhedsbreve, e-mails fra Teknologiens Mediehus kan der forefindes markedsføring fra samarbejdspartnere.

Første kvantecomputer på en optisk chip

Så er kvantecomputerchippen klar, melder britiske forskere. De har som de første i verden udført kvanteberegninger i en lille chip, hvor andre hidtil har måttet bruge større opstillinger til formålet.

Fremtidige kvantecomputere vil blandt andet være rigtig gode til at faktorisere tal, der er produktet af to store primtal. Det er en opgave, som er så vanskelig - i praksis umulig - for traditionelle computere, at produkter af store primtal danner grundlag for kryptografi og sikker kommunikation over internettet.

En kvantecomputer kan dog sammen med Eulers teorem udnytte en særlig algoritme udviklet af Peter Shor fra Massachusetts Institute of Technology i 1994 til at faktorisere tal, som er produkt af to primtal.

For store tal kræver det dog mange kvantebits - qubits - så derfor øver alverdens forskere som regel sig i først at lave en simpel beregning, der kun kræver en håndfuld qubits - som for eksempel at faktorisere tallet 15 - ligesom forskerne i Bristol har gjort.

»Ethvert skolebarn, der har lært at opsplitte et tal i faktorer, kan gøre det væsentligt hurtigere end vores computer,« siger ph.d.-studerende Alberto Politi, der sammen med sin medstuderende Jonathan Matthews har udførte eksperimentet under ledelse af professor Jeremy O'Brien.

»Men det er et helt afgørende bevis princippets anvendelighed,« tilføjer han.

I den aktuelle chip kobler forskerne fire fotoner ind og ud af en optisk chip ved hjæp af optiske fibre. Inde i chippen vekselvirker fotonerne med hinanden, der for det første sørger at bringe dem i to entangled tilstande. Entanglement er det kvantemekaniske trick, der gør, at man ikke regner med bits, der enten er "0" eller "1", men med kvantebits, qubits, der både er "0" og "1" på samme tidspunkt.

Dernæst vekselvirker qubits med hinanden i henhold til Shors opskrift, og endelig detekterer de fotoner, som kommer ud af chippen. Tre af de fire output-fotoner, giver direkte en bestemmelse af ordenen for Eulers algoritme (se nederst).

Andre forskere har tidligere lavet kvanteberegninger baseret på Shors algoritme, men det har været i opstillinger, som kun vanskelig kan opskaleres til mange qubits. Ved at udføre hele beregningen på en optisk chip (silica-on-silicon) i form af bølgeledere, der danner flere en-bit eller to-bit qubit gates, åbner der sig et perspektiv for lave endnu mere komplicerede beregninger.

FAKTA: Eulers teorem

Faktorisering af et produkt af to primtal tager udgangpunkt i Eulers teorem fra 1736. For alle relative primtal a og N findes der er en mindste eksponent r, så a^r diveret med N giver en rest på 1 (a^r modulus N er lig med 1). Relative primtal er tal, som ikke har fælles divisorer bortset fra 1 - dvs. 8 og 9 er relative primtal).

Er N= 15 og a=2 ses det, at r=4, og primtalsfaktorer i N findes da som 2^4-1 = 0 (modulus 15). Det kan omskrives til, at (2^2-1)(2^2+1) = 0 (modulus 15) eller 3 x 5 = 0 (modulus 15). Heraf ses primtalsfaktorerne direkte.

Når N er et meget stort tal, som er produkt af to primtal, er den svære opgave af bestemme r. Det er stort set en umulig opgave med konventionelle computere.

Dokumentation

Shors algoritme

sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

Enten har jeg glemt min matematik eller også er artiklen blevet til vrøvl.
At faktorisere produktet af to primtal, kan vel ikke være et problem. Faktorerne er de to primtal!
Senere dukker så, som trold af en æske, relative primtal op, som ikke i sig selv er primtal.
Se at få læst lidt korrektur på den artikel.

  • 0
  • 0

Beklager. Der var lille sproglig detalje i artiklen, der ikke var helt korrekt, som jeg har forsøgt at rette nu.

Men pointen er, hvis man kun ved, at et meget stort tal er produktet at to primtal, så er det uhyre vanskeligt at finde disse to primtal. Så jo, det er vanskeligt at faktorisere et produkt af to primtal med en almindelig computer. Vær glad for det, for ellers havde vi ingen krypeteringssikkerhed ved internettransaktioner i dag.

Begrebet "relative primtal" kaldes på engelsk for "coprimes" eller "relatively prime". Disse tal er ikke (nødvendigvis) primtal i sig selv. Så lige her behøves skam ingen ekstra korrekturlæsning.
Jeg har brugt den danske betegnelse "relative primtal, som også anvendes i denne note:
http://kom.aau.dk/~heb/kurser/NOTER/RSANOT... - se f.eks. side 11 i dette dokument.

  • 0
  • 0

At faktorisere produktet af to primtal, kan vel ikke være et problem. Faktorerne er de to primtal!

Enten misforstår jeg dig, eller også, så...
Du har ret i at hvis man kender svaret så er det let at finde svaret.
Du har jo kun produktet af de to primtal, og skal dernæst finde de to ukendte primtalsfaktorer.
Du har tallet 7787 og skal nu finde dets faktorer.
Der skulle gerne kun være to som er 83 og 89, men dem kender jeg umiddelbart kun fordi jeg selv gangede dem sammen.

  • 0
  • 0

Du har får kun at vide, at 7787 er et produkt af to primtal. Din opgave er at finde dem. Det er overkommeligt for tal med fire cifre som i dette tilfælde. Det er kun at prøve alle mulige kombinationer og finde den rigtige Men sæt nu jeg giver dig et tal, som jeg har ganget sammen af to store primtal - måske med tusindvis af cifre - og beder dig om at finde de to primtal. Så tror jeg, at du og din nuværende computer vil give op.

Men har du en kvantecomputer med mange qubits, så kan du let finde de to primtal.

  • 0
  • 0

Du har får kun at vide, at 7787 er et produkt af to primtal. Din opgave er at finde dem

Det fremstår som et svar til mig? Det var måske en fejl. I hvert fald er jeg godt klar over problemet, hvorfor det er svært og de mulige løsninger. Det var et simpelt eksempel med 7787 der skulle vise hvad man egentlig søger og hvad man allerede har.

  • 0
  • 0

Hej Thomas

Det er langt fra sikkert at blot man kendet svaret så er spærgsmålet også nemt at finde.

Tag f.eks følgende (næsten) tilfældige C204 tal:

346369145517616832561580518436338147877062893457679622195929206654524672587613049343558394373396338194585783775269785675210636696425094776859733305947996048061499249566197147212934512427988113420226762897

Hvilke to primtal skal man gange med hinanden for at få dette tal?

Ok, ok C204 tallet er nu nok ikke helt tilfældigt valgt og Alex og Poul over på:

http://www.worldofnumbers.com/em_topic1.htm

givetvis sender dig en ramme øl hvis du løser led nr. 100 på home prime 49 (HP(49)).

-Eivind

  • 0
  • 0

Det er langt fra sikkert at blot man kendet svaret så er spærgsmålet også nemt at finde.

Argh!
Jeg skrev
"Du har ret i at hvis man kender svaret så er det let at finde svaret."

Efter at have implementeret ikke så få kryptografiske algoritmer, så er jeg fuldt ud på det rene med sværheden af faktorisering af store tal.

  • 0
  • 0
Bidrag med din viden – log ind og deltag i debatten