Een opvallend nieuw bewijs in de complexiteit van kwantumcomputers kan het best worden begrepen met een speels gedachte-experiment. Laat een bad lopen en gooi dan een stel drijvende staafmagneten in het water. Elke magneet zal zijn richting heen en weer draaien en proberen uit te lijnen met zijn buren. Het zal duwen en trekken aan de andere magneten en wordt terug geduwd en getrokken. Probeer nu dit te beantwoorden: wat zal de uiteindelijke regeling van het systeem zijn?
Dit probleem en andere soortgelijke problemen, zo blijkt, zijn onmogelijk ingewikkeld. Met meer dan een paar honderd magneten zouden computersimulaties een belachelijke hoeveelheid tijd vergen om het antwoord uit te spuwen.
Maak die magneten nu kwantum - individuele atomen onderworpen aan de byzantijnse regels van de kwantumwereld. Zoals je zou kunnen raden, wordt het probleem nog moeilijker. "De interacties worden ingewikkelder", zei Hendrik Yuen van de Columbia-universiteit. "Er is een meer gecompliceerde beperking wanneer twee aangrenzende 'kwantummagneten' gelukkig zijn."
Deze eenvoudig ogende systemen hebben uitzonderlijke inzichten opgeleverd in de grenzen van de berekening, zowel in de klassieke als in de kwantumversie. In het geval van klassieke of niet-kwantumsystemen, a mijlpaalstelling uit de informatica brengt ons verder. Het wordt de PCP-stelling genoemd (voor "waarschijnlijk controleerbaar bewijs"), het zegt dat niet alleen de uiteindelijke toestand van de magneten (of aspecten die ermee verband houden) ongelooflijk moeilijk te berekenen is, maar dat geldt ook voor veel van de stappen die ernaartoe leiden. De complexiteit van de situatie is zelfs nog ingrijpender, met andere woorden, met de uiteindelijke toestand omgeven door een zone van mysterie.
Een andere versie van de PCP-stelling, die nog niet is bewezen, gaat specifiek over de kwantumzaak. Computerwetenschappers vermoeden dat het vermoeden van kwantum-PCP waar is, en bewijzen dat het ons begrip van de complexiteit van kwantumproblemen zou veranderen. Het wordt beschouwd als het belangrijkste open probleem in de quantum computationele complexiteitstheorie. Maar tot nu toe is het onbereikbaar gebleven.
Negen jaar geleden identificeerden twee onderzoekers een tussendoel om ons te helpen daar te komen. Ze kwamen met een eenvoudigere hypothese, bekend als het "no low-energy triviale state" (NLTS) vermoeden, dat waar zou moeten zijn als het kwantum-PCP-vermoeden waar is. Bewijzen zou het niet per se gemakkelijker maken om het kwantum-PCP-vermoeden te bewijzen, maar het zou enkele van de meest intrigerende vragen oplossen.
Toen vorige maand drie computerwetenschappers bewees het NLTS vermoeden. Het resultaat heeft opvallende implicaties voor de informatica en de kwantumfysica.
"Het is heel spannend," zei Dorit Aharanov van de Hebreeuwse Universiteit van Jeruzalem. "Het zal mensen aanmoedigen om het moeilijkere probleem van het kwantum-PCP-gissing te onderzoeken."
Om het nieuwe resultaat te begrijpen, begint u met het voorstellen van een kwantumsysteem zoals een reeks atomen. Elk atoom heeft een eigenschap, spin genaamd, die enigszins lijkt op de uitlijning van een magneet, in die zin dat het langs een as wijst. Maar in tegenstelling tot de uitlijning van een magneet, kan de spin van een atoom zich in een toestand bevinden die een gelijktijdige vermenging van verschillende richtingen is, een fenomeen dat bekend staat als superpositie. Verder kan het onmogelijk zijn om de spin van één atoom te beschrijven zonder rekening te houden met de spins van andere atomen uit verre gebieden. Wanneer dit gebeurt, zouden die onderling verbonden atomen zich in een staat van kwantumverstrengeling bevinden. Verstrengeling is opmerkelijk, maar ook fragiel en gemakkelijk verstoord door thermische interacties. Hoe meer warmte in een systeem, hoe moeilijker het is om het te verstrikken.
Stel je nu voor dat je een stel atomen afkoelt tot ze het absolute nulpunt naderen. Naarmate het systeem koeler wordt en de verstrengelingspatronen stabieler worden, neemt de energie ervan af. De laagst mogelijke energie, of 'grondenergie', geeft een beknopte beschrijving van de gecompliceerde eindtoestand van het hele systeem. Of dat zou het tenminste zijn, als het kon worden berekend.
Vanaf het einde van de jaren negentig ontdekten onderzoekers dat voor bepaalde systemen deze grondenergie nooit binnen een redelijk tijdsbestek kon worden berekend.
Natuurkundigen dachten echter dat een energieniveau dicht bij de grondenergie (maar niet helemaal daar) gemakkelijker te berekenen zou zijn, omdat het systeem warmer en minder verstrikt zou zijn, en daarom eenvoudiger.
Computerwetenschappers waren het daar niet mee eens. Volgens de klassieke PCP-stelling zijn energieën die dicht bij de eindtoestand liggen net zo moeilijk te berekenen als de eindenergie zelf. En dus zou de kwantumversie van de PCP-stelling, indien waar, zeggen dat de voorloperenergieën van de grondenergie net zo moeilijk te berekenen zijn als de grondenergie. Omdat de klassieke PCP-stelling waar is, denken veel onderzoekers dat de kwantumversie ook waar zou moeten zijn. "Zeker, een kwantumversie moet waar zijn", zei Yuen.
De fysieke implicaties van een dergelijke stelling zouden ingrijpend zijn. Het zou betekenen dat er kwantumsystemen zijn die hun verstrengeling behouden bij hogere temperaturen - volledig in tegenspraak met de verwachtingen van natuurkundigen. Maar niemand kon bewijzen dat dergelijke systemen bestaan.
In 2013 verkleinden Michael Freedman en Matthew Hastings, beiden werkzaam bij Microsoft Research's Station Q in Santa Barbara, Californië, het probleem. Ze besloten op zoek te gaan naar systemen waarvan de laagste en bijna laagste energieën moeilijk te berekenen zijn volgens slechts één metriek: de hoeveelheid circuits die een computer nodig zou hebben om ze te simuleren. Deze kwantumsystemen zouden, als ze ze konden vinden, rijke patronen van verstrengeling moeten behouden bij al hun laagste energieën. Het bestaan van dergelijke systemen zou het vermoeden van kwantum-PCP niet bewijzen - er kunnen andere hardheidsstatistieken zijn om te overwegen - maar het zou als vooruitgang gelden.
Computerwetenschappers kenden dergelijke systemen niet, maar ze wisten waar ze moesten zoeken: in het studiegebied dat kwantumfoutcorrectie wordt genoemd, waar onderzoekers recepten voor verstrengeling creëren die zijn ontworpen om atomen te beschermen tegen verstoring. Elk recept staat bekend als een code en er zijn veel codes van zowel grotere als kleinere omvang.
Eind 2021 zullen computerwetenschappers een grote doorbraak gemaakt bij het creëren van kwantumfoutcorrigerende codes van in wezen ideale aard. In de daaropvolgende maanden bouwden verschillende andere groepen onderzoekers voort op die resultaten om verschillende versies te maken.
De drie auteurs van het nieuwe artikel, die de afgelopen twee jaar hadden samengewerkt aan gerelateerde projecten, kwamen samen om te bewijzen dat een van de nieuwe codes alle eigenschappen had die nodig zijn om een kwantumsysteem te maken van het soort dat Freedman en Hastings hadden verondersteld . Daarmee bewezen ze het NLTS-vermoeden.
Hun resultaat toont aan dat verstrengeling niet per se zo kwetsbaar en temperatuurgevoelig is als fysici dachten. En het ondersteunt het kwantum-PCP-vermoeden, wat suggereert dat zelfs buiten de grondenergie de energie van een kwantumsysteem vrijwel onmogelijk te berekenen is.
"Het vertelt ons dat wat onwaarschijnlijk leek te zijn waar is," zei Isaak Kim van de Universiteit van Californië, Davis. "Zij het in een heel raar systeem."
Onderzoekers zijn van mening dat er verschillende technische hulpmiddelen nodig zullen zijn om het volledige vermoeden van kwantum-PCP te bewijzen. Ze zien echter redenen om optimistisch te zijn dat het huidige resultaat hen dichterbij zal brengen.
Ze zijn misschien het meest geïntrigeerd door de vraag of de nieuw ontdekte NLTS-kwantumsystemen - hoewel in theorie mogelijk - daadwerkelijk in de natuur kunnen worden gecreëerd en hoe ze eruit zouden zien. Volgens het huidige resultaat zouden ze complexe patronen van langeafstandsverstrengeling nodig hebben die nooit in het laboratorium zijn geproduceerd en die alleen kunnen worden gebouwd met behulp van astronomische aantallen atomen.
"Dit zijn hoogontwikkelde objecten," zei Chinmay Nirkhe, een computerwetenschapper aan de University of California, Berkeley, en een co-auteur van het nieuwe artikel samen met Anurag Anshu van Harvard University en Nikolas Breuckman van University College Londen.
"Als je echt verre qubits kunt koppelen, denk ik dat je het systeem kunt realiseren", zei Anshu. "Maar er moet nog een reis worden gemaakt om echt naar het lage-energiespectrum te gaan." Breuckmann toegevoegd: "Misschien is er een deel van het universum dat NLTS is. Ik weet het niet."
