Quantum algorithm for the gradient of a logarithm-determinant

In het uitgestrekte landschap van de moderne wetenschap, van het modelleren van het gedrag van subatomaire deeltjes tot het trainen van kunstmatige intelligentie, is er een terugkerende wiskundige uitdaging: begrijpen hoe een enorme collectie getallen verandert wanneer je slechts één van hen aanpast. Wetenschappers werken vaak met rasters van gegevens, bekend als matrices, die alles kunnen vertegenwoordigen van de energietoestanden van een molecuul tot de relaties tussen miljoenen gebruikers in een sociaal netwerk. Om deze rasters betekenis te geven, moeten onderzoekers frequent een specifieke waarde berekenen die de logaritme-determinant wordt genoemd. Deze waarde fungeert als een samenvatting van het gedrag van het gehele raster, en zijn veranderingssnelheid — de afgeleide — onthult cruciale fysieke grootheden, zoals hoe een systeem reageert op druk of hoe men een wiskundige operatie kan omkeren om een ontbrekend stukje informatie te vinden. Op klassieke computers, de machines die we dagelijks gebruiken, is het berekenen van deze afgeleiden voor grote rasters ongelooflijk traag en intensief qua middelen. Naarmate de omvang van de data groeit, neemt de tijd die nodig is om het probleem op te lossen zo snel toe dat het snel onmogelijk wordt om te voltooien, wat effectief een muur vormt die de vooruitgang in velden zoals kwantumfysica en machine learning blokkeert.

Een team van onderzoekers heeft nu een nieuwe manier voorgesteld om dit probleem aan te pakken met behulp van de unieke mogelijkheden van kwantumcomputers. In plaats van te proberen elk enkel getal in een enorm raster één voor één te berekenen, richt hun methode zich op de onderliggende patronen die het gedrag van het raster definiëren. Ze ontwikkelden een algoritme dat het raster niet behandelt als een statisch blok getallen, maar als een dynamisch systeem met specifieke trilling-achtige toestanden, bekend als eigentoestanden. Door de kwantumcomputer voor te bereiden om een paar van deze belangrijkste toestanden vast te houden, kunnen de onderzoekers de machine vragen hoe de algemene samenvattingswaarde van het systeem verandert wanneer een kleine, gecontroleerde duw wordt toegepast op de data. De belangrijkste innovatie is dat ze niet het hele raster hoeven te zien om het antwoord te krijgen. In plaats van elk element van de matrix te meten, wat een onmogelijk lange tijd zou kosten, meet het algoritme een enkele gemiddelde waarde van de kwantumtoestand. Deze aanpak stelt de computer in staat om de afgeleide van de logaritme-determinant te bepalen met een efficiëntieniveau dat zeer traag groeit naarmate de data groter wordt, in plaats van dat de complexiteit explodeert.

De onderzoekers hebben aangetoond dat deze methode werkt door het probleem op te splitsen in twee hoofdstappen. Eerst gebruiken ze een techniek om de meest significante trillingstoestanden van de invoerdata te identificeren, waarbij ze de ruis wegfilteren en zich concentreren op de delen die er het meest toe doen. Dit is bijzonder effectief wanneer de data een structuur heeft waarbij slechts enkele toestanden het gedrag domineren, een veelvoorkomend scenario in veel fysische systemen en machine learning-modellen. Zodra deze sleuteltoestanden zijn geïsoleerd, past het algoritme een gecontroleerde verstoring toe op het systeem. Vervolgens gebruiken ze een proces dat vergelijkbaar is met het meten van de toonhoogte van een geluid om te detecteren hoe de energie van deze toestanden verschuift als reactie op de verstoring. Door deze verschuiving te analyseren, kan de computer de afgeleide van de logaritme-determinant afleiden. De schoonheid van de methode is dat het de computer in staat stelt het antwoord te produceren door slechts een beperkt aantal instructies op te vragen, ongeacht hoe groot het oorspronkelijke raster met getallen was.

Deze aanpak biedt een dramatische verbetering ten opzichte van de beste methoden die beschikbaar zijn op klassieke computers. Terwijl traditionele technieken tijd vereisen die kubisch groeit met de omvang van de data, waardoor ze onpraktisch zijn voor zeer grote systemen, schaalt deze kwantummethode op een manier die bijna constant is ten opzien van de omvang van de data, afhankelijk van alleen het aantal belangrijke toestanden en de gewenste precisie. De onderzoekers toonden aan dat voor systemen waarbij slechts een klein aantal toestanden relevant is, het algoritme veel sneller convergeert naar het juiste antwoord dan enig bekend klassiek alternatief. Ze verkenden ook hoe dit toegepast kon worden op machine learning, specifiek voor het trainen van modellen die vertrouwen op kernelfuncties, wat wiskundige hulpmiddelen zijn die worden gebruikt om patronen in complexe data te vinden. In deze gevallen kan het vermogen om snel de inverse van een matrix te berekenen — een taak die centraal staat bij het trainen van deze modellen — de analyse van veel grotere en complexere datasets mogelijk maken dan momenteel haalbaar is.

Het artikel erkent dat hoewel het theoretische kader solide is, de praktische implementatie afhangt van het vermogen om kwantumcomputers te bouwen die deze stappen met hoge precisie en zonder fouten kunnen uitvoeren. Het algoritme vertrouwt op het vermogen van de computer om tijdsevolutie-operaties uit te voeren, wat in essentie simulaties zijn van hoe een systeem in de loop van de tijd verandert, met extreem kleine foutmarges. De auteurs suggereren dat, hoewel volledig fouttolerante kwantumcomputers nog in ontwikkeling zijn, de methode potentieel aangepast kan worden voor gebruik op nabije-toekomst machines (near-term machines). Ze merkten ook op dat de efficiëntie van het algoritme sterk verbonden is met het vermogen om de initiële kwantumtoestand correct voor te bereiden. Als de computer gevoed kan worden met een toestand die een gelijke mix vertegenwoordigt van alle belangrijke trillingsmodi, wordt de methode zelfs krachtiger, wat de computationele kosten potentieel verder verlaagt.

Uiteindelijk biedt dit werk een duidelijk pad voor het oplossen van een probleem dat al lang een knelpunt vormt in zowel de fysica als de computerwetenschappen. Door de focus te verleggen van het berekenen van elk individueel getal naar het meten van de collectieve respons van de belangrijkste toestanden van het systeem, hebben de onderzoekers aangetoond dat kwantumcomputers deze berekeningen kunnen uitvoeren met een snelheid die klassieke machines niet kunnen evenaren. De bevindingen suggereren dat taken die momenteel dagen of weken aan berekeningen vergen, in de toekomst in momenten voltooid kunnen worden, wat de deur opent naar nieuwe ontdekkingen in de statistische fysica, kwantumveldentheorie en de volgende generatie kunstmatige intelligentie. De methode claimt niet om elke instantie van het probleem direct op te lossen, maar het vestigt een nieuwe standaard voor efficiëntie, waarmee wordt bewezen dat met de juiste aanpak, de exponentiële groei van data niet hoeft te betekenen dat de moeilijkheid ook exponentieel groeit.