“Ik denk dat ik gerust kan zeggen dat niemand de kwantummechanica begrijpt.” – Richard Feynman
Het onderwerp quantum computing heeft technologieschrijvers en journalisten altijd gefascineerd. Het computationele potentieel en de complexiteit ervan gaven het een zekere mystieke uitstraling. Te vaak beschrijven hoofdartikelen en infographics in detail de verschillende perspectieven van deze sector, terwijl ze nauwelijks ingaan op de praktische toepassing ervan: dit kan de minder oplettende lezer misleiden.
Populair-wetenschappelijke artikelen laten beschrijvingen van kwantumsystemen achterwege en doen uitspraken als:
Een gewone bit kan een 1 of een 0 zijn, maar een qubit kan tegelijkertijd een 1 en een 0 zijn.
Als je veel geluk hebt (waar ik niet zeker van ben), krijg je het volgende te horen:
De qubit bevindt zich in een superpositie tussen "1" en "0".
Geen van deze verklaringen lijkt plausibel, omdat we een kwantummechanisch fenomeen proberen te formuleren met behulp van taal die in een zeer traditionele wereld is ontwikkeld. Om de principes van kwantumcomputers duidelijk uit te leggen, is het noodzakelijk om een andere taal te gebruiken: wiskundig.
In deze zelfstudie bespreek ik de wiskundige hulpmiddelen die nodig zijn om kwantumcomputersystemen te modelleren en te begrijpen, en hoe ik de logica van kwantumcomputers kan illustreren en toepassen. Bovendien zal ik een voorbeeld geven van een kwantumalgoritme en je vertellen wat het voordeel ervan is ten opzichte van een traditionele computer.
Ik zal mijn best doen om dit allemaal in duidelijke taal uit te leggen, maar ik hoop nog steeds dat de lezers van dit artikel een basiskennis hebben van lineaire algebra en digitale logica (lineaire algebra komt aan bod , over digitale logica - ).
Laten we eerst de principes van digitale logica bespreken. Het is gebaseerd op het gebruik van elektrische circuits om berekeningen uit te voeren. Om onze beschrijving abstracter te maken, vereenvoudigen we de toestand van de elektrische draad tot “1” of “0”, wat overeenkomt met de toestanden “aan” of “uit”. Door transistors in een bepaalde volgorde te plaatsen, zullen we zogenaamde logische elementen creëren die een of meer ingangssignaalwaarden nemen en deze omzetten in een uitgangssignaal op basis van bepaalde regels van de Booleaanse logica.
Gemeenschappelijke logische poorten en hun toestandstabellen
Op basis van de ketens van dergelijke basiselementen kunnen complexere elementen worden gecreëerd, en op basis van de ketens van complexere elementen kunnen we uiteindelijk, met een grote mate van abstractie, verwachten een analoog van de centrale processor te verkrijgen.
Zoals ik eerder al zei, hebben we een manier nodig om digitale logica wiskundig weer te geven. Laten we eerst de wiskundige traditionele logica introduceren. Met behulp van lineaire algebra kunnen de klassieke bits met de waarden "1" en "0" worden weergegeven als twee kolomvectoren:
waar de cijfers aan de linkerkant staan vector. Door onze bits op deze manier weer te geven, kunnen we logische bewerkingen op de bits modelleren met behulp van vectortransformaties. Let op: hoewel het gebruik van twee bits in logische poorten veel bewerkingen kan uitvoeren (AND, NOT, XOR, etc.), kunnen bij gebruik van één bit slechts vier bewerkingen worden uitgevoerd: identiteitsconversie, negatie, berekening van de constante “0” en berekening van de constante “1”. Bij een identiteitsconversie blijft de bit ongewijzigd, bij een negatie verandert de bitwaarde naar het tegenovergestelde (van “0” naar “1” of van “1” naar “0”), en de berekening van de constante “1” of “0” stelt de bit in op “1” of “0”, ongeacht de vorige waarde.
| Identiteit | Identiteitstransformatie |
| Ontkenning | ontkenning |
| Constant-0 | Berekening van de constante "0" |
| Constant-1 | Berekening van de constante "1" |
Gebaseerd op onze voorgestelde nieuwe weergave van een bit, is het vrij eenvoudig om bewerkingen uit te voeren op de overeenkomstige bit met behulp van een vectortransformatie:
Laten we, voordat we verder gaan, eerst naar het concept kijken , wat eenvoudigweg impliceert dat om de omkeerbaarheid van een bewerking of een logisch element te garanderen, het noodzakelijk is om een lijst met ingangssignaalwaarden te bepalen op basis van de uitgangssignalen en de namen van de gebruikte bewerkingen. We kunnen dus concluderen dat de identiteitstransformatie en ontkenning omkeerbaar zijn, maar de bewerkingen voor het berekenen van de constanten “1” en “0” zijn dat niet. Dankzij kwantummechanica, kwantumcomputers gebruiken uitsluitend omkeerbare operaties, dus daar zullen we ons op concentreren. Vervolgens zetten we onomkeerbare elementen om in omkeerbare elementen, zodat ze door een kwantumcomputer kunnen worden gebruikt.
Met individuele bits kunnen door veel bits worden weergegeven:
Nu we bijna alle noodzakelijke wiskundige concepten hebben, gaan we verder met onze eerste kwantumlogische poort. Dit is de exploitant , of gecontroleerde Not (NOT), wat van groot belang is in omkeerbare en kwantumcomputers. Het CNOT-element is van toepassing op twee bits en retourneert twee bits. De eerste bit wordt aangeduid als de “control”-bit, en de tweede als de “control”-bit. Als de besturingsbit is ingesteld op "1", verandert de besturingsbit zijn waarde; Als de besturingsbit op "0" is ingesteld, wordt de besturingsbit niet gewijzigd.
Deze operator kan worden weergegeven als de volgende transformatievector:
Om alles te demonstreren wat we tot nu toe hebben besproken, laat ik je zien hoe je het CNOT-element op meerdere bits gebruikt:
Om samen te vatten wat al is gezegd: in het eerste voorbeeld ontleden we |10⟩ in delen van zijn tensorproduct en gebruiken we de CNOT-matrix om een nieuwe overeenkomstige toestand van het product te verkrijgen; we factoriseren het vervolgens naar |11⟩ volgens de eerder gegeven tabel met CNOT-waarden.
We hebben dus alle wiskundige regels onthouden die ons zullen helpen traditioneel computergebruik en gewone bits te begrijpen, en we kunnen eindelijk overgaan tot moderne kwantumcomputers en qubits.
Als je tot nu toe hebt gelezen, dan heb ik goed nieuws voor je: qubits kunnen eenvoudig wiskundig worden uitgedrukt. Als een klassieke bit (cbit) kan worden ingesteld op |1⟩ of |0⟩, bevindt de qubit zich over het algemeen eenvoudigweg in superpositie en kan vóór de meting zowel |0⟩ als |1⟩ zijn. Na meting valt het uiteen in |0⟩ of |1⟩. Met andere woorden: een qubit kan worden weergegeven als een lineaire combinatie van |0⟩ en |1⟩ volgens de onderstaande formule:
waar a₀ и een₁ vertegenwoordigen respectievelijk de amplitudes |0⟩ en |1⟩. Deze kunnen worden gezien als "kwantumkansen", die de waarschijnlijkheid vertegenwoordigen dat een qubit in een van de toestanden instort nadat deze is gemeten, aangezien in de kwantummechanica een object in superpositie in een van de toestanden instort nadat het is gefixeerd. Laten we deze uitdrukking uitbreiden en het volgende verkrijgen:
Om mijn uitleg te vereenvoudigen, is dit de weergave die ik in dit artikel zal gebruiken.
Voor deze qubit is de kans op instorten naar de waarde a₀ na meting is gelijk aan |a₀|², en de kans op ineenstorting van de waarde a₁ is gelijk aan |a₁|². Bijvoorbeeld voor de volgende qubit:
de kans om in “1” te vervallen is gelijk aan |1/ √2|², oftewel ½, dat wil zeggen 50/50.
Omdat in het klassieke systeem alle kansen opgeteld één moeten zijn (voor een volledige kansverdeling), kunnen we concluderen dat de kwadraten van de absolute waarden van de amplitudes |0⟩ en |1⟩ op één moeten uitkomen. Op basis van deze informatie kunnen we de volgende vergelijking formuleren:
Als u bekend bent met trigonometrie, zult u merken dat deze vergelijking overeenkomt met de stelling van Pythagoras (a²+b²=c²), dat wil zeggen dat we de mogelijke toestanden van de qubit grafisch kunnen weergeven als punten op de eenheidscirkel, namelijk:
Logische operatoren en elementen worden op dezelfde manier op qubits toegepast als in de situatie met klassieke bits - op basis van een matrixtransformatie. Alle inverteerbare matrixoperatoren die we tot nu toe hebben opgeroepen, in het bijzonder CNOT, kunnen worden gebruikt om met qubits te werken. Met dergelijke matrixoperatoren kunt u elk van de amplitudes van de qubit gebruiken zonder deze te meten en in te klappen. Laat me u een voorbeeld geven van het gebruik van de negatie-operator op een qubit:
Voordat we verder gaan, wil ik u eraan herinneren dat de amplitudewaarden a₀ en a₁ zijn eigenlijk , zodat de toestand van een qubit het nauwkeurigst kan worden weergegeven op een driedimensionale eenheidsbol, ook wel bekend als :
Om de uitleg te vereenvoudigen beperken we ons hier echter tot reële getallen.
Het lijkt tijd om enkele logische elementen te bespreken die uitsluitend zinvol zijn in de context van kwantumcomputing.
Een van de belangrijkste operatoren is het "Hadamard-element": het duurt een beetje in de toestand "0" of "1" en plaatst het in de juiste superpositie met een kans van 50% om in een "1" of "0" te vallen. na meting.
Merk op dat er rechtsonder in de Hadamard-operator een negatief getal staat. Dit komt door het feit dat het resultaat van het toepassen van de operator afhangt van de waarde van het ingangssignaal: - |1⟩ of |0⟩, en daarom is de berekening omkeerbaar.
Een ander belangrijk punt over het Hadamard-element is de invertibiliteit ervan, wat betekent dat het een qubit in de juiste superpositie kan nemen en deze kan transformeren in |0⟩ of |1⟩.
Dit is erg belangrijk omdat het ons de mogelijkheid geeft om vanuit een kwantumtoestand te transformeren zonder de toestand van de qubit te bepalen - en dus zonder deze ineen te laten storten. We kunnen quantum computing dus structureren op basis van een deterministisch in plaats van een probabilistisch principe.
Kwantumoperatoren die alleen reële getallen bevatten, zijn hun eigen tegendeel, dus we kunnen het resultaat van het toepassen van de operator op een qubit weergeven als een transformatie binnen de eenheidscirkel in de vorm van een toestandsmachine:
Zo wordt de qubit, waarvan de status in het bovenstaande diagram wordt weergegeven, na toepassing van de Hadamard-bewerking, getransformeerd naar de staat aangegeven door de overeenkomstige pijl. Op dezelfde manier kunnen we een andere statusmachine construeren die de transformatie van een qubit zal illustreren met behulp van de negatie-operator zoals hierboven weergegeven (ook bekend als de Pauli-negatie-operator of bit-inversie), zoals hieronder weergegeven:
Om complexere bewerkingen op onze qubit uit te voeren, kunnen we meerdere operators aan elkaar koppelen of elementen meerdere keren toepassen. Voorbeeld van seriële transformatie op basis van ziet er zo uit:
Dat wil zeggen, als we beginnen met bit |0⟩, een bit-inversie toepassen, en dan een Hadamard-bewerking, dan nog een bit-inversie, en opnieuw een Hadamard-bewerking, gevolgd door een laatste bit-inversie, krijgen we uiteindelijk de vector gegeven door op de rechterkant van de ketting. Door verschillende toestandsmachines op elkaar te plaatsen, kunnen we beginnen bij |0⟩ en de gekleurde pijlen volgen die overeenkomen met elk van de transformaties om te begrijpen hoe het allemaal werkt.
Nu we zo ver zijn gekomen, is het tijd om een van de soorten kwantumalgoritmen te overwegen, namelijk: , en laat zijn voordeel zien ten opzichte van een klassieke computer. Het is vermeldenswaard dat het Deutsch-Jozsa-algoritme volledig deterministisch is, dat wil zeggen dat het 100% van de tijd het juiste antwoord retourneert (in tegenstelling tot veel andere kwantumalgoritmen die zijn gebaseerd op de probabilistische definitie van qubits).
Laten we ons voorstellen dat je een zwarte doos hebt die een functie/operator op één bit bevat (onthoud: met één bit kunnen slechts vier bewerkingen worden uitgevoerd: identiteitsconversie, negatie, evaluatie van de constante "0" en evaluatie van de constante "1 "). Wat is precies de functie die in de doos wordt uitgevoerd? Je weet niet welke, maar je kunt zoveel varianten van invoerwaarden doorlopen als je wilt en de uitvoerresultaten evalueren.
Hoeveel inputs en outputs zou je door de zwarte doos moeten laten lopen om erachter te komen welke functie wordt gebruikt? Denk hier even over na.
In het geval van een klassieke computer moet u twee vragen stellen om te bepalen welke functie u moet gebruiken. Als de ingang "2" bijvoorbeeld een "1"-uitgang produceert, wordt het duidelijk dat de functie van het berekenen van de constante "0" of de negatiefunctie wordt gebruikt, waarna u de waarde van het ingangssignaal moet wijzigen. naar "0" en kijk wat er bij de uitgang gebeurt.
In het geval van een kwantumcomputer zijn er ook twee queries nodig, omdat je nog steeds twee verschillende uitvoerwaarden nodig hebt om precies te definiëren welke functie op de invoerwaarde moet worden toegepast. Als je de vraag echter een beetje herformuleert, blijkt dat kwantumcomputers nog steeds een serieus voordeel hebben: als je wilt weten of de gebruikte functie constant of variabel is, hebben kwantumcomputers het voordeel.
De in de box gebruikte functie is variabel als verschillende waarden van het ingangssignaal verschillende resultaten opleveren aan de uitgang (bijvoorbeeld identiteitsconversie en bitinversie), en als de uitgangswaarde niet verandert, ongeacht de ingangswaarde, dan functie is constant (bijvoorbeeld het berekenen van een constante "1" of het berekenen van de constante "0").
Met behulp van een kwantumalgoritme kun je op basis van slechts één query bepalen of een functie in een black box constant of variabel is. Maar voordat we in detail bekijken hoe we dit kunnen doen, moeten we een manier vinden om elk van deze functies op een kwantumcomputer te structureren. Omdat alle kwantumoperatoren omkeerbaar moeten zijn, worden we meteen geconfronteerd met een probleem: de functies voor het berekenen van de constanten “1” en “0” zijn dat niet.
Een veelgebruikte oplossing in quantum computing is het toevoegen van een extra uitvoerqubit die de invoerwaarde retourneert die de functie ontvangt.
| aan: | na: |
|
|
|
Op deze manier kunnen we de invoerwaarden uitsluitend op basis van de uitvoerwaarde bepalen en wordt de functie omkeerbaar. De structuur van kwantumcircuits creëert de behoefte aan een extra invoerbit. Om de corresponderende operators te ontwikkelen, gaan we ervan uit dat de extra invoerqubit is ingesteld op |0⟩.
Laten we, met behulp van dezelfde kwantumcircuitrepresentatie die we eerder hebben gebruikt, kijken hoe elk van de vier elementen (identiteitstransformatie, negatie, evaluatie van de constante "0" en evaluatie van de constante "1") kan worden geïmplementeerd met behulp van kwantumoperatoren.
Zo kunt u bijvoorbeeld de functie voor het berekenen van de constante “0” implementeren:
Berekening van de constante "0":
Hier hebben we helemaal geen operators nodig. De eerste invoerqubit (waarvan we aannamen dat deze |0⟩ was) retourneert met dezelfde waarde, en de tweede invoerwaarde retourneert zichzelf, zoals gewoonlijk.
Met de functie voor het berekenen van de constante “1” is de situatie een beetje anders:
Berekening van de constante "1":
Omdat we hebben aangenomen dat de eerste invoerqubit altijd is ingesteld op |0⟩, is het resultaat van het toepassen van de bitinversie-operator dat deze altijd een één produceert aan de uitvoer. En zoals gewoonlijk geeft de tweede qubit zijn eigen waarde aan de uitgang.
Bij het in kaart brengen van de operator voor identiteitstransformatie begint de taak ingewikkelder te worden. Hier leest u hoe u het moet doen:
Identieke transformatie:
Het hier gebruikte symbool geeft het CNOT-element aan: de bovenste regel geeft de besturingsbit aan, en de onderste regel geeft de besturingsbit aan. Ik wil u eraan herinneren dat bij gebruik van de CNOT-operator de waarde van de besturingsbit verandert als de besturingsbit gelijk is aan |1⟩, maar onveranderd blijft als de besturingsbit gelijk is aan |0⟩. Omdat we ervan uitgingen dat de waarde van de bovenste regel altijd gelijk is aan |0⟩, wordt de waarde ervan altijd toegewezen aan de onderste regel.
We gaan op dezelfde manier te werk met de negatie-operator:
ontkenning:
We keren eenvoudigweg het bit aan het einde van de uitvoerregel om.
Nu we dat voorlopige begrip achter de rug hebben, gaan we kijken naar de specifieke voordelen van een kwantumcomputer ten opzichte van een traditionele computer als het gaat om het bepalen van de constantheid of variabiliteit van een functie die verborgen is in een zwarte doos met behulp van slechts één query.
Om dit probleem op te lossen met behulp van quantum computing in één enkel verzoek, is het noodzakelijk om de invoerqubits in een superpositie te plaatsen voordat ze aan de functie worden doorgegeven, zoals hieronder weergegeven:
Het Hadamard-element wordt opnieuw toegepast op het resultaat van de functie om de qubits uit de superpositie te halen en het algoritme deterministisch te maken. We starten het systeem in de status |00⟩ en krijgen, om redenen die ik binnenkort zal uitleggen, het resultaat |11⟩ als de toegepaste functie constant is. Als de functie binnen de zwarte doos variabel is, retourneert het systeem na meting het resultaat |01⟩.
Laten we, om de rest van het artikel te begrijpen, eens kijken naar de illustratie die ik eerder liet zien:
Door de bitinversie-operator te gebruiken en vervolgens het Hadamard-element toe te passen op beide invoerwaarden gelijk aan |0⟩, zorgen we ervoor dat ze als volgt worden vertaald naar dezelfde superpositie van |0⟩ en |1⟩:
Met behulp van het voorbeeld waarbij deze waarde wordt doorgegeven aan een black box-functie, is het eenvoudig aan te tonen dat beide constante-waardefuncties |11⟩ uitvoeren.
Berekening van de constante "0":
Op dezelfde manier zien we dat de functie voor het berekenen van de constante “1” ook |11⟩ als uitvoer produceert, dat wil zeggen:
Berekening van de constante "1":
Merk op dat de uitvoer |1⟩ zal zijn, aangezien -1² = 1.
Volgens hetzelfde principe kunnen we bewijzen dat we bij gebruik van beide variabele functies altijd |01⟩ aan de uitgang krijgen (op voorwaarde dat we dezelfde methode gebruiken), hoewel alles iets ingewikkelder is.
Identieke transformatie:
Omdat CNOT een operator van twee qubits is, kan deze niet worden weergegeven als een eenvoudige toestandsmachine, en daarom is het noodzakelijk om twee uitgangssignalen te definiëren op basis van het tensorproduct van beide invoerqubits en vermenigvuldiging met de CNOT-matrix, zoals eerder beschreven:
Met deze methode kunnen we ook bevestigen dat de uitvoerwaarde |01⟩ wordt ontvangen als de negatiefunctie verborgen is in de zwarte doos:
ontkenning:
We hebben dus zojuist een situatie aangetoond waarin een kwantumcomputer duidelijk efficiënter is dan een conventionele computer.
Wat is het volgende?
Ik stel voor dat we hier eindigen. Wij hebben al geweldig werk geleverd. Als je alles hebt begrepen wat ik heb behandeld, denk ik dat je nu een goed begrip hebt van de basisprincipes van kwantumcomputers en kwantumlogica, en waarom kwantumalgoritmen in bepaalde situaties efficiënter kunnen zijn dan traditioneel computergebruik.
Mijn beschrijving kan nauwelijks een volwaardige gids voor kwantumcomputing en algoritmen worden genoemd - het is eerder een korte inleiding tot wiskunde en notatie, bedoeld om de ideeën van lezers over het onderwerp te ontkrachten die door populair-wetenschappelijke bronnen worden opgelegd (serieus, velen kunnen het echt niet begrijpen de situatie!). Ik had geen tijd om veel belangrijke onderwerpen aan te raken, zoals , complexiteit van de amplitudewaarden |0⟩ en |1⟩ en de werking van verschillende kwantumlogische elementen tijdens transformatie door de Bloch-bol.
Als je je kennis over kwantumcomputers wilt systematiseren en structureren, sterk Ik raad je aan om te lezen Emma Strubel: Ondanks de overvloed aan wiskundige formules bespreekt dit boek kwantumalgoritmen veel gedetailleerder.
Bron: www.habr.com