Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes

Quantumcomputers beloven problemen op te lossen die de machines van vandaag millennia zouden kosten om te kraken, maar ze zijn ongelooflijk fragiel. De kleinste verstoring uit de omgeving kan de delicate informatie die ze bevatten verstoren. Om een machine te bouwen die werkt, moeten wetenschappers deze fragiele data omhullen met een beschermende laag die kwantumfoutcorrectie wordt genoemd. Dit systeem controleert constant op fouten, vergelijkbaar met een spellingscontrole voor een document, maar in plaats van typefouten te corrigeren, identificeert en herstelt het fysieke fouten in de kwantumbits, of qubits. De meest veelbelovende ontwerpen voor deze machines maken gebruik van een specifiek type bescherming dat bekend staat als topologische codes. In deze systemen wordt de informatie niet in één enkel deeltje opgeslagen, maar verspreid over een uitgestrekt, tweedimensionaal rooster van qubits, wat het robuust maakt tegen lokale ruis.

Voor deze bescherming om in de echte wereld te werken, moet de computer in staat zijn de resultaten van zijn controles te lezen en te achterhalen wat er precies mis is gegaan, een proces dat decoderen wordt genoemd. Het doel is om de eenvoudigste, meest waarschijnlijke verklaring te vinden voor de geobserveerde fouten. Als de computer deze fouten niet snel en nauwkeurig kan decoderen, faalt de bescherming en stort de berekening in. Lange tijd hoopten onderzoekers dat het vinden van deze eenvoudigste verklaring voor de meest voorkomende soorten fouten een taak zou zijn die een computer efficiënt aan zou kunnen. Echter, een nieuwe studie door Louay Bazzi en Georges Khater suggereert dat deze hoop mogelijk onterecht is voor de krachtigste foutcorrigerende schema's. Zij hebben bewezen dat voor bepaalde geavanceerde kwantumcodes het vinden van de perfecte oplossing zo computationeel moeilijk is dat zelfs de beste mogheden voor afkortingen uiteindelijk zullen falen om de fout klein genoeg te houden naarmate het systeem groter wordt.

De onderzoekers concentreerden zich op twee leidende families van kwantumcodes: surface codes en color codes. Surface codes zijn de huidige favorieten voor het bouwen van kwantumcomputers omdat ze compatibel zijn met bestaande hardwareontwerpen, terwijl color codes unieke voordelen bieden voor het uitvoeren van berekeningen. In beide systemen meet de computer een reeks signalen die syndromen worden genoemd, die fungeren als een kaart van waar fouten zijn opgetreden. De decoderingsopdracht is om een pad door het rooster te tekenen dat de foutpunten verbindt op een manier die de minste "inspanning", of gewicht, vereist. In de eenvoudigste scenario's is dit vergelijkbaar met het verbinden van punten op een stuk papier met de kortste mogende string. Voor sommige oudere, eenvoudigere codes is dit een rechttoe waarvan afan wiskundig probleem dat snel kan worden opgelost.

Bazzi en Khater onderzochten wat er gebeurt wanneer de fouten complexer zijn, specifal wanneer verschillende soorten fouten tegelijkertijd kunnen optreden en elkaar kunnen beïnvloeden, een situatie die een depolariserend kanaal wordt genoemd. Ze stelden een fundamentele vraag: Is er een snel, efficiënt algoritme dat altijd een oplossing kan vinden die zeer dicht bij de absoluut beste oplossing ligt? Om dit te beantwoordenen, hebben ze geen simulaties op een computer uitgevoerd; in plaats daarvan construeerden ze een rigoureus wiskundig bewijs. Ze toonden aan dat voor surface codes en color codes het probleem van het vinden van de beste correctie niet alleen moeilijk is, maar fundamenteel onhandelbaar op een specifieke manier. Ze bewezen dat ongeacht hoe slim een computerprogramma ook is, naarmate de kwantumcomputer in omvang groeit, de absolute fout in de beste gok groter wordt, wat betekent dat de kloof tussen de oplossing van het algoritme en het perfecte antwoord groter wordt op een manier die niet genegeerd kan worden.

Het team demonstreerde dat voor een kwantumcomputer met een bepaald aantal qubits, elk snel algoritme onvermijdelijk een oplossing zal produceren die aanzienlijk afwijkt van het perfecte antwoord. Specifiek vonden zij dat voor de toric code en de 4.8.8 color code, de fout in de oplossing groeit met een snelheid die gerelateerd is aan de veertiende wortel van het totaal aantal qubits. Voor de planaire surface code groeit de fout met een snelheid die gerelateerd is aan de achttiende wortel van het aantal qubits. Hoewel deze getallen klein lijken, vertegenwoordigen ze een groeiende kloof die niet gedicht kan worden door de computer simpelweg slimmer of sneller te maken. De onderzoekers stelden vast dat, tenzij er een grote doorbraak in de computerwetenschap plaatsvindt — specifiek, als een probleem dat bekend staat als extreem moeilijk, blijkt gemakkelijk te zijn — geen enkel polynoomtijd-algoritme een oplossing binnen deze marge kan garanderen.

Om tot deze conclusie te komen, bouwden de auteurs een complexe logische structuur met behulp van kleine, modulaire structuren die ze gadgets noemden. Stel je deze voor als kleine, zelfstandige machines ontworpen om specifieke regels af te dwingen, vergelijkbaar met hoe een slot ervoor zorgt dat een deur alleen opent met de juiste sleutel. Ze plaatsten deze gadgets in een rooster om het gedrag van een moeilijk op te lossen logisch puzzelprobleem na te bootsen. Door deze gadgets zorgvuldig uit elkaar te plaatsen, zorgden ze ervoor dat de oplossing van de puzzel geen afkortingen over het rooster kon nemen. Ze bewezen dat de enige manier om de puzzel efficiënt op te lossen, het oplossen van het onderliggende logische probleem is, wat zij weten moeilijk te zijn voor grote inputs. Deze methode stelde hen in staat om de moeilijkheid van een bekend hard probleem direct te vertalen naar de moeilijkheid van het decoderen van kwantumfouten.

De studie behandelde ook een recente golf van optimisme in het vakgebied. Vlak voor dit werk hadden andere onderzoekers ontdekt dat het voor deze zelfde codes mogelijk is om heel dicht bij het perfecte antwoord te komen als men bereid is een kleine, vaste foutmarge te accepteren. Dit leidde tot de overtuiging dat efficiënt decoderen binnen handbereik was. Het werk van Bazzi en Kharter verheldert de grenzen van dit optimisme. Ze toonden aan dat hoewel je dicht bij het beste antwoord kunt komen, je niet willekeurig dichtbij kunt komen. Er is een harde muur waar de fout te groot wordt om te negeren naarmate het systeem opschaalt. Dit onderscheid is cruciaal omdat in kwantumcomputing zelfs een kleine, aanhoudende fout zich in de loop van de tijd kan opstapelen en de berekening kan vernietigen.

De implicaties van deze bevinding zijn aanzienlijk voor de toekomst van kwantumhardware. Het suggereert dat ingenieurs niet kunnen vertrouwen op een enkel, universeel algoritme om fouten te herstellen voor alle formaten van kwantumcomputers. Naarmate zij grotere machines bouwen, zullen zij mogelijk moeten accepteren dat het decoderingsproces minder precies wordt, of moeten zij geheel nieuwe manieren vinden om hun codes te structureren die deze specifieke wiskundige vallen vermijden. De onderzoekers hebben ook een nieuwe toolkit van "gadgets" ontwikkeld en een methode voor het beheersen van hun interacties, wat andere wetenschappers kan helpen de grenzen van het decoderen in verschillende soorten kwantumsystemen te verkennen. Hun werk zegt niet dat kwantumcomputers onmogelijk zijn, maar trekt een duidelijke lijn in het zand over hoe efficiënt we hun fouten kunnen beheren.

Uiteindelijk biedt het artikel een nuchtere maar noodzakelijke reality check. Het bevestigt dat de weg naar een fouttolerante kwantumcomputer niet alleen een kwestie is van het bouwen van betere hardware of snellere software. Het onthult een fundamentele complexiteit in de wiskunde van foutcorrectie die nieuwe strategieën zal vereisen om deze te overwinnen. De onderzoekers hebben aangetoond dat voor de meest veelbelovende codes die momenteel op tafel liggen, de droom van een perfecte, snelle decoder wiskundig gezien buiten bereik is. De uitdaging verschuift nu naar het vinden van manieren om binnen deze limieten te werken, bijvoorbeeld door codes te ontwerpen die inherent gemakkelijker te decoderen zijn of door te accepteren dat een bepaald niveau van benadering onvermijdelijk is in de race om een werkende kwantummachine te bouwen.