211service.com
De kwantumgrens
In mei 1981 beschreef Richard Feynman '39 op een conferentie georganiseerd door MIT's Laboratory for Computer Science een theoretisch apparaat dat hij een kwantumcomputer noemde, dat berekeningen zou uitvoeren door gebruik te maken van het vreemde gedrag van materie op zeer kleine schaal. Theoretische natuurkundigen namen het idee over en toonden aan dat kwantumcomputers in principe alles kunnen doen wat gewone computers kunnen, en voerden aan dat ze sommige dingen veel, veel sneller zouden kunnen doen. Toch bleef kwantumberekening gedurende meer dan een decennium voor iedereen, op een paar liefhebbers na, alleen een onderwerp voor nutteloze speculatie.
Van links: professoren Peter Shor, Scott Aaronson en Edward Farhi
Dat veranderde spectaculair in 1994, toen Peter Shor, PhD '85, nu hoogleraar toegepaste wiskunde aan het MIT, een kwantumalgoritme beschreef om de priemfactoren van een getal te vinden. Een kwantumcomputer met het algoritme van Shor zou factoringtaken kunnen uitvoeren die de huidige computers tijdens de levensduur van het universum niet zouden kunnen voltooien. Aangezien de moeilijkheid om grote getallen te ontbinden de enige garantie is voor de veiligheid van de meeste moderne cryptografische systemen, moest de rest van de wereld - en met name organisaties zoals de National Security Agency - er nota van nemen. Shor toonde aan dat als je kwantumcomputers kon bouwen, er mensen zouden zijn die ze wilden kopen, zegt Seth Lloyd, een professor werktuigbouwkunde die kwantumcomputers bestudeert. Het algoritme van Shor vormde de killer-app die iedereen interesseerde.
Hoewel volledig functionele kwantumcomputers voor algemene doeleinden waarschijnlijk tientallen jaren verwijderd zijn, veranderde het algoritme van Shor kwantumberekening in een weelderig onderzoeksgebied. Volgens Lloyd ligt het aantal onderzoekers wereldwijd dat momenteel aan kwantumcomputing werkt, waarschijnlijk ergens rond de 5.000. Ik denk dat als we nog eens 300 leden krijgen bij de American Physical Society, we een afdeling zullen zijn van de American Physical Society, zegt hij. En in elk opzicht, van het ontdekken van nieuwe algoritmen tot het bedenken van nieuwe soorten computers, MIT-onderzoekers zitten midden in de strijd.
Kwantum Mogelijkheid
Kwantumberekening is geworteld in het centrale mysterie van de kwantumfysica: dat kleine materiedeeltjes tegelijkertijd meerdere, schijnbaar elkaar uitsluitende toestanden kunnen bewonen. Vuur een enkel foton - een lichtdeeltje - af op een barrière met twee spleten erin, en het zal door beide spleten tegelijk gaan. Elektronen hebben een eigenschap genaamd spin, die kan worden gezien als rotatie met de klok mee of tegen de klok in, maar een enkel elektron kan tegelijkertijd met de klok mee en tegen de klok in draaien. Dit vermogen om in meer dan één toestand tegelijk te zijn, wat natuurkundigen superpositie noemen, is, zoals Feynman het ooit zei, onmogelijk, absoluut onmogelijk, op een klassieke manier uit te leggen. Om het nog vreemder te maken, als je een kwantumdeeltje hebt dat zich in meerdere toestanden tegelijk bevindt en je er een meting op uitvoert, springt het onmiddellijk in slechts één van die toestanden. En welke van hen het veronderstelt, is volkomen willekeurig. (Dat is de basis van een ander beroemd natuurkundig citaat: Einsteins aandringen, tegen de uitspraken van de kwantumfysica in, dat God niet dobbelt met het universum.)
In de informatica is de fundamentele eenheid van informatie de bit, die een van twee waarden kan aannemen, meestal uitgedrukt als 0 en een . De pioniers van kwantumcomputers realiseerden zich dat, aangezien een kwantumdeeltje in twee toestanden tegelijk kan zijn, het zou kunnen vertegenwoordigen: 0 en een tegelijkertijd. Twee kwantumbits - of qubits - kunnen vier waarden vertegenwoordigen, drie van hen acht, vier van hen 16, enzovoort. Een enkele berekening met: N qubits zou zijn als 2 doen N berekeningen in één keer.
Stel echter dat je acht qubits hebt, die de resultaten vertegenwoordigen van 256 gelijktijdige berekeningen. Als je een meting uitvoert op de qubits, stort de superpositie in: elke qubit neemt onmiddellijk een waarde aan van 0 of een . Je blijft achter met slechts één van de 256 initiële mogelijkheden, en die willekeurig gekozen. Hoe garandeer je dat het degene is die je wilt?
Het eerste kwantumalgoritme
Dat is de vraag die Shor beantwoordde, in wat nog steeds het belangrijkste resultaat in ons vakgebied is, volgens Edward Farhi, de directeur van MIT's Center for Theoretical Physics, die ook onderzoek doet naar kwantumberekening.
Wanneer een deeltje in superpositie willekeurig een enkele toestand aanneemt, doet het dat in overeenstemming met bepaalde waarschijnlijkheden: na verloop van tijd zullen deeltjes vaker in bepaalde toestanden terechtkomen dan in andere. Die kansen kunnen worden weergegeven als een curve die toevallig veel lijkt op de top van een golf. Het blijkt dat dezelfde wiskunde die de fysica van golven beschrijft, ook de fysica van kwantumwaarschijnlijkheden beschrijft.
Wanneer golven botsen, interfereren ze met elkaar, constructief of destructief. Als twee toppen elkaar kruisen, is het resultaat een grotere kam; als een kam een trog kruist, heffen ze elkaar op. Shor vond een ingenieuze manier om het probleem van factoring met kansgolven weer te geven, zodat de juiste antwoorden elkaar zouden versterken terwijl de verkeerde in wezen zouden verdwijnen. Het resultaat is nog steeds een waarschijnlijkheidsgolf, maar wanneer de superpositie instort, is de kans erg groot dat je het juiste antwoord krijgt.
Shor begon in 1993 aan het algoritme te werken, toen hij in het onderzoekscentrum van Bell Labs van AT&T was, nadat hij een lezing had gehoord over kwantumcomputing door Umesh Vazirani '81, een professor aan de University of California, Berkeley. Niet fulltime ermee bezig natuurlijk, zegt hij. Sterker nog, ik heb niemand echt verteld dat ik eraan werkte totdat ik het bedacht.
Eigenlijk was het eerste kwantumalgoritme waar Shor in april 1994 over vertelde, een algoritme voor het berekenen van logaritmen, een probleem dat nauw verband houdt met factorisatie. Ik heb dinsdag een lezing gegeven over het algoritme bij Bell Labs, zegt hij. Die zaterdag was ik thuis met een zware verkoudheid, en Umesh Vazirani belde me op vanuit Californië, heel opgewonden, en zei: 'Ik hoor dat je weet hoe je rekening moet houden met een kwantumcomputer.' In feite deed hij dat: in de tussenliggende vier dagen had hij zijn algoritme aan datzelfde probleem aangepast. De Econoom interviewde me niet lang daarna, zegt Shor. Al snel kreeg ik tonnen e-mails over het algoritme, en ik had de paper nog steeds niet geschreven. Toen hij er begin mei zijn eerste openbare lezing over gaf in Cornell, zegt hij lachend dat iemand van de NSA er daarna met mij over sprak.
Gebruikmaken van MRI-technologie
Toen Seth Lloyd in 1994 naar het MIT kwam, had ik een heleboel artikelen geschreven over kwantumcomputers, zegt hij. Ik en misschien wel vijf of zes andere mensen hadden hier vóór 1994 aan gewerkt. Voor Lloyd had de aankondiging van Shors algoritme een heel concreet effect: het maakte het een stuk gemakkelijker om een vaste aanstelling te krijgen.
Een van de papieren die Lloyd had gepubliceerd, in Wetenschap stelde in 1993 het eerste haalbare ontwerp voor een kwantumcomputer voor. Je zou het kunnen zien als een kopje vol moleculen, zegt hij. In elk molecuul werden qubits weergegeven door verschillende soorten atomen, en alle moleculen in de beker zouden tegelijkertijd dezelfde berekening uitvoeren.
In afzonderlijk onderzoek toonden gasthoogleraar David Cory en Neil Gershenfeld, hoofd van de Physics and Media Group van het Media Lab, aan dat het ontwerp van Lloyd kon worden gerealiseerd met behulp van nucleaire magnetische resonantie (NMR), het fenomeen dat ten grondslag ligt aan magnetische resonantiebeeldvorming. Een krachtige magneet zou de spins van de atomen die de moleculen vormen op één lijn brengen. Verschillende frequenties van radiogolven kunnen dan sommige van de atomen in superpositie plaatsen en de spins van anderen omdraaien. De elektronen met duidelijke spins zouden gegevens vertegenwoordigen, en de spins in superpositie zouden de resultaten vertegenwoordigen van meerdere bewerkingen die op die gegevens zijn uitgevoerd.
In 1998 werkte Gershenfeld samen met Isaac Chuang '90, '91, SM '91, vervolgens bij IBM Almaden Research Center in San Jose, Californië, en Mark Kubinec van UC Berkeley om het eerste computersysteem te bouwen dat NMR gebruikte om een kwantum algoritme. Het had twee qubits.
In 2000 keerde Chuang terug naar MIT, waar hij nu hoogleraar natuurkunde en elektrotechniek en informatica is. Het jaar daarop bouwden hij en IBM-collega's een zeven-qubit NMR-computer die voor het eerst het algoritme van Shor met succes uitvoerde. Het stelde vast dat de priemfactoren van 15 zeer waarschijnlijk drie en vijf zijn.
Een probleem met NMR-kwantumcomputing is dat, aangezien qubits worden weergegeven door verschillende atomen in een enkel molecuul, complexere berekeningen complexere moleculen vereisen. Maar hoe groter het molecuul, hoe sterker het elektromagnetische veld en hoe moeilijker het is om het elektromagnetische signaal van een enkel atoom te onderscheiden. Sommige onderzoekers onderzoeken kleine sensoren die magnetische signalen van individuele moleculen kunnen lezen. Maar onder andere Chuang heeft zich tot kwantumcomputers gewend die ionen gebruiken die gevangen zitten in elektromagnetische velden als qubits, een techniek die in 1995 werd voorgesteld door onderzoekers van de Oostenrijkse Universiteit van Innsbruck.
Ion-trap quantum computing maakt gebruik van roterende magnetische velden om individuele moleculen te isoleren, en laserlicht in plaats van radiopulsen om de kwantumtoestanden van de moleculen te veranderen. Hoewel dat onderzoekers een nauwkeurigere controle geeft over qubits dan bestaande NMR-technieken, vereist het dat ook. Elektronen die om een kern draaien, kunnen zich in verschillende energietoestanden bevinden. Voeg genoeg energie toe aan een elektron en het zal naar het volgende energieniveau komen; als het maar een beetje energie verliest, zal het weer naar beneden vallen. Ion-trap quantum computing vereist dat elektronen in verschillende, nauwkeurig gespecificeerde energietoestanden worden gehouden. Dit is zo lastig dat sommige onderzoekers begonnen te overwegen of er een kwantumcomputer zou kunnen zijn die gewoon in zijn laagste energietoestand bleef.
Een adiabatische benadering
In 2000 stelden MIT-natuurkundigen Edward Farhi en Jeffrey Goldstone, Michael Sipser van de wiskundeafdeling en Sam Gutmann, '73, PhD '77 van Northeastern een nieuw type kwantumcomputer voor, een adiabatische kwantumcomputer genaamd, die altijd in zijn laagste energie staat. staat. (Objecten hebben de neiging om de laagste energietoestanden te zoeken die ze kunnen vinden, dus lage energietoestanden zijn meestal stabieler dan hoge.) Het artikel specificeerde niet hoe de qubits zouden worden gerealiseerd. Maar het was gebaseerd op de erkenning dat oplossingen voor rekenproblemen konden worden voorgesteld als de toestanden met de laagste energie van een fysiek systeem.
Twee magneten hebben bijvoorbeeld de neiging om de noordpool op de zuidpool te plaatsen, omdat het minder energie kost dan de noordpolen samen te dwingen. Een willekeurig aantal magneten die willekeurig op een bord zijn geplaatst, zullen daarom gaan flippen, zodat er zoveel mogelijk van noord naar zuid zijn uitgelijnd. Als je magneten in het juiste patroon plaatst en hun initiële oriëntaties op de juiste manier instelt, zou je in theorie een rekenprobleem kunnen coderen. Terwijl de magneten omdraaiden om hun oriëntatie met de laagste energie te vinden, zouden ze convergeren naar de oplossing van het probleem. Adiabatische kwantumcomputing is vergelijkbaar, maar het zou veel mogelijke oplossingen tegelijkertijd kunnen onderzoeken, omdat het qubits zou gebruiken in plaats van magneten.
Met adiabatische kwantumcomputing zou een kwantummechanisch fysiek systeem worden opgezet in de laagste energietoestand, de grondtoestand genoemd. Aanvankelijk zou het systeem een veel eenvoudiger probleem coderen dan het probleem dat het moet oplossen. Maar na verloop van tijd zou een bepaalde regelparameter van het systeem, bijvoorbeeld de sterkte van het elektromagnetische veld, geleidelijk veranderen, totdat het systeem uiteindelijk het moeilijkere probleem codeerde. Als de verandering langzaam genoeg zou plaatsvinden, zou het systeem in zijn grondtoestand blijven, dus het zou uiteindelijk de oplossing voor het probleem vertegenwoordigen.
Sommige mensen denken dat als je een kwantumcomputer had die in zijn grondtoestand moest blijven - door, laten we zeggen, hem erg koud te maken - dat het systeem een beetje minder vatbaar zou maken voor fouten, zegt Farhi. Want als je het altijd koud hebt, en je bent altijd in de grondtoestand, dan is dat waarschijnlijk een gemakkelijkere plek om te zijn dan in een opgewonden toestand die je zorgvuldig moet beheersen.
Het probleem met de adiabatische benadering is dat het systeem langzaam moet veranderen om te voorkomen dat het naar een hogere energietoestand springt, en niemand weet hoe langzaam langzaam genoeg is. Als het oneindig langzaam is, weten we dat het zal werken, zegt Farhi. Maar als het systeem te langzaam moet veranderen, biedt het geen voordelen ten opzichte van conventionele computers.
Farhi blijft de vraag onderzoeken hoe snel een adiabatisch kwantumcomputersysteem kan veranderen, zowel door computermodellering van relatief eenvoudige systemen als door wiskundige analyse. Ondertussen, in 2002, hebben Lloyd en Bill Kaminsky, een afgestudeerde student in zijn groep, een manier voorgesteld om een adiabatische kwantumcomputer te realiseren met behulp van supergeleidende elektrische circuits, waarin de stroom in superpositie kan zijn: in feite loopt de stroom met de klok mee en tegen de klok in bij een keer. De richting van de stroom vertegenwoordigt de waarde van een qubit en de totale energie van het systeem hangt af van de richting van de stroom in aangrenzende circuits. Wanneer een magnetisch veld wordt aangelegd, gaan de stromen in superpositie. Wanneer gemeten, springt het systeem vervolgens in de laagste energietoestand en onthult het antwoord. Twee jaar later, Lloyd; Wim van Dam, een postdoc in de groep van Farhi; en vier andere onderzoekers van vier verschillende universiteiten bewezen dat een adiabatische kwantumcomputer in principe elke berekening kan uitvoeren die een conventionele kwantumcomputer kan.
In 2007 demonstreerde een bedrijf in Burnaby, British Columbia, wat het zei een 16-qubit adiabatische kwantumcomputer was die supergeleidende circuits gebruikte. Eind 2008 maakte het bedrijf D-Wave bekend dat het het aantal qubits op 128 had gebracht. Veel experts waren sceptisch, maar in een Natuur paper dat eerder dit jaar werd gepubliceerd, toonden D-Wave-onderzoekers aan dat hun cel van acht qubit kwantumeffecten vertoont. Het bedrijf heeft meer dan $ 65 miljoen aan financiering opgehaald en in mei verkocht het zijn eerste commerciële apparaat, een 128-qubit D-Wave One, aan Lockheed Martin.
De supercomputers overtreffen
Een deel van het probleem met demonstraties zoals die van D-Wave, of zelfs met NMR-kwantumcomputers zoals die van Chuang, is dat de kwantumcircuits te eenvoudig zijn om berekeningen uit te voeren die conventionele computers niet kunnen. Scott Aaronson, een universitair hoofddocent informatica die met zijn 30 de jongste van de spraakmakende kwantumcomputeronderzoekers van het MIT is, probeert dat probleem aan te pakken door, zoals hij het uitdrukt, de onderzoekers halverwege te ontmoeten.
In 2011 stelden Aaronson en zijn afstudeerder Aleksandr Arkhipov een experiment voor dat, als het zou werken, een berekening zou uitvoeren die zelfs de krachtigste van de huidige supercomputers niet zou kunnen uitvoeren. De experimentele opstelling zou volgens hem veel eenvoudiger te bouwen moeten zijn dan een volledige kwantumcomputer.
Het experiment zou een reeks bundelsplitsers gebruiken, apparaten die worden gebruikt in optische netwerken om laserstralen in tweeën te splitsen. In 1987 ontdekten natuurkundigen van de Universiteit van Rochester dat als twee fotonen op exact hetzelfde moment bij een bundelsplitser zouden arriveren, kwantummechanische interacties beide zouden dwingen om naar rechts of naar links te gaan. Ze zouden nooit, zoals de wet van waarschijnlijkheden zou voorspellen, de bundelsplitser in verschillende richtingen verlaten.
Aaronson en Arkhipov stellen voor om een eindig aantal fotonen, bijvoorbeeld 20, door een reeks bundelsplitsers naar een reeks lichtdetectoren te leiden, bijvoorbeeld ongeveer 400. Het berekenen van de frequentie waarmee verschillende aantallen fotonen bij verschillende detectoren aankomen, is waarschijnlijk meer dan de rekencapaciteit van alle computers ter wereld. Maar, zo bewezen Aaronson en Arkhipov, dat geldt ook voor het berekenen van statistisch plausibele resultaten voor zelfs een paar dozijn runs van het experiment. Dit is echter een probleem dat een paar dozijn succesvolle uitvoeringen van het experiment zou oplossen.
Toen ze hun experiment voor het eerst beschreven, zei Terry Rudolph, een geavanceerd onderzoeker in de Quantum Optics and Laser Science-groep van Imperial College London, dat het de potentie heeft om ons voorbij te brengen aan wat ik de 'kwantum-singulariteit' zou willen noemen, waar we het eerste wat we kwantum niet kunnen doen op een klassieke computer.
Experimentele natuurkundigen van verschillende universiteiten zijn de uitdaging van Aaronson en Arkhipov aangegaan en hebben er vertrouwen in dat ze het experiment in relatief korte tijd aan het werk zullen krijgen met misschien vier fotonen. Een versie met 20 fotonen zal langer duren, en een volledig functionerende kwantumcomputer kan nog langer duren. Maar als die computer eindelijk is gebouwd en de geschiedenis van zijn uitvinding is geschreven, zullen de eerste hoofdstukken bezaaid zijn met de namen van MIT-professoren.