⚛️ quantum physics

A Quantum Search Approach to Magic Square Constraint Problems with Classical Benchmarking

Dit artikel presenteert een quantumzoekbenadering voor het oplossen van magische vierkanten via Grover's algoritme, waarbij klassieke voorverwerking wordt gebruikt voor gestructureerde initialisatie en de resultaten een theoretisch kwadratisch voordeel bevestigen ten opzichte van klassieke zoekmethoden.

Oorspronkelijke auteurs: Rituparna R, Harsha Varthini, Aswani Kumar Cherukuri

Gepubliceerd 2026-04-07

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Rituparna R, Harsha Varthini, Aswani Kumar Cherukuri

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

Het Grote Magische Raadsel: Een Kwantumjacht

Stel je voor dat je een magisch vierkant moet maken. Dit is een rooster (bijvoorbeeld 3 bij 3 vakjes) waarin je de getallen 1 tot en met 9 moet plaatsen. De regel is simpel maar lastig: elke rij, elke kolom en beide diagonalen moeten precies hetzelfde totaal geven (bijvoorbeeld 15).

Het probleem is dat er ontzettend veel manieren zijn om die getallen neer te zetten, maar slechts een paar daarvan zijn echt "magisch". Het vinden van die juiste combinatie is als het zoeken naar een enkele, specifieke naald in een gigantische hooiberg.

Dit artikel beschrijft hoe wetenschappers een nieuwe manier hebben bedacht om dit probleem op te lossen, niet met een gewone computer, maar met een kwantumcomputer die gebruikmaakt van een slimme zoektechniek genaamd Grover's algoritme.

1. De Gewone Manier: De "Blinde" Zoeker

Stel je voor dat je een gewone computer (zoals je laptop) gebruikt om dit op te lossen.

Hoe het werkt: De computer begint met het proberen van elke mogelijke combinatie. Hij zet de getallen 1, 2, 3... neer, controleert of het klopt, en als het niet klopt, gooit hij het weg en probeert hij de volgende.
Het nadeel: Dit is als het proberen van elke sleutel in een bos van 362.880 sleutels om één slot te openen. Het kan heel lang duren, vooral als het rooster groter wordt. De computer moet één voor één kijken.

2. De Kwantum Manier: De "Spook" Zoeker

Nu komt de kwantumcomputer in beeld. In plaats van één voor één te kijken, doet de kwantumcomputer iets magisch: superpositie.

De Analogie: Stel je voor dat je niet één sleutel probeert, maar dat je een spook bent dat op dat moment alle 362.880 sleutels tegelijk in zijn hand houdt.
De Zoektocht: De kwantumcomputer zet al die mogelijke oplossingen tegelijk in de lucht (een "superpositie"). Vervolgens gebruikt hij een speciale "magische lantaarn" (de Oracle) die alleen oplicht voor de juiste oplossing.
Het Versterken: Omdat de computer alle opties tegelijk heeft, kan hij de "goede" oplossing versterken en de "slechte" oplossingen laten verdwijnen. Dit is als het versterken van een zacht geluid tot een schreeuw, terwijl je alle andere geluiden dempt.

3. De Slimme Voorbereiding (De Klassieke Hulp)

De onderzoekers zijn niet dom genoeg om de kwantumcomputer alles te laten doen. Ze gebruiken een slimme truc:

De Siamese Bouwtechniek: Voordat de kwantumcomputer begint, gebruiken ze een klassieke methode (een oude wiskundige techniek) om alvast een paar vakjes vast te zetten.
De Analogie: Het is alsof je een schatkaart hebt die je alvast de helft van het eiland afsluit. Je hoeft niet het hele eiland te doorzoeken, maar alleen nog het kleine stukje waar de schat waarschijnlijk ligt. Dit maakt de zoektocht voor de kwantumcomputer veel sneller en efficiënter.

4. Wat hebben ze ontdekt?

De onderzoekers hebben dit systeem getest op een klein 3x3 magisch vierkant.

Resultaat: De kwantumcomputer vond de oplossing in theorie veel sneller dan de gewone computer. Waar de gewone computer duizenden pogingen nodig heeft, heeft de kwantumcomputer er maar een paar honderd nodig (wiskundig gezien is het de wortel van het totaal aantal opties).
De Realiteit: Er is een klein "maar". De computer die ze gebruikten was een simulatie op een gewone laptop. Een echte kwantumcomputer is nog niet zo groot of stabiel dat je dit direct kunt testen voor grote problemen. Op een simpele laptop ziet het er soms zelfs even snel uit als de oude methode, omdat het "simuleren" van een kwantumcomputer veel rekenkracht kost. Maar de theorie is sterk: op een echte, grote kwantumcomputer zou dit een enorme versnelling zijn.

5. Waarom is dit belangrijk?

Dit onderzoek is als het bouwen van de blauwdruk voor een nieuwe soort auto.

Het bewijst dat je complexe puzzels (zoals magische vierkanten, maar ook Sudoku's of logistieke problemen) kunt vertalen naar een taal die kwantumcomputers begrijpen.
Het laat zien dat we in de toekomst, als de technologie rijper is, problemen kunnen oplossen die voor huidige computers onmogelijk zijn.

Kortom: De onderzoekers hebben een brug gebouwd tussen de oude wereld van wiskundige puzzels en de nieuwe wereld van kwantumkracht. Ze hebben bewezen dat je met de juiste "magische lantaarn" (Grover's algoritme) en een beetje voorbereiding, de naald in de hooiberg veel sneller kunt vinden dan ooit tevoren.

Titel: Een Kwantumzoekbenadering voor Magische Vierkanten met Classieke Benchmarking

Auteurs: Rituparna R, Harsha Varthini en Aswani Kumar Cherukuri (Vellore Institute of Technology, India).

1. Probleemstelling

Het artikel richt zich op het genereren van magische vierkanten, een klassiek combinatorisch constraint satisfaction problem (CSP). Een magisch vierkant van de orde $n$ is een $n \times n$ rooster gevuld met de gehele getallen 1 tot $n^2$ , zodanig dat de som van elke rij, kolom en beide hoofddiagonalen gelijk is aan een constante (de magische constante $M$ ).

Complexiteit: De zoekruimte groeit factorieel met $n$ . Voor een $3 \times 3$ rooster zijn er $9! = 362.880$ mogelijke permutaties, maar slechts 8 geldige oplossingen. Voor grotere $n$ (bijv. $n=4$ ) wordt de zoekruimte ( $16! \approx 2 \times 10^{13}$ ) onbereikbaar voor exhaustieve klassieke enumeratie.
Doel: Het bewijzen dat kwantumcomputing, specifiek via Grover's algoritme, een efficiëntere aanpak biedt voor het vinden van deze geldige configuraties door een kwadratische versnelling in de query-complexiteit te realiseren.

2. Methodologie

De auteurs presenteren een gestructureerde pijplijn die klassieke pre-processing combineert met een kwantumzoekproces. Het systeem is geïmplementeerd in IBM's Qiskit.

A. Klassieke Pre-processing

Voordat de kwantumencoding plaatsvindt, wordt de zoekruimte verkleind via klassieke filters:

Siamese constructie: Het centrale cel van oneven-orde vierkanten wordt vastgelegd volgens de deterministische De la Loubère-methode.
Partiële constraints: Rij- en kolomsums worden gecontroleerd om duidelijk onhaalbare toewijzingen vroeg te verwijderen.
Doel: Het genereren van een compacte kandidaat-domein om het signaal-ruisverhouding tijdens de kwantumamplificatie te verbeteren.

B. Kwantum Encoding

Elke cel van het magische vierkant wordt gecodeerd in binaire vorm. Voor een $n \times n$ vierkant zijn er $n^2$ cellen, wat leidt tot een hoofdregister van $n^2 \times \lceil \log_2(n^2) \rceil$ qubits.
Een Hadamard-transformatie wordt toegepast om het systeem te initialiseren in een uniforme superpositie van alle mogelijke kandidaat-toestanden.

C. Oracle Constructie

De kern van de aanpak is een reversibele kwantum-oracle die geldige magische vierkanten markeert:

Modulaire optellers: Berekenen van rij-, kolom- en diagonaalsommen in ancilla-registers.
Vergelijkers: Controleren of deze sommen gelijk zijn aan de magische constante $M$ en of alle elementen uniek zijn.
Phase Flip: Een multi-controlled gate flippt de fase van de toestanden die aan alle constraints voldoen (fase -1).
Uncomputation: Alle tussenresultaten worden teruggedraaid om de ancilla-qubits te resetten, wat essentieel is voor de reversibiliteit en interferentie.

D. Grover Iteratie

Het algoritme past de oracle ( $O$ ) en een diffusie-operator ( $D$ ) herhaaldelijk toe.

De diffusie-operator invert alle amplitudes rond het gemiddelde, waardoor de amplitude van de gemarkeerde (geldige) toestanden wordt versterkt.
Het optimale aantal iteraties is $k \approx \frac{\pi}{4}\sqrt{N/M}$ , waarbij $N$ de zoekruimte is en $M$ het aantal oplossingen.

3. Belangrijkste Bijdragen

Formele Encoding: Een complete kwantumbenadering voor het genereren van magische vierkanten als een zoekprobleem.
Reversibele Oracle: Het ontwerp van een oracle gebaseerd op modulaire rekenkringen en multi-controlled gates voor constraint-verificatie.
Hybride Pijplijn: Een unieke architectuur waarbij klassieke pre-processing dient voor initialisatie en de kwantumcomponent voor de daadwerkelijke zoektocht (geen iteratieve loop, maar sequentiële stappen).
Benchmarking: Een empirische vergelijking tussen kwantumzoek, klassieke brute-force en backtracking.
Implementatie: Een volledige end-to-end implementatie in Qiskit, inclusief circuits voor $3 \times 3$ en een spel voor $5 \times 5$ .

4. Resultaten en Experimenten

De experimenten werden uitgevoerd op klassieke statevector-simulators (vanwege de beperkte qubit-capaciteit voor grotere instellingen).

Experiment 1: Magisch Vierkant Spel ( $5 \times 5$ ):
- Zoeken naar een specifieke waarde in een reeds gegenereerd vierkant.
- Resultaat: Grover's algoritme vond de index in 3 iteraties met 5 qubits, wat de basisfunctionaliteit van de zoekprimitief bevestigde.
Experiment 2: Grover vs. Brute-Force ( $3 \times 3$ ):
- Zoekruimte: $N = 362.880$ .
- Klassiek: Brute-force controleerde 69.075 permutaties in 0,0744 seconden.
- Kwantum: De simulatie nam 0,0053 seconden in beslag (theoretisch ~602 oracle-calls vs. 362.880 klassieke checks).
- Opmerking: De snellere tijd is voornamelijk te wijten aan de overhead van de klassieke simulator, niet aan echte kwantumversnelling.
Experiment 3: Grover vs. Backtracking ( $3 \times 3$ ):
- Klassiek backtracking (met pruning) nam 0,0033 seconden.
- Kwantumsimulatie nam 0,0032 seconden.
- De tijden zijn bijna identiek, wat bevestigt dat bij kleine $n$ de simulatie-overhead elke theoretische snelheidswinst maskeert.

5. Discussie en Beperkingen

Simulatie-Overhead: De grootste beperking is dat klassieke simulatie van kwantumcircuits exponentieel schaalt ( $O(2^q)$ ). Voor een volledig constraint-oracle van een $3 \times 3$ vierkant zijn er al bijna 30 qubits nodig, wat de geheugenlimieten van standaard werkstations overschrijdt.
Hardware Beperkingen: Huidige kwantumhardware (NISQ-era) heeft te veel ruis en te weinig qubits om dit probleem op grotere schaal ( $n \geq 4$ ) op te lossen.
Theoretische vs. Praktische Versnelling: De kwadratische versnelling ( $O(\sqrt{N})$ ) is een theoretisch bewijs. In de praktijk is deze pas zichtbaar op echte hardware bij grotere probleemgroottes, waar klassieke algoritmen onhaalbaar worden.

6. Conclusie en Significantie

Het artikel demonstreert succesvol dat het genereren van magische vierkanten kan worden geformuleerd als een kwantumzoekprobleem met een correct werkende reversibele oracle. Hoewel de huidige experimenten beperkt blijven tot kleine instanties door hardware- en simulatiebeperkingen, valideert het werk de theoretische haalbaarheid van een kwadratische versnelling voor CSP's.

De studie legt de basis voor toekomstig werk, zoals het toepassen van deze oracle-architectuur op andere CSP's (zoals Sudoku of Latijnse vierkanten) en het uitvoeren van experimenten op echte kwantumhardware om de effecten van decoherentie en gate-fouten te bestuderen. Het artikel benadrukt dat de echte meerwaarde van Grover's algoritme pas tot zijn recht komt bij schaalbare problemen die klassiek onoplosbaar zijn.