Categorieën
Artificial Intelligence Computers

Hoe je een Quantum Computer in de Ultimate Randomness Generator verandert.

*Martin Knops: een artikel gepubliceerd Quanta magazine.

Quantumcomputers zullen in de toekomst een grote rol van betekenis kunnen gaan spelen in onze informatie technologie. En in de wetenschap.

Zeg de woorden “kwantum suprematie” op een bijeenkomst van computerwetenschappers, en de ogen zullen waarschijnlijk rollen. De uitdrukking verwijst naar het idee dat kwantumcomputers binnenkort een drempel zullen overschrijden waar ze met relatief gemak taken kunnen uitvoeren die extreem moeilijk zijn voor klassieke computers. Tot voor kort dacht men dat deze taken weinig praktisch nut hadden, vandaar dat het oog rolt.

Maar nu het gerucht gaat dat de kwantumprocessor van Google dit doel bijna heeft bereikt, kan de op handen zijnde kwantumoverheersing toch een belangrijke toepassing blijken te hebben: het genereren van pure willekeur.

Willekeurigheid is cruciaal voor bijna alles wat we doen met onze computer- en communicatie-infrastructuur. Het wordt in het bijzonder gebruikt om gegevens te versleutelen en alles te beschermen, van alledaagse gesprekken tot financiële transacties en staatsgeheimen.

Echte, verifieerbare willekeur – denk eraan als de eigenschap die een reeks getallen bezit die het onmogelijk maakt om het volgende getal in de reeks te voorspellen – is buitengewoon moeilijk te verkrijgen.

Dat zou kunnen veranderen zodra kwantumcomputers hun superioriteit aantonen. Die eerste taken, in eerste instantie bedoeld om simpelweg te pronken met de bekwaamheid van de technologie, kunnen ook echte, gecertificeerde willekeur opleveren. “We zijn er erg enthousiast over”, zegt John Martinis, een natuurkundige aan de Universiteit van Californië in Santa Barbara, die de leiding heeft over de kwantumcomputers van Google. “We hopen dat dit de eerste toepassing van een kwantumcomputer is.”

Willekeurigheid en entropie

Willekeurigheid en kwantumtheorie gaan samen als donder en bliksem. In beide gevallen is het eerste een onvermijdelijk gevolg van het laatste. In de kwantumwereld wordt vaak gezegd dat systemen zich in een combinatie van toestanden bevinden – in een zogenaamde ‘superpositie’. Wanneer je het systeem meet, zal het “instorten” in slechts een van die toestanden. En hoewel je met de kwantumtheorie kansen kunt berekenen voor wat je zult vinden als je je meting uitvoert, is het specifieke resultaat altijd fundamenteel willekeurig.

Natuurkundigen hebben deze verbinding benut om generatoren voor willekeurige getallen te maken. Deze zijn allemaal gebaseerd op metingen van een soort kwantumsuperpositie. En hoewel deze systemen meer dan voldoende zijn voor de willekeur van de meeste mensen, kan het moeilijk zijn om ermee te werken. Bovendien is het buitengewoon moeilijk om aan een scepticus te bewijzen dat deze generatoren van willekeurige getallen echt willekeurig zijn. En tot slot vereisen enkele van de meest effectieve methoden om verifieerbare willekeurigheid te genereren, kieskeurige opstellingen met meerdere apparaten die over grote afstanden van elkaar zijn gescheiden.

Een recent voorstel om willekeur uit een enkel apparaat te halen – een kwantumcomputer – maakt gebruik van een zogenaamde bemonsteringstaak, die een van de eerste tests van kwantumsuprematie zal zijn. Om de taak te begrijpen, stel je voor dat je een doos met tegels krijgt. Elke tegel heeft een paar 1’en en 0’en erop gegraveerd – 000, 010, 101 enzovoort.

Het Google AI-lab introduceerde in 2018 een kwantumprocessor van 72 qubit, Bristlecone genaamd.

Als er slechts drie bits zijn, zijn er acht mogelijke opties. Maar er kunnen meerdere exemplaren van elke gelabelde tegel in de doos zitten. Mogelijk zijn er 50 tegels met het label 010 en 25 met het label 001. Deze verdeling van tegels bepaalt de kans dat je willekeurig een bepaalde tegel eruit trekt. In dit geval is de kans twee keer zo groot dat u een tegel met het label 010 eruit trekt als een tegel met het label 001.

Een bemonsteringstaak omvat een computeralgoritme dat het equivalent doet van het bereiken van een doos met een bepaalde verdeling van tegels en er willekeurig een van hen extraheren. Hoe groter de kans die is opgegeven voor een tegel in de distributie, hoe waarschijnlijker het is dat het algoritme die tegel uitvoert.

Natuurlijk zal een algoritme niet in een letterlijke zak reiken en tegels eruit halen. In plaats daarvan zal het willekeurig een binair getal uitvoeren dat bijvoorbeeld 50 bits lang is, nadat het een verdeling heeft gekregen die de gewenste waarschijnlijkheid specificeert voor elke mogelijke 50-bits uitvoerreeks.

“We hopen dat dit de eerste toepassing is van een kwantumcomputer.

John Martinis

De kwantumcomputer begint met al zijn kwantumbits – qubits – in een bepaalde toestand. Laten we zeggen dat ze allemaal beginnen bij 0. Net zoals klassieke computers werken op klassieke bits met behulp van zogenaamde logische poorten, manipuleren kwantumcomputers qubits met behulp van het kwantumequivalent, bekend als kwantumpoorten.

Maar kwantumpoorten kunnen qubits in een vreemde toestand brengen. Een soort poort kan bijvoorbeeld een qubit die begint met een beginwaarde 0 in een superpositie van 0 en 1 plaatsen. Als je vervolgens de toestand van de qubit zou meten, zou deze willekeurig in 0 of 1 met dezelfde waarschijnlijkheid instorten. .

Nog bizarder kunnen kwantumpoorten die op twee of meer qubits tegelijk inwerken, ervoor zorgen dat de qubits met elkaar ‘verstrengeld’ raken. In dit geval raken de toestanden van de qubits met elkaar verweven, zodat de qubits nu alleen beschreven kunnen worden met een enkele kwantumtoestand.

Als je een aantal kwantumpoorten samenvoegt en ze vervolgens laat werken op een set qubits in een bepaalde volgorde, heb je een kwantumcircuit gemaakt. Om in ons geval willekeurig een 50-bits reeks uit te voeren, kun je een kwantumcircuit bouwen dat 50 qubits bij elkaar brengt in een superpositie van toestanden die de distributie vastlegt die je opnieuw wilt creëren.

Wanneer de qubits worden gemeten, wordt de hele superpositie willekeurig samengevouwen tot één 50-bits reeks. De kans dat het instort tot een bepaalde string wordt bepaald door de verdeling die wordt gespecificeerd door het kwantumcircuit. Het meten van de qubits is vergelijkbaar met geblinddoekt in de doos reiken en willekeurig een string uit de distributie bemonsteren.

Hoe brengt dit ons tot willekeurige getallen? Cruciaal is dat de 50-bits string die door de kwantumcomputer wordt bemonsterd, veel entropie heeft, een mate van wanorde of onvoorspelbaarheid, en dus willekeur. “Dit is misschien een groot probleem”, zei Scott Aaronson, een computerwetenschapper aan de Universiteit van Texas, Austin, die het nieuwe protocol bedacht. “Niet omdat het de belangrijkste toepassing van kwantumcomputers is – ik denk dat het verre van dat is – maar omdat het lijkt alsof het waarschijnlijk de eerste toepassing van kwantumcomputers is die technologisch haalbaar zal zijn om te implementeren.”

Scott Aaronson, een computerwetenschapper aan de Universiteit van Texas, Austin, zegt dat het genereren van willekeurige getallen waarschijnlijk “de eerste toepassing van kwantumcomputers zal zijn die technologisch haalbaar zal zijn om te implementeren”. Afdeling Computerwetenschappen, Universiteit van Texas in Austin

Het protocol van Aaronson om willekeur te genereren is redelijk eenvoudig. Een klassieke computer verzamelt eerst een paar stukjes willekeur uit een vertrouwde bron en gebruikt deze “seed randomness” om de beschrijving van een kwantumcircuit te genereren. De willekeurige bits bepalen de soorten kwantumpoorten en de volgorde waarin ze op de qubits moeten werken. De klassieke computer stuurt de beschrijving naar het kwantumcomputer, die het kwantumcircuit implementeert, de qubits meet en de 50-bits uitvoerbitstring terugstuurt. Daarbij heeft het willekeurig bemonsterd uit de door het circuit gespecificeerde distributie.

Herhaal het proces nu keer op keer – bijvoorbeeld 10 keer voor elk kwantumcircuit. De klassieke computer gebruikt statistische tests om ervoor te zorgen dat de outputstrings veel entropie hebben. Aaronson heeft aangetoond, gedeeltelijk in werk dat is gepubliceerd met Lijie Chen en gedeeltelijk in werk dat nog moet worden gepubliceerd, dat onder bepaalde plausibele veronderstellingen dat dergelijke problemen rekenkundig moeilijk zijn, geen enkele klassieke computer een dergelijke entropie kan genereren in de tijd die een kwantumcomputer nodig zou hebben. willekeurig steekproeven uit een distributie. Na de controles plakt de klassieke computer alle 50-bits outputstrings aan elkaar en voert dit allemaal naar een bekend klassiek algoritme. ‘Het produceert een lange snaar die bijna perfect willekeurig is,’ zei Aaronson.

De Quantum Trapdoor

Het protocol van Aaronson is het meest geschikt voor kwantumcomputers met ongeveer 50 tot 100 qubits. Naarmate het aantal qubits in een kwantumcomputer deze drempel overschrijdt, wordt het rekenkundig onhandelbaar voor zelfs klassieke supercomputers om het protocol te gebruiken. Dit is waar een ander schema voor het genereren van verifieerbare willekeur met behulp van kwantumcomputers in beeld komt. Het maakt gebruik van een bestaande wiskundige techniek met een verboden naam: een klauwvrije functie van een luik. “Het klinkt veel erger dan het is”, zei Umesh Vazirani, een computerwetenschapper aan de University of California, Berkeley, die de nieuwe strategie samen met Zvika Brakerski, Paul Christiano, Urmila Mahadev en Thomas Vidick bedacht.

Stel je weer een doos voor. In plaats van een string in te pakken en eruit te halen, laat je deze keer een n-bit string vallen, noem het x, en eruit springt weer een n-bit string. Het vak wijst op de een of andere manier een invoertekenreeks toe aan een uitvoerstring. Maar het vak heeft een speciale eigenschap: voor elke x is er een andere invoertekenreeks y die dezelfde uitvoertekenreeks genereert.

Met andere woorden, er bestaan twee unieke invoertekenreeksen – x en y – waarvoor het vak dezelfde uitvoerreeks retourneert, z. Dit triplet van x, y en z wordt een klauw genoemd. De doos, in de informatica, is een functie. De functie is gemakkelijk te berekenen, wat betekent dat gegeven x of y, het gemakkelijk is om z te berekenen. Maar als je alleen x en z krijgt, is het vinden van y – en dus de klauw – onmogelijk, zelfs niet voor een kwantumcomputer.

Update 21 juni 2019: dit artikel is bijgewerkt met een verwijzing naar het niet-gepubliceerde werk van Aaronson.

Urmila Mahadev, Umesh Vazirani en Thomas Vidick ontwikkelden een generator voor willekeurige getallen door cryptografie te koppelen aan kwantuminformatieverwerking.

Jana Asenbrennerova voor Quanta Magazine; Simons Institute for the Theory of Computing; Met dank aan Caltech.

De enige manier om bij de klauw te komen, is als je wat voorkennis had, het zogenaamde luik.

Vazirani en zijn collega’s willen dergelijke functies niet alleen gebruiken om kwantumcomputers willekeurigheid te laten genereren, maar ook om te verifiëren dat de kwantumcomputer zich kwantummechanisch gedraagt – wat essentieel is om op de willekeur te vertrouwen.

Het protocol begint met een kwantumcomputer die n qubits in een superpositie van alle n-bit strings plaatst. Vervolgens stuurt een klassieke computer een beschrijving van een kwantumcircuit waarin de functie wordt gespecificeerd die op de superpositie moet worden toegepast – een klauwvrije functie zonder valluik. De kwantumcomputer implementeert het circuit, maar zonder iets van het luik te weten.

In dit stadium komt de kwantumcomputer in een toestand waarin een set van zijn qubits zich in een superpositie van alle n-bit strings bevindt, terwijl een andere set het resultaat bevat van het toepassen van de functie op deze superpositie. De twee sets qubits zijn met elkaar verstrengeld.

De kwantumcomputer meet vervolgens de tweede set qubits, waarbij de superpositie willekeurig wordt samengevouwen tot een output z. De eerste set qubits stort echter in een gelijke superpositie van twee n-bit strings, x en y, omdat beide als input hadden kunnen dienen voor de functie die tot z heeft geleid.

De klassieke computer ontvangt de uitvoer z en doet vervolgens een van de volgende twee dingen. Meestal vraagt het de kwantumcomputer om de resterende qubits te meten. Dit zal de superpositie, met een kans van 50-50, inklappen tot x of y. Dat komt overeen met het willekeurig krijgen van een 0 of een 1.

Af en toe vraagt de klassieke computer om een speciale meting om de kwantumheid van de kwantumcomputer te controleren. De meting en de uitkomst zijn zo ontworpen dat de klassieke computer, met behulp van het luik waartoe alleen hij toegang heeft, ervoor kan zorgen dat het apparaat dat zijn vragen beantwoordt inderdaad kwantum is. Vazirani en collega’s hebben aangetoond dat als het apparaat het juiste antwoord geeft op de speciale meting zonder gebruik te maken van instortende qubits, dat hetzelfde is als het uitzoeken van de klauw zonder het luik te gebruiken. Dit is natuurlijk onmogelijk. Er moet dus ten minste één qubit in het apparaat instorten (willekeurig een 0 of een 1 geven). “[Het protocol] creëert een fraudebestendige qubit in een niet-vertrouwde kwantumcomputer,” zei Vazirani.

Deze fraudebestendige qubit levert bij elke ondervraging één werkelijk willekeurig bit aan informatie; een reeks van dergelijke zoekopdrachten kan vervolgens worden gebruikt om lange, willekeurige bitstrings te creëren.

Dit schema is misschien sneller dan het kwantum-bemonsteringsprotocol van Aaronson, maar het heeft een duidelijk nadeel. “Het zal niet praktisch zijn met 50 of 70 qubits,” zei Aaronson.

Aaronson wacht voorlopig op het systeem van Google. “Of het ding dat ze gaan uitrollen daadwerkelijk goed genoeg zal zijn om kwantumoverheersing te bereiken, is een grote vraag”, zei hij.

Als dat zo is, dan ligt de verifieerbare kwantum-willekeurigheid van een enkel kwantumapparaat om de hoek. “We denken dat het nuttig is en een potentiële markt is, en dat is iets wat we willen overwegen om mensen aan te bieden”, zei Martinis.

This article was reprinted on Wired.com.


Gerelateerd:

  1. Graduate Student Solves Quantum Verification Problem
  2. Computer Scientists Expand the Frontier of Verifiable Knowledge
  3. The Universe’s Ultimate Complexity Revealed by Simple Quantum Games

Auteur:

Anil Anatashwany

— Lees op Quantum Magazine


Geef een reactie

Vul je gegevens in of klik op een icoon om in te loggen.

WordPress.com logo

Je reageert onder je WordPress.com account. Log uit /  Bijwerken )

Google photo

Je reageert onder je Google account. Log uit /  Bijwerken )

Twitter-afbeelding

Je reageert onder je Twitter account. Log uit /  Bijwerken )

Facebook foto

Je reageert onder je Facebook account. Log uit /  Bijwerken )

Verbinden met %s

Deze site gebruikt Akismet om spam te bestrijden. Ontdek hoe de data van je reactie verwerkt wordt.