Kvantecomputer løser Sodoku

Ikke for at være flabet eller noget men det hedder sudoku.

Kan almindelige computere ikke løse sudoku? Hvorfor ikke?

#2 Jo sagtens: http://en.wikipedia.org/wiki/Sudoku#Computer_solut...
Men en sand kvantecomputer vil sansynligvis kunne gøre det på brøkdelen af en sekund, selv ved abnormt store sudokuer.

Så vidt jeg har forstået kvanteberegning (hvilket vil sige overhoved ikke), så er fordelen at man opererer med to forskellige tidskompleksiteter for det samme problem. Én for problemet løst på en normal turing maskine, og en anden for problemet løst på en kvantecomputer.

Men selv hvis der skal meget færre cykluser til f.eks. at faktorisere et tal der er produktet af to meget store primtal på en kvantecomputer, kan det stadig være uoverkommeligt hvis de enkelte operationer i stedet tager faktor million gange længere tid at udføre fordi det er for svært at aflæse registeret.

---

Jeg kunne godt tænke mig et relativt mål for styrkeforskellen af de to arkitekturer så jeg har kigget lidt på wikipedia artiklen for Quantum Computing.

Nu er jeg godt nok klar over at for lidt viden kan være en farlig ting, så det er med det forbehold at jeg skriver følgende: Man kan sammenligne dimensionen af de to typer af registre og dermed få et mål for forskellen i tidskompleksitet.

Der står at for et n-qubit register er dimensionen 2^(n+1)-2. Holdt op imod de n for en n-bit turing maskine, er fordelen ved kvanteberegning fænomenal (eksponentiel vs. lineær). Eller mere konkret at 2^(n+1)-2/n er et øvre loft for med hvilken faktor kompleksiteten af problemet reduceres ved at flytte det fra et n-bit til et n-qubit register.

Jeg vil *meget* gerne korrigeres hvis mine gæt er ude i skoven. For det er bare spekulation fra min side.

#4

Det er faktisk rigtigt hvad du skriver. Kvantecomputeren virker på en meget indviklet måde, men rent praktisk foregår det ved at den bruger et andet bitsystem end normalt. Normalt vil en computer aflæse data ved enten at se et 1-tal eller et 0. Dette er ikke tilfældet ved en kvantecomputer. Den ser istedet både et 1-tal og et 0. Samt alle tal derimellem.

Dette betyder at den kan beregne udfra nogen andre formler. Som du også skriver. På stående fod kan jeg dog ikke huske alle disse formler men den du skriver er i hvert fald én af dem. Alt efter hvad der skal beregnes skal der jo bruges nogen andre formler og i samtlige tilfælde skal kvantecomputeren beregne væsentlig mindre da den gør det på en anden måde.

Mon der findes snydekoder til den Sudoku?

#6

"There is no Cow Level"

#4

Så vidt jeg har forstået kvanteberegning (hvilket vil sige overhoved ikke)

nemlig! man kan nemlig ikke forstå kvantemekanik, se f.eks. følgende quotes.

Anyone who is not shocked by quantum theory has not understood a single word.
--Niels Bohr

I think it is safe to say that no one understands quantum mechanics.
-- Richard Feynman

Marvelous, what ideas the young people have these days. But I don't believe a word of it.
-- Albert Einstein

#8

Jeg vil give dig, og forskerne, ganske ret;) Det er simpelthen umuligt at forstå det hele som en helhed. Faktisk har man til dags dato stadig svært ved at forklare hvordan kvantecomputerne egetnlig virker, da det rent fysisk ud fra de gamle fysiske love og regler slet ikke er muligt.

Det er højst sandsynligt derfor der også er tvivl om hvorvidt man egentlig kan lave en effektiv kvantecomputer.

Hvis man forestiller sig en ladning i position A. Her vil den repræsentere et 1-tal. Befinder den sig i position B vil den give et 0. Teorien er nu at den befinder sig både i position A og B samt alle punkterne der ligger mellem disse. Dette kan simpelthen ikke lade sig gøre, men alligevel viser hvert eneste forsøgat det er præcist hvad der sker:)

Det er ganske spændende forskning. Men det kræver at man "leger" lidt med fysikkens love...

#9 det er da ganske forståeligt!
Hvorfor er det er problem?
Er det ikke blot fordi folk er så ensporede at de stoler på de ting som blev skrevet og sagt for mange år siden?

Husk iøvrigt på at Jorden er flad og ikke rund ;)

Bemærk venligst at der stadig er tvivl om den fungerer som kvantecomputer

http://www.physorg.com/news90693138.html

#9 Det er en ret kraftig forenkling af kvantemekanikken du er ude i dér. Og de citater af Bohr og Einstein, beror primært på at begge forskere var foruroligede over det faktum at kvantemekanikken i kan forenes ordentligt med f.eks. relativitetsteorien og elektrodynamikken/-statikken. Det er ganske enkelt en teori der passer meget bekvemt med det man observerer.

#10

Joh det er det da:) Men de eksisterende love er man vel efterhånden ret enige om er rigtige... dog kan man jo aldrig regne med noget:)

#12

Helt klart... Men tænkte også at en mere teknisk forklaring for det første ville fylde for meget og for det andet ville være spildt på de fleste;)
Men det er rigtig som du siger. Kvantemekanikken passer med samtlige målinger og forsøg nogensinde lavet, og samtidig modsiger den de fleste af de kendte fysiske love. Blandt andet at en ting ikke kan være to steder på én gang...