Quantum Computing heeft nu een krachtige zoekfunctie

Grover's algoritme

In 1996 onthulde een computerwetenschapper genaamd Lov Grover van Bell Labs in New Jersey een ongebruikelijk algoritme voor het doorzoeken van een database. Zoekalgoritmen behoren tot de belangrijkste in de informatica. Ze maken alledaagse taken mogelijk, zoals jagen door telefoonboeken, maar ook meer exotische taken zoals het breken van cryptografische codes. Dit soort algoritme is alomtegenwoordig in de informatica.

Dus elke manier om de taak te versnellen is enorm belangrijk. Een standaard zoekopdracht duurt een periode die ongeveer evenredig is met het aantal elementen in de zoekopdracht. Dat komt omdat het algoritme in het ergste geval alle elementen moet doorzoeken om er maar één te vinden.

Maar het algoritme van Grover is anders. De tijd die nodig is, is evenredig met de vierkantswortel van het aantal elementen. Computerwetenschappers noemen dit een kwadratische versnelling. En in een wereld waar snelheidsverhogingen van een paar fracties van een procent enorm waardevol zijn, is een kwadratische versnelling een enorme prestatie.

De truc van Grover was om de vreemde maar krachtige ideeën achter de kwantummechanica te gebruiken. In de klassieke wereld zijn bits slechts nullen en enen. Maar in de kwantumwereld kan een enkele kwantumbit, of qubit, tegelijkertijd een 0 en een 1 zijn. Natuurkundigen zeggen dat de qubit zich in een superpositie van staten bevindt.

De superpositie is de sleutel. In deze toestand kan een algoritme zowel de 0 als de 1 op hetzelfde moment zoeken. Omdat het meer dan één element tegelijk kan doorzoeken, kan een kwantumalgoritme veel sneller door een lijst zoeken dan een algoritme dat wordt beperkt door het ploetertempo van de klassieke natuurkunde.

Kwantumalgoritmen moeten worden geïmplementeerd door een kwantumcomputer, en in 1996, toen Grover zijn werk deed, was dit niet meer dan een verre droom. Maar de doorbraak kwam snel. Natuurkundigen demonstreerden de eerste primitieve kwantumcomputer in 1998 en toonden in hetzelfde jaar hoe deze het algoritme van Grover kon uitvoeren.

Maar deze specifieke vorm van quantum computing was uiterst beperkt. Het werkte op een paar qubits, maar niet meer, en zelfs in principe zou het nooit kunnen worden opgeschaald naar grotere berekeningen. Dit probleem van het bouwen en demonstreren van schaalbare kwantumcomputers heeft de discipline sindsdien geplaagd.

Nu, zo'n 20 jaar later, beginnen natuurkundigen kwantumcomputers te bouwen die het potentieel hebben om te schalen en dus in staat zijn tot krachtigere berekeningen. En vandaag zeggen Caroline Figgatt en vrienden van de Universiteit van Maryland dat ze het algoritme van Grover voor het eerst op een schaalbare kwantumcomputer hebben uitgevoerd.

Het werk demonstreert de snelle versnelling van kwantumberekeningen en maakt de weg vrij voor ambitieuzer werk met het algoritme dat zou kunnen beginnen met het kraken van echte uitdagingen zoals het breken van code.

De kwantumcomputer waar Figgatt en zijn collega's mee werken, bestaat uit een reeks van vijf ytterbium-ionen die in een elektromagnetisch veld hangen. Elk ion is als een kleine magneet die omhoog of omlaag kan worden gericht en met een laser van de ene toestand naar de andere kan worden gedraaid. Zo kan elk ion informatie opslaan: een 1 voor spin up en een 0 voor spin down bijvoorbeeld. En omdat het kwantumobjecten zijn, kunnen de ionen bestaan ​​in een superpositie van deze toestanden.

De ionen werken ook met elkaar in wisselwerking via de afstotende krachten die samenhangen met hun positieve lading. Door deze interactie kan de ene qubit communiceren met een andere qubit om informatie te verwerken. Dit is de essentie van kwantumberekening. De volgorde van de stappen in deze berekening is het kwantumalgoritme, in dit geval het algoritme van Grover.

Figgatt en co gebruiken hun systeem om een ​​drie-qubit kwantumcomputer te maken die tot acht items in een database kan opslaan. Vervolgens voeren ze het algoritme van Grover uit om aan te tonen dat het mogelijk is om een ​​item gemiddeld aanzienlijk sneller te vinden dan een klassieke computer die minstens acht bits nodig heeft. We rapporteren resultaten voor een compleet Grover-zoekalgoritme met drie qubits dat gebruikmaakt van de schaalbare kwantumcomputertechnologie van ingesloten atomaire ionen, met beter dan klassieke prestaties, zeggen Figgatt en co.

Dat is interessant werk met een aanzienlijk potentieel. Dit maakt de weg vrij voor uitgebreider gebruik van het Grover-zoekalgoritme bij het oplossen van grotere problemen op kwantumcomputers, inclusief het gebruik van het circuit als een subroutine voor andere kwantumalgoritmen, aldus het team.

Maar het werk biedt ook een interessant kijkje in de race om krachtige kwantumcomputers te bouwen. De winnaar van deze race zal waarschijnlijk enorme financiële beloningen oogsten, maar niemand weet precies welke technologie het beste is.

Deze wereld is in verwarring gebracht door een Canadese startup genaamd D-Wave Systems, die schijnbaar krachtige kwantumcomputers heeft verkocht aan bedrijven als Google en Lockheed Martin. Deze computers werken met 1.000 qubits, veel meer dan enige andere technologie.

Maar veel theoretici zeggen dat de beweringen van D-Wave overdreven zijn en dat de machines niet in de buurt komen van het soort rekenkracht waartoe andere kwantumcomputers in staat zouden moeten zijn.

Daarom proberen veel groepen andere kwantumtechnologieën te commercialiseren die enorm verschillen in de manier waarop ze kwantuminformatie opslaan en verwerken. Deze zijn op verschillende manieren afhankelijk van fotonen, elektronen, atomen, ionen en moleculen om hun kwantumbiedingen uit te voeren.

Van deze technieken is een van de oudste en best ontwikkelde ion trap quantum computing, en de University of Maryland-groep is een wereldleider op dit gebied. De leider van de groep, Chris Monroe, heeft inderdaad een startup genaamd IonQ die tot doel heeft deze technologie te commercialiseren.

Dus de demonstratie van een schaalbare kwantumcomputer die het algoritme van Grover kan implementeren, zij het met slechts drie qubits, kan worden gezien als een intentieverklaring.

In 1998, na de eerste implementatie van Grover's algoritme, was er een waaier van meningen over hoe lang het zou duren voor natuurkundigen om de volgende stap schaalbare computers te maken. Op basis van optimistische voorspellingen is een aantal startups naar behoren gevormd en ingestort. Maar in die tijd was 20 jaar aan het pessimistische einde van het spectrum van voorspellingen. Het feit dat het zo lang heeft geduurd, relativeert de moeilijkheidsgraad van de taak.

Het heelal beheersen op de kwantumschaal is moeilijk. Een interessante vraag voor technologen en durfkapitalisten is nu of het tempo van de technologische vooruitgang aanzienlijk kan worden versneld.

Referentie: arxiv.org/abs/1703.10535 : Voltooi 3-Qubit Grover Search op een programmeerbare Quantum Computer

zich verstoppen