Een nieuwe studie heeft vragen over natuurkunde, informatica en wiskunde opgelost
De dagdromen van computerwetenschappers hebben de kracht van de kwantummechanica onthuld.
Stel je voor dat je alwetende wezens ontmoet die beweren de oplossing te hebben voor een complex probleem dat geen enkele computer ooit zou kunnen oplossen. U zou waarschijnlijk het antwoord niet kunnen controleren. Maar nu melden computerwetenschappers dat de kwantummechanica een manier biedt om snel de oplossingen te verifiëren voor een ongelooflijk brede klasse van problemen, waaronder enkele die in de eerste plaats onmogelijk op te lossen zijn.
Hoewel het resultaat geen voor de hand liggende praktische toepassingen heeft, hebben de theoretische gevolgen dat wel had een rimpeleffect, die onopgeloste vragen in de natuurkunde en wiskunde beantwoorden, rapporteren wetenschappers in een paper dat op 13 januari op arXiv.org is geplaatst. ‘Het heeft zoveel gevolgen voor al deze gebieden. Het maakt niet uit hoe je het bekijkt, ‘zegt de theoretische informaticus Scott Aaronson van de Universiteit van Texas in Austin, die niet betrokken was bij de nieuwe studie.
In de informatica zijn sommige problemen moeilijk op te lossen, maar hebben oplossingen die gemakkelijk te controleren zijn. Onderzoekers classificeren vragen dus naar hoe moeilijk het voor computers is om vermeende antwoorden te verifiëren.
Op zichzelf kan een computer slechts zo ver gaan in het verifiëren van oplossingen. Maar wetenschappers hebben een paar trucjes voor de boeg. Ze verzinnen scenario’s waarin een ‘bewaker’ – een computer of persoon die beweert een oplossing voor een probleem te hebben – wordt doorspekt met vragen van de persoon die de oplossing probeert te controleren, de ‘verificateur’.
Stel je bijvoorbeeld voor dat je een vriend hebt die beweert te hebben afgeleid hoe hij het verschil tussen Pepsi en Coke kan onderscheiden, ook al kun je geen onderscheid maken tussen de twee. Om deze bewering te bevestigen, kunt u – de verificateur – een kopje Pepsi of Coca-Cola bereiden en uw vriend, de spreekwoordelijke, vragen over welke het is. Als je vriend consequent het juiste antwoord geeft op dergelijke vragen, zou je ervan overtuigd zijn dat het cola-identificatie-dilemma was opgelost.
Bekend als een interactief bewijs, kan deze strategie aanvullende informatie onthullen waarmee computerwetenschappers oplossingen voor problemen kunnen verifiëren die te moeilijk zijn voor een computer om de wetenschappers onafhankelijk te overtuigen. Bij nog krachtigere interactieve proefdrukken zijn meerdere bewijzen betrokken. Dat scenario lijkt een beetje op een politieverhoor van twee verdachten, geïsoleerd in aparte kamers, die hun antwoorden niet kunnen coördineren om een onderzoeker te misleiden.
De klasse van problemen die op deze manier kan worden geverifieerd, is ‘groot, maar niet belachelijk groot’, zegt studieauteur Thomas Vidick, een theoretisch informaticus bij Caltech. Om de oplossingen voor een nog grotere verscheidenheid aan problemen te controleren, kunnen wetenschappers zich voorstellen dat ze een andere wending toevoegen: de testers delen een kwantumverbinding genaamd verstrengeling, waardoor twee schijnbaar onafhankelijke objecten zich op gecorreleerde manieren gedragen (SN: 25-4-18).
Tot nu toe was niet bekend hoeveel problemen verifieerbaar waren met kwantumverstrengeling. Het nieuwe resultaat laat zien dat het ‘een ongelooflijk groot aantal problemen’ is, zegt Aaronson.
Die enorme groep wordt recursief opsommen of RE-problemen genoemd. ‘Het bevat alle problemen die door computers kunnen worden opgelost en nog meer’, zegt medeauteur Henry Yuen, informaticus aan de Universiteit van Toronto. ‘Dat is gek.’ Het is het ‘en nog wat’ dat echt verbijsterend is. Geen enkele computer zou die problemen ronduit kunnen oplossen, maar als twee met elkaar verweven alwetende wezens een oplossing hadden, konden ze je ervan overtuigen dat het juist was. Natuurlijk wordt het toepassen van de verificatietechniek in de echte wereld ongeloofwaardig gemaakt door het gebrek aan alwetende wezens om de antwoorden te geven.
Het resultaat wordt samengevat in de beknopte gelijkheid, MIP * = RE, waar MIP * staat voor Multi-prover Interactive Proof met kwantumverstrengeling. Elk probleem bij RE zit ook in MIP * en vice versa.
Hoewel nog niet door vakgenoten beoordeeld, wordt de studie zeer serieus genomen, zegt informaticus Lance Fortnow van het Illinois Institute of Technology in Chicago. ‘Ik durf te wedden dat het waarschijnlijk juist is…. Er is geen reden om te denken dat het verkeerd is. ‘
En het resultaat is een drievoudige bedreiging: het loste drie problemen tegelijk op. Behalve dat MIP * gelijk is aan RE, beantwoordde het tegelijkertijd twee andere open vragen, één in de natuurkunde en één in de wiskunde. De eerste is een kwantumfysica-puzzel genaamd Tsirelson’s probleem, die vraagt of de soorten kwantumcorrelaties die kunnen worden geproduceerd met een oneindige hoeveelheid verstrengeling kunnen worden benaderd met een zeer grote, maar eindige hoeveelheid verstrengeling. Het antwoord, zo blijkt uit de studie, is nee: soms kun je niet eens in de buurt komen van het repliceren van oneindige verstrikking met eindige verstrikking.
In de wiskunde lost de studie Connes ‘inbeddingstwist op, een al lang bestaand idee dat wiskundig gelijkwaardig is aan het probleem van Tsirelson. Het behandelt ook de vraag of een eindige benadering noodzakelijkerwijs iets echt oneindigs kan repliceren. Nogmaals, het antwoord is nee.
‘Het is een ongelooflijke prestatie; het is gewoon heel spannend ‘, zegt wiskundige William Slofstra van de University of Waterloo in Canada. ‘Het is een vervulling van iets dat we al heel lang willen.’