In de wereld van informatie is het beschermen van gegevens tegen corruptie een kwestie van overleven. Of het nu gaat om het verzenden van een bericht via een ruisachtig radiokanaal of het opslaan van een bestand op een harde schijf, ingenieurs gebruiken foutcorrigerende codes. Dit zijn wiskundige structuren die redundantie aan gegevens toevoegen, waardoor een ontvanger fouten kan detecteren en herstellen zonder om een herverzending te vragen. Decennialang hebben wetenschappers geweten dat het vinden van de meest robuuste versie van deze codes een ongelooflijk moeilijk puzzelstuk is. In de klassieke wereld, waar gegevens bestaan uit eenvoudige bits die ofwel nul of één zijn, is bewezen dat het berekenen van de exacte sterkte van een code een taak is die zo complex is dat geen enkel efficiënt computeralgoritme dit voor elk geval kan oplossen.

Het kwantumdomein werkt echter volgens andere regels. In plaats van bits gebruiken kwantumcomputers qubits, die in delicate superposities van toestanden kunnen bestaan. Om deze fragiele informatie te beschermen, gebruiken natuurkundigen kwantumfoutcorrigerende codes, die veel ingewikder zijn dan hun klassieke tegenhangers. Een belangrijke maatstaf voor de sterkte van een kwantumcode is de "afstand", een getal dat ons vertelt hoeveel fouten de code kan weerstaan voordat de informatie verloren gaat. Als de afstand klein is, is de code fragiel; als de afstand groot is, is de code robuust. Lange tijd geloofden onderzoekers dat hoewel het vinden van deze afstand moeilijk was, het misschien niet zo moeilijk was als de klassieke versie. Enkele recente studies suggereerden dat de moeilijkheid op een bepaald punt zou kunnen afvlakken, wat een barrière creëerde waarbij het probleem gemakkelijker te benaderen bleek dan voorheen gedacht. Dit idee hintte erop dat kwantumcodes een verborgen eenvoud zouden kunnen bezitten die klassieke codes missen.

Een nieuwe studie door Upendra Kapshikar aan de Universiteit van Ottawa daagt dit idee direct uit. De onderzoeker heeft aangetoond dat de moeilijkheid van het benaderen van de afstand van een kwantumcode net zo ernstig is als de klassieke versie, en reikt tot aan de uiterste grenzen van wat computers kunnen doen, mits bepaalde fundamentele complexiteitshypothesen standhouden. Door een specifieke brug te bouwen tussen klassieke en kwantumproblemen, bewijst Kapshikar dat er geen kortere weg is naar het vinden van de sterkte van deze kwantumcodes. Het werk demonstreert dat het proberen te raden van de afstand binnen een redelijke foutmarge een taak is die computationeel onmogelijk blijft voor elk efficiënt algoritme, tenzij breed geaccepteerde aannames over de aard van berekeningen instorten. Dit sluit effectief de deur op de gedachte dat kwantumcodes een speciale, gemakkelijker op te lossen eigenschap bezitten.

Om de betekenis van dit resultaat te begrijpen, moet men eerst de aard van het probleem vatten. In een kwantumcomputer kunnen fouten binnensluipen vanuit de omgeving, waarbij de toestand van een qubit wordt omgeklapt of de fase verschuift. Een kwantumcode is ontworpen om deze fouten op te vangen. De "afstand" van de code is het minimum aantal qubits dat beïnvloed moet worden door een fout voordat de code er niet meer in slaagt deze te detecteren. Als een code een afstand van tien heeft, kan hij elke fout detecteren die negen of minder qubits beïnvloedt. De uitdaging voor computerwetenschappers is dat het, gegeven een beschrijving van een code, een nachtmerrie is om dit exacte getal te berekenen. In de klassieke wereld werd jaren geleden bewezen dat je zelfs niet snel dicht bij het juiste antwoord kunt komen; het probleem is "NP-hard", wat betekent dat naarmate de code groter wordt, de benodigde tijd explosief toeneemt.

Voor kwantumcodes leek de situatie minder helder. Eerdere onderzoeken hadden weliswaar bewezen dat het probleem moeilijk was, maar slechts tot een bepaald punt. Die eerdere bewijzen konden aantonen dat het vinden van de afstand moeilijk was als men een antwoord wilde binnen een gat dat meegroeide met de vierkantswortel van de grootte van de code. Ze konden echter niet bewijzen dat het moeilijk was om een antwoord te vinden binnen een gat dat lineair meegroeide met de grootte. Stel je een code voor met duizend qubits voor. Een foutmarge gebaseerd op de vierkantswortel zou een antwoord kunnen toestaan dat er dertig naast zit, terwijl een lineaire foutmarge een antwoord zou toestaan dat er honderd naast zit. De vorige resultaten lieten de mogelijkheid open dat kwantumcodes gemakkelijk te benaderen zouden kunnen zijn als men bereid was een grotere foutmarge te accepteren. Kapshikars werk neemt deze onzekerheid weg.

De onderzoeker bereikte dit door een nieuw type kwantumcode te bouwen, een zogenaamde "codeword-stabilized" code. Deze constructie fungeert als een vertaler die een moeilijk klassiek probleem omzet in een kwantumprobleem. Het proces omvat twee hoofdingrediënten: een klassieke code en een graaf, wat een netwerk van punten is die verbonden zijn door lijnen. De graaf bepaalt hoe de qubits met elkaar interageren, terwijl de klassieke code de onderliggende structuur biedt. De belangrijkste innovatie lag in de manier waarop de graaf werd gekozen. Eerdere methoden vertrouwden op grafen met zeer specifieke, ijle verbindingen, wat de kracht van het bewijs beperkte. Kapshikar realiseerde zich dat door een willekeurige graaf te gebruiken — een netwerk waarbij verbindingen door toeval worden gekozen — men een veel sterker resultaat kon bereiken.

In een willekeurige graaf zijn de verbindingen dicht en onvoorspelbaar. De studie laat zien dat voor bijna elke willekeurige graaf die gekozen wordt, de resulterende kwantumcode een afstand heeft die nauw verbonden is met de afstand van de oorspronkelijke klassieke code. Als de klassieke code sterk is, is de kwantumcode sterk. Als de klassieke code zwak is, is de kwantumcode zwak. Deze link is zo nauw dat als je de afstand van de kwantumcode gemakkelijk zou kunnen benaderen, je ook de afstand van de klassieke code gemakkelijk zou kunnen benaderen. Omdat we weten dat het klassieke probleem onmogelijk efficiënt op te lossen is, moet het kwantumprobleem dat ook zijn, ervan uitgaande dat standaard complexiteitshypothesen zoals de Exponential Time Hypothesis (SETH) en de Gap-Exponential Time Hypothesis (Gap-ETH) standhouden. Het bewijs stelt dat geen enkele computer de kwantumafstand binnen een lineaire marge kan benaderen, tenzij deze fundamentele aannames over de aard van berekeningen instorten.

De studie gaat verder en bekijkt het probleem door de lens van "fine-grained" complexiteit. Deze benadering vraagt niet alleen of een probleem moeilijk is, maar precies hoe moeilijk het is. Het beschouwt de tijd die nodig is om het probleem op te lossen naarmate de grootte van de invoer groeit. Het onderzoek toont aan dat zelfs als je een algoritme heel lang laat draaien — langer dan elke polynoom maar korter dan een volledige exponentiële zoektocht — het het probleem nog steeds niet kan oplossen, mits de SETH- en Gap-ETH-hypothesen waar zijn. Specifiek bewijst het artikel dat geen enkel algoritme het probleem kan oplossen in een tijd die aanzienlijk minder is dan de tijd die nodig is om elk mogelijk foutpatroon te controleren. Dit geldt voor krachtige theoretische computers, mits zij opereren binnen de standaardregels van logica en waarschijnlijkheid en de eerder genoemde hypothesen geldig blijven.

Een van de meest opvallende aspecten van de bevinding is de robuustheid ervan. Het resultaat blijft van kracht zelfs wanneer de kwantumcode beperkt is tot een specifiek, populair type dat bekend staat als een CSS-code. Deze codes worden veel gebruikt in praktische kwantumcomputerontwerpen omdat ze gemakkelijker te implementeren zijn. De onderzoeker heeft aangetoond dat de moeilijkheid ook voor hen geldt, wat betekent dat de moeilijkheid geen artefact is van een vreemd of exotisch codedesign, maar een fundamentele eigenschap van kwantumfoutcorrectie zelf. Het bewijs houdt ook rekening met "degeneracy", een uniek kenmerk van kwantumcodes waarbij sommige fouten onschadelijk zijn omdat ze triviaal inwerken op de informatie. De studie houdt hier zorgvuldig rekening mee en laat zien dat het probleem, zelfs met deze kwantum-eigenaardigheid, onhandelbaar blijft.

De implicaties van dit werk zijn diepgaand voor de toekomst van kwantumcomputing. Het bevestigt dat de barrière voor het ontwerpen en analyseren van kwantumcodes geen tijdelijk obstakel is dat overwonnen zal worden door betere algoritmen. In plaats daarvan is de moeilijkheid inherent aan de wiskunde van het probleem, uitgaande van standaard complexiteitconjecturen. Dit betekent dat ingenieurs die kwantumcomputers ontwerpen, niet kunnen vertrouwen op een snelle berekening om de sterkte van hun codes te verifiëren. Ze moeten ofwel accepteren dat het vinden van de exacte afstand computationeel onhaalbaar is voor grote systemen, of vertrouwen op specifieke constructies waarbij de afstand per ontwerp bekend is. De studie trekt effectief een lijn in het zand en laat zien dat de zoektocht naar het begrijpen van de grenzen van kwantumfoutcorrectie moet voortgaan met het besef dat de onderliggende wiskunde zo koppig is als het maar kan zijn.

Het artikel raakt ook aan de aard van willekeur in berekeningen. Het bewijs steunt op het idee dat een willekeurige keuze van graaf voldoende is om een moeilijke instantie te creëren. Hoewel het initiële bewijs een willekeurig proces gebruikt, laat de onderzoeker ook zien hoe de willekeur kan worden verwijderd onder een algemeen geaccepteerde hypothese over de kracht van computercircuits. Dit betekent dat de moeilijkheid niet slechts een statistische toevalligheid van willekeur is, maar een deterministische realiteit. Er bestaan specifieke, vaste kwantumcodes die gegarandeerd moeilijk te analyseren zijn, en deze codes kunnen door een computer worden gegenereerd zonder dat er dobbelstenen worden gegooid. Dit versterkt de conclusie en brengt deze van een probabilistische uitspraak naar een stevige garantie over de grenzen van berekening.

Uiteindelijk sluit dit onderzoek een gat dat al enige tijd openstond. Het neemt de bekende moeilijkheid van klassieke codes en breidt deze volledig uit naar de kwantumwereld, waarbij de vierkantswortel-barrière die eerdere studies tegenkwamen, wordt opgeheven. Het resultaat schetst een duidelijk beeld van het computationele landschap: het probleem van het vinden van de afstand van een kwantumcode is even moeilijk als de moeilijkste problemen in de computerwetenschappen, mits de standaard complexiteitshypothesen standhouden. Voor de geïntrigeerde waarnemer betekent dit dat de kwantumwereld, hoewel vol vreemde en wonderlijke fenomenen, geen ontsnapping biedt aan de fundamentele grenzen van de logica. De complexiteit van het beschermen van kwantuminformatie is echt, diepgaand en, voor nu, onverzettelijk.