Is de kwantum-Fouriertransformatie exponentieel sneller dan een klassieke transformatie, en is dit de reden waarom het moeilijke problemen oplosbaar kan maken voor een quantumcomputer?

/ / Gepubliceerd in Quantum informatie, EITC/QI/QIF Quantum Informatie Fundamentals, Quantum Fourier-transformatie, Eigenschappen van Quantum Fourier-transformatie

De kwantum-Fouriertransformatie (QFT) speelt een centrale rol in de kwantuminformatietheorie en quantumcomputing. Het ontwerp en de implementatie ervan hebben grote gevolgen voor de efficiëntie van kwantumalgoritmen, met name bij problemen waarvan klassieke benaderingen als inefficiënt worden beschouwd. Om te onderzoeken of de QFT exponentieel sneller is dan zijn klassieke tegenhanger en of dit het kwantumvoordeel bij het oplossen van bepaalde rekenkundig moeilijke problemen ondersteunt, is het essentieel om zowel de wiskundige structuur als de rekencomplexiteit van de QFT te onderzoeken en deze te vergelijken met de bekendste klassieke algoritmen.

## De klassieke discrete Fourier-transformatie (DFT)

De klassieke discrete Fourier-transformatie (DFT) is een wiskundige bewerking waarbij een vector met complexe getallen wordt afgebeeld op een andere vector met dezelfde dimensie, die de frequentiecomponenten van de oorspronkelijke vector vertegenwoordigt. De DFT van een N-dimensionale vector x = (x_0, x_1, ..., x_{N-1}) is gegeven door:

    \[ \tilde{x}_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i jk/N}, \quad k = 0, 1, ..., N-1 \]

De naïeve implementatie van de DFT vereist O (N ^ 2) tijd omdat elk uitvoerelement een som over alle elementen omvat N invoerelementen, en er zijn N uitgangen.

De snelle Fourier-transformatie (FFT), een klassiek algoritme, reduceert deze complexiteit echter tot O(N \log N) Door de DFT recursief op te splitsen in kleinere DFT's. De FFT is een van de meest gevierde algoritmen in de computationele wetenschap en vormt de basis voor toepassingen van signaalverwerking tot numerieke analyse.

## De kwantum-Fouriertransformatie (QFT): definitie en circuitcomplexiteit

De kwantum-Fouriertransformatie is de kwantumanaloog van de klassieke DFT, die werkt op kwantumtoestanden. Voor een n-qubit-systeem, waarbij N = 2^n, de kwantummechanica is de lineaire operator gedefinieerd door:

    \[ |x\rangle \mapsto \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i xk/N} |k\rangle \]

besteld, x in 0, 1, ..., N-1.

De implementatie van de kwantumfrequentie (QFT) als kwantumcircuit is bijzonder efficiënt. Het kan worden ontbonden in een reeks Hadamard-poorten en gecontroleerde faseverschuivingspoorten. De diepte en de grootte van het circuit zijn beide O (n ^ 2), dat wil zeggen, O((\log N)^2), Waar n is het aantal qubits en N = 2^n is de dimensie van de Hilbertruimte.

Gedetailleerde circuitbeschrijving

Voor een n-qubitregister, bestaat het QFT-circuit doorgaans uit:

1. Een Hadamard-poort op de meest significante qubit.
2. Gecontroleerde faseverschuivingen tussen de meest significante qubit en elke minder significante qubit, met faseverschuivingen e^{2\pi i/2^k} voor de kde controle.
3. Recursie op de resterende n-1 qubits.
4. Een laatste omkering van de volgorde van de qubits (swap gates).

Het totale aantal poorten voor een exacte QFT is O (n ^ 2)Als een kleine fout echter acceptabel is (wat vaak voldoende is voor kwantumalgoritmen), is het mogelijk om de kwantummechanica nauwkeurig te benaderen \ epsilon alleen met behulp van O(n \log n + \log n \log(1/\epsilon)) poorten, waardoor de benodigde middelen nog verder worden verminderd.

Computationele complexiteitsvergelijking

- Klassieke FFT: O(N \log N) = O(2^nn)
- Kwantum-kwadraatstelsel: O (n ^ 2) poorten

Door deze complexiteiten in dezelfde eenheden te vertalen, werkt de QFT in O(\log^2 N) kwantumpoorten, terwijl de FFT vereist O(N \log N) klassieke bewerkingen. Dit is een exponentiële verbetering in het aantal benodigde basisbewerkingen, althans ten opzichte van de invoergrootte gemeten in bits (n = \log N).

## Is de QFT alleen exponentieel sneller?

Hoewel de QFT exponentieel sneller kan worden geïmplementeerd dan de klassieke FFT bij het meten van bronnen aan de hand van het aantal basiskwantumpoorten versus klassieke bewerkingen, is het belangrijk om te analyseren wat dit betekent voor praktische berekeningen. De exponentiële versnelling verwijst naar de complexiteit van het interne circuit: de QFT brengt een volledige superpositie van N amplitudes met alleen O (n ^ 2) poorten. Kwantummeting beperkt de kwantumtoestand echter tot één uitkomst, waardoor de directe extractie van alle uitvoeramplitudes beperkt is.

Als je geïnteresseerd bent in het berekenen van alle N De outputamplitudes van een kwantumcomputer zouden niet sneller zijn, omdat er slechts één meetresultaat per run kan worden waargenomen en het reconstrueren van het volledige spectrum exponentieel veel herhalingen zou vereisen. De exponentiële versnelling zit hem dus niet in de berekening van *alle* outputwaarden, maar in de transformatie van quantuminformatie binnen een quantumalgoritme.

## De rol van QFT in kwantumalgoritmen

De kwantummechanica (QFT) is een belangrijke subroutine in verschillende kwantumalgoritmen die exponentiële of superpolynomiale versnellingen bieden ten opzichte van de bekendste klassieke algoritmen. Het meest prominente voorbeeld is Shors algoritme voor het ontbinden van gehele getallen.

Algoritme van Shor

Het algoritme van Shor gebruikt de kwantummechanica om de periode van een functie te bepalen (periodebepaling), die vervolgens wordt gebruikt om grote gehele getallen te ontbinden. Het algoritme werkt als volgt:

1. Bereid een gelijkmatige superpositie voor over N staten.
2. Bereken een functie f(x) = a^x \mod N in superpositie.
3. Meet het tweede register, waarbij u de status samenvoegt tot een superpositie van ingangen die allemaal overeenkomen met de gemeten uitgang.
4. Pas de QFT toe op het eerste register, waardoor de periodieke structuur wordt omgezet in een superpositie, waarbij de meting informatie oplevert over de periode.
5. Gebruik het meetresultaat en de klassieke nabewerking (kettingbreuken) om de periode te herstellen en het gehele getal te ontbinden.

De QFT is exponentieel sneller dan de klassieke FFT wat betreft het aantal basisbewerkingen voor de transformatie. Deze efficiëntie is *belangrijk* voor de polynomiale prestaties van Shor's algoritme.

Verborgen subgroepproblemen

De kwantum-Fouriertransformatie is ook centraal in de klasse van verborgen subgroepproblemen (HSP), waarbij het doel is om een ​​verborgen subgroep te bepalen H van een groep G gegeven een functie die constant is op de nevenklassen van H en verschillend op verschillende cosets. Veel problemen van significant belang, zoals discrete logaritmen en bepaalde grafiekisomorfieproblemen, kunnen in deze vorm gegoten worden. De kwantummechanica (QFT) maakt het mogelijk om de subgroepstructuur uit kwantumtoestanden te extraheren, wat efficiënte oplossingen mogelijk maakt waar klassieke algoritmen onhaalbaar zijn.

## Beperkingen en misvattingen

Het is belangrijk om de subtiliteiten in de bewering dat QFT exponentieel sneller is dan klassieke FFT te onderkennen:

- Efficiënte transformatie, geen efficiënte bemonstering: De kwantummechanica (QFT) transformeert de kwantumtoestand efficiënt, maar een quantumcomputer kan niet de volledige getransformeerde toestand weergeven. Metingen leveren een steekproef op uit de waarschijnlijkheidsverdeling die wordt gedefinieerd door de kwadratische amplitudes. Voor veel toepassingen is dit voldoende, omdat het kwantumalgoritme is ontworpen om de waarschijnlijkheid van het meten van een bruikbaar antwoord hoog te maken.
- Klassieke outputreconstructie: Als het doel is om alle N Voor Fouriercoëfficiënten biedt de kwantummechanica (QFT) geen uitkomst; per run kan slechts een kwantummonster worden verkregen. De exponentiële efficiëntie van de QFT is daarom nuttig binnen kwantumalgoritmen, maar niet voor directe klassieke berekening van alle transformatiewaarden.
- Niet alle problemen: De kwantummechanica (QFT) zelf maakt niet alle klassiek moeilijke problemen hanteerbaar. De bruikbaarheid ervan is specifiek voor probleemklassen waar kwantumcoherentie en interferentie, in combinatie met de kwantummechanica, het mogelijk maken om globale eigenschappen (zoals periode) efficiënt te extraheren.

## Voorbeeld: Ordervinden en periodiciteit

Beschouw het probleem van het vinden van een periode, dat ten grondslag ligt aan het algoritme van Shor:

Stel dat iemand een functie krijgt f: \mathbb{Z}_N \naar S dat is periodiek met periode r, dat wil zeggen, f(x) = f(x + r) alle xHet doel is om te bepalen r.

Klassiek gezien is het vinden r vereist O(\sqrt{N}) evaluaties van f In het ergste geval (voor algemene functies) omvat het proces:

1. Een uniforme superpositie voorbereiden \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\bereik.
2. Computeren f (x) in superpositie: \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\bereik|f(x)\bereik.
3. Het meten van het tweede register levert een waarde op y, waarbij het eerste register wordt verstrengeld met de subset van x with f(x) = y: \sum_{j} |x_0 + jr\rangle.
4. Toepassing van de kwantummechanica transformeert dit in een superpositie met scherpe pieken bij veelvouden van N/rHet meten van opbrengsten k zoals dat k/N benadert een rationaal getal met noemer r.
5. Klassieke nabewerking maakt het mogelijk om r.

Hierbij is de exponentiële efficiëntie van de kwantumfrequentie (QFT) van cruciaal belang: de transformatie van periodiciteit in het tijdsdomein naar pieken in het frequentiedomein wordt bereikt met een polynomiaal groot aantal kwantumpoorten, terwijl een klassieke zoektocht een exponentiële tijd in het aantal invoerbits zou vereisen.

## Benaderende kwantum-Fouriertransformatie

In praktische toepassingen, vooral naarmate het aantal qubits toeneemt, is het vaak voldoende om een ​​benaderende QFT te gebruiken. Door gecontroleerde fasepoorten met zeer kleine hoeken weg te laten, kan de QFT met aanzienlijk minder poorten worden geïmplementeerd met behoud van een hoge betrouwbaarheid. Dit is met name handig voor NISQ-apparaten (Noisy Intermediate-Scale Quantum), waar het verminderen van het aantal poorten helpt om de effecten van ruis en decoherentie te verminderen.

## Verdere implicaties

De impact van de kwantummechanica (QFT) reikt verder dan de reeds genoemde specifieke algoritmen. Ook in kwantumfaseschatting, een fundamentele subroutine voor algoritmen die problemen oplossen zoals eigenwaardeschatting voor Hamiltonianen, speelt de QFT een sleutelrol. Het algoritme gebruikt de QFT om fase-informatie te extraheren die gecodeerd is in de amplitudes van een kwantumtoestand, waardoor eigenwaarden exponentieel sneller geschat kunnen worden dan met klassieke tegenhangers voor bepaalde problemen.

Bovendien is de kwantummechanica (QFT) fundamenteel verbonden met de structuur van kwantuminformatieverwerking, wat ten grondslag ligt aan het vermogen van kwantumalgoritmen om globale eigenschappen en symmetrieën te benutten die ontoegankelijk zijn voor klassieke berekeningen. Dit is met name duidelijk zichtbaar in kwantumchemie en simulatiealgoritmen, waar de QFT wordt gebruikt om efficiënt te schakelen tussen positie- en impulsrepresentaties.

## Slotwoord

De kwantum-Fouriertransformatie is exponentieel efficiënter dan de klassieke snelle Fouriertransformatie wat betreft het aantal benodigde kwantumpoorten ten opzichte van de invoergrootte, uitgedrukt in qubits. Deze efficiëntie is echter van belang binnen de context van kwantumalgoritmen, waar de kwantum-Fourier-transformatie (QFT) de extractie van globale periodieke eigenschappen uit kwantumtoestanden mogelijk maakt met behulp van een aantal stappen dat polynoom is in het aantal qubits. Hoewel de kwantum-Fourier-transformatie niet de efficiënte berekening van alle uitvoeramplitudes als een klassieke lijst toestaat, is haar rol binnen kwantumalgoritmen het efficiënt manipuleren en onthullen van structuur in kwantuminformatie, wat leidt tot exponentiële of superpolynomiale kwantumversnellingen in problemen zoals factorisatie en identificatie van verborgen subgroepen.

Andere recente vragen en antwoorden over EITC/QI/QIF Quantum Informatie Fundamentals:

Bekijk meer vragen en antwoorden in EITC/QI/QIF Quantum Information Fundamentals

Meer vragen en antwoorden:

Tagged onder: , , , , ,