⚛️ quantum physics

Linguistic Predictability and Search Complexity: How Linguistic Redundancy Constraints the Landscape of Classical and Quantum Search

Deze studie onderzoekt hoe linguïstische redundantie in Renaissance-Italiaanse teksten de zoekruimte voor cryptanalyse beperkt door de relatie tussen de waarschijnlijkheid van een geldige decryptie en de benodigde computationele inspanning te kwantificeren binnen een hybride klassiek-kwantumkader.

Oorspronkelijke auteurs: Alessio Di Santo, Gabriella Lanziani

Gepubliceerd 2026-03-27

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Alessio Di Santo, Gabriella Lanziani

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een oude, geheime brief uit de Renaissance (de tijd van Machiavelli en Ariosto) hebt gevonden. De brief is geschreven in een code: elke letter is vervangen door een andere. Je doel is om de code te kraken.

Deze studie, geschreven door Alessio Di Santo en Gabriella Lanziani, onderzoekt hoe moeilijk het is om zo'n code te kraken, en hoe de taal zelf ons helpt of hindert. Ze kijken naar dit probleem door de bril van zowel klassieke computers als de futurische wereld van kwantumcomputers.

Hier is een simpele uitleg van hun ontdekkingen, met behulp van alledaagse vergelijkingen:

1. Het Taal-Raadsel: Waarom is taal niet willekeurig?

Stel je voor dat je een woordraadsel moet oplossen. Als je een willekeurige rij letters hebt (bijv. "XQZJL"), is de kans dat dit een echt woord is in het Italiaans bijna nul. Taal heeft namelijk regels. Letters komen niet zomaar voor; ze volgen patronen.

De Analogie: Denk aan een bak met Lego-stenen. Als je willekeurig stenen op elkaar plakt, krijg je een brij. Maar als je een instructieboekje (de taalregels) hebt, kun je alleen bepaalde vormen bouwen.
De Studie: De auteurs keken naar vier beroemde Italiaanse teksten uit de 15e en 16e eeuw. Ze bouwden een "model" dat weet hoe vaak welke letters achter elkaar voorkomen (bijvoorbeeld dat 'q' bijna altijd gevolgd wordt door 'u').

2. De Zoektocht: Een berg beklimmen

Het kraken van de code is als het zoeken naar de top van een berg in een mistig landschap.

Het landschap: Elke mogelijke manier om de letters te vervangen is een punt op dit landschap.
De top: De juiste oplossing (waar de tekst leesbaar Italiaans wordt) is de hoogste piek.
De mist: Omdat er zo veel mogelijke combinaties zijn (meer dan het aantal zandkorrels op aarde), is het moeilijk om de top te vinden.

De onderzoekers gebruikten verschillende methoden om deze berg te beklimmen:

Klassieke methoden: Een "hill climber" (die stap voor stap omhoog probeert te gaan) en "simulated annealing" (een methode die soms een stapje terug doet om een hogere piek te vinden).
Kwantum-inspiratie: Een methode die lijkt op de beroemde Grover-algoritme. Dit is een kwantumtechniek die zoekt als je een naald in een hooiberg zoekt, maar dan veel sneller door het hele hooiberg tegelijk te "voelen".

3. De Grote Ontdekking: Hoe langer de tekst, hoe kleiner de zoekruimte

Dit is het belangrijkste punt van het papier.

Korte tekst (200 letters): Stel je voor dat je een kort zinnetje hebt. Er zijn duizenden manieren om die letters te vervangen die er misschien als Italiaans uitzien. Het zoeklandschap is breed en vlak. Het is moeilijk om de echte oplossing te vinden omdat er veel "nep-topjes" zijn.
Lange tekst (1000 letters): Nu heb je een heel hoofdstuk. Als je de letters verkeerd vervangt, wordt de tekst direct onleesbaar en onnatuurlijk. De "nep-topjes" verdwijnen. Het landschap wordt heel smal en er is maar één duidelijke, scherpe piek over.

De conclusie: Hoe langer de geheime tekst, hoe meer de taalregels de zoekruimte verkleinen. De taal "drukt" de mogelijke oplossingen samen tot een heel klein gebied.

4. Kwantum vs. Klassiek: De snelheidswinst

De onderzoekers maten hoeveel moeite het kost om de code te kraken.

Klassieke computers: Moeten bijna elke mogelijke combinatie proberen. Als de tekst lang is, duurt dit eeuwen.
Kwantum-computers (in theorie): Kunnen veel sneller zoeken. De studie toont aan dat de snelheid van een kwantumcomputer precies voorspelbaar is door de "taaldichtheid".
- De formule: Als de kans dat een willekeurige oplossing goed is heel klein is (wat gebeurt bij lange teksten), dan moet een kwantumcomputer minder vaak "kijken" dan een klassieke computer. Het voordeel wordt groter naarmate de tekst langer wordt.

5. Waarom maakt dit uit?

De auteurs laten zien dat taalredundantie (de herhaling en regels in taal) niet alleen iets is voor taalkundigen, maar een fundamentele factor is in de rekenkracht die nodig is om iets te vinden.

Vergelijking: Het is alsof je een sleutel zoekt in een kamer.
- Bij een korte tekst is de kamer een groot veld met gras, en de sleutel kan overal liggen.
- Bij een lange tekst is het veld zo vol met struiken (taalregels) dat de sleutel eigenlijk alleen nog maar op één specifieke plek kan liggen. De taal heeft de zoekruimte voor je ingekrompen.

Samenvattend

Deze studie bewijst dat de structuur van het Italiaanse taalgebruik uit de Renaissance een krachtige "filter" is. Of je nu een klassieke computer of een geavanceerde kwantumcomputer gebruikt: hoe langer de geheime tekst, hoe makkelijker het wordt om de juiste oplossing te vinden, omdat de taal zelf alle verkeerde antwoorden uitsluit. Het is een mooie brug tussen oude literatuur, wiskunde en de toekomst van computers.

Titel en Context

Het onderzoek, uitgevoerd door Alessio Di Santo en Gabriella Lanziani, onderzoekt de kwantitatieve relatie tussen linguïstische regulariteiten (redundantie) en de computationele complexiteit van zoekproblemen. De studie combineert klassieke en kwantum-geïnspireerde zoekmethoden om te analyseren hoe de voorspelbaarheid van taal de zoekruimte beïnvloedt bij het kraken van monoalfabetische substitutie-cijfers.

1. Het Probleem

Het centrale probleem is het bepalen van de complexiteit van het kraken van een monoalfabetische substitutie-cijfer (waarbij elke letter van het alfabet wordt vervangen door een andere).

De uitdaging: De zoekruimte bestaat uit alle mogelijke permutaties van het alfabet. Voor een standaard alfabet is dit een enorm aantal combinaties.
De rol van taal: De moeilijkheid van deze taak hangt niet alleen af van de grootte van de zoekruimte, maar vooral van hoe sterk de taalstructuur (redundantie) de ruimte van "plausibele" oplossingen beperkt.
Doel: Kwantificeren hoe de waarschijnlijkheid dat een willekeurige sleutel een linguïstisch plausibele decryptie oplevert ( $p_{good}$ ), correleert met de verwachte computationele inspanning voor zowel klassieke als kwantum-algoritmen.

2. Methodologie

De auteurs hanteren een hybride framework dat historische tekstcorpora combineert met probabilistische taalmodellen en zoekalgoritmen.

Corpora: Er zijn vier representatieve werken uit de Italiaanse Renaissance gebruikt, variërend in genre (politieke filosofie, hofgesprek, aforismen, epische poëzie):
- Il Principe (Machiavelli)
- Il Cortegiano (Castiglione)
- I Ricordi (Guicciardini)
- Orlando Furioso (Ariosto)
Voorbewerking: Teksten werden genormaliseerd naar twee orthografische standaarden: een historisch 25-letter alfabet (zonder k, w, y; met i/j en u/v vereenvoudigd) en het moderne Italiaanse alfabet.
Taalmodellen: Er werden karakter-gebaseerde n-gram modellen (unigram, bigram, trigram) getraind. Trigram-modellen ( $n=3$ ) werden gebruikt als de beste balans tussen expressiviteit en statistische robuustheid.
Cijfergeneratie: Platte tekstsegmenten van verschillende lengtes ( $L \in \{200, 400, 600, 800, 1000\}$ ) werden willekeurig geselecteerd en versleuteld met willekeurige monoalfabetische substituties.
Zoekstrategieën:
1. Klassieke heuristieken: Hill climbing (greedy) en Simulated Annealing.
2. QUBO Annealing: Een kwantum-geïnspireerde formulering (Quadratic Unconstrained Binary Optimization) om de permutatie te vinden die de score maximaliseert.
3. Grover-stijl schatting: Een theoretische berekening van het aantal benodigde "oracle calls" voor een ideale kwantumzoekopdracht, gebaseerd op de formule $N_{oracle} \approx \frac{\pi}{4\sqrt{p_{good}}}$ .
Scorefunctie: De log-likelihood van de ontcijferde tekst, berekend via het getrainde n-gram model, diende als objectieve functie.

3. Belangrijkste Bijdragen

Koppeling van Linguïstiek en Complexiteit: Het artikel biedt een empirisch raamwerk dat de linguïstische redundantie (gemeten via $p_{good}$ ) direct linkt aan de zoekruimte-contractie.
Validatie van Grover-schaling: Het bewijst empirisch dat de zoekinspanning voor kwantum-algoritmen inderdaad schaalt met $1/\sqrt{p_{good}}$ op basis van corpus-afgeleide verdelingen.
Vergelijkend Framework: Het stelt een unificatie voor tussen klassieke heuristieken, QUBO-optimatie en ideale kwantumzoektheorie onder dezelfde corpus-gedreven beperkingen.
Historische Analyse: Het toont aan dat, ondanks stilistische verschillen tussen auteurs, de statistische structuur van het Italiaans uit de Renaissance op karakter-trigram-niveau een homogeen beeld geeft voor cryptanalyse.

4. Resultaten

Concentratie van Scores: Naarmate de lengte van het cijfer ( $L$ ) toeneemt, worden de verdelingen van de scores voor willekeurige sleutels scherper en nauwer. Dit betekent dat de kans op een hoge score voor een willekeurige sleutel exponentieel afneemt.
Afname van $p_{good}$ : De fractie van "goede" sleutels ( $p_{good}$ ) daalt monotoon met toenemende tekstlengte. Voor $L \geq 600$ en een strenge drempel ( $\tau \geq 0.95$ ) daalt $p_{good}$ onder $10^{-4}$ .
Zoekinspanning:
- Klassiek: Het verwachte aantal trials schaalt met $1/p_{good}$ , wat leidt tot een zeer snelle toename van de moeilijkheidsgraad bij langere teksten.
- Kwantum (Grover): Het aantal benodigde iteraties schaalt met $1/\sqrt{p_{good}}$ . Hoewel dit een kwadratische versnelling biedt ten opzichte van klassieke methoden, neemt de absolute inspanning toch sterk toe bij langere teksten (bijv. $10^5$ iteraties voor $L=1000$ bij strenge drempels).
Convergentie: Klassieke heuristieken (Hill climbing, Simulated Annealing) en QUBO-annealing convergeren naar vergelijkbare hoogscorende gebieden, wat aantoont dat de linguïstische structuur de zoeklandschap sterk beperkt.
Niet-monotoniteit: Er werd een lichte lokale fluctuatie waargenomen bij $L=600$ , veroorzaakt door steekproefvariatie in de staart van de verdeling, maar dit weerlegt niet de algemene trend van sterke contractie.

5. Betekenis en Conclusie

De studie concludeert dat linguïstische redundantie de primaire factor is die de complexiteit van cryptanalytische zoekproblemen bepaalt, meer dan de grootte van het alfabet zelf.

Theoretische Implicatie: Het onderzoek valideert dat corpus-afgeleide beperkingen coherent vertalen naar kwantumzoekmodellen. Het biedt een meetbare basis voor het vergelijken van klassieke en kwantum-algoritmen.
Praktische Toepassing: Hoewel trigram-modellen geen lange-afstand syntaxis vangen, zijn ze voldoende voor het kraken van substitutie-cijfers omdat deze voornamelijk afhankelijk zijn van korte orthografische en fonotactische patronen.
Toekomstperspectief: Het raamwerk biedt een basis voor verdere vergelijkingen tussen verschillende talen, historische periodes en complexere taalmodellen, en helpt bij het begrijpen van hoe linguïstische structuren combinatorische zoekmoeilijkheid beïnvloeden.

Kortom, het artikel toont aan dat de "voorspelbaarheid" van taal de zoekruimte voor cryptanalyse drastisch verkleint, en dat deze verkleining systematisch kan worden gemodelleerd en voorspeld voor zowel klassieke als kwantum-computers.