Een belangrijk kwantumalgoritme is mogelijk een eigenschap van de natuur

Conceptuele afbeelding van dubbele DNA-helix mevrouw Tech; Originele afbeelding: Wikimedia commons

In 1996 publiceerde een kwantumfysicus van Bell Labs in New Jersey een nieuw recept voor het doorzoeken van een database met N inzendingen. Computerwetenschappers weten al lang dat dit proces ongeveer N stappen, omdat in het ergste geval het laatste item op de lijst het item van belang kan zijn.

Deze natuurkundige, Lov Grover, liet echter zien hoe de vreemde regels van de kwantummechanica het mogelijk maakten om te zoeken in een aantal stappen gelijk aan de vierkantswortel van N .

Dat was een groot probleem. Het doorzoeken van databases is een fundamentele taak in de informatica, die voor alles wordt gebruikt, van het vinden van telefoonnummers tot het breken van cryptografische codes. Elke versnelling is dus een aanzienlijke vooruitgang.

Verwant verhaal

Wat is kwantumcomputing?

De kwantummechanica zorgde voor een extra draai. Destijds was het recept van Grover slechts het tweede kwantumalgoritme dat sneller was bewezen dan zijn klassieke tegenhanger. (De eerste was het algoritme van Peter Shor voor het ontbinden van getallen, dat hij in 1994 ontdekte.) Het werk van Grover was een belangrijke factor bij het voorbereiden van de weg voor de kwantumcomputerrevolutie die vandaag de dag nog steeds aan de gang is.

Maar ondanks de interesse heeft het implementeren van het algoritme van Grover tijd gekost vanwege de aanzienlijke technische uitdagingen. De eerste kwantumcomputer die het kon implementeren verscheen in 1998, maar de eerste schaalbare versie verscheen pas in 2017, en zelfs toen werkte het met slechts drie qubits. Nieuwe manieren om het algoritme te implementeren zijn dus hard nodig.

Vandaag zeggen Stéphane Guillet en collega's van de Universiteit van Toulon in Frankrijk dat dit misschien makkelijker is dan iemand had verwacht. Ze zeggen dat ze bewijs hebben dat het zoekalgoritme van Grover een natuurlijk fenomeen is. We leveren het eerste bewijs dat elektronen onder bepaalde omstandigheden zich van nature kunnen gedragen als een Grover-zoekopdracht, op zoek naar defecten in een materiaal, zeggen ze.

Dat heeft duidelijke implicaties voor kwantumcomputing, maar de echte betekenis ervan kan veel diepgaander zijn. Theoretici debatteren al een tijdje over de vraag of kwantumonderzoek een van de grootste mysteries over de oorsprong van het leven zou kunnen verklaren. Het idee dat Grover-zoekopdrachten in de natuur plaatsvinden, zou het raadsel uiteindelijk kunnen oplossen.

Eerst wat achtergrond. Omdat het zo fundamenteel is, kan het zoekalgoritme van Grover op verschillende manieren worden geherformuleerd. Een daarvan is als een kwantumwandeling over een oppervlak - de manier waarop een kwantumdeeltje willekeurig van het ene punt naar het andere zou bewegen.

Verwant verhaal

Wat is kwantumcommunicatie? Onderzoekers en bedrijven creëren ultraveilige communicatienetwerken die de basis kunnen vormen van een kwantuminternet. Dit is hoe het werkt.

Het is duidelijk dat dit proces een soort zoektocht is in de tweedimensionale ruimte. Maar omdat een kwantumdeeltje veel paden tegelijk kan verkennen, gaat het veel sneller dan een klassieke zoektocht.

De aard van de ondergrond heeft een belangrijke invloed op het zoeken. Een type oppervlak bestaat bijvoorbeeld uit een vierkant raster waar het kwantumdeeltje vier mogelijke bewegingen heeft op elk hoekpunt.

Maar er zijn nog veel meer mogelijke rasters; een driehoekige, bijvoorbeeld, waar het kwantumdeeltje drie keuzes heeft bij elk hoekpunt. Het driehoekige raster is van bijzonder belang vanwege de gelijkenis met verschillende natuurlijk voorkomende kristalachtige materialen, zeggen Guillet en co.

Het team concentreerde zich op het simuleren van de manier waarop een Grover-zoekopdracht werkt voor elektronen die driehoekige en vierkante rasters verkennen, maar ze omvatten ook andere fysiek realistische effecten, zoals defecten in het raster in de vorm van gaten, en kwantumeigenschappen zoals interferentie-effecten.

De resultaten zijn eye-openend. De vraag die ze stellen is hoe snel een elektron het gat in een rooster kan vinden. En de grote doorbraak van het team is om aan te tonen dat deze simulaties reproduceren hoe echte elektronen zich gedragen in echte materialen.

Met andere woorden, dit is het bewijs dat vrije elektronen van nature het Grover-zoekalgoritme implementeren wanneer ze over het oppervlak van bepaalde kristallen bewegen.

Verwant verhaal

Verwant verhaal

Dat heeft directe gevolgen voor quantum computing. [Dit werk] kan het pad zijn naar een serieuze technologische sprong, waarbij experimentatoren de behoefte aan een volwaardige schaalbare en foutcorrigerende Quantum Computer zouden omzeilen en in plaats daarvan de kortere weg zouden nemen om te zoeken naar 'natuurlijke gebeurtenissen' van de Grover-zoekopdracht, zegt de ploeg.

Het werk heeft ook implicaties voor ons denken over de genetische code en het ontstaan ​​van leven. Elk levend wezen op aarde gebruikt dezelfde code, waarin DNA informatie opslaat met behulp van vier nucleotidebasen. De sequenties van nucleotiden coderen voor informatie voor het construeren van eiwitten uit een alfabet van 20 aminozuren.

Maar waarom deze cijfers - vier en 20 - en niet enkele andere? In 2000, slechts een paar jaar nadat Grover zijn werk publiceerde, Apoorva Patel van het Indian Institute of Science in Bangalore liet zien hoe het algoritme van Grover deze cijfers kon verklaren .

Patels idee houdt verband met de manier waarop DNA in cellen wordt geassembleerd. In deze situatie moet de moleculaire machinerie in een cel de moleculaire soep van nucleotidebasen doorzoeken om de juiste te vinden. Als er vier keuzes zijn, duurt een klassieke zoekopdracht gemiddeld vier stappen. De machine zou dus vier verschillende bases moeten proberen tijdens elke montagestap.

Maar een kwantumzoekopdracht met het algoritme van Grover is veel sneller: Patel toonde aan dat wanneer er vier keuzes zijn, een kwantumzoekopdracht in één stap onderscheid kan maken tussen vier alternatieven. Vier is inderdaad het optimale aantal.

Dit denken verklaart ook waarom er 20 aminozuren zijn. In DNA definieert elke set van drie nucleotiden een enkel aminozuur. Dus de volgorde van tripletten in DNA definieert de volgorde van aminozuren in een eiwit.

Maar tijdens de eiwitassemblage moet elk aminozuur worden gekozen uit een soep van 20 verschillende opties. Het algoritme van Grover verklaart deze getallen: een kwantumzoekopdracht in drie stappen kan een object vinden in een database met maximaal 20 soorten invoer. Nogmaals, 20 is het optimale aantal.

Met andere woorden, als de zoekprocessen die betrokken zijn bij het samenstellen van DNA en eiwitten zo efficiënt mogelijk moeten zijn, moet het aantal basen vier zijn en het aantal aminozuren 20 - precies zoals wordt gevonden. Het enige voorbehoud is dat de zoekopdrachten kwantum van aard moeten zijn.

Toen Patel zijn idee publiceerde, gooiden kwantumfysici het meteen weg. Destijds waren ze verzand in hun eigen pogingen om kwantumprocessen te beheersen, wat ze alleen konden doen door kwantumdeeltjes te isoleren in extreme omgevingen, zoals bij temperaturen dicht bij het absolute nulpunt.

Het voor de hand liggende probleem, zeiden ze, was dat levende wezens opereren in een warme, rommelige omgeving waarin kwantumtoestanden onmiddellijk zouden worden vernietigd.

Biologen waren even minachtend en zeiden dat kwantumprocessen onmogelijk aan het werk kunnen zijn in levende wezens.

Sindsdien is er steeds meer bewijs dat kwantumprocessen een belangrijke rol spelen in een aantal biologische mechanismen. Fotosynthese, bijvoorbeeld, wordt nu beschouwd als een in wezen kwantumproces.

Het werk van Guillet en co werpt een nieuw perspectief op dit alles. Het suggereert dat het algoritme van Grover niet alleen in bepaalde materialen mogelijk is; het lijkt een eigenschap van de natuur te zijn. En als dat waar is, dan beginnen de bezwaren tegen Patels ideeën af te brokkelen.

Het kan zijn dat het leven slechts een voorbeeld is van Grovers kwantumzoektocht aan het werk, en dat dit algoritme zelf een fundamentele eigenschap van de natuur is. Dat is een groot idee als er ooit een was.

Referentie: arxiv.org/abs/1908.11213 : De zoektocht naar Grover als een natuurlijk fenomeen

zich verstoppen