Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Applied Optics

Efficient parallel algorithms for optical computing with the discrete Fourier transform (DFT) primitive

John H. Reif, Akhilesh K. Tyagi

Published Oct 10, 1997• 37 citations
Publisher

Abstract

Optical-computing technology offers new challenges to algorithm designers since it can perform an n-point discrete Fourier transform (DFT) computation in only unit time. Note that the DFT is a nontrivial computation in the parallel random-access machine model, a model of computing commonly used by parallel-algorithm designers. We develop two new models, the DFT-VLSIO (very-large-scale integrated optics) and the DFT-circuit, to capture this characteristic of optical computing. We also provide two paradigms for developing parallel algorithms in these models. Efficient parallel algorithms for many problems, including polynomial and matrix computations, sorting, and string matching, are presented. The sorting and string-matching algorithms are particularly noteworthy. Almost all these algorithms are within a polylog factor of the optical-computing (VLSIO) lower bounds derived by Barakat and Reif [Appl. Opt. 26, 1015 (1987) and by Tyagi and Reif [Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing (Institute of Electrical and Electronics Engineers, New York, 1990) p. 14].

DOI
10.1364/ao.36.007327

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 {â0,â1,...,â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 B•Jan 26, 2007•66 citations

A Discrete Fourier Transform on Lattices with Quantum Applications

Lior Eldar, Peter W. Shor

In this work, we introduce a definition of the Discrete Fourier Transform (DFT) on Euclidean lattices in $\R^n$, that generalizes the $n$-th fold DFT of the integer lattice $\Z^n$ to arbitrary lattices. This definition is not applicable for every lattice, but can be defined on lattices known as Systematic Normal Form (SysNF) introduced in \cite{ES16}. Systematic Normal Form lattices are sets of integer vectors that satisfy a single homogeneous modular equation, which itself satisfies a certain number-theoretic property. Such lattices form a dense set in the space of $n$-dimensional lattices, and can be used to approximate efficiently any lattice. This implies that for every lattice $L$ a DFT can be computed efficiently on a lattice near $L$. Our proof of the statement above uses arguments from quantum computing, and as an application of our definition we show a quantum algorithm for sampling from discrete distributions on lattices, that extends our ability to sample efficiently from the discrete Gaussian distribution \cite{GPV08} to any distribution that is sufficiently "smooth". We conjecture that studying the eigenvectors of the newly-defined lattice DFT may provide new insights into the structure of lattices, especially regarding hard computational problems, like the shortest vector problem.

arXiv:1703.02515•Mar 7, 2017•1 citation

Coherent optical implementations of the fast Fourier transform and their comparison to the optical implementation of the quantum Fourier transform

Rupert C. D. Young, Philip M. Birch, Chris R. Chatwin

Optical structures to implement the discrete Fourier transform (DFT) and fast Fourier transform (FFT) algorithms for discretely sampled data sets are considered. In particular, the decomposition of the FFT algorithm into the basic Butterfly operations is described, as this allows the algorithm to be fully implemented by the successive coherent addition and subtraction of two wavefronts (the subtraction being performed after one has been appropriately phase shifted), so facilitating a simple and robust hardware implementation based on waveguided hybrid devices as employed in coherent optical detection modules. Further, a comparison is made to the optical structures proposed for the optical implementation of the quantum Fourier transform and they are shown to be very similar.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 29, 2013•8 citations

A quantum search algorithm of two entangled registers to realize quantum discrete Fourier transform of signal processing

Chao-Yang Pang, Ben-Qiong Hu

The discrete Fourier transform (DFT) is the base of modern signal processing. 1-dimensional fast Fourier transform (ID FFT) and 2D FFT have time complexity O ( N log N ) and O ( N 2 log N ) respectively. Since 1965, there has been no more essential breakthrough for the design of fast DFT algorithm. DFT has two properties. One property is that DFT is energy conservation transform. The other property is that many DFT coefficients are close to zero. The basic idea of this paper is that the generalized Grover's iteration can perform the computation of DFT which acts on the entangled states to search the big DFT coefficients until these big coefficients contain nearly all energy. One-dimensional quantum DFT (ID QDFT) and two-dimensional quantum DFT (2D QDFT) are presented in this paper. The quantum algorithm for convolution estimation is also presented in this paper. Compared with FFT, ID and 2D QDFT have time complexity O(√ N ) and O ( N ) respectively. QDFT and quantum convolution demonstrate that quantum computation to process classical signal is possible.

Chinese Physics B•Sep 1, 2008•7 citations

Model of computation for Fourier optical processors

Thomas J. Naughton

We present a novel and simple theoretical model of computation that captures what we believe are the most important characteristics of an optical Fourier transform processor. We use this abstract model to reason about the computational properties of the physical systems it describes. We define a grammar for our model's instruction language, and use it to write algorithms for well-known filtering and correlation techniques. We also suggest suitable computational complexity measures that could be used to analyze any coherent optical information processing technique, described with the language, for efficiency. Our choice of instruction language allows us to argue that algorithms describable with this model should have optical implementations that do not require a digital electronic computer to act as a master unit. Through simulation of a well known model of computation from computer theory we investigate the general-purpose capabilities of analog optical processors.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 24, 2000•25 citations

Fourier Transform Evolution from DFT to FFT to QFT: the Journey of Cost Reduction from $O\left(N^{2}\right)$ to $O(N \log N)$ to $O\left(\log ^{2} N\right)$

Chris Nguyễn, Vladimir Okhmatovski

Paper provides description of methods for Discrete Fourier Transform computation from direct$O\left(N^{2}\right)$approach to its$O(N \log N)$evaluation with FFT, to$O\left(\log ^{2} N\right)$complexity Quantum Fourier Transform algorithm. It can serve as an introduction for computational electromagnetics (CEM) engineers to quantum information processing using an example of a familiar algorithm. We also outline the key role of QFT in Quantum Phase Estimation method foundational to solution of matrix equations arising from Method of Moments (MoM) and Finite Element Method (FEM) on quantum computers.

Digest - IEEE Antennas and Propagation Society. International Symposium•Jul 13, 2025•0 citations
Optical-computing technology offers new challenges to algorithm designers since it can perform an n-point discrete Fourier transform (DFT) computation in only unit time. Note that the DFT is a nontrivial computation in the parallel random-access machine model, a model of computing commonly used by parallel-algorithm designers. We develop two new models, the DFT-VLSIO (very-large-scale integrated optics) and the DFT-circuit, to capture this characteristic of optical computing. We also provide two paradigms for developing parallel algorithms in these models. Efficient parallel algorithms for many problems, including polynomial and matrix computations, sorting, and string matching, are presented. The sorting and string-matching algorithms are particularly noteworthy. Almost all these algorithms are within a polylog factor of the optical-computing (VLSIO) lower bounds derived by Barakat and Reif [Appl. Opt. 26, 1015 (1987) and by Tyagi and Reif [Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing (Institute of Electrical and Electronics Engineers, New York, 1990) p. 14].
Using the quantum fast Fourier transform in linear optics the input mode annihilation operators {â0,â1,...,â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.
In this work, we introduce a definition of the Discrete Fourier Transform (DFT) on Euclidean lattices in Rn\R^nRn, that generalizes the nnn-th fold DFT of the integer lattice Zn\Z^nZn to arbitrary lattices. This definition is not applicable for every lattice, but can be defined on lattices known as Systematic Normal Form (SysNF) introduced in \cite{ES16}. Systematic Normal Form lattices are sets of integer vectors that satisfy a single homogeneous modular equation, which itself satisfies a certain number-theoretic property. Such lattices form a dense set in the space of nnn-dimensional lattices, and can be used to approximate efficiently any lattice. This implies that for every lattice LLL a DFT can be computed efficiently on a lattice near LLL. Our proof of the statement above uses arguments from quantum computing, and as an application of our definition we show a quantum algorithm for sampling from discrete distributions on lattices, that extends our ability to sample efficiently from the discrete Gaussian distribution \cite{GPV08} to any distribution that is sufficiently "smooth". We conjecture that studying the eigenvectors of the newly-defined lattice DFT may provide new insights into the structure of lattices, especially regarding hard computational problems, like the shortest vector problem.
Optical structures to implement the discrete Fourier transform (DFT) and fast Fourier transform (FFT) algorithms for discretely sampled data sets are considered. In particular, the decomposition of the FFT algorithm into the basic Butterfly operations is described, as this allows the algorithm to be fully implemented by the successive coherent addition and subtraction of two wavefronts (the subtraction being performed after one has been appropriately phase shifted), so facilitating a simple and robust hardware implementation based on waveguided hybrid devices as employed in coherent optical detection modules. Further, a comparison is made to the optical structures proposed for the optical implementation of the quantum Fourier transform and they are shown to be very similar.
The discrete Fourier transform (DFT) is the base of modern signal processing. 1-dimensional fast Fourier transform (ID FFT) and 2D FFT have time complexity O ( N log N ) and O ( N 2 log N ) respectively. Since 1965, there has been no more essential breakthrough for the design of fast DFT algorithm. DFT has two properties. One property is that DFT is energy conservation transform. The other property is that many DFT coefficients are close to zero. The basic idea of this paper is that the generalized Grover's iteration can perform the computation of DFT which acts on the entangled states to search the big DFT coefficients until these big coefficients contain nearly all energy. One-dimensional quantum DFT (ID QDFT) and two-dimensional quantum DFT (2D QDFT) are presented in this paper. The quantum algorithm for convolution estimation is also presented in this paper. Compared with FFT, ID and 2D QDFT have time complexity O(√ N ) and O ( N ) respectively. QDFT and quantum convolution demonstrate that quantum computation to process classical signal is possible.
We present a novel and simple theoretical model of computation that captures what we believe are the most important characteristics of an optical Fourier transform processor. We use this abstract model to reason about the computational properties of the physical systems it describes. We define a grammar for our model's instruction language, and use it to write algorithms for well-known filtering and correlation techniques. We also suggest suitable computational complexity measures that could be used to analyze any coherent optical information processing technique, described with the language, for efficiency. Our choice of instruction language allows us to argue that algorithms describable with this model should have optical implementations that do not require a digital electronic computer to act as a master unit. Through simulation of a well known model of computation from computer theory we investigate the general-purpose capabilities of analog optical processors.
Fourier Transform Evolution from DFT to FFT to QFT: the Journey of Cost Reduction from O(N2)O\left(N^{2}\right)O(N2) to O(Nlog⁡N)O(N \log N)O(NlogN) to O(log⁡2N)O\left(\log ^{2} N\right)O(log2N)
Paper provides description of methods for Discrete Fourier Transform computation from directO(N2)O\left(N^{2}\right)O(N2)approach to itsO(Nlog⁡N)O(N \log N)O(NlogN)evaluation with FFT, toO(log⁡2N)O\left(\log ^{2} N\right)O(log2N)complexity Quantum Fourier Transform algorithm. It can serve as an introduction for computational electromagnetics (CEM) engineers to quantum information processing using an example of a familiar algorithm. We also outline the key role of QFT in Quantum Phase Estimation method foundational to solution of matrix equations arising from Method of Moments (MoM) and Finite Element Method (FEM) on quantum computers.