211service.com
Quantum Frontier
I maj 1981, vid en konferens anordnad av MIT:s laboratorium för datavetenskap, beskrev Richard Feynman '39 en teoretisk anordning som han kallade en kvantdator, som skulle utföra beräkningar genom att utnyttja materiens konstiga beteende i mycket små skalor. Teoretiska fysiker tog upp idén och visade att kvantdatorer i princip kunde göra allt vanliga datorer kunde och argumenterade för att de kanske skulle kunna göra vissa saker mycket, mycket snabbare. Ändå förblev kvantberäkning i mer än ett decennium, för alla utom ett fåtal entusiaster, ett ämne endast för passiv spekulation.
Från vänster: Professorerna Peter Shor, Scott Aaronson och Edward Farhi
Det förändrades spektakulärt 1994, när Peter Shor, PhD '85, nu professor i tillämpad matematik vid MIT, beskrev en kvantalgoritm för att hitta ett tals primtalsfaktorer. En kvantdator som kör Shors algoritm skulle kunna utföra factoring-uppgifter som dagens datorer inte kunde slutföra under universums livstid. Eftersom svårigheten att faktorisera stora siffror är allt som garanterar säkerheten för de flesta moderna kryptografiska system, var resten av världen - och särskilt organisationer som National Security Agency - tvungna att ta hänsyn till det. Shor visade att om man kunde bygga kvantdatorer så skulle det finnas folk som ville köpa dem, säger Seth Lloyd, professor i maskinteknik som studerar kvantdatorer. Shors algoritm utgjorde den mördande appen som fick alla intresserade.
Även om fullt fungerande kvantdatorer för allmänna ändamål förmodligen är decennier bort, gjorde Shors algoritm kvantberäkning till ett myllrande forskningsområde. Idag, säger Lloyd, är antalet forskare över hela världen som arbetar med kvantberäkning förmodligen någonstans runt 5 000. Jag tror att om vi får ytterligare 300 medlemmar i American Physical Society så blir vi en avdelning av American Physical Society, säger han. Och i alla avseenden, från att upptäcka nya algoritmer till att drömma om nya typer av datorer, är MIT-forskare mitt i striden.
Kvantmöjlighet
Kvantberäkning har sina rötter i kvantfysikens centrala mysterium: att små partiklar av materia kan leva i flera, till synes uteslutande tillstånd samtidigt. Avfyra en enskild foton - en ljuspartikel - mot en barriär med två slitsar i den, och den kommer att passera genom båda slitsarna på en gång. Elektroner har en egenskap som kallas spinn, vilket kan ses som rotation medurs eller moturs - men en enda elektron kan samtidigt snurra medurs och moturs. Denna förmåga att vara i mer än ett tillstånd åt gången, som fysiker kallar superposition, är, som Feynman en gång uttryckte det, omöjlig, absolut omöjlig, att förklara på något klassiskt sätt. För att göra saker ännu konstigare, om du har en kvantpartikel som är i flera tillstånd samtidigt och du utför någon mätning på den, snäpper den omedelbart till bara ett av dessa tillstånd. Och vilken av dem det antar är helt slumpmässigt. (Det är grunden för ett annat berömt fysikcitat - Einsteins insisterande, mot kvantfysikens dicta, att Gud inte spelar tärning med universum.)
Inom datavetenskap är den grundläggande informationsenheten biten, som kan ha ett av två värden, vanligtvis uttryckt som 0 och ett . Kvantberäkningspionjärerna insåg att eftersom en kvantpartikel kan vara i två tillstånd samtidigt, kan den representera 0 och ett på samma gång. Två kvantbitar – eller kvantbitar – skulle kunna representera fyra värden, tre av dem åtta, fyra av dem 16, och så vidare. En enda beräkning involverar N qubits skulle vara som att göra 2 N beräkningar på en gång.
Antag dock att du har åtta qubits, som representerar resultatet av 256 samtidiga beräkningar. Om du utför en mätning på qubits, kollapsar superpositionen: varje qubit antar omedelbart ett värde av antingen 0 eller ett . Du har bara en av de 256 initiala möjligheterna kvar, och den som väljs slumpmässigt. Hur garanterar du att det är den du vill ha?
Den första kvantalgoritmen
Det är frågan Shor svarade på, i det som fortfarande är det viktigaste resultatet inom vårt område, enligt Edward Farhi, chef för MIT:s Center for Theoretical Physics, som också forskar om kvantberäkning.
När en partikel i superposition slumpmässigt antar ett enda tillstånd, gör den det i enlighet med vissa sannolikheter: med tiden kommer partiklar att knäppa in i vissa tillstånd oftare än andra. Dessa sannolikheter kan avbildas som en kurva som råkar likna en vågtopp. Det visar sig att samma matematik som beskriver vågornas fysik också beskriver kvantsannolikheternas fysik.
När vågor kolliderar stör de varandra, antingen konstruktivt eller destruktivt. Om två krön skär varandra, blir resultatet en större krön; om ett krön skär ett tråg, tar de ut varandra. Shor hittade ett genialt sätt att representera problemet med factoring med sannolikhetsvågor, så att de rätta svaren skulle tendera att förstärka varandra medan de felaktiga i princip skulle försvinna. Resultatet är fortfarande en sannolikhetsvåg, men när superpositionen kollapsar är oddsen mycket höga att du får rätt svar.
Shor började arbeta med algoritmen 1993, när han var på AT&T:s Bell Labs forskningscenter, efter att ha hört ett föredrag om kvantberäkning av Umesh Vazirani '81, en professor vid University of California, Berkeley. Jobbar inte på heltid förstås, säger han. Faktum är att jag egentligen inte berättade för någon att jag arbetade med det förrän jag kom på det.
Egentligen var den första kvantalgoritmen som Shor berättade för någon om, i april 1994, en för att beräkna logaritmer, ett problem som är nära relaterat till faktorisering. Jag höll ett föredrag om algoritmen på Bell Labs på en tisdag, säger han. Den lördagen var jag hemma med en rejäl förkylning, och Umesh Vazirani ringde upp mig från Kalifornien, väldigt upprymd och sa: 'Jag hör att du vet hur man räknar med en kvantdator.' Det gjorde han faktiskt: i de mellanliggande fyra dagar hade han anpassat sin algoritm till just det problemet. De Ekonom intervjuade mig inte långt efter det, säger Shor. Snart fick jag massor av e-postmeddelanden om algoritmen, och jag hade fortfarande inte skrivit tidningen ännu. När han höll sitt första offentliga föredrag om det på Cornell i början av maj, säger han och skrattar, någon från NSA pratade med mig om det efteråt.
Utnyttja MRI-teknik
När Seth Lloyd kom till MIT 1994, hade jag skrivit en massa artiklar om kvantberäkning, säger han. Jag och kanske, typ, fem eller sex andra personer hade arbetat med detta före 1994. För Lloyd hade tillkännagivandet av Shors algoritm en mycket konkret effekt: Det gjorde det mycket lättare att få anställning.
En av tidningarna Lloyd hade publicerat, i Vetenskap 1993 föreslog den första genomförbara designen för en kvantdator. Man kan tänka sig det som en kopp full av molekyler, säger han. I varje molekyl representerades qubits av olika typer av atomer, och alla molekyler i koppen skulle utföra samma beräkning samtidigt.
I separat forskning visade gästprofessor David Cory och Neil Gershenfeld, chef för Media Labs Physics and Media Group, att Lloyds design kunde realiseras med hjälp av kärnmagnetisk resonans (NMR), fenomenet som ligger bakom magnetisk resonanstomografi. En kraftfull magnet skulle rikta in snurrarna hos atomerna som utgör molekylerna. Olika frekvenser av radiovågor kan sedan sätta några av atomerna i superposition och vända snurrarna på andra. Elektronerna med bestämda snurr skulle representera data, och snurren i superposition skulle representera resultatet av flera operationer utförda på dessa data.
1998 slog Gershenfeld sig ihop med Isaac Chuang '90, '91, SM '91, sedan vid IBM Almaden Research Center i San Jose, Kalifornien, och Mark Kubinec från UC Berkeley för att bygga det första datorsystemet som använde NMR för att exekvera ett kvantum. algoritm. Den hade två qubits.
År 2000 återvände Chuang till MIT, där han nu är professor i fysik och elektroteknik och datavetenskap. Nästa år byggde han och IBM-kollegor en sju-qubit NMR-dator som framgångsrikt körde Shors algoritm för första gången. Den fastställde att primfaktorerna för 15 mycket troligt är tre och fem.
Ett problem med NMR-kvantberäkning är att eftersom qubits representeras av olika atomer i en enda molekyl, kräver mer komplexa beräkningar mer komplexa molekyler. Men ju större molekylen är, desto starkare är dess elektromagnetiska fält, och desto större är svårigheten att särskilja den elektromagnetiska signal som produceras av en enda atom. Vissa forskare undersöker små sensorer som kan läsa magnetiska signaler från enskilda molekyler. Men Chuang, bland andra, har vänt sig till kvantdatorer som använder joner fångade i elektromagnetiska fält som qubits, en teknik som föreslogs 1995 av forskare vid Österrikes universitet i Innsbruck.
Kvantberäkning av jonfällor använder roterande magnetfält för att isolera enskilda molekyler, och laserljus snarare än radiopulser för att ändra molekylernas kvanttillstånd. Även om det ger forskare mer exakt kontroll över qubits än vad befintliga NMR-tekniker gör, kräver det också det. Elektroner som kretsar kring en kärna kan vara i olika energitillstånd. Lägg till tillräckligt med energi till en elektron, och den kommer att dyka upp till nästa energinivå; om den bara tappar lite energi kommer den att falla ner igen. Kvantberäkning av jonfällor kräver att elektroner hålls i olika, exakt specificerade energitillstånd. Detta är så knepigt att vissa forskare började fundera på om det kunde finnas en kvantdator som bara stannade i sitt lägsta energitillstånd.
Ett adiabatiskt tillvägagångssätt
År 2000 föreslog MIT-fysikerna Edward Farhi och Jeffrey Goldstone, matematikavdelningens Michael Sipser och Northeasterns Sam Gutmann, '73, PhD '77, en ny typ av kvantdator, kallad en adiabatisk kvantdator, som alltid är i sin lägsta energi stat. (Objekt tenderar att söka de lägsta energitillstånden de kan hitta, så lågenergitillstånd tenderar att vara mer stabila än höga.) Uppsatsen specificerade inte hur qubits skulle realiseras. Men det var baserat på insikten att lösningar på beräkningsproblem kunde representeras som de lägsta energitillstånden i ett fysiskt system.
Två magneter, till exempel, kommer att tendera att rada upp nordpolen till sydpolen eftersom det tar mindre energi än att tvinga ihop nordpolerna. Ett gäng magneter placerade godtyckligt på en bräda kommer därför att börja vända så att så många av dem som möjligt är riktade nord-sydlig. I teorin, om du placerade magneter i rätt mönster och ställer in deras initiala orienteringar på precis rätt sätt, kan du koda ett beräkningsproblem. När magneterna vände för att hitta sin lägsta energiorientering, skulle de konvergera på problemets lösning. Adiabatisk kvantberäkning är liknande, men den kan utforska många möjliga lösningar samtidigt, eftersom den skulle använda qubits snarare än magneter.
Med adiabatisk kvantberäkning skulle ett kvantmekaniskt fysiskt system sättas upp i sitt lägsta energitillstånd, kallat grundtillstånd. Inledningsvis skulle systemet koda ett mycket enklare problem än det det är avsett att lösa. Men med tiden skulle någon kontrollparameter för systemet – säg styrkan på dess elektromagnetiska fält – gradvis förändras, tills systemet slutade koda det svårare problemet. Om förändringen skedde tillräckligt långsamt, skulle systemet stanna i sitt grundtillstånd, så det skulle sluta representera lösningen på problemet.
Vissa människor tror att om du hade en kvantdator som behövdes för att stanna i sitt marktillstånd - genom att, låt oss säga, göra den väldigt kall - att det kan göra systemet lite mindre benäget att fel, säger Farhi. För om du alltid är kall, och du alltid är i marktillståndet, är det förmodligen en lättare plats att vara på än i något upphetsat tillstånd som du noggrant måste kontrollera.
Problemet med det adiabatiska tillvägagångssättet är att systemet måste förändras långsamt för att hindra det från att hoppa till ett högre energitillstånd, och ingen vet hur långsamt det är långsamt nog. Om det går oändligt långsamt vet vi att det kommer att fungera, säger Farhi. Men om systemet måste förändras för långsamt kommer det inte att erbjuda några fördelar jämfört med konventionella datorer.
Farhi fortsätter att undersöka frågan om hur snabbt ett adiabatiskt kvantberäkningssystem kan förändras, både genom datormodellering av relativt enkla system och genom matematisk analys. Samtidigt, 2002, föreslog Lloyd och Bill Kaminsky, en doktorand i hans grupp, ett sätt att realisera en adiabatisk kvantdator med hjälp av supraledande elektriska kretsar, i vilka strömflödet kan vara i superposition: i praktiken flyter strömmen medurs och moturs kl. en gång. Strömflödets riktning representerar värdet av en qubit, och systemets totala energi beror på strömflödesriktningen i intilliggande kretsar. När ett magnetfält appliceras går strömmarna i superposition. När det mäts, snäpper systemet sedan in i sitt lägsta energitillstånd och avslöjar svaret. Två år senare, Lloyd; Wim van Dam, postdoc i Farhis grupp; och fyra andra forskare från fyra olika universitet bevisade att en adiabatisk kvantdator i princip kunde utföra vilken beräkning som helst som en konventionell kvantdator kunde.
2007 visade ett företag i Burnaby, British Columbia, vad det sa var en 16-qubit adiabatisk kvantdator som använde supraledande kretsar. I slutet av 2008 meddelade företaget, D-Wave, att det hade fått qubit-antalet upp till 128. Många experter har varit skeptiska, men i en Natur I ett dokument som publicerades tidigare i år, visade D-Wave-forskare att deras åtta-qubit-cell uppvisar kvanteffekter. Företaget har samlat in mer än 65 miljoner dollar i finansiering och i maj sålde det sin första kommersiella enhet, en 128-qubit D-Wave One, till Lockheed Martin.
Överträffar superdatorerna
En del av problemet med demonstrationer som D-Waves, eller till och med med NMR-kvantdatorer som Chuangs, är att kvantkretsarna är för enkla för att utföra beräkningar som konventionella datorer inte kan. Scott Aaronson, en docent i datavetenskap som, vid 30, är den yngsta av MIT:s högprofilerade kvantberäkningsforskare, försöker ta itu med det problemet genom att, som han uttrycker det, möta experimentalisterna halvvägs.
År 2011 föreslog Aaronson och hans doktorand Aleksandr Arkhipov ett experiment som, om det fungerade, skulle utföra en beräkning som inte ens den mest kraftfulla av dagens superdatorer kunde utföra. Den experimentella uppställningen borde, menar han, vara mycket enklare att bygga än en fullskalig kvantdator.
Experimentet skulle använda en serie stråldelare, enheter som används i optiska nätverk för att dela laserstrålar i två. 1987 upptäckte fysiker vid University of Rochester att om två fotoner anlände till en stråldelare på exakt samma tid, skulle kvantmekaniska interaktioner tvinga båda att gå till höger eller vänster. De skulle aldrig, som sannolikhetslagen skulle förutsäga, lämna stråldelaren i olika riktningar.
Aaronson och Arkhipov föreslår att dirigera ett ändligt antal fotoner – säg 20 – genom en serie stråldelare till en uppsättning ljusdetektorer – säg cirka 400. Att beräkna frekvensen med vilken olika antal fotoner skulle anlända till olika detektorer är förmodligen bortom beräkningskapaciteten hos alla datorer i världen. Men Aaronson och Arkhipov bevisade, så är att beräkna statistiskt rimliga utfall även för ett par dussin körningar av experimentet. Detta är dock ett problem som ett par dussin framgångsrika körningar av experimentet skulle lösa.
När de först beskrev sitt experiment, sa Terry Rudolph, en avancerad forskare i Imperial College Londons Quantum Optics and Laser Science-grupp, att det har potential att ta oss förbi vad jag skulle vilja kalla 'kvantsingulariteten', där vi gör det första kvantmässigt som vi inte kan göra på en klassisk dator.
Experimentella fysiker vid flera universitet har antagit Aaronson och Arkhipovs utmaning och är övertygade om att de inom relativt kort tid kommer att få experimentet att fungera med kanske fyra fotoner. En version med 20 fotoner kommer att ta längre tid, och en fullt fungerande kvantdator kan ta längre tid. Men när den datorn äntligen är byggd och historien om dess uppfinning är skriven, kommer de tidiga kapitlen att fyllas med namn på MIT-professorer.