Algoritmy doby.Quantum Algorithms

Zesílení amplitudAmplitude Amplification

Zesílení amplitud je jedním z základních nástrojů pro výpočetní výkon.Amplitude Amplification is one of the fundamental tools of Quantum Computing. Je to základní nápad, který představuje hledání Grover, odhad amplitud a mnoho hlavních algoritmů strojového učení.It is the fundamental idea that underlies Grover's search, amplitude estimation and many quantum machine learning algorithms. Existuje mnoho variant a v Q # poskytujeme obecnou verzi na základě zesílení amplitud oblivious s částečnými odrazy, které umožňují nejširší oblast aplikace.There are many variants, and in Q# we provide a general version based on Oblivious Amplitude Amplification with Partial Reflections to allow for the widest area of application.

Centrální nápad na zesílení amplitud je rozšířit pravděpodobnost požadovaného výsledku, ke kterému dochází, provedením posloupnosti odrazů.The central idea behind amplitude amplification is to amplify the probability of a desired outcome occurring by performing a sequence of reflections. Tyto odrazy otočí počáteční stav blíže k požadovanému cílovému stavu, který se často označuje jako označený stav.These reflections rotate the initial state closer towards a desired target state, often called a marked state. Konkrétně platí, že pokud je pravděpodobnost měření počátečního stavu v označeném stavu, je $ \sin ^ 2 (\theta) $ poté, co se použije amplituda amplitud $m $ kolikrát se pravděpodobnost úspěchu stala $ \sin ^ 2 ((2 min + 1) \theta) $.Specifically, if the probability of measuring the initial state to be in a marked state is $\sin^2(\theta)$ then after applying amplitude amplification $m$ times the probability of success becomes $\sin^2((2m+1)\theta)$. To znamená, že pokud $ \theta = \ PI/[2 (2n + 1)] $ pro určitou hodnotu $n $ pak amplituda zesílení může zvýšit pravděpodobnost úspěchu až $100\% $ po $n $ iterace zesílení amplitudy.This means that if $\theta = \pi/[2(2n+1)]$ for some value of $n$ then amplitude amplification is capable of boosting the probability of success to $100\%$ after $n$ iterations of amplitude amplification. Vzhledem k tomu, že $ \theta = \sin ^{-1}(\sqrt{\Pr (úspěch)}) $) $ to znamená, že počet iterací potřebných k obdržení úspěchu je kvadratický, než očekávané číslo potřebné k vyhledání označeného stavu, který nedeterministické pomocí náhodného. kontrol.Since $\theta = \sin^{-1}(\sqrt{\Pr(success)})$ this means that the number of iterations needed to obtain a success deterministically is quadratically lower than the expected number needed to find a marked state non-deterministically using random sampling.

Každá iterace zesílení amplitudy vyžaduje, aby byly zadány dva operátory reflexe.Each iteration of Amplitude amplification requires that two reflection operators be specified. Konkrétně, pokud $Q $ je iterace zesílení a $P _0 $ je operátor projektoru na počáteční mezeru a $P _1 $ je projektor na označený dílčí prostor a pak $Q =-(\boldone-2P_0) (\boldone-2P_1) $.Specifically, if $Q$ is the amplitude amplification iterate and $P_0$ is a projector operator onto the initial subspace and $P_1$ is the projector onto the marked subspace then $Q=-(\boldone-2P_0)(\boldone -2P_1)$. Odvolání, že projektor je Hermitian operátor, který má eigenvalues $ + $1 a $0 $ a jako výsledek $ (\boldone-2P_0) $ je jednotná, protože obsahuje eigenvalues, které jsou kořeny Unity (v tomto případě $ \Pm $1).Recall that a projector is a Hermitian operator that has eigenvalues $+1$ and $0$ and as a result $(\boldone -2P_0)$ is unitary because it has eigenvalues that are roots of unity (in this case $\pm 1$). Jako příklad si představte, že se v případě hledání v Grover s počátečním stavem $H ^ {\otimes n} \ket{0}$ a označili State $ \ket{m} $, $P _0 = H ^ {\otimes n} \ket{0}\bra{0}H ^ {\otimes n} $ a $P _1 = \ket{m}\bra{m} $.As an example, consider the case of Grover's search with initial state $H^{\otimes n} \ket{0}$ and marked state $\ket{m}$, $P_0 = H^{\otimes n}\ket{0}\bra{0}H^{\otimes n}$ and $P_1= \ket{m}\bra{m}$. Ve většině aplikací amplitudy zesílení $P _0 $ bude projektor do počátečního stavu, což znamená, že $P _0 = \boldone-2 \ KET {\ psí} \ Bra {\ psí} $ pro nějaký vektor $ \ket{\psi} $; Nicméně pro oblivious amplituda amplication $P _0 $ obvykle se projektuje na mnoho stavových stavů (tj. násobnost $ + $1 eigenvalue $P _0 $ je větší než $1 $).In most applications of amplitude amplification $P_0$ will be a projector onto an initial state meaning that $P_0 = \boldone -2\ket{\psi}\bra{\psi}$ for some vector $\ket{\psi}$; however, for oblivious amplitude amplication $P_0$ will typically project onto many quantum states (i.e. the multiplicity of the $+1$ eigenvalue of $P_0$ is greater than $1$).

Logika za zesílením amplitudy následuje přímo z Eigen-dekompozice $Q $.The logic behind amplitude amplification follows directly from the eigen-decomposition of $Q$. Konkrétně eigenvectors $Q $, že počáteční stav má nenulovou podporu, se může zobrazit jako lineární $1 kombinace $P eigenvectors 0 $ a $P 1 $.Specifically, the eigenvectors of $Q$ that the initial state has non-zero support over can be shown to be linear combinations of the $+1$ eigenvectors of $P_0$ and $P_1$. Konkrétně počáteční stav pro zesílení amplitudy (za předpokladu, že je to $ + $1 eigenvector of $P 0 $), může být zapsaný jako $ $ \ket{\psi} = \frac{-i}{\sqrt{2}} \left (e ^ {i\theta} \ KET {\ psi +} + e ^ {-i\theta} \ KET {\ psi-} \ vpravo), $ $ WHERE $ \ket{\psi\pm } $ jsou eigenvectors z $Q $ with eigenvalues $e ^ {\Pm 2i \ théta} $ a podporují jenom eigenvectors $ + $1 $P 0 $ a $P 1 $.Specifically, the initial state for amplitude amplification (assuming it is a $+1$ eigenvector of $P_0$) can be written as $$ \ket{\psi}=\frac{-i}{\sqrt{2}}\left(e^{i\theta}\ket{\psi+} + e^{-i\theta}\ket{\psi-}\right), $$ where $\ket{\psi_\pm}$ are eigenvectors of $Q$ with eigenvalues $e^{\pm 2i\theta}$ and only have support on the $+1$ eigenvectors of $P_0$ and $P_1$. Fakt, že eigenvalues jsou $e ^ {\Pm i \theta} $ znamená, že operátor $Q $ provede otočení v dvojrozměrném prostoru určeném dvěma projektory a počátečním stavem, kde je úhel otočení $2 \ théta $.The fact that the eigenvalues are $e^{\pm i \theta}$ implies that the operator $Q$ performs a rotation in a two-dimensional subspace specified by the two projectors and the initial state where the rotation angle is $2\theta$. To je důvod, proč po $m $ iterace $Q $ pravděpodobnost úspěchu je $ \sin ^ 2 ([2 min + 1] \theta) $.This is why after $m$ iterations of $Q$ the success probability is $\sin^2([2m+1]\theta)$.

Další užitečnou vlastností, která se z nich nachází, je, že eigenvalue $ \theta $ přímo souvisí s pravděpodobností, že počáteční stav bude označený (v případě, že $P _0 $ je projektor pouze do počátečního stavu).Another useful property that comes out of this is that the eigenvalue $\theta$ is directly related to probability that the initial state would be marked (in the case where $P_0$ is a projector onto only the initial state). Vzhledem k tomu, že eigenphases $Q $ jsou $2 \ théta = 2 \ Sin ^{-1}(\sqrt{\Pr (úspěch)}) $, pak se vám postupuje podle toho, že pokud použijete odhad fáze na $Q $, můžeme zjistit pravděpodobnost úspěchu při použití v případě, že se jedná o postupné řízení.Since the eigenphases of $Q$ are $2\theta = 2\sin^{-1}(\sqrt{\Pr(success)})$ it then follows that if we apply phase estimation to $Q$ then we can learn the probability of success for a unitary quantum procedure. To je užitečné, protože pro zjištění pravděpodobnosti úspěšnosti, která by jinak vyžadovala, je nutné, aby bylo v případě, že vyžaduje kvadratickou, méně aplikací tohoto postupuThis is useful because it requires quadratically fewer applications of the quantum procedure to learn the success probability than would otherwise be needed.

Q # zavádí zesílení amplitud jako specializace zesílení amplitudy oblivious.Q# introduces amplitude amplification as a specialization of oblivious amplitude amplification. Zesílení amplitud oblivious umožňuje získat tento moniker, protože projektor na počáteční eigenspace nemusí být projektor do počátečního stavu.Oblivious amplitude amplification earns this moniker because the projector onto the initial eigenspace need not be a projector onto the initial state. V tomto smyslu je protokol oblivious do počátečního stavu.In this sense, the protocol is oblivious to the initial state. Klíčová aplikace zesílení amplitud oblivious je v některých lineárních kombinacích Hamiltonian metod simulace, přičemž je v tom, že počáteční stav není znám, ale je entangled s registrem ancilla v protokolu simulace.The key application of oblivious amplitude amplification is in certain linear combinations of unitary Hamiltonian simulation methods, wherein the initial state is unknown but becomes entangled with an ancilla register in the simulation protocol. Pokud by byl tento registr ancilla měřen jako pevná hodnota, řekněme $0 $, pak tyto metody simulace aplikují požadovanou jednotnou transformaci na zbývající qubits (označované jako systémový registr).If this ancilla register were to be measured to be a fixed value, say $0$, then such simulation methods apply the desired unitary transformation to the remaining qubits (called the system register). U všech ostatních výsledků měření se ale povede k selhání.All other measurement outcomes lead to failure however. Zesílení amplitud oblivious umožňuje zvýšit pravděpodobnost úspěchu tohoto měření na $100\% $ pomocí výše uvedeného důvodu.Oblivious amplitude amplification allows the probability of success of this measurement to be boosted to $100\%$ using the above reasoning. Navíc běžné zesílení amplitudy odpovídá případu, kde je systémový registr prázdný.Further, ordinary amplitude amplification corresponds to the case where the system register is empty. Důvodem je, proč Q # používá zesílení oblivious amplitud jako základní podprogram amplitudy zesílení.This is why Q# uses oblivious amplitude amplification as its fundamental amplitude amplification subroutine.

Obecná rutina (AmpAmpObliviousByReflectionPhases) má dva Registry, které voláme ancillaRegister a systemRegister.The general routine (AmpAmpObliviousByReflectionPhases) has two registers that we call ancillaRegister and systemRegister. Přijímá také dva Oracle pro nezbytné odrazy.It also accepts two oracles for the necessary reflections. ReflectionOracle funguje pouze v ancillaRegister, zatímco ObliviousOracle pracuje společně na obou registrech.The ReflectionOracle acts only on the ancillaRegister while the ObliviousOracle acts jointly on both registers. Vstup do ancillaRegister musí být inicializován na hodnotu-1 eigenstate prvního operátoru reflexe $ \boldone-2P_1 $.The input to ancillaRegister must be initialized to a -1 eigenstate of the first reflection operator $\boldone -2P_1$.

Obvykle Oracle připraví stav v výpočetních intervalech $ \ket{0...0} $.Typically, the oracle prepares the state in the computational basis $\ket{0...0}$. V naší implementaci ancillaRegister sestávají z jednoho qubit (flagQubit), který řídí stateOracle a zbytek požadovaného ancillas.In our implementation, the ancillaRegister consistes of one qubit (flagQubit) that controls the stateOracle and the rest of the desired ancillas. stateOracle se použije, pokud je flagQubit $ \ket{1}$.The stateOracle is applied when the flagQubit is $\ket{1}$.

Jeden může také poskytovat StateOracle Oracle a ObliviousOracle namísto odrazů prostřednictvím volání AmpAmpObliviousByOraclePhases.One may also provide oracles StateOracle and ObliviousOracle instead of reflections via a call to AmpAmpObliviousByOraclePhases.

Jak už bylo zmíněno, tradiční zesílení amplitud je pouze zvláštní případ těchto rutin, kde ObliviousOracle je operátorem identity a neexistuje qubits systému (tj. systemRegister je prázdná).As mentioned, traditional Amplitude Amplification is just a special case of these routines where ObliviousOracle is the identity operator and there are no system qubits (i.e., systemRegister is empty). Pokud chcete získat fáze pro částečné odrazy (například pro hledání Grover), je funkce AmpAmpPhasesStandard k dispozici.If you wish to obtain phases for partial reflections (e.g., for Grover search), the function AmpAmpPhasesStandard is available. Ukázkovou implementaci algoritmu Grover najdete v tématu DatabaseSearch.qs.Please refer to DatabaseSearch.qs for a sample implementation of Grover's algorithm.

Připravujeme fáze qubit rotace na fáze operátoru reflexe, jak je popsáno v dokumentu G.H. nízká, I. L. Čuangština.We relate the single-qubit rotation phases to the reflection operator phases as described in the paper by G.H. Low, I. L. Chuang. Použité fáze s pevným bodem jsou podrobně popsány v Yoder, low a Čuangština spolu s fázemi v dolních Yoder a Čuangština.The fixed point phases that are used are detailed in Yoder, Low and Chuang along with the phases in Low, Yoder and Chuang.

V případě pozadí můžete začít ze standardního zesílení amplitud , přejít na Úvod k oblivious amplitud a nakonec vytvořit generalize v dolních a Čuangština.For background, you could start from Standard Amplitude Amplification then move to an introduction to Oblivious Amplitude Amplification and finally generalizations presented in Low and Chuang. V rámci této Dominicyje k disHamiltonianá prezentace s dobrým přehledem této celé oblasti (stejně jako v souvislosti s simulací).A nice overview presentation of this entire area (as it relates to Hamiltonian Simulation) was given by Dominic Berry.

Fourierova transformaceQuantum Fourier Transform

Fourierova transformace je základní nástroj pro klasický rozbor a je stejně důležitá pro výpočetní prostředky.The Fourier transform is a fundamental tool of classical analysis and is just as important for quantum computations. Kromě toho efektivita aplikace Fourierova transformace (QFT) daleko přebírá, co je možné na klasickém počítači, takže při navrhování algoritmu pro plnění hodnot.In addition, the efficiency of the quantum Fourier transform (QFT) far surpasses what is possible on a classical machine making it one of the first tools of choice when designing a quantum algorithm.

Jako přibližné generalizace QFT poskytujeme operaci ApproximateQFT, která umožňuje další optimalizace vyřazením rotací, které nejsou bezpodmínečně nutné pro požadovanou přesnost algoritmu.As an approximate generalization of the QFT, we provide the ApproximateQFT operation that allows for further optimizations by pruning rotations that aren't strictly necessary for the desired algorithmic accuracy. Přibližná QFT vyžaduje operaci otočení dyadic $Z $-RFrac a operaci H.The approximate QFT requires the dyadic $Z$-rotation operation RFrac as well as the H operation. Předpokládá se, že vstup a výstup mají kódování ve formátu big endian (nejnižší bitů/qubit je vlevo, totéž jako KET Notation).The input and output are assumed to be encoded in big endian encoding (lowest bit/qubit is on the left, same as ket notation). Parametr aproximace $a $ určuje úroveň vyřazení $Z $-rotace, tj. $a \in [0.. n] $.The approximation parameter $a$ determines the pruning level of the $Z$-rotations, i.e., $a \in [0..n]$. V tomto případě všechny $Z $-rotace $2 \ pi/2 ^ k $, kde $k > a $, se odeberou z okruhu QFT.In this case all $Z$-rotations $2\pi/2^k$ where $k > a$ are removed from the QFT circuit. Je známo, že pro $k \ge \log_2 (n) + \log_2 (1/\epsilon) + $3.It is known that for $k \ge \log_2(n) + \log_2(1 / \epsilon) + 3$. jedna může být vázaná na $\| \operatorname{QFT}-\operatorname{AQFT} \| < \epsilon $.one can bound $\| \operatorname{QFT} - \operatorname{AQFT} \| < \epsilon$. Tady $\| \cdot\| $ je norma operátoru, která v tomto případě je druhá odmocnina největší eigenvalue z $ (\Operatorname{QFT}-\operatorname{AQFT}) (\Operatorname{QFT}-\operatorname{AQFT}) ^ \dagger $.Here $\|\cdot\|$ is the operator norm which in this case is the square root of the largest eigenvalue of $(\operatorname{QFT} - \operatorname{AQFT})(\operatorname{QFT} - \operatorname{AQFT})^\dagger$.

PrůměrArithmetic

Stejně jako aritmetická role hraje centrální roli v klasickém výpočetním prostředí, je také indispensible ve výpočetním prostředí.Just as arithmetic plays a central role in classical computing, it is also indispensible in quantum computing. Algoritmy jako algoritmus pro simulaci Shor, metody simulace a také mnoho algoritmů oracular spoléhají na souvislé aritmetické operace.Algorithms such as Shor's factoring algorithm, quantum simulation methods as well as many oracular algorithms rely upon coherent arithmetic operations. Nejvíc přístupů k aritmetickému sestavování po okruhech přidáváníMost approaches to arithmetic build upon quantum adder circuits. Nejjednodušší přizpůsobování přebírá klasický vstup $b $ a přidává hodnotu do stavového pole s celým číslem $ \ket{a} $.The simplest adder takes a classical input $b$ and adds the value to a quantum state holding an integer $\ket{a}$. Matematicky, přidávání (což znamená, že Poznámka $ \operatorname{Add} (b) $ pro klasický vstup $b $) má vlastnost, kteráMathematically, the adder (which we denote $\operatorname{Add}(b)$ for classical input $b$) has the property that

$ $ \operatorname{Add} (b) \ket{a} = \ket{a + b}.$$ \operatorname{Add}(b)\ket{a}=\ket{a + b}. $ $ Tento okruh základního přidaných je více než přidaným objektem pro přidání.$$ This basic adder circuit is more of an incrementer than an adder. Dá se převést na modul pro přidávání, který má dva vstupy za sebou přes $ $ \operatorname{Add}\ket{a}\ket{b} = \ket{a}\ket{a + b}, $ $ s použitím $n $ kontrolovaných aplikací ve tvaru \begin{align} \operatorname{Add} \ket{a} \ket{b} & = \Lambda_{a_0} \left (\operatorname{Add} (1) \right) \Lambda_{a_1} \left (\operatorname{Add} (2) \right) \Lambda_{a_2} \left (\operatorname{Add} (4) \right) \cdots \Lambda_{a_{n-1}} \left (\ operátor {Add} ({{n-1}}) \right) \ket{a}\ket{b} \\ & = \ket{a} \ket{b + a}, \end{align} pro $n $-bitová čísla $a $ a $b $ a další modulo $2 ^ n $.It can be converted into an adder that has two quantum inputs via $$ \operatorname{Add}\ket{a}\ket{b}=\ket{a}\ket{a+b}, $$ using $n$ controlled applications of adders of the form \begin{align} \operatorname{Add} \ket{a} \ket{b} & = \Lambda_{a_0} \left(\operatorname{Add}(1) \right) \Lambda_{a_1} \left(\operatorname{Add}(2) \right) \Lambda_{a_2} \left(\operatorname{Add}(4) \right) \cdots \Lambda_{a_{n-1}} \left(\operatorname{Add}({{n-1}}) \right) \ket{a}\ket{b} \\ & = \ket{a} \ket{b + a}, \end{align} for $n$-bit integers $a$ and $b$ and addition modulo $2^n$. Odvolat, že Notation $ \Lambda_x (A) $ odkazuje pro všechny operace $A $ na kontrolovanou verzi této operace s ovládacím prvkem qubit $x $.Recall that the notation $\Lambda_x(A)$ refers, for any operation $A$, to the controlled version of that operation with the qubit $x$ as control.

Podobně, Classic kontrolované násobení (modulární forma, která je základem pro faktor vytváření Shor), lze provádět pomocí podobné série řízených přídavků: \begin{align} \operatorname{Mult} (a) \ket{x}\ket{b} & = \Lambda_{x_0} \left (\operatorname{Add} (2 ^ 0 a) \right) \Lambda_{a_1} \left (\operatorname{Add} (2 ^ 1a) \right) \Lambda_{a_2} \left (\operatorname{Add} (2 ^ 2 a) \right) \cdots \Lambda_{x_{ n-1}} \left (\operatorname{Add} ({2 ^ {n-1}} a) \right) \ket{x}\ket{b} \\ & = \ket{x}\ket{b + AX}.Similarly, classically controlled multiplication (a modular form of which is essential for Shor's factoring algorithm) can be performed by using a similar series of controlled additions: \begin{align} \operatorname{Mult}(a)\ket{x}\ket{b} & = \Lambda_{x_0}\left(\operatorname{Add}(2^0 a)\right) \Lambda_{a_1}\left(\operatorname{Add}(2^1a)\right) \Lambda_{a_2}\left(\operatorname{Add}(2^2 a)\right) \cdots \Lambda_{x_{n-1}} \left(\operatorname{Add}({2^{n-1}}a) \right)\ket{x}\ket{b} \\ & = \ket{x}\ket{b+ax}. \end{align} je Subtlety s násobnou částí na počítačích, které si můžete všimnout od definice $ \operatorname{Mult} $ výše.\end{align} There is a subtlety with multiplication on quantum computers that you may notice from the definition of $\operatorname{Mult}$ above. Na rozdíl od přípravné verze tohoto okruhu ukládá produkt ze vstupů v doplňkovém registru, nikoli v vstupním registru.Unlike addition, the quantum version of this circuit stores the product of the inputs in an ancillary register rather than in the input register. V tomto příkladu se registr inicializuje s hodnotou $b $, ale obvykle se začne držet hodnota nula.In this example, the register is initialized with the value $b$, but typically it will start holding the value zero. To je potřeba v důsledku toho, že obecně není multiplikativní INVERT pro obecné $a $ a $x $.This is needed in because in general there is not a multiplicative inverse for general $a$ and $x$. Vzhledem k tomu, že všechny provozní operace, šetří měření, potřebujeme, abychom měli dostatek informací, aby bylo možné Invertovat násobení.Since all quantum operations, save measurement, are reversible we need to keep enough information around to invert the multiplication. Z tohoto důvodu je výsledek uložen v samostatném poli.For this reason the result is stored in a separate array. Tento způsob uložení výstupu nevratné operace, jako je násobení, se v samostatném registru označuje jako "Bennett štych" po Charlie Bennett a je základním nástrojem v vratném i nem výpočetním prostředí.This trick of saving the output of an irreversible operation, like multiplication, in a separate register is known as the "Bennett trick" after Charlie Bennett and is a fundamental tool in both reversible and quantum computing.

Mnoho okruhů za sebou bylo navrženo pro přidání a každý prozkoumat různé kompromisy na základě počtu qubits (místa) a počtu potřebných operací s bránou (čas).Many quantum circuits have been proposed for addition and each explores a different tradeoff in terms of the number of qubits (space) and the number of gate operations (time) required. Prověříme dva vysoce dostupné efektivní přidávání, které je známé jako Draper přidávání a přidávání Beauregard.We review two highly space efficient adders below known as the Draper adder and the Beauregard adder.

Přidávání DraperDraper Adder

Přidávání Draper je pravděpodobně jedním z nejpokročilejších přidaných kódů, protože přímo vyvolá vlastnosti pro každý z nich k provedení sčítání.The Draper adder is arguably one of the most elegant quantum adders, as it directly invokes quantum properties to perform addition. Vhledem k přidávání Draper je, že transformační transformaci lze použít k posunutí fází posunu do bitového posunu.The insight behind the Draper adder is that the Fourier transform can be used to translate phase shifts into a bit shift. Následně se postupuje pomocí Fourierova transformace, použití vhodných fází posunu a následnou transformací Fourierova transformace, kterou můžete použít k implementaci přidávání.It then follows that by applying a Fourier transform, applying appropriate phase shifts, and then undoing the Fourier transform you can implement an adder. Na rozdíl od mnoha dalších přidaných přidaných, Draper přidávání explicitně používá efekty s velkým množstvím, které byly zavedeny prostřednictvím Fourierova transformace.Unlike many other adders that have been proposed, the Draper adder explicitly uses quantum effects introduced through the quantum Fourier transform. Nemá přirozený klasický protějšek.It does not have a natural classical counterpart. Konkrétní kroky přidávání Draper jsou uvedené níže.The specific steps of the Draper adder are given below.

Předpokládejme, že máte dva $n $-bit qubit Registry ukládají celá čísla $a $ a $b $ then pro všechny $a $ $ $ \operatorname{QFT}\ket{a} = \frac{1}{\sqrt{2 ^ n}} \sum_{j = 0} ^ {2 ^ n-1} e ^ {i2\pi (AJ)/2 ^ n} \ket{j}.Assume that you have two $n$-bit qubit registers storing the integers $a$ and $b$ then for all $a$ $$ \operatorname{QFT}\ket{a}= \frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1} e^{i2\pi(aj)/2^n} \ket{j}. $ $ Pokud definujeme $ $ \ket{\phi_k (a)} = \frac{1}{\sqrt{2}} \left (\ket{0} + e ^ {i2\pi a/2 ^ k} \ket{1} \right), $ $ then po nějaké algebraický vidíte, že $ $ \operatorname{QFT}\ket{a} = \ket{\phi_1 (a)} \otimes \cdots \ otimes \ket{\phi_n (a)}.$$ If we define $$ \ket{\phi_k(a)} = \frac{1}{\sqrt{2}}\left(\ket{0} + e^{i2\pi a /2^k}\ket{1} \right), $$ then after some algebra you can see that $$ \operatorname{QFT}\ket{a}=\ket{\phi_1(a)}\otimes \cdots \otimes \ket{\phi_n(a)}. $ $ Cesta k provedení operace přidávání se pak po zjištění, že součet vstupních hodnot může zapsat jako $ $ \ket{a + b} = \operatorname{QFT} ^{-1}\ket{\phi_1 (a + b)} \otimes \cdots \otimes \ket{\phi_n (a + b)}.$$ The path towards performing an adder then becomes clear after observing that the sum of the inputs can be written as $$ \ket{a+b}=\operatorname{QFT}^{-1}\ket{\phi_1(a+b)}\otimes \cdots \otimes \ket{\phi_n(a+b)}. $ $ Celá čísla $b $ a $a $ je pak možné přidat při řízeném otočení fáze na každé qubits v rozloženém formátu pomocí ovládacích prvků $b $ as.$$ The integers $b$ and $a$ can then be added by performing controlled-phase rotation on each of the qubits in the decomposition using the bits of $b$ as controls.

Toto rozšíření může být dále zjednodušené. zaznamená si, že pro libovolné celé číslo $j $ a reálné číslo $x $, $e ^ {i2\pi (x + j)} = e ^ {i2\pi x} $.This expansion can be further simplified by noting that for any integer $j$ and real number $x$, $e^{i2\pi(x+j)}=e^{i2\pi x}$. Důvodem je to, že Pokud otočíte v kruhu $360 ^ {\circ} $ Degrees ($ 2 \ PI $ radiánů), budete mít přesně na začátku místo, kde jste začali.This is because if you rotate $360^{\circ}$ degrees ($2\pi$ radians) in a circle then you end up precisely where you started. Jedinou důležitou součástí $x $ for $e ^ {i2\pi x} $ je proto desetinná část $x $.The only important part of $x$ for $e^{i2\pi x}$ is therefore the fractional part of $x$. Konkrétně, pokud máme binární rozšíření formuláře $x = y +0. x_0x_2 \ ldots x_n $ then $e ^ {i2\pi x} = e ^ {i2\pi (0. x_0x_2 \ ldots x_{n-1})} $, a proto $ $ \ket{\ fí_k (a + b)} = \frac{1}{\sqrt{2}} \left (\ket{0} + e ^ {i2\pi [a/2 ^ k +0. b_k\ldots b_1]} \ket{1} \right). $ $ to znamená, že pokud provádíme sčítání, zvýšíme všechny tensor faktory v rozšíření Fourierova transformace $ \ket{a} $, přičemž počet otočení se zmenší, protože se $k $ zmenší.Specifically, if we have a binary expansion of the form $x=y+0.x_0x_2\ldots x_n$ then $e^{i2\pi x}=e^{i2\pi (0.x_0x_2\ldots x_{n-1})}$ and hence $$\ket{\phi_k(a+b)}=\frac{1}{\sqrt{2}}\left(\ket{0} + e^{i2\pi [a/2^k+0.b_k\ldots b_1]}\ket{1} \right).$$ This means that if we perform addition by incrementing each of the tensor factors in the expansion of the Fourier transform of $\ket{a}$ then the number of rotations shrinks as $k$ decreases. Tím se podstatně sníží počet bran, které jsou potřeba při přidávání.This substantially reduces the number of quantum gates needed in the adder. Poznamenejte si kroky Fourierova transformace, fáze sčítání a invertované funkce Fourierova transformace, které tvoří Draper jako $ \operatorname{QFT} ^{-1} \left (\phi\!\operatorname{ADD}\right) \operatorname{QFT} $.We denote the Fourier transform, phase addition and the inverse Fourier transform steps that comprise the Draper adder as $\operatorname{QFT}^{-1} \left(\phi\!\operatorname{ADD}\right) \operatorname{QFT}$. Okruh nároků, který používá toto zjednodušení k implementaci celého procesu, je možné zobrazit níže.A quantum circuit that uses this simplification to implement the entire process can be seen below.

Zobrazení Draper jako diagram obvodu

Každá řízená $eá brána ^ {I2 \ pi/k} $ v okruhu odkazuje na bránu řízených fází.Each controlled $e^{i2\pi/k}$ gate in the circuit refers to a controlled-phase gate. Taková omezení mají vlastnost, která se nachází na páru qubits, na které jednají, $ \ket{00}\mapsto \ket{00}$, ale $ \ket{11}\mapsto e ^ {I2 \ pi/k} \ KET{11}$.Such gates have the property that on the pair of qubits on which they act, $\ket{00}\mapsto \ket{00}$ but $\ket{11}\mapsto e^{i2\pi/k}\ket{11}$. Tento okruh vám umožní doplněním bez dalších qubits kromě těch, které jsou potřeba k uložení vstupů a výstupů.This circuit allows us to perform addition using no additional qubits apart from those needed to store the inputs and the outputs.

Přidávání BeauregardBeauregard Adder

Přidávání Beauregard je modulární přizpůsobování, které používá přidávání Draper, aby se daly přidat modulo $N $ pro libovolnou hodnotu kladné celé číslo $N $.The Beauregard adder is a quantum modular adder that uses the Draper adder in order to perform addition modulo $N$ for an arbitrary value positive integer $N$. Význam modulárních přidaných modulů, jako je například přidání Beauregard, je ve velkém rozsahu od jejich použití v modulárním umocněném kroku v rámci Shor algoritmu pro účely faktoringu.The significance of quantum modular adders, such as the Beauregard adder, stems to a large extent from their use in the modular exponentiation step within Shor's algorithm for factoring. Modulární přihlašování do modulárního příprocesoru má následující akci pro vstupy a výstupy na $a \ket{b} $, kde $a $ a $b $ jsou přislíbené jako celá čísla $N $, což znamená, že jsou v intervalu $ [0, \ldots, N-1] $.A quantum modular adder has the following action for quantum input $\ket{b}$ and classical input $a$ where $a$ and $b$ are promised to be integers mod $N$, meaning that they are in the interval $[0,\ldots, N-1]$.

$ $ \ket{b}\rightarrow \ket{b + a \Text{mod} N} = \begin{Cases} \ket{b + a}, & b + < N\\ \ket{b + a-N}, & (b + a) \ge N \end{Cases}.$$ \ket{b}\rightarrow \ket{b+a \text{ mod }N}=\begin{cases} \ket{b+a},& b+a < N\\ \ket{b+a-N},& (b+a)\ge N \end{cases}. $$

K přidání $a $ a $b $ ve fázi Beauregard přidáváte pomocí přidávání Draper, nebo speciálně !\phi\\operatorname{ADD} $.The Beauregard adder uses the Draper adder, or more specifically $\phi\!\operatorname{ADD}$, to add $a$ and $b$ in phase. Pak používá stejnou operaci k určení, zda $a + b < N $ pomocí odečítání $N $ a testování, pokud $a + b-N < 0 $.It then uses the same operation to identify whether $a+b <N$ by subtracting $N$ and testing if $a+b-N<0$. Okruh tyto informace uchovává v doplňkovém qubit a potom přidá $N $ back-Register, pokud $a + b < N $.The circuit stores this information in an ancillary qubit and then adds $N$ back the register if $a+b<N$. Pak ukončí nevýpočetní Tento doplňkový bit (Tento krok je nutný, aby bylo zajištěno, že ancilla lze po volání přidávání zrušit přidělení).It then concludes by uncomputing this ancillary bit (this step is needed to ensure that the ancilla can be de-allocated after calling the adder). Okruh pro přidání Beauregard je uveden níže.The circuit for the Beauregard adder is given below.

Zobrazení Beauregard jako diagram obvodu

Tady je brána $ \phi\!\operatorname{ADD} $ má stejný tvar jako $ \phi\!\operatorname{ADD} $ s tím rozdílem, že v tomto kontextu je vstup klasický, ale nejedná se o něj.Here the gate $\Phi\!\operatorname{ADD}$ takes the same form as $\phi\!\operatorname{ADD}$ except that in this context the input is classical rather than quantum. To umožňuje, aby řízené fáze v $ \phi\!\operatorname{ADD} $ nahradily fázemi, které se pak dají kompilovat do menšího počtu operací, aby se snížil počet qubits a počet bran potřebných pro daný modul.This allows the controlled phases in $\Phi\!\operatorname{ADD}$ to be replaced with phase gates that can then be compiled together into fewer operations to reduce both the number of qubits and number of gates needed for the adder.

Další podrobnosti najdete v tématu M. Roetteler, Th. Beth a D. Coppersmith.For more details, please refer to M. Roetteler, Th. Beth and D. Coppersmith.

Odhad fáze doby přístupnostiQuantum Phase Estimation

Jednou obzvláště důležitou aplikací pro Fourierova transformaci je naučit se eigenvaluesí jednotlivých operátorů, problém známý jako odhad fáze.One particularly important application of the quantum Fourier transform is to learn the eigenvalues of unitary operators, a problem known as phase estimation. Vezměte v úvahu jednotkové $U $ a State $ \ket{\phi} $, což znamená, že $ \ket{\phi} $ je eigenstate $U $ s neznámým eigenvalue $ \phi $, \begin{Equation} U\ket {\ fí} = \phi\ket{\phi}.Consider a unitary $U$ and a state $\ket{\phi}$ such that $\ket{\phi}$ is an eigenstate of $U$ with unknown eigenvalue $\phi$, \begin{equation} U\ket{\phi} = \phi\ket{\phi}. \end{Equation} Pokud máme přístup pouze k $U $ jako Oracle, můžeme se naučit fázi $ \phi $ pomocí toho, že $Z $ rotace aplikovaná na cíl kontrolované operace se rozšíří zpátky na ovládací prvek.\end{equation} If we only have access to $U$ as an oracle, then we can learn the phase $\phi$ by utilizing that $Z$ rotations applied to the target of a controlled operation propagate back onto the control.

Předpokládejme, že $V $ je řízená aplikace $U $, například \begin{align} V (\ket{0} \otimes \ket{\phi}) & = \ket{0} \otimes \ket{\phi} \\ \textrm{a} V (\ket{1} \otimes \ket{\phi}) & = e ^ {i \phi} \ket{1} \otimes \ket{\phi}.Suppose that $V$ is a controlled application of $U$, such that \begin{align} V (\ket{0} \otimes \ket{\phi}) & = \ket{0} \otimes \ket{\phi} \\ \textrm{ and } V (\ket{1} \otimes \ket{\phi}) & = e^{i \phi} \ket{1} \otimes \ket{\phi}. \end{Align} a potom lineární, \begin{align} V (\ket{+} \otimes \ket{\phi}) & = \frac{(\ket{0} \otimes \ket{\phi}) + e ^ {i \phi} (\ket{1} \otimes \ket{\phi})} {\sqrt{2}}.\end{align} Then, by linearity, \begin{align} V(\ket{+} \otimes \ket{\phi}) & = \frac{ (\ket{0} \otimes \ket{\phi}) + e^{i \phi} (\ket{1} \otimes \ket{\phi}) }{\sqrt{2}}. \end{align} můžeme shromažďovat výrazy, abychom zjistili, že \begin{align} V (\ket{+} \otimes \ket{\phi}) & = \frac{\ket{0} + e ^ {i \phi} \ket{1}} {\sqrt{2}} \otimes \ket{\phi} \\ & = (R_1 (\phi) \ket{+}) \otimes \ket{\phi} , \end{align}, kde $R _1 $ je jednotná operace R1.\end{align} We can collect terms to find that \begin{align} V(\ket{+} \otimes \ket{\phi}) & = \frac{\ket{0} + e^{i \phi} \ket{1}}{\sqrt{2}} \otimes \ket{\phi} \\ & = (R_1(\phi) \ket{+}) \otimes \ket{\phi}, \end{align} where $R_1$ is the unitary applied by the R1 operation. Nefunguje jinak, účinek použití $V $ je přesně stejný jako při použití $R _1 $ s neznámým úhlem, i když máme přístup pouze k $V $ jako Oracle.Put differently, the effect of applying $V$ is precisely the same as applying $R_1$ with an unknown angle, even though we only have access to $V$ as an oracle. Proto se pro zbytek této diskuze podíváme na fázi odhadu v souvislosti s $R _1 (\phi) $, kterou implementujeme pomocí Kickback fázes názvem.Thus, for the rest of this discussion we will discuss phase estimation in terms of $R_1(\phi)$, which we implement by using so-called phase kickback.

Vzhledem k tomu, že registr řízení a cíle zůstane untangled po tomto procesu, můžeme použít $ \ket{\phi} $ jako cíl kontrolované aplikace $U ^ $2 a připravit druhý qubit ovládacího prvku ve stavu $R 1 (2 \phi) \ket{+} $.Since the control and target register remain untangled after this process, we can reuse $\ket{\phi}$ as the target of a controlled application of $U^2$ to prepare a second control qubit in the state $R_1(2 \phi) \ket{+}$. V tomto případě můžeme získat registraci formuláře \begin{align} \ket{\psi} & = \sum{j = 0} ^ n R_1 (2 ^ j \phi) \ket{+} \\ & \propto \bigotimes_{j = 0} ^ {n} \left (\ket{0} + \exp (i 2 ^ {j} \phi) \ket{1}\right) @no__ t_4_ \ & \propto \sum_{k = 0} ^ {2 ^ n-1} \exp (i \phi k) \ket{k} \end{align}, kde $n $ je počet bitů, které potřebujeme, a kde jsme použili ${} \propto {}$ k indikaci, že jsme potlačili faktor normalizace $ 1/\sqrt{2 ^ n} $.Continuing in this way, we can obtain a register of the form \begin{align} \ket{\psi} & = \sum_{j = 0}^n R_1(2^j \phi) \ket{+} \\ & \propto \bigotimes_{j=0}^{n} \left(\ket{0} + \exp(i 2^{j} \phi) \ket{1}\right) \\ & \propto \sum_{k = 0}^{2^n - 1} \exp(i \phi k) \ket{k} \end{align} where $n$ is the number of bits of precision that we require, and where we have used ${} \propto {}$ to indicate that we have suppressed the normalization factor of $1 / \sqrt{2^n}$.

Pokud předpokládáme, že $ \phi = 2 \pi p/2 ^ k $ pro celé číslo $p $, rozpoznáme to jako $ \ket{\psi} = \operatorname{QFT} \ket{p_0 p_1 \dots p_n} $, kde $p _J $ je $j ^ {\textrm{th}} $ bit of $2 \pi \phi $.If we assume that $\phi = 2 \pi p / 2^k$ for an integer $p$, then we recognize this as $\ket{\psi} = \operatorname{QFT} \ket{p_0 p_1 \dots p_n}$, where $p_j$ is the $j^{\textrm{th}}$ bit of $2 \pi \phi$. Když použijete sousedící transformaci Fourierova transformace, získáme proto binární reprezentace fáze kódované jako stav pro stav.Applying the adjoint of the quantum Fourier transform, we therefore obtain the binary representation of the phase encoded as a quantum state.

V Q # to je implementováno operací QuantumPhaseEstimation, která přebírá DiscreteOracle implementující aplikaci $U ^ m $ jako funkci kladných celých čísel $m $.In Q#, this is implemented by the QuantumPhaseEstimation operation, which takes a DiscreteOracle implementing application of $U^m$ as a function of positive integers $m$.