Quantum Fourier transform (original) (raw)
Die Quanten-Fouriertransformation ist ein Algorithmus aus dem Gebiet der Quanteninformatik. Sie ist eine Zerlegung der diskreten Fouriertransformation in ein Produkt unitärer Matrizen. Dadurch kann sie als Quantenschaltkreis aus Hadamard-Gattern und implementiert werden. Die Quanten-Fouriertransformation ist ein wesentlicher Bestandteil eines der prominentesten Quantenalgorithmen, des Shor-Algorithmus.
| Property | Value |
|---|---|
| dbo:abstract | Die Quanten-Fouriertransformation ist ein Algorithmus aus dem Gebiet der Quanteninformatik. Sie ist eine Zerlegung der diskreten Fouriertransformation in ein Produkt unitärer Matrizen. Dadurch kann sie als Quantenschaltkreis aus Hadamard-Gattern und implementiert werden. Die Quanten-Fouriertransformation ist ein wesentlicher Bestandteil eines der prominentesten Quantenalgorithmen, des Shor-Algorithmus. (de) En computación cuántica, la transformada cuántica de Fourier es una transformación sobre bits cuánticos, y es la analogía cuántica de la transformada de Fourier discreta. La transformada de Fourier es una parte de muchos algoritmos cuánticos, el algoritmo de factorización de Shor y el cálculo del logaritmo discreto, el algoritmo de estimación de fase para estimar los eigenvalores de un operador unitario, y logaritmos para HSP (hidden subgroup problem). La transformada de Fourier puede ser realizada eficientemente en un ordenador cuántico, con una particular descomposición en un producto de matrices unitarias simples. Usando una descomposición simple, la trasformación discreta de Fourier puede ser implementada como un circuito cuántico que tiene solo puertas Hadamard y puertas de desplazamiento de fase controladas, donde es el número de qubits. Esto puede ser comparado con la transformada de Fourier discreta, que utiliza puertas (donde es el número de bits), lo cual es exponencialmente mayor que . Sin embargo, la transformada cuántica de Fourier actúa sobre un estado cuántico, mientras que la trasformada de Fourier clásica actúa sobre un vector, así que no todas las tareas que usan la transformada de Fourier clásica pueden utilizar la ventaja de esta aceleración exponencial. Los mejores algoritmos cuánticos de transformada de Fourier conocidos actualmente requieren solo puertas para alcanzar una aproximación eficiente. (es) In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform was discovered by Don Coppersmith. The quantum Fourier transform can be performed efficiently on a quantum computer with a decomposition into the product of simpler unitary matrices. The discrete Fourier transform on amplitudes can be implemented as a quantum circuit consisting of only Hadamard gates and controlled phase shift gates, where is the number of qubits. This can be compared with the classical discrete Fourier transform, which takes gates (where is the number of bits), which is exponentially more than . The quantum Fourier transform acts on a quantum state vector (a quantum register), and the classical Fourier transform acts on a vector. Both types of vectors can be written as lists of complex numbers. In the quantum case it is a sequence of probability amplitudes for all the possible outcomes upon measurement (called basis states, or eigenstates). Because measurement collapses the quantum state to a single basis state, not every task that uses the classical Fourier transform can take advantage of the quantum Fourier transform's exponential speedup. The best quantum Fourier transform algorithms known (as of late 2000) require only gates to achieve an efficient approximation. (en) En informatique quantique, la transformée de Fourier quantique (TFQ) est une transformation linéaire sur des bits quantiques, et est l'analogie quantique de la transformée de Fourier discrète . La transformée de Fourier quantique est l'un des nombreux algorithmes quantiques, qui incluent notamment l'algorithme de Shor qui permet de factoriser et de calculer le logarithme discret, l' algorithme d'estimation de phase quantique qui estime les valeurs propres d'un opérateur unitaire et les algorithmes traitant du problème de sous-groupe caché . La transformée de Fourier quantique a été découverte par Don Coppersmith . La transformée de Fourier quantique peut être calculée efficacement à l'aide d'un ordinateur quantique,en utilisant une décomposition en un produit de matrices unitaires plus simples. A l'aide de cette décomposition, la transformée de Fourier discrète sur amplitudes peut être mises en œuvre sous la forme d'un circuit quantique avec un nombre de Portes d' Hadamard et de portes à déphasage commandé évoluant en , où est le nombre de qubits (le nombre de porte évolue selon une fonction en n^2). En comparaison, la transformée de Fourier discrète classique requiert un nombre de porte évoluant en , soit exponentiellement supérieur à . La transformée de Fourier quantique agit sur un vecteur d'état quantique, tandis que la transformée de Fourier classique agit sur un vecteur(classique). Dans les deux cas ces vecteurs peuvent être écrits sous la forme de listes de nombres complexes. En ce qui concerne le cas quantique, ces nombres complexes représentent les amplitudes de probabilité des différents résultats obtenables par la mesure . Étant donné que la mesure réduit l'état quantique à une seule valeur (appelée état de base ou état propre ), il n'est pas possible de profiter de l'accélération exponentielle apportée par la transformée de Fourier quantique pour chacune des tâches impliquant la transformée de Fourrier classique(la mesure d'un état quantique étant irréversible, on ne peut utiliser la transformée quantique comme raccourci que si cela n'implique qu'une seule mesure) Les meilleurs algorithmes de transformée de Fourier quantique connus à ce jour (à la fin des années 2000) ne nécessitent qu'un nombre en de portes pour obtenir une approximation efficace. (fr) In computazione quantistica, la trasformata di Fourier quantistica (abbreviazione dall'inglese: QFT) è una trasformazione lineare su qubit, ed è l'analogo quantistico della trasformata discreta di Fourier inversa. La trasformata di Fourier quantistica fa parte di molti algoritmi quantistici, in particolare l'algoritmo di fattorizzazione di Shor per fattorizzare e calcolare il logaritmo discreto, l'algoritmo quantistico di stima della fase per stimare gli autovalori di un operatore unitario, e algoritimi per il problema del sottogruppo nascosto. La trasformata di Fourier quantistica fu inventata da Don Coppersmith. La trasformata di Fourier quantistica può essere effettuata efficientemente su un computer quantistico, con una particolare scomposizione in un prodotto di matrici unitarie più semplici. Usando una semplice scomposizione, la trasformata di Fourier discreta su ampiezze può essere implementato come un che consiste solo di porte di Hadamard e porte di phase shift controllate, dove è il numero dei qubit. Ciò può essere paragonato alla trasformata di Fourier discreta classica, che ha porte (dove è il numero dei bit), che è esponenzialmente più di . I migliori algoritmi noti per la trasformata di Fourier quantistica (agli ultimi anni 2000) necessitano solo di porte per ottenere una buona approssimazione. (it) Na computação quântica, a transformada de Fourier quântica (abreviadamente: QFT) é uma transformação linear em bits quânticos e é o análogo quântico da transformada discreta inversa de Fourier . A transformada de Fourier quântica é uma parte de muitos algoritmos quânticos, notavelmente o algoritmo de Shor para fatorar e calcular o logaritmo discreto, o algoritmo de estimativa de fase quântica para estimar os valores próprios de um operador unitário e algoritmos para o problema do subgrupo oculto . A transformada quântica de Fourier foi inventada por Don Coppersmith . A transformada quântica de Fourier pode ser realizada de forma eficiente em um computador quântico, com uma decomposição particular em um produto de matrizes unitárias mais simples. Usando uma decomposição simples, a transformada discreta de Fourier em amplitudes podem ser implementadas como um circuito quântico consistindo apenas em Portões Hadamard e portões de mudança de fase controlada, onde é o número de qubits. Isso pode ser comparado com a transformada discreta de Fourier clássica, que leva portões (onde é o número de bits), que é exponencialmente maior que . No entanto, a transformada de Fourier quântica atua em um estado quântico, enquanto a transformada de Fourier clássica atua em um vetor, portanto, nem toda tarefa que usa a transformada de Fourier clássica pode tirar vantagem dessa aceleração exponencial. Os melhores algoritmos de transformada quântica de Fourier conhecidos (no final de 2000) exigem apenas portas para conseguir uma aproximação eficiente. (pt) Kwantowa transformata Fouriera (ang. quantum Fourier transform, QFT) – kwantowa analogia dyskretnej transformaty Fouriera. Na dowolny -kubitowy stan bazowy działa ona jak następuje: gdzie Należy zwrócić uwagę, że wielkość jest „zespolonym pierwiastkiem -tego rzędu” z liczby 1 (zob. wzór de Moivre’a). Spostrzeżenie to pomaga wyobrazić sobie, jak działa QFT, obrazując ją sobie w układzie współrzędnych przestrzeni zespolonej. (pl) Квантовое преобразование Фурье (сокр. КПФ) — линейное преобразование квантовых битов (кубитов), являющееся квантовым аналогом дискретного преобразования Фурье (ДПФ). КПФ входит во множество квантовых алгоритмов, в особенности в алгоритм Шора разложения числа на множители и вычисления дискретного логарифма, в квантовый алгоритм оценки фазы для нахождения собственных чисел унитарного оператора и алгоритмы для нахождения скрытой подгруппы. Квантовое преобразование Фурье эффективно исполняется на квантовых компьютерах путём специального разложения матрицы в произведение более простых унитарных матриц. С помощью такого разложения, дискретное преобразование Фурье на входных амплитудах может быть осуществлено квантовой сетью, состоящей из вентилей Адамара и контролируемых квантовых вентилей, где — число кубитов. По сравнению с классическим ДПФ, использующим элементов памяти ( — количество бит), что экспоненциально больше, чем квантовых вентилей КПФ. Наилучшие из известных алгоритмов квантового преобразования Фурье (по состоянию на конец 2000) задействуют только вентилей для достижения желаемого приближения результата. (ru) 量子傅立葉變換（quantum Fourier transform）是一種離散傅立葉變換，將原式分解成更為簡單的多個么正矩陣的積。利用這般的分解方式，離散傅立葉變換可以用作量子電路，其包含了多個哈達瑪閘與受控移相閘。 量子傅立葉變換在量子演算法中有多處應用，以其可提供相位估算步驟的理論基礎，在一些演算法中佔核心地位，例如用在做質因數分解的秀爾演算法（Shor's algorithm）、以及（hidden subgroup problem）。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Q_fourier_nqubits.png?width=300 |
| dbo:wikiPageExternalLink | http://algassert.com/quirk%23circuit=%7B%22cols%22%3A%5B%5B%22Counting8%22%5D%2C%5B%22Chance8%22%5D%2C%5B%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%5D%2C%5B%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C%22Swap%22%2C%22Swap%22%5D%2C%5B%22H%22%5D%2C%5B%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C%22H%22%5D%2C%5B%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%86%E2%82%84%22%2C%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%81%E2%82%82%E2%82%88%22%2C%22Z%5E%E2%85%9F%E2%82%86%E2%82%84%22%2C%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%5D%5D%7D http://demonstrations.wolfram.com/QuantumFourierTransformCircuit/ http://demonstrations.wolfram.com/QuantumCircuitImplementingGroversSearchAlgorithm/ |
| dbo:wikiPageID | 30872292 (xsd:integer) |
| dbo:wikiPageLength | 15266 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123746557 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probability_amplitude dbr:Quantum_algorithms dbr:Quantum_logic_gate dbr:Quantum_state dbr:Qubit dbr:Root_of_unity dbr:Boolean_group dbc:Fourier_analysis dbr:John_Preskill dbr:Unitary_operator dbr:Vector_(mathematics_and_physics) dbr:Quantum_computing dbr:Matrix_multiplication dbr:Measurement_in_quantum_mechanics dbr:Norm_(mathematics) dbr:Eigenvalue dbr:Shor's_algorithm dbc:Quantum_algorithms dbr:Hadamard_transform dbr:Discrete_logarithm dbr:Fourier_transform_on_finite_groups dbr:Quantum_gate dbr:Quantum_register dbr:Hadamard_gate dbr:Hermitian_adjoint dbr:Tensor_product dbc:Transforms dbr:K._R._Parthasarathy_(probabilist) dbr:Binary_number dbr:Hidden_subgroup_problem dbr:Eigenstate dbr:Unitary_transformation dbr:Discrete_Fourier_transform dbr:Don_Coppersmith dbr:Unitary_matrix dbr:Quantum_circuit dbr:Linear_transformation dbr:Quantum_phase_estimation_algorithm dbr:Phase_shift_gate dbr:Wave-function_collapse dbr:File:Q_fourier_3qubits.png dbr:File:Q_fourier_nqubits.png |
| dbp:wikiPageUsesTemplate | dbt:See_also dbt:Short_description dbt:Use_American_English dbt:Quantum_computing |
| dct:subject | dbc:Fourier_analysis dbc:Quantum_algorithms dbc:Transforms |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatQuantumAlgorithms |
| rdfs:comment | Die Quanten-Fouriertransformation ist ein Algorithmus aus dem Gebiet der Quanteninformatik. Sie ist eine Zerlegung der diskreten Fouriertransformation in ein Produkt unitärer Matrizen. Dadurch kann sie als Quantenschaltkreis aus Hadamard-Gattern und implementiert werden. Die Quanten-Fouriertransformation ist ein wesentlicher Bestandteil eines der prominentesten Quantenalgorithmen, des Shor-Algorithmus. (de) Kwantowa transformata Fouriera (ang. quantum Fourier transform, QFT) – kwantowa analogia dyskretnej transformaty Fouriera. Na dowolny -kubitowy stan bazowy działa ona jak następuje: gdzie Należy zwrócić uwagę, że wielkość jest „zespolonym pierwiastkiem -tego rzędu” z liczby 1 (zob. wzór de Moivre’a). Spostrzeżenie to pomaga wyobrazić sobie, jak działa QFT, obrazując ją sobie w układzie współrzędnych przestrzeni zespolonej. (pl) 量子傅立葉變換（quantum Fourier transform）是一種離散傅立葉變換，將原式分解成更為簡單的多個么正矩陣的積。利用這般的分解方式，離散傅立葉變換可以用作量子電路，其包含了多個哈達瑪閘與受控移相閘。 量子傅立葉變換在量子演算法中有多處應用，以其可提供相位估算步驟的理論基礎，在一些演算法中佔核心地位，例如用在做質因數分解的秀爾演算法（Shor's algorithm）、以及（hidden subgroup problem）。 (zh) En computación cuántica, la transformada cuántica de Fourier es una transformación sobre bits cuánticos, y es la analogía cuántica de la transformada de Fourier discreta. La transformada de Fourier es una parte de muchos algoritmos cuánticos, el algoritmo de factorización de Shor y el cálculo del logaritmo discreto, el algoritmo de estimación de fase para estimar los eigenvalores de un operador unitario, y logaritmos para HSP (hidden subgroup problem). (es) En informatique quantique, la transformée de Fourier quantique (TFQ) est une transformation linéaire sur des bits quantiques, et est l'analogie quantique de la transformée de Fourier discrète . La transformée de Fourier quantique est l'un des nombreux algorithmes quantiques, qui incluent notamment l'algorithme de Shor qui permet de factoriser et de calculer le logarithme discret, l' algorithme d'estimation de phase quantique qui estime les valeurs propres d'un opérateur unitaire et les algorithmes traitant du problème de sous-groupe caché . La transformée de Fourier quantique a été découverte par Don Coppersmith . (fr) In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform was discovered by Don Coppersmith. (en) In computazione quantistica, la trasformata di Fourier quantistica (abbreviazione dall'inglese: QFT) è una trasformazione lineare su qubit, ed è l'analogo quantistico della trasformata discreta di Fourier inversa. La trasformata di Fourier quantistica fa parte di molti algoritmi quantistici, in particolare l'algoritmo di fattorizzazione di Shor per fattorizzare e calcolare il logaritmo discreto, l'algoritmo quantistico di stima della fase per stimare gli autovalori di un operatore unitario, e algoritimi per il problema del sottogruppo nascosto. La trasformata di Fourier quantistica fu inventata da Don Coppersmith. (it) Na computação quântica, a transformada de Fourier quântica (abreviadamente: QFT) é uma transformação linear em bits quânticos e é o análogo quântico da transformada discreta inversa de Fourier . A transformada de Fourier quântica é uma parte de muitos algoritmos quânticos, notavelmente o algoritmo de Shor para fatorar e calcular o logaritmo discreto, o algoritmo de estimativa de fase quântica para estimar os valores próprios de um operador unitário e algoritmos para o problema do subgrupo oculto . A transformada quântica de Fourier foi inventada por Don Coppersmith . (pt) Квантовое преобразование Фурье (сокр. КПФ) — линейное преобразование квантовых битов (кубитов), являющееся квантовым аналогом дискретного преобразования Фурье (ДПФ). КПФ входит во множество квантовых алгоритмов, в особенности в алгоритм Шора разложения числа на множители и вычисления дискретного логарифма, в квантовый алгоритм оценки фазы для нахождения собственных чисел унитарного оператора и алгоритмы для нахождения скрытой подгруппы. (ru) |
| rdfs:label | Transformada quàntica de Fourier (ca) Quanten-Fouriertransformation (de) Transformada cuántica de Fourier (es) Transformée de Fourier quantique (fr) Trasformata di Fourier quantistica (it) Quantum Fourier transform (en) Kwantowa transformata Fouriera (pl) Transformada Quântica de Fourier (pt) Квантовое преобразование Фурье (ru) 量子傅立葉變換 (zh) |
| rdfs:seeAlso | dbr:Generalizations_of_Pauli_matrices dbr:Hadamard_transform dbr:Shift_matrices |
| owl:sameAs | freebase:Quantum Fourier transform yago-res:Quantum Fourier transform wikidata:Quantum Fourier transform dbpedia-ca:Quantum Fourier transform dbpedia-de:Quantum Fourier transform dbpedia-es:Quantum Fourier transform dbpedia-fa:Quantum Fourier transform dbpedia-fi:Quantum Fourier transform dbpedia-fr:Quantum Fourier transform dbpedia-he:Quantum Fourier transform dbpedia-it:Quantum Fourier transform dbpedia-pl:Quantum Fourier transform dbpedia-pt:Quantum Fourier transform dbpedia-ru:Quantum Fourier transform dbpedia-vi:Quantum Fourier transform dbpedia-zh:Quantum Fourier transform https://global.dbpedia.org/id/Tu5P |
| prov:wasDerivedFrom | wikipedia-en:Quantum_Fourier_transform?oldid=1123746557&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Q_fourier_3qubits.png wiki-commons:Special:FilePath/Q_fourier_nqubits.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Quantum_Fourier_transform |
| is dbo:wikiPageDisambiguates of | dbr:QFT |
| is dbo:wikiPageRedirects of | dbr:Quantum_Fourier_Transform dbr:Quantum_fourier_transform dbr:Quantum_fourier_transforms |
| is dbo:wikiPageWikiLink of | dbr:Quantum_logic_gate dbr:Quantum_computing dbr:List_of_harmonic_analysis_topics dbr:Quantum_Fourier_Transform dbr:Quantum_fourier_transform dbr:Quantum_Computation_and_Quantum_Information dbr:Quantum_Computing:_A_Gentle_Introduction dbr:Quantum_algorithm dbr:Quantum_counting_algorithm dbr:Quil_(instruction_set_architecture) dbr:Generalizations_of_Pauli_matrices dbr:Shor's_algorithm dbr:Adder_(electronics) dbr:Hadamard_transform dbr:Fourier_analysis dbr:Fourier_transform dbr:Fast_Fourier_transform dbr:Fourier_transform_on_finite_groups dbr:List_of_Fourier_analysis_topics dbr:QFT dbr:Quantum_Computation_Language dbr:Hidden_subgroup_problem dbr:Discrete_Fourier_transform dbr:Umesh_Vazirani dbr:Quantum_phase_estimation_algorithm dbr:Quantum_fourier_transforms |
| is foaf:primaryTopic of | wikipedia-en:Quantum_Fourier_transform |
