quote:http://www.tweakers.net/nieuws/27147
Op dinsdag 27 mei 2003 15:40 schreef zim_ra het volgende:
Hallo kan iemand mij goed uitleggen hoe een quantumcomputer werkt of zo moeten werken en wat is Quantum entanglement..?
quote:
Quantum entanglement zorgt ervoor dat twee aparte deeltjes op een willekeurige afstand van elkaar, op hetzelfde moment, precies hetzelfde lot ondergaan. Tot voor kort lukte het wetenschappers alleen om dit verschijnsel op micrometerschaal plaats te laten vinden. Entanglement is cruciaal voor quantumcomputers, maar een afstand van enkele micrometers is niet voldoende.
[Dit bericht is gewijzigd door Brad op 27-05-2003 15:58]
quote:denk dat je beter ffies een paar jaar naar de UT kunt gaan . .. want ik vermoed dat het "gemiddelde" FoK! IQ niet zo ver gaat. . . (dat van mij iig niet)
hoe werkt quantummechanica en wat is quantum entanglement.. hoe snel wordt een pc dan..
Je kunt het ook niet vergelijken met de pc van nu. Nu doet een pc alles achterelkaar. Dan zou het mogelijk zijn om in verschillende demensies (toch ? ) een bewerking uit te voeren. Dus niet alleen in deze demensie waarin wij ons nu bevinden... klopt dit een beetje (heel simpel). Bij de pc is ook alles opgebouwd uit 0 en 1, bij een quantum pc kan dit 0 of 1 zijn of 0 en 1 tegelijk.
Klopt het ook niet dat bij elke beslissing die je maakt een nieuwe demensie ontstaat ??? naja dit is te moeilijk voor de 99,9999 % van de mensen om te begrijpen. Ik het het eens oooit mijn oom gevraagd (die er wel iets van snapt) maar het is heel moeilijk om uit te leggen.
Ik zou het zo zeggen, elke beveiliging die er ook bestaat op deze aarde... maakt niet uit met hoeveel bits encryptie is binnen een seconde (of minder) te kraken.. er heeft eens een stukje op tweakers hierover gestaan, ik zal eens zoeken.
Ik blijf dit topic eff volgen, is best wel leuk...
quote:Dat snappen die studiebollen daar ook niet. Daar moet je nog net iets slimmer voor zijn denk ik, maja ook het snappen hiervan is ook weer iets anders, zijn de geleerde er zelf eigenlijk al uit hoe het precies inelkaar zit ?
Op dinsdag 27 mei 2003 15:58 schreef Flierp het volgende:[..]
denk dat je beter ffies een paar jaar naar de UT kunt gaan . .. want ik vermoed dat het "gemiddelde" FoK! IQ niet zo ver gaat. . . (dat van mij iig niet)
quote:[punnikmode]
Op dinsdag 27 mei 2003 16:03 schreef Ruudje het volgende:
Hmm... dit is eigenlijk een onderwerp wat ik denk niemand echt hier zal begrijpen...Je kunt het ook niet vergelijken met de pc van nu. Nu doet een pc alles achterelkaar. Dan zou het mogelijk zijn om in verschillende demensies (toch ? ) een bewerking uit te voeren. Dus niet alleen in deze demensie waarin wij ons nu bevinden... klopt dit een beetje (heel simpel). Bij de pc is ook alles opgebouwd uit 0 en 1, bij een quantum pc kan dit 0 of 1 zijn of 0 en 1 tegelijk.
Klopt het ook niet dat bij elke beslissing die je maakt een nieuwe demensie ontstaat ??? naja dit is te moeilijk voor de 99,9999 % van de mensen om te begrijpen. Ik het het eens oooit mijn oom gevraagd (die er wel iets van snapt) maar het is heel moeilijk om uit te leggen.
Ik zou het zo zeggen, elke beveiliging die er ook bestaat op deze aarde... maakt niet uit met hoeveel bits encryptie is binnen een seconde (of minder) te kraken.. er heeft eens een stukje op tweakers hierover gestaan, ik zal eens zoeken.
Ik blijf dit topic eff volgen, is best wel leuk...
Het is dimensie
[/punnikmode]
quote:sorry zat eff in een andere dimensie
Op dinsdag 27 mei 2003 16:05 schreef Sjaakman het volgende:[..]
[punnikmode]
Het is dimensie
[/punnikmode]
quote:Quantum-mechanica en daarbij (deels) quantum computers komen al langs voor het eind van je 2e jaar Natuurkunde (at least in Utrecht). Maarja.. Quantum is al lang verouderd, string-theorie is the future..
Op dinsdag 27 mei 2003 16:05 schreef Ruudje het volgende:[..]
Dat snappen die studiebollen daar ook niet. Daar moet je nog net iets slimmer voor zijn denk ik, maja ook het snappen hiervan is ook weer iets anders, zijn de geleerde er zelf eigenlijk al uit hoe het precies inelkaar zit ?
quote:Je maakt al gebruik van quantummechanica bij het gebruik van al je elektronische apparatuur. Zonder quantummechanica zou de straling van een warm kopje koffie dodelijk zijn. Wat een onzin dus om te stellen dat quantummechanica verouderd zou zijn. Iedere keer als je koffie drinkt test je zelf de theorie.
Op dinsdag 27 mei 2003 16:14 schreef ZeroVince het volgende:[..]
Quantum-mechanica en daarbij (deels) quantum computers komen al langs voor het eind van je 2e jaar Natuurkunde (at least in Utrecht). Maarja.. Quantum is al lang verouderd, string-theorie is the future..
Stringtheorie is niet meer dan wat de naam zegt; een theorie, en nog geen eens de theorie. Pas als er praktische toepassingen of zelfs een eenvoudige voorspelling uit de Stringtheorie uit zou komen, dan heel misschien wel. De enige reden voor het bestaan van de Stringtheorie is het feit dat Quantummechanica geen gravitatie omvat. De filosofische vraag of gravitatie als fundamentele natuurkracht moet worden gezien is echter nog niet eens beantwoord.
Het is dus heel goed mogelijk dat de Stringtheorie niet meer dan een (verouderd) hersenspinsel is. 
Het effect zal wel opgewekt moeten worden door iets, en dus zal een quantumcomputer met 2 keer zoveel van die opwekdingen ook 2 keer zo snel zijn. zodoende hoeft een quantumcomputer niet oneindig snel te zijn. 
Dit alles in het geval dat een quantumcomputer werkt zoals in Ruudjes post beschreven.
Zie: http://www.rootnode.com/Members/cranmer/Wiki/QuantumComputing
Meer informatie over Quantumcomputing in het wfT-topic Informatieoverdracht sneller dan het licht..
quote:Ok gaat goed. Mooie verwijzingen.
Op dinsdag 27 mei 2003 19:17 schreef the.moderator het volgende:
Ik heb een paar jaar geleden zelf een encyclopedische webpublicatie over quantumcomputing gemaakt:Zie: http://www.rootnode.com/Members/cranmer/Wiki/QuantumComputing
Meer informatie over Quantumcomputing in het wfT-topic Informatieoverdracht sneller dan het licht..
Maar idd. o.a. http://qt.tn.tudelft.nl/~chiorescu/fluxqubit/ gaf een mooie uitleg (hoewel ik hoofdpijn krijg van al die formules).
quote:Daar bestaat maar één remedie voor. Namelijk een king-size bril. Ja, ik heb er ook één, het werkt echt.
Op dinsdag 27 mei 2003 22:12 schreef M.ALTA het volgende:[..]
...hoewel ik hoofdpijn krijg van al die formules.
Prof. David Deutsch (Oxford University) Prof. David K. Lewis (Princeton University) Dr. Peter Shor (AT&T Research)
FA Jump: webicon weggehaald wegens wachtwoord beveiliging
Stel je voor dat je een voetbalveld onderverdeeld in kleine vierkantjes van 10 bij 10 cm. onder 1 vierkantje ligt een balletjes verstopt.
wil je dat balletje met en 'gewone ' pc vinden dan kijkt die pc 1 voor 1 onder die vierkantjes, dit kan dus wel even duren voordat die dat balletje heeft gevonden.en hoe sneller je pc, hoe sneller hij kan zoeken.
een quantum computer daarintegen kijkt gelijk onder alle vierkantjes, en zal dat balletje dus veel sneller vinden.
verder weet ik er weinig van af.
quote:Nee helaas zijn de exponentiële tijd problemen nog een te complexe rekenkundige klasse.
Op woensdag 28 mei 2003 07:56 schreef paladin het volgende:
kon je met quantumcomputers niet van van die mooie exponentiele problemen binnen niet-exponentiele tijd oplossen?
De complexiteitsverdeling van rekenkundige problemen - in afnemende complexiteit - is als volgt:
De klasse NP-Problems, hebben nog een verdere onderverdeling in NP-Hardness, maar NP-Complete omvat ze allemaal en geen systeem kan ze allemaal uitrekenen. Ook een Quantum Computer niet.
Enkele z.g. Non NP-Hard Problems waarschijnlijk wel, maar alleen een kleine subset ervan. Hoe klein die subset is weten we zelfs theoretisch nog niet. De teller staat nu nog maar op enkele specifieke typen, zoals Prime Factorization and Discrete Logarithms. Deze NP-Problems worden dan door de Quantum-Computer in Polynomial-time uitgerekend. We weten dat het theoretisch kan, omdat er Quantum-Algorithmen voor zijn geschreven. Zodra er dus meer Quantumalgorithmen, voor problemen uit die categorie zijn, zal de subset pas toenemen.
Waar die Quantumalgorithmen dus toe instaat moeten zijn is een vorm van declassificatie van de probleemcomplexiteit naar Polynomial-time (klasse P) problemen. De normale klasse P-Problems zijn eigenlijk verificatieproblemen van een soort waarbij de uitkomst al bekend is of verondersteld wordt. De verificatie van die uitkomst is dan in Polynomial-time mogelijk. Het "voetbalveld met verstopte balletjes" voorbeeld van * gebruikersnaam is zo'n simpel Polynomial-time Problem.
It's now a class P-Problem Scotty? "No problem Captain Kirk!"
De schrik voor de beveiligingsindustrie is nu dat de huidige cryptografie op factorisatie van priemgetallen gabaseerd is. Het kraken van een encryptiesleutel via het Quantumalgoritme voor Prime Factorization van Peter Shor kost daardoor geen miljoenen processors en miljoenen jaren meer. Het verhaal op Tweekers dat het nu in seconden kan klopt echter ook niet, want ook Polynomial-time problemen kunnen groot zijn.
Zoals je nu wel duidelijk zal zijn, blijven de nog complexere Exponential-time en Universal-time Problems praktisch en ook theoretisch nog steeds onoplosbaar. Helaas pindakaas.
[Dit bericht is gewijzigd door the.moderator op 28-05-2003 13:03]
quote:Niet als je een algoritme hebt gevonden dat evenzo een (negatief) exponentiele zoeksnelheid heeft (afh. van het NP-probleem uiteraard).
Op woensdag 28 mei 2003 09:20 schreef the.moderator het volgende:[..]
Nee helaas zijn de exponentiële tijd problemen nog een te complexe rekenkundige klasse.
v.b. probleem t orde complexiteit is exp(nt) ---> zoek een algoritme
met (neagtieve) katalysator exp(-nt) of sneller dempend in het aantal tussenberekeningen tot de eindoplossing.
quote:Bedankt voor het overzicht, dat weet ik dan ook weer.
De complexiteitsverdeling van rekenkundige problemen - in afnemende complexiteit - is als volgt:
Universal-time Exponential-time Non-deterministic Polynomial-time (NP) Complete Non-deterministic Polynomial-time (NP) Polynomial-time (P)
quote:Afhankelijk van het probleem (groote en de complexiteit) denk ik.
De klasse NP-Problems, hebben nog een verdere onderverdeling in NP-Hardness, maar NP-Complete omvat ze allemaal en geen systeem kan ze allemaal uitrekenen. Ook een Quantum Computer niet.
Voorbeeld: traveling salesman problem.
Afhankelijk van de randvoorwaarden van het model, kan men toch een
eindige (of lineaire) berekeningstijd vinden.
quote:De Laplace-transformatie en de
Enkele z.g. Non NP-Hard Problems waarschijnlijk wel, maar alleen een kleine subset ervan. Hoe klein die subset is weten we zelfs theoretisch nog niet. De teller staat nu nog maar op enkele specifieke typen, zoals Prime Factorization and Discrete Logarithms. Deze NP-Problems worden dan door de Quantum-Computer in Polynomial-time uitgerekend. We weten dat het theoretisch kan, omdat er Quantum-Algorithmen voor zijn geschreven. Zodra er dus meer Quantumalgorithmen, voor problemen uit die categorie zijn, zal de subset pas toenemen.
Bolzmann-machine kunnen soms wonderen verrichten/uitkomst bieden.
Worden die ook gebruikt bij Quantum-algoritmen om een polynomial-time af te dwingen ?
quote:leuke metafoor
Waar die Quantumalgorithmen dus toe instaat moeten zijn is een vorm van declassificatie van de probleemcomplexiteit naar Polynomial-time (klasse P) problemen. De normale klasse P-Problems zijn eigenlijk verificatieproblemen van een soort waarbij de uitkomst al bekend is of verondersteld wordt. De verificatie van die uitkomst is dan in Polynomial-time mogelijk. Het "voetbalveld met verstopte balletjes" voorbeeld van * gebruikersnaam is zo'n simpel Polynomial-time Problem.It's now a class P-Problem Scotty? "No problem Captain Kirk!"
quote:Daar ben ik een tijdje mee bezig geweest. De Mossad is er al met dit idee vandoor gegaan zie: DIGITAAL: M.ALTA eigen cryptosystemen bedenken en zie de posts van ChOAs.
De schrik voor de beveiligingsindustrie is nu dat de huidige cryptografie op factorisatie van priemgetallen gabaseerd is. Het kraken van een encryptiesleutel via het Quantumalgoritme voor Prime Factorization van Peter Shor kost daardoor geen miljoenen processors en miljoenen jaren meer. Het verhaal op Tweekers dat het nu in seconden kan klopt echter ook niet, want ook Polynomial-time problemen kunnen groot zijn.
quote:Niet zo snel opgeven.
Zoals je nu wel duidelijk zal zijn, blijven de nog complexere Exponential-time en Universal-time Problems praktisch en ook theoretisch nog steeds onoplosbaar. Helaas pindakaas.
quote:* Zelfs king-size brillen helpen niet meer. Nou dan maar een paardenmiddel om M.ALTA zoet te houden.
Op woensdag 28 mei 2003 15:57 schreef M.ALTA het volgende:[.. de formule-hoofdpijn van M.ALTA neemt extreme vormen aan ..]
Mathematical and Non Mathematical Properties of 17 .......... http://www.vinc17.org/d17_eng.pdf ..........
quote:Dacht het niet helemaal.
Op woensdag 28 mei 2003 09:20 schreef the.moderator het volgende:[..]
Nee helaas zijn de exponentiële tijd problemen nog een te complexe rekenkundige klasse.
v.b.
Probleem ~ n delen, rekentijd gewone iteratieve oplossing algoritme in
~ f(n) = c* exp(kn) stappen.
Truc: zoek een beter algoritme (dus G) dat garandeert:
rekentijd algoritme ~ a*n^q * G (f (n)) , zodat je een rekentijd in polynomial time van n hebt.
b.v. G (f(n)) = ln (f(n))
quote:Ik ken nog een onderverdeling (N = grootte probleem): tussen universele en exponentiele rekenproblemen.
De complexiteitsverdeling van rekenkundige problemen - in afnemende complexiteit - is als volgt:
Universal-time Exponential-time Non-deterministic Polynomial-time (NP) Complete Non-deterministic Polynomial-time (NP) Polynomial-time (P)
1) N^q exp (K*N) q integer, k konstant, q > N
2) N! exp (k*N) k konstant
3) N^q exp (k * N) q integer, k konstant, q<N
4) N!
3) & 4) zijn in het algemeen goed op te lossen binnen polynomial N based time (Bron: Philips Natlab).
Hoe ? bedrijfsgeheim, helaas (maar geen pindakaas).
quote:Je geeft hier zelf een voorbeeld van een Polynomial-time (class-P) probleem. Waarbij je in het begin zegt dat als je een onhandig algorithme gebruikt het eigenlijk een exponential-time problem is. Als je nu je afleiding niet van boven naar beneden, maar van beneden naar boven leest, dan zie je dat het probleem gewoon Polynomial-time is en blijft.
Op maandag 2 juni 2003 15:36 schreef M.ALTA het volgende:Dacht het niet helemaal.
v.b.
Probleem ~ n delen, rekentijd gewone iteratieve oplossing algoritme in~ f(n) = c* exp(kn) stappen.
Truc: zoek een beter algoritme (dus G) dat garandeert:
rekentijd algoritme ~ a*n^q * G (f (n)) , zodat je een rekentijd in polynomial time van n hebt.
b.v. G (f(n)) = ln (f(n))
Bewijs uit het ongerede: Neem een foutief algorithme dat door een bug in een oneindige loop komt. Dat maakt het probleem waar het algorithme voor bedoeld was niet plotseling een Universal-time problem. Dat zou dan dus de omgekeerde wereld zijn en dat is precies wat jij in dit natte vinger voorbeeld wel doet.
quote:Hier geldt exact hetzelfde. Je definieert eerst in 3. een exponentiële oplossingstijd in N bijvoorbeeld 2N seconden rekentijd. Dan zeg je vervolgens dat het via een andere methodiek (algorithme) ook in Polynomial-time bijvoorbeeld N2 berekent kan worden. Dan klopt of je uitgangsdefinitie niet of je hebt inmiddels een betere methode gevonden, waardoor je uitgangsdefinitie moet worden bijgesteld. Het probleem is en was dan altijd een Polynomial-time probleem. Het meest efficiënte algorithme is hiervoor bepalend.
Ik ken nog een onderverdeling (N = grootte probleem): tussen universele en exponentiele rekenproblemen.1) N^q exp (K*N) q integer, k konstant, q > N
2) N! exp (k*N) k konstant
3) N^q exp (k * N) q integer, k konstant, q<N
4) N!3) & 4) zijn in het algemeen goed op te lossen binnen polynomial N based time (Bron: Philips Natlab).
Hoe ? bedrijfsgeheim, helaas (maar geen pindakaas).
Er is nog een leuk openstaand probleem voor je. Hoeveel kleurpotloden van verschillende kleur heb je nodig om een kaart van alle landen te kunnen intekenen, zonder dat twee aan elkaar liggende landen dezelfde kleur krijgen. Ik stel voor dat we niet te overmoedig beginnen met een aantal landen N = 100.
quote:Ja, dat is juist, maar de truc/moeilijkheid zit hem in/ is om van een schijnbaar (b.v. a.g.v. onhandig algoritme) hopeloos NP-probleem, een beheersbaar (class-P) probleem te maken. Het gaat om het vinden van die G.
Op dinsdag 3 juni 2003 06:22 schreef the.moderator het volgende:[..]
Je geeft hier zelf een voorbeeld van een Polynomial-time (class-P) probleem. Waarbij je in het begin zegt dat als je een onhandig algorithme gebruikt het eigenlijk een exponential-time problem is. Als je nu je afleiding niet van boven naar beneden, maar van beneden naar boven leest, dan zie je dat het probleem gewoon Polynomial-time is en blijft.
quote:Nee, het gaat er om het oorspronkelijke probleem NP(n) met oplossing A te tranformeren (b.v. m.b.v. slimme transformaties) naar een probleem P(n) met oplossing B en dan direct uit B op A uit te komen via een terugherleiding.
Bewijs uit het ongerede: Neem een foutief algorithme dat door een bug in een oneindige loop komt. Dat maakt het probleem waar het algorithme voor bedoeld was niet plotseling een Universal-time problem. Dat zou dan dus de omgekeerde wereld zijn en dat is precies wat jij in dit natte vinger voorbeeld wel doet.
[..]
quote:Dat is niet zo direct te zeggen.
Hier geldt exact hetzelfde. Je definieert eerst in 3. een exponentiële oplossingstijd in N bijvoorbeeld 2N seconden rekentijd. Dan zeg je vervolgens dat het via een andere methodiek (algorithme) ook in Polynomial-time bijvoorbeeld N2 berekent kan worden. Dan klopt of je uitgangsdefinitie niet of je hebt inmiddels een betere methode gevonden, waardoor je uitgangsdefinitie moet worden bijgesteld. Het probleem is en was dan altijd een Polynomial-time probleem. Het meest efficiënte algorithme is hiervoor bepalend.
Het gaat er om, niet direct bij een hopeloze NP situatie te stellen dat het probleem een hopeloos lange oplossingsberekentijd nodig heeft.
quote:4, dit was wel heel makkelijk (doe ik zo uit mijn hoofd).
Er is nog een leuk openstaand probleem voor je. Hoeveel kleurpotloden van verschillende kleur heb je nodig om een kaart van alle landen te kunnen intekenen, zonder dat twee aan elkaar liggende landen dezelfde kleur krijgen. Ik stel voor dat we niet te overmoedig beginnen met een aantal landen N = 100.
Nu heb ik een vraagje voor jou:
Hoe kan het dat als je de maximum snelheid op een ononderbroken snelweg van 50 km lengte verhoogt van 120 km/h naar 140 km/h, dat de gemiddelde snelheid van alle vervoermiddelen die deze snelweg gebruiken DAALT, er van uitgaande dat alle bestuurders niet vrijwillig gas terug gaan nemen (en zonder dat er zich ongelukken voordoen).
quote:Whaa! simpel! tijd voor een leuke graaf die we gaan kleuren
Er is nog een leuk openstaand probleem voor je. Hoeveel kleurpotloden van verschillende kleur heb je nodig om een kaart van alle landen te kunnen intekenen, zonder dat twee aan elkaar liggende landen dezelfde kleur krijgen. Ik stel voor dat we niet te overmoedig beginnen met een aantal landen N = 100
Ehmm.. welke landen grenzen aan elkaar?
FA Jump: webicon weggehaald wegens wachtwoord beveiliging
quote:Dit is misschien wel één van de moeilijkste wiskundige problemen met direkte praktische toepassing.
Op dinsdag 3 juni 2003 18:05 schreef paladin het volgende:[..]
Whaa! simpel! tijd voor een leuke graaf die we gaan kleuren
Ehmm.. welke landen grenzen aan elkaar?
quote:De toepassing is trouwens niet alleen voor atlassen en globes, maar ook voor meer zwaarwichtige zaken. Zoals lesroosters en spoorboekjes die nu nog steeds mathematisch vaak suboptimaal zijn geplanned.
Math Lecture: The Strong Perfect Graph Theorem by Maria Chudnovsky (CMI/Princeton University)Thursday, March 20, 2003 at 1:30 PM
Clay Mathematics Institute One Bow Street (4th Floor) Cambridge, MA 02138
Abstract
A graph is a set of vertices some pairs of which are joined by an edge and others are not. One of the properties of graphs studied in graph theory is graph coloring: color the vertices with as few colors as possible so that no two vertices with an edge between them receive the same color. Clearly, if a graph contains 10 vertices every two of which are joined by an edge, we need at least 10 colors in order to color it. However even that may not be enough. It has been a central questions in graph theory to characterize all graph for which it would be enough. In 1961 Claude Berge conjectured a possible characterization (that became known as The Strong Perfect Graph Conjecture), in 2002, in join work with Neil Robertson, Paul Seymour and Robin Thomas, we proved it. In my talk I will explain the problem more precisely and discuss some ideas used in the proof.
[Dit bericht is gewijzigd door the.moderator op 04-06-2003 01:59]
|
|
