Er kvante-Fourier-transformasjonen eksponentielt raskere enn en klassisk transformasjon, og er det derfor den kan gjøre vanskelige problemer løselige for en kvantedatamaskin?

/ / Publisert i Kvanteinformasjon, EITC/QI/QIF Quantum Information Fundamentals, Quantum Fourier Transform, Egenskaper ved Quantum Fourier Transform

Kvante-Fourier-transformasjonen (QFT) har en sentral rolle i kvanteinformasjonsteori og kvanteberegning. Design og implementering av den har betydelige implikasjoner for effektiviteten til kvantealgoritmer, spesielt i problemer der klassiske tilnærminger antas å være ineffektive. For å undersøke om QFT er eksponentielt raskere enn sin klassiske motpart, og om dette underbygger kvantefordelen ved å løse visse beregningsmessig vanskelige problemer, er det viktig å undersøke både den matematiske strukturen og beregningskompleksiteten til QFT og sammenligne disse med de mest kjente klassiske algoritmene.

## Den klassiske diskrete Fourier-transformasjonen (DFT)

Den klassiske diskrete Fourier-transformasjonen (DFT) er en matematisk operasjon som avbilder en vektor med komplekse tall til en annen vektor med samme dimensjon, som representerer frekvenskomponentene til den opprinnelige vektoren. DFT-en til en N-dimensjonal vektor x = (x_0, x_1, ..., x_{N-1}) er gitt av:

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

Den naive implementeringen av DFT krever O(N^2) tid fordi hvert utgangselement involverer en sum over alle N inngangselementer, og det finnes N utganger.

Den raske Fourier-transformasjonen (FFT), en klassisk algoritme, reduserer imidlertid denne kompleksiteten til O(N \log N) ved rekursivt å dele ned DFT-en i mindre DFT-er. FFT-en er en av de mest berømte algoritmene innen beregningsvitenskap, og ligger til grunn for applikasjoner fra signalbehandling til numerisk analyse.

## Kvante-Fourier-transformasjonen (QFT): Definisjon og kretskompleksitet

Kvante-Fourier-transformasjonen er kvanteanalogen til den klassiske DFT, som virker på kvantetilstander. n-qubit-system, hvor N = 2^n, QFT er den lineære operatoren definert av:

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

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

Implementeringen av QFT som en kvantekrets er spesielt effektiv. Den kan dekomponeres i en sekvens av Hadamard-porter og kontrollerte faseskiftporter. Kretsens dybde og størrelse er begge O (n ^ 2), dvs, O((\log N)^2), Hvor n er antallet qubits og N = 2^n er dimensjonen til Hilbert-rommet.

Detaljert kretsbeskrivelse

For en n-qubit-registeret, QFT-kretsen består vanligvis av:

1. En Hadamard-port på den viktigste qubitten.
2. Kontrollerte faseskift mellom den mest signifikante qubitten og hver mindre signifikante qubit, med fase e^{2\pi i/2^k} for kkontrollen.
3. Rekursjon på de gjenværende n-1 qubits.
4. En endelig reversering av rekkefølgen på qubittene (swap-porter).

Det totale antallet porter for en eksakt QFT er O (n ^ 2)Men hvis en liten feil er tolererbar (noe som ofte er tilstrekkelig for kvantealgoritmer), er det mulig å tilnærme QFT med nøyaktighet. \epsilon kun ved hjelp O(n ≤ log n + ≤ log n ≤ log(1/epsilon)) porter, noe som reduserer ressursbehovet ytterligere.

Sammenligning av beregningskompleksitet

- Klassisk FFT: O(N \log N) = O(2^nn)
- Kvante QFT: O (n ^ 2) porter

Ved å oversette disse kompleksitetene til de samme enhetene, opererer QFT i O(\log^2 N) kvanteporter, mens FFT krever O(N \log N) klassiske operasjoner. Dette er en eksponentiell forbedring i antall grunnleggende operasjoner som kreves, i hvert fall i forhold til inngangsstørrelsen målt i biter (n = ∫log N).

## Er QFT alene eksponentielt raskere?

Selv om QFT kan implementeres eksponentielt raskere enn den klassiske FFT når man måler ressurser etter antall grunnleggende kvanteporter kontra klassiske operasjoner, er det viktig å analysere hva dette betyr for praktisk beregning. Den eksponensielle hastighetsøkningen refererer til den interne kretskompleksiteten: QFT kartlegger en hel superposisjon av N amplituder ved bruk av kun O (n ^ 2) porter. Kvantemåling kollapser imidlertid kvantetilstanden til ett enkelt utfall, noe som begrenser den direkte utvinningen av alle utgangsamplituder.

Hvis man er interessert i å beregne alt N utgangsamplitudene til en QFT, ville ikke dette vært raskere på en kvantedatamaskin fordi bare ett enkelt måleresultat kan observeres per kjøring, og rekonstruksjon av hele spekteret ville kreve eksponentielt mange repetisjoner. Derfor ligger ikke den eksponensielle hastighetsøkningen i beregningen av *alle* utgangsverdier, men i transformasjonen av kvanteinformasjon innenfor en kvantealgoritme.

## Rollen til QFT i kvantealgoritmer

QFT er en nøkkelsubrutine i flere kvantealgoritmer som gir eksponensielle eller superpolynomiske hastighetsøkninger i forhold til de mest kjente klassiske algoritmene. Det mest fremtredende eksemplet er Shors algoritme for heltallsfaktorisering.

Shors algoritme

Shors algoritme bruker QFT til å finne perioden til en funksjon (periodefunn), som deretter brukes til å faktorisere store heltall. Algoritmen går frem som følger:

1. Forbered en jevn superposisjon over N stater.
2. Beregn en funksjon f(x) = a^x \mod N i superposisjon.
3. Mål det andre registeret, og kollaps tilstanden til en superposisjon av innganger som alle tilordnes den målte utgangen.
4. Bruk QFT-en på det første registeret, som transformerer den periodiske strukturen til en superposisjon der måling gir informasjon om perioden.
5. Bruk det målte resultatet og klassisk etterbehandling (kontinuerlige brøker) for å gjenopprette perioden og faktorisere heltallet.

QFT-en er eksponentielt raskere enn den klassiske FFT-en når det gjelder antall grunnleggende operasjoner for transformasjonen. Denne effektiviteten er *viktig* for polynomtidsytelsen til Shors algoritme.

Skjulte undergruppeproblemer

Kvante-Fourier-transformasjonen er også sentral i klassen av skjulte undergruppeproblemer (HSP), der målet er å bestemme en skjult undergruppe. H av en gruppe G gitt en funksjon som er konstant på sidemengdene til H og distinkte på forskjellige sidemengder. Mange problemer av betydelig interesse, som diskrete logaritmer og visse grafisomorfiproblemer, kan formuleres i denne formen. QFT muliggjør utvinning av undergruppestruktur fra kvantetilstander, noe som gir effektive løsninger der klassiske algoritmer er umulige.

## Begrensninger og misoppfatninger

Det er viktig å gjenkjenne finessene i påstanden om at QFT er eksponentielt raskere enn klassisk FFT:

- Effektiv transformasjon, ikke effektiv prøvetaking: QFT-en transformerer kvantetilstanden effektivt, men en kvantedatamaskin kan ikke sende ut hele den transformerte tilstanden. Måling gir et utvalg fra sannsynlighetsfordelingen definert av de kvadrerte amplitudene. For mange applikasjoner er dette tilstrekkelig, ettersom kvantealgoritmen er designet for å gjøre sannsynligheten for å måle et nyttig svar høy.
- Klassisk utgangsrekonstruksjon: Hvis målet er å beregne og sende ut alt N I klassiske Fourier-koeffisienter hjelper ikke QFT; bare et kvanteutvalg kan oppnås per kjøring. Som sådan er QFTs eksponensielle effektivitet nyttig innenfor kvantealgoritmer, ikke for direkte klassisk beregning av alle transformasjonsverdier.
- Ikke alle problemer: Selve QFT-en gjør ikke alle klassisk vanskelige problemer håndterbare. Nytten er spesifikk for problemklasser der kvantekoherens og interferens, i forbindelse med QFT-en, muliggjør effektiv utvinning av globale egenskaper (som periode).

## Eksempel: Ordensøkning og periodisitet

Tenk på problemet med periodefunn, som ligger til grunn for Shors algoritme:

Anta at man får en funksjon f: \mathbb{Z}_N \to S som er periodisk med periode r, dvs, f(x) = f(x + r) for alle xMålet er å bestemme r.

Klassisk sett, å finne r Krever O(\sqrt{N}) evalueringer av f i verste fall (for generelle funksjoner). Kvantemessig involverer prosessen:

1. Forberedelse av en jevn superposisjon \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle.
2. Databehandling f (x) i superposisjon: \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle|f(x)\rangle.
3. Måling av det andre registeret gir en verdi y, og viklet det første registeret inn i delmengden av x med f(x) = y: \sum_{j} |x_0 + jr\rangle.
4. Ved å bruke QFT-en transformeres dette til en superposisjon med en skarp topp ved multipler av N/rMåling av avkastning k slik at k/N tilnærmer et rasjonelt tall med nevner r.
5. Klassisk etterbehandling muliggjør gjenoppretting av r.

Her er den eksponensielle effektiviteten til QFT-en kritisk: transformasjonen fra periodisitet i tidsdomenet til topper i frekvensdomenet oppnås med polynomisk mange kvanteporter, mens et klassisk søk ​​ville kreve eksponensiell tid i antall inngangsbiter.

## Omtrentlig kvante-Fourier-transformasjon

I praktiske anvendelser, spesielt ettersom antallet qubits øker, er det ofte tilstrekkelig å bruke en omtrentlig QFT. Ved å utelate kontrollerte faseporter med svært små vinkler, kan QFT implementeres med betydelig færre porter samtidig som høy gjengivelse opprettholdes. Dette er spesielt nyttig for NISQ-enheter (Noisy Intermediate-Scale Quantum), der reduksjon av portantall bidrar til å redusere effektene av støy og dekoherens.

## Ytterligere implikasjoner

Virkningen av QFT strekker seg utover de spesifikke algoritmene som allerede er nevnt. I kvantefaseestimering, en grunnleggende subrutine for algoritmer som løser problemer som egenverdiestimering for Hamiltonianere, er QFT igjen et nøkkelelement. Algoritmen bruker QFT til å trekke ut faseinformasjon kodet i amplitudene til en kvantetilstand, noe som muliggjør estimering av egenverdier eksponentielt raskere enn klassiske motparter kan oppnå for visse problemer.

I tillegg er QFT fundamentalt knyttet til strukturen i kvanteinformasjonsbehandling, som ligger til grunn for kvantealgoritmers evne til å utnytte globale egenskaper og symmetrier som er utilgjengelige for klassisk beregning. Dette er spesielt tydelig i kvantekjemi og simuleringsalgoritmer, der QFT brukes til å effektivt veksle mellom posisjons- og momentumrepresentasjoner.

## Avsluttende bemerkninger

Kvante-Fourier-transformasjonen er eksponentielt mer effektiv enn den klassiske raske Fourier-transformasjonen når det gjelder antall kvanteporter som kreves i forhold til inngangsstørrelsen uttrykt i qubits. Denne effektiviteten er imidlertid meningsfull i konteksten av kvantealgoritmer, der QFT muliggjør utvinning av globale periodiske egenskaper fra kvantetilstander ved hjelp av et antall trinnpolynomer i antall qubits. Selv om QFT ikke tillater effektiv beregning av alle utgangsamplituder som en klassisk liste, er dens rolle innen kvantealgoritmer å effektivt manipulere og avsløre struktur i kvanteinformasjon, noe som fører til eksponentielle eller superpolynomiske kvantehastighetsøkninger i problemer som faktorisering og identifisering av skjulte undergrupper.

Andre nyere spørsmål og svar vedr EITC/QI/QIF Quantum Information Fundamentals:

Se flere spørsmål og svar i EITC/QI/QIF Quantum Information Fundamentals

Flere spørsmål og svar:

Merket under: , , , , ,