The Open Optics Journal

More on Quantum Fast Fourier Transform by Linear Optics

Kazuto Oshima

Published Nov 28, 2014• 0 citations

Abstract

It is shown by Barak and Ben-Aryeh that the quantum fast Fourier transform by linear optics is applicable for an n -qubit system.We point out that the quantum fast Fourier transform by linear optics is applicable not only for a qubit system but also for a qutrit system and a compound system of qubits and qutrits etc.We compute an upper bound for the number of the beam splitters, which gives a basis for planning an experiment.

DOI: 10.2174/1874328501408010001

Related papers

Quantum fast Fourier transform and quantum computation by linear optics

Ronen Barak, Y. Ben-Aryeh

Using the quantum fast Fourier transform in linear optics the input mode annihilation operators {â0,â1,...,âs−1} are transformed into output mode annihilation operators {b̂0,b̂1,...,b̂s−1}. We show how to implement experimentally such transformations based on the Cooley-Tukey algorithm, by the use of beam splitters and phase shifters in a linear optical system. Optical systems implementing 1,2, and 3 qubits discrete Fourier transform (DFT) are described, and a general method for implementing the n-qubit DFT is analyzed. These transformations are used on various input radiation states by which phase estimation and order finding can be computed.

Journal of the Optical Society of America BJan 26, 200766 citations

Reducing the complexity of linear optics quantum circuits

John C. Howell, John A. Yeazell

Integrated optical elements can simplify the linear optics used to simulate quantum circuits. These linear optical simulations of quantum circuits have been developed primarily in terms of the free space optics associated with single-photon interferometry. For an L-bit simulation the number of required free-space optical elements is $\ensuremath{\propto}{2}^{L}$ if 50/50 beam splitters are used. The implementation (construction and alignment) of these circuits with these free-space elements is nontrivial. On the other hand, for the cases presented in this paper in which linear integrated optics (e.g., ${2}^{L}\ifmmode\times\else\texttimes\fi{}{2}^{L}$ fiber couplers) are used, the number of optical devices does not grow exponentially with L. The problem is changed from having an exponential growth of the number of devices to having devices with an exponential growth in the number of ports. In addition to simplifying the construction, the association of an $N\ifmmode\times\else\texttimes\fi{}N$ fiber coupler with the discrete Fourier transform suggests alternative formulations for the circuits. Several examples of circuit reductions are given.

Physical Review AApr 3, 200026 citations

Fast Quantum Fourier Transforms for a Class of Non-abelian Groups

Markus Püschel, Martin Roetteler, Thomas Beth

An algorithm is presented allowing the construction of fast Fourier transforms for any solvable group on a classical computer. The special structure of the recursion formula being the core of this algorithm makes it a good starting point to obtain systematically fast Fourier transforms for solvable groups on a quantum computer. The inherent structure of the Hilbert space imposed by the qubit architecture suggests to consider groups of order 2^n first (where n is the number of qubits). As an example, fast quantum Fourier transforms for all 4 classes of non-abelian 2-groups with cyclic normal subgroup of index 2 are explicitly constructed in terms of quantum circuits. The (quantum) complexity of the Fourier transform for these groups of size 2^n is O(n^2) in all cases.

arXiv:quant-ph/9807064Jul 22, 19980 citations

Quantum homogenization for continuous variables: Realization with linear optical elements

Daniel Nagaj, Peter Štelmachovič, Vladimír Bužek +1 more

Recently Ziman et al. [Phys. Rev. A 65, 042105 (2002)] have introduced a concept of a universal quantum homogenizer which is a quantum machine that takes as input a given (system) qubit initially in an arbitrary state $\ensuremath{\rho}$ and a set of N reservoir qubits initially prepared in the state $\ensuremath{\xi}.$ The homogenizer realizes, in the limit sense, the transformation such that at the output each qubit is in an arbitrarily small neighborhood of the state $\ensuremath{\xi}$ irrespective of the initial states of the system and the reservoir qubits. In this paper we generalize the concept of quantum homogenization for qudits, that is, for d-dimensional quantum systems. We prove that the partial-swap operation induces a contractive map with the fixed point which is the original state of the reservoir. We propose an optical realization of the quantum homogenization for Gaussian states. We prove that an incoming state of a photon field is homogenized in an array of beam splitters. Using Simon's criterion, we study entanglement between outgoing beams from beam splitters. We derive an inseparability condition for a pair of output beams as a function of the degree of squeezing in input beams.

Physical Review ADec 9, 200213 citations

Quantum circuit for the fast Fourier transform

Ryo Asaka, Kazumitsu Sakai, Ryoko Yahagi

Abstract We propose an implementation of the algorithm for the fast Fourier transform (FFT) as a quantum circuit consisting of a combination of some quantum gates. In our implementation, a data sequence is expressed by a tensor product of vector spaces. Namely, our FFT is defined as a transformation of the tensor product of quantum states. It is essentially different from the so-called quantum Fourier transform (QFT) defined to be a linear transformation of the amplitudes for the superposition of quantum states. The quantum circuit for the FFT consists of several circuits for elementary arithmetic operations such as a quantum adder, subtractor and shift operations, which are implemented as effectively as possible. Namely, our circuit does not generate any garbage bits. The advantages of our method compared to the QFT are its high versatility, and data storage efficiency in terms, for instance, of the quantum image processing.

arXiv:1911.03055Quantum Information ProcessingAug 1, 202031 citations

Quantum Fourier transform revisited

Camps, D, Van Beeumen, R, Yang, C

The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank-1 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix-2 QFT decomposition to a radix-d QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.

Jan 1, 202125 citations