Physics and computation: An insight from non-Hermitian quantum computing

Dit artikel introduceert een niet-Hermitisch kwantumcomputermodel dat, dankzij een niet-unitaire poort en exponentieel grote fysieke middelen, in staat is om alle problemen binnen de complexiteitsklasse $\text{P}^{\sharp\text{P}}$ in polynomiale tijd op te lossen.

De kern

De Droom van de Supercomputer: Waarom we (nog) niet kunnen vliegen

Stel je voor dat je een computer hebt die niet alleen snel is, maar onmogelijke taken in een flits kan oplossen. Denk aan het vinden van de perfecte route voor een bezorger die duizenden pakketten moet bezorgen, of het kraken van de allerstrengste beveiligingssystemen. Wetenschappers noemen dit "NP-problemen". Normale computers (en zelfs de huidige quantumcomputers) hebben hier eeuwen voor nodig.

In dit artikel stellen de auteurs, Qi Zhang en Biao Wu, een nieuw soort computer voor: de Niet-Hermitische Quantumcomputer (NQC). Ze laten zien dat deze machine theoretisch gezien alles kan oplossen wat er bestaat, en dat in een handomdraai. Maar er is een grote "maar". Het is alsof je een vliegtuig hebt dat kan vliegen, maar alleen als je het bouwt van goud en het brandstofverbruik de hele wereld verbruikt.

Laten we kijken hoe dit werkt, stap voor stap.

1. De Regelbreker: De Magische Deur

Normale quantumcomputers werken volgens strikte regels. Alles wat erin gaat, moet er ook weer uitkomen zonder dat er informatie verloren gaat of "vervuilt". Dit noemen ze unitair. Het is alsof je een bal in een glazen doos gooit: hij kan stuiteren, draaien en bewegen, maar hij blijft altijd een bal en verdwijnt nooit.

Deze nieuwe computer breekt die regel. Ze voegen een speciale poort toe, de G-poort.

• De Analogie: Stel je voor dat je een bal hebt. Bij een normale computer kun je de bal alleen roteren. Bij deze nieuwe computer kun je de bal vergroten of verkleinen.
• Als je een bal (een bit) hebt die "1" is, kan de G-poort deze bal zo enorm groot maken dat hij de hele kamer vult, terwijl een bal die "0" is, zo klein wordt dat hij onzichtbaar is.
• Hierdoor kun je het juiste antwoord (de grote bal) zo hard "opblazen" dat je het direct ziet, terwijl alle foutieve antwoorden (de kleine ballen) verwaarloosbaar klein worden.

2. De Kracht: Het Oplossen van Onmogelijke Puzzels

Met deze magische G-poort kunnen ze een probleem oplossen dat bekend staat als het "Maximaal Onafhankelijke Stelsel" (MIS).

• De Analogie: Denk aan een grote groep mensen op een feestje. Sommige mensen kennen elkaar niet en kunnen samen in een groepje zitten. Je wilt het grootste mogelijke groepje vinden waar niemand elkaar kent.
• Een gewone computer moet elke mogelijke combinatie één voor één proberen. Dat duurt eeuwen.
• De NQC gebruikt de G-poort om alle "goede" groepjes tegelijkertijd enorm groot te maken en alle "slechte" groepjes te laten verdwijnen. Na een paar seconden is het antwoord het enige dat nog overblijft.
• De auteurs bewijzen wiskundig dat deze computer elke puzzel kan oplossen die in de categorie P♯P valt. Dit is een categorie die nog veel moeilijker is dan de bekende "NP-complete" problemen. Het is alsof je niet alleen de sleutel vindt, maar ook de hele fabriek waar de sleutels worden gemaakt, in één seconde.

3. De Valstrik: De Prijs van de Kracht

Nu komt het belangrijke deel. Waarom hebben we zo'n computer nog niet? Omdat de natuurkunde een prijskaartje hangt aan deze kracht.

De auteurs onderzoeken twee manieren om deze magische G-poort te bouwen in de echte wereld:

Optie A: Het Deeltjes-Explosie (Cold Atoms)
Om de bal (het bit) groter te maken, moet je meer deeltjes toevoegen.

• De Analogie: Stel je voor dat je een klein poppetje wilt laten groeien tot een reus. Je moet duizenden, miljoenen of zelfs oneindig veel nieuwe poppetjes toevoegen.
• Om een probleem op te lossen met 100 variabelen, heb je niet 100 deeltjes nodig, maar 2 tot de macht 100 deeltjes. Dat is meer deeltjes dan er sterren in het heelal zijn.
• Om deze computer te bouwen, heb je dus een hoeveelheid materie nodig die fysiek onmogelijk is om te verzamelen. Het is alsof je een auto wilt bouwen die vliegt, maar die brandstof nodig heeft die zwaarder is dan de aarde.

Optie B: Het Gokspel (Postselectie)
Een andere manier is om te gokken. Je doet een experiment en als het niet lukt, gooi je het weg en probeer je het opnieuw.

• De Analogie: Stel je voor dat je een loterij speelt waarbij de kans om te winnen 1 op een miljard is. Je kunt het antwoord vinden door te wachten tot je wint. Maar omdat de kans zo klein is, moet je miljarden identieke computers tegelijk laten draaien om er zeker van te zijn dat er één wint.
• Ook hier heb je dus een exponentieel grote hoeveelheid hardware nodig.

4. De Conclusie: De Muur van de Realiteit

De auteurs concluderen iets fascinerends:
Deze computer is theoretisch een supermachine die alles kan oplossen. Maar praktisch is het onmogelijk om hem te bouwen.

• De kracht van de computer komt niet uit een nieuw wiskundig genie, maar uit het feit dat je onbeperkt veel fysieke middelen (deeltjes, energie, ruimte) kunt gebruiken.
• Het is als het proberen om een berg te verplaatsen door hem met je handen te duwen. Het is fysiek mogelijk (je kunt de berg verplaatsen), maar het kost zoveel kracht dat je het nooit zult doen.

Samenvattend in één zin:
Deze paper laat zien dat we een computer kunnen ontwerpen die alle problemen oplost, maar dat de natuurwetenschappen ons vertellen dat we hiervoor een hoeveelheid materie nodig hebben die groter is dan het universum zelf. Het is een prachtige droom, maar een droom die we waarschijnlijk nooit in de praktijk kunnen verwezenlijken.

Het leert ons dat er een diepe band is tussen wat we kunnen rekenen en wat de natuur ons toestaat om te bouwen. Om de grenzen van de quantumcomputing te doorbreken, moeten we misschien wachten op een compleet nieuwe ontdekking in de natuurkunde, of accepteren dat sommige problemen simpelweg te zwaar zijn voor onze fysieke realiteit.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Physics and computation: An insight from non-Hermitian quantum computing" in het Nederlands.

Titel: Fysica en berekening: Een inzicht uit niet-Hermitiaans kwantumcomputen

Auteurs: Qi Zhang en Biao Wu

---

1. Het Probleem

De huidige stand van de kwantumcomputing (gebaseerd op standaard kwantummechanica en unitaire evolutie) heeft beperkte rekenkracht. Hoewel algoritmen zoals die van Shor en Grover superieure prestaties leveren voor specifieke problemen, kunnen conventionele kwantumcomputers NP-complete problemen niet efficiënt oplossen (binnen polynomiale tijd).

Om deze beperking te overwinnen, zijn er eerder theoretische modellen voorgesteld die de wetten van de kwantummechanica uitbreiden of hypothetische middelen gebruiken, zoals:

• Gesloten tijdsachtige krommen (Closed Timelike Curves).
• Niet-lineaire poorten.
• Post-selectie.
• Lorentz-kwantumcomputers.

Deze modellen tonen aan dat het mogelijk is om problemen in complexiteitsklassen zoals P♯P (Polynomial-time counting problems) op te lossen, maar ze vereisen vaak fysiek onrealistische aannames of hypothetische toestanden. Het centrale vraagstuk is of er een fysiek realiseerbaar model bestaat dat deze rekenkracht biedt zonder de fundamentele wetten van de natuurkunde te schenden, en wat de fysieke kosten daarvan zijn.

2. Methodologie

De auteurs stellen een nieuw theoretisch model voor: de Niet-Hermitiaanse Kwantumcomputer (NQC).

• Fundamentele Aannames: Het model verwijdert de restrictie van unitariteit voor kwantumpoorten. In plaats van alleen unitaire poorten (Hadamard $H$, fase $T$, CNOT), introduceert het een niet-unitaire lineaire poort $G$:
  $$G = \begin{pmatrix} g^{-1} & 0 \\ 0 & g \end{pmatrix}$$
  waarbij $g > 0$ en $g \neq 1$ een reëel getal is.
• Complexiteitsklasse: De auteurs definiëren de klasse BNQP (Bounded-error Non-Hermitian Quantum Polynomial time) als de verzameling problemen die door een NQC in polynomiale tijd opgelost kunnen worden.
• Algoritme-ontwerp: Om de kracht van het model te demonstreren, ontwikkelen ze een algoritme voor het Maximum Independent Set (MIS) probleem (een NP-hard probleem).
  • Ze gebruiken $n$ werk-qubits voor de vertices van een graaf en een extra qubit die onderhevig is aan niet-unitaire transformaties.
  • Door de niet-unitaire poort $G$ (en gecontroleerde versies $C-G^r$) toe te passen, worden de amplitudes van oplossingen die een "Independent Set" vormen exponentieel versterkt ten opzichte van niet-oplossingen.
• Fysieke Implementatie: Om te analyseren of dit fysiek mogelijk is, onderzoeken ze twee specifieke schetsen voor het realiseren van poort $G$:
  1. Verandering in deeltjesaantal: Een systeem met twee putten en veel bosonen (bijv. koude atomen) waarbij deeltjeswinst en -verlies (gain and loss) worden geïntroduceerd via Feshbach-resonantie en optische excitatie.
  2. Post-selectie: Een methode waarbij een hulp-qubit wordt gemeten en alleen resultaten worden behouden waarbij de hulp-qubit in een specifieke toestand ($|0\rangle$) is, wat effectief een niet-unitaire transformatie op de doel-qubit simuleert.

3. Belangrijkste Bijdragen

1. Theoretische Equivalentie: De auteurs bewijzen dat de complexiteitsklasse BNQP equivalent is aan P♯P. Dit betekent dat een NQC in theorie in staat is om alle problemen binnen deze klasse (waaronder NP-complete en #P-problemen) in polynomiale tijd op te lossen. Dit wordt bereikt door "exponentiële amplitude-versterking" via de niet-unitaire poort $G$.
2. Fysieke Realisatie: In tegenstelling tot eerdere modellen die puur hypothetisch waren, tonen de auteurs aan dat de poort $G$ theoretisch kan worden geïmplementeerd met bestaande niet-Hermitiaanse fysieke systemen (zoals PT-symmetrische systemen en systemen met uitzonderlijke topologie).
3. De "Resource-Barrier": De meest cruciale bijdrage is de analyse van de fysieke kosten. De auteurs concluderen dat de enorme rekenkracht van de NQC direct voortkomt uit de exponentieel grote hoeveelheid fysieke middelen die nodig zijn om de niet-unitaire poort te implementeren.

4. Resultaten

• Algoritmische Prestatie: Het voorgestelde algoritme voor het MIS-probleem heeft een tijdscomplexiteit van $O(n^2)$, wat een enorme versnelling is ten opzichte van klassieke methoden.
• Fysieke Kosten (Systeem 1 - Bosonen):
  • Om de poort $G$ te realiseren via verandering in deeltjesaantal, moet het aantal bosonen exponentieel toenemen met de invoerlengte $n$ (d.w.z. $N \sim 2^n$).
  • Het prepareren van verstrengelde toestanden met zo'n groot aantal deeltjes is extreem moeilijk.
  • Decoherentie: De decoherentietijd ($T_2$) voor een systeem met $N$ deeltjes schaalt als $T_2/N$. Omdat $N$ exponentieel groeit, wordt de decoherentietijd exponentieel korter, waardoor het systeem onbruikbaar wordt voordat de berekening voltooid is, tenzij de omgeving perfect geïsoleerd is.
• Fysieke Kosten (Systeem 2 - Post-selectie):
  • De kans op succesvolle post-selectie neemt exponentieel af met de invoerlengte $n$.
  • Om met zekerheid een resultaat te krijgen, moet men een exponentieel groot aantal identieke kwantumcomputers parallel laten draaien om te garanderen dat ten minste één succesvol post-selecteert.
• Conclusie over Implementatie: Hoewel de poort $G$ fysiek realiseerbaar is in theorie, vereist de praktische uitvoering middelen (deeltjesaantal of parallelle systemen) die exponentieel groeien met het probleem. Dit maakt het fysiek onuitvoerbaar in de praktijk, vergelijkbaar met het simuleren van een kwantumsysteem op een klassieke computer.

5. Betekenis en Conclusie

Het artikel legt een fundamentele relatie bloot tussen rekenkracht en fysieke middelen:

1. Geen "Gratis Lunch": Het is mogelijk om de complexiteitsklasse P♯P te bereiken door de unitariteit van de kwantummechanica los te laten, maar de prijs is de noodzaak van exponentieel grote fysieke resources.
2. Fysieke Barrière: De "superkracht" van niet-Hermitiaans kwantumcomputen is niet gratis; het wordt gecompenseerd door de onmogelijkheid om de benodigde niet-unitaire transformaties efficiënt te realiseren zonder dat decoherentie of resource-tekorten het proces verstoren.
3. Toekomstperspectief: De auteurs suggereren dat om echt efficiënter te zijn dan conventioneel kwantumcomputen, we óf nieuwe fysica moeten ontdekken die deze resource-eisen verlaagt, óf we moeten accepteren dat de complexiteitsklassen van de natuurkunde (zoals P, NP, P♯P) direct gekoppeld zijn aan de fysieke middelen die beschikbaar zijn in ons universum.

Kortom, het papier toont aan dat terwijl niet-Hermitiaans kwantumcomputen theoretisch een enorme rekenkracht belooft, de fysieke realiteit (de noodzaak van exponentieel veel deeltjes of post-selectie) deze kracht in de praktijk onbereikbaar maakt voor grote problemen.