Het Bernstein-Vazirani-algoritme: een geheime code in één klap kraken
Stel je voor: iemand heeft een geheim getal bedacht, geschreven als een rij van bijvoorbeeld twintig nullen en enen, zoiets als 01101001011000111010. Je mag dat getal raden met hulp van een rekenmachine, maar die rekenmachine beantwoordt maar één soort vraag. Jij voert zelf ook een rij van twintig nullen en enen in, en de machine vertelt je alleen of het totaal aantal overeenkomende enen in jouw rij en de geheime rij even of oneven is. Verder niets. Hoe ontdek je het geheime getal zo snel mogelijk?
Met een gewone computer moet je dat орacle, zoals zo'n zwarte-doos-functie heet, minstens twintig keer raadplegen: één keer per cijfer. Het Bernstein-Vazirani-algoritme, genoemd naar de Amerikaanse onderzoekers Ethan Bernstein en Umesh Vazirani die het begin jaren negentig beschreven, laat zien dat een kwantumcomputer dezelfde geheime rij kan achterhalen met slechts één vraag aan diezelfde zwarte doos — ongeacht hoe lang de rij is. Het is een van de eerste en meest overzichtelijke voorbeelden waarmee natuurkundigen en informatici konden aantonen dat een kwantumcomputer in theorie iets kan wat een klassieke computer principieel niet zo snel kan.
Wat is het precies?
Het algoritme draait om een wiskundige functie die in de vakliteratuur een 'orakel' wordt genoemd: een zwarte doos die, gegeven een rij nullen en enen als invoer, telkens een simpel antwoord teruggeeft. In het geval van Bernstein-Vazirani berekent het orakel het zogeheten inproduct (ook wel puntproduct) van jouw invoerrij en een verborgen geheime rij, en geeft het antwoord modulo twee — dat wil zeggen: even of oneven, oftewel een 0 of een 1.
Een klassieke computer kan uit zo'n orakel maar één bit informatie per vraag halen, en moet daarom voor elk cijfer van de geheime rij apart een vraag stellen. Een kwantumcomputer gaat anders te werk. Alle qubits — de kwantumversie van bits, die tegelijk een beetje 0 én een beetje 1 kunnen zijn — worden eerst met zogeheten Hadamard-poorten in een gelijkmatige superpositie gebracht: ze vertegenwoordigen als het ware alle mogelijke invoerrijen tegelijk.
Vervolgens wordt het orakel precies één keer aangeroepen, maar dan op deze superpositie van alle rijen tegelijk. Door een kwantumtruc die 'phase kickback' heet, codeert het orakel het antwoord niet als een los bit, maar als een subtiele faseverschuiving die verweven raakt met elke qubit. Een tweede ronde Hadamard-poorten zet die verweven fase-informatie vervolgens om in een leesbaar patroon. Wanneer de qubits daarna worden gemeten, lees je in één keer de volledige geheime rij af — niet bit voor bit, maar in zijn geheel, na precies één raadpleging van het orakel.
Wat wil men ermee bereiken?
Het Bernstein-Vazirani-algoritme is niet bedacht om een praktisch probleem in de echte wereld op te lossen; de geheime-rij-puzzel komt in het dagelijks leven nauwelijks voor. Het doel was fundamenteler: aantonen dat er problemen bestaan waarbij een kwantumcomputer aantoonbaar minder vragen aan een orakel nodig heeft dan elke mogelijke klassieke computer, hoe slim die ook geprogrammeerd is.
Zulk bewijs is belangrijk in de theoretische informatica, waar onderzoekers de grenzen van rekenkracht in kaart brengen aan de hand van 'querycomplexiteit' — hoe vaak je een zwarte doos moet raadplegen om een antwoord te vinden. Het algoritme bouwt voort op het iets oudere Deutsch-Jozsa-algoritme, dat alleen kon vaststellen of een functie 'constant' of 'gebalanceerd' is, en breidt dat idee uit: in plaats van één bit informatie onttrekt Bernstein-Vazirani in één klap de volledige geheime rij.
Daarnaast dient het algoritme als bouwsteen en lesmateriaal: het illustreert op een relatief eenvoudige manier kernbegrippen van kwantumcomputing — superpositie, interferentie en phase kickback — die ook terugkomen in krachtigere algoritmen zoals dat van Simon en uiteindelijk het beroemde factorisatie-algoritme van Shor.
Voorbeelden uit de praktijk
Omdat het algoritme geen commercieel doel dient, zijn de 'praktijkvoorbeelden' vooral demonstraties, lesmateriaal en hardwaretests:
- IBM's open-source lesmateriaal, de Qiskit-textbook, bevat een volledig uitgewerkt hoofdstuk waarin studenten het Bernstein-Vazirani-algoritme zelf programmeren en laten draaien op echte IBM-kwantumchips via de cloud, niet alleen op een simulator.
- Sinds IBM in 2016 gratis cloudtoegang tot kleine kwantumprocessors opende, is dit algoritme — samen met Deutsch-Jozsa en het zoekalgoritme van Grover — een van de standaardprogramma's geworden waarmee onderzoekers en studenten wereldwijd voor het eerst kennismaken met echte kwantumhardware.
- Verschillende academische cursussen kwantuminformatica, onder meer aan de TU Delft (via onderzoeksinstituut QuTech) en andere technische universiteiten, gebruiken het algoritme als standaardoefening om het verschil tussen klassieke en kwantumberekeningen tastbaar te maken.
- Onderzoekers gebruiken het algoritme ook als eenvoudige benchmark om te testen hoeveel ruis en foutjes een kwantumchip introduceert: omdat de uitkomst voorspelbaar is (de ingevoerde geheime rij moet er precies uitkomen), is elke afwijking een directe maatstaf voor hardwarefouten.
Hoe ver is de techniek?
Het algoritme zelf is wiskundig al sinds de jaren negentig volledig uitgewerkt en verandert niet meer; wat wél verandert is de hardware waarop het draait. De uitdaging zit tegenwoordig niet in het algoritme, maar in de kwaliteit van de beschikbare kwantumchips.
Huidige kwantumcomputers behoren tot wat de sector 'NISQ' noemt: noisy intermediate-scale quantum, oftewel ruizige, middelgrote kwantumsystemen met enkele tientallen tot een paar honderd qubits, die nog relatief veel fouten maken. Bernstein-Vazirani laat zich op zulke machines prima demonstreren voor korte geheime rijen van een paar qubits, maar hoe langer de rij — en dus hoe meer qubits nodig zijn — hoe groter de kans dat ruis en onvolkomen poorten een foutief antwoord opleveren. Er bestaat nog geen zogeheten foutgecorrigeerde, 'fouttolerante' kwantumcomputer die dit probleem structureel oplost.
Belangrijk om eerlijk te benoemen: het algoritme is niet 'in ontwikkeling' zoals een nieuw product. Het dient vooral als meetlat voor hardwarevooruitgang. Elke verbetering in qubit-kwaliteit, koppeling tussen qubits en foutonderdrukking laat zich direct aflezen aan hoe betrouwbaar en hoe lang een geheime rij correct kan worden teruggevonden.
Wie werken eraan?
Het algoritme is oorspronkelijk ontwikkeld aan de University of California, Berkeley, waar Umesh Vazirani nog altijd hoogleraar is en een vooraanstaande rol speelt in het onderzoek naar kwantumcomplexiteit. Aan de toepassing en demonstratie van het algoritme op echte hardware werken tegenwoordig vooral de grote aanbieders van cloud-kwantumcomputers mee, zoals IBM Quantum, Google Quantum AI, IonQ, Rigetti Computing en Microsoft Azure Quantum, die hun systemen toegankelijk maken voor onderzoekers en studenten.
Op onderzoeksinstituutsniveau zijn onder meer QuTech (een samenwerking tussen de TU Delft en TNO in Nederland), het Institute for Quantum Computing van de University of Waterloo in Canada, en diverse Amerikaanse universiteiten actief betrokken bij onderwijs en onderzoek waarin dit type algoritme een rol speelt. Landen die fors investeren in kwantumonderzoek — de Verenigde Staten, Nederland en andere EU-lidstaten, China en Canada voorop — dragen zo indirect bij aan de infrastructuur waarop dit soort demonstraties draait.