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

Journal of Information and Computational Science

Algorithm of Walsh-Hadamard Transform with Optical Approach

Yunfu Shen

Published Sep 20, 2013• 3 citations
Publisher

Abstract

In this paper, the fast algorithm to Walsh-Hadamard transform (WHT) is studied from the point of view of the optical computation. Firstly, MSD addition and butterfly calculation in discrete WHT are presented in detail. Then the design and implementation scheme of fast algorithm of WHT is proposed and the software simulations to fast WHT are carried out optically. Meanwhile, the computational complexity of the algorithms in time and space are analyzed. The analysis shows that the problem of WHT with large-scale data can be solved in a few of clock cycles with optical computational method. The scheme also provides a good way for the design of fast optical Walsh-Hadamard transformer and an application in ternary optical computer.

DOI
10.12733/jics20102176

Related papers

Design and implementation of a parallel Stein algorithm based on a ternary optical computer

Kai Song, Jingyang Wei, Huanyu Hu +3 more

The Stein algorithm is used to solve the problem that the Euclidean algorithm is inefficient when dealing with large integers, and it is widely used in mathematics, physics, and cryptography. When the algorithm is implemented on a traditional electronic computer, the problems of slow computation speed, low computational efficiency, and large space occupation become more evident with the increase in the number of integer bits and the improvement of precision demands. The ternary optical computer (TOC), with low power consumption, abundant data bits, ease of expansion, and bitwise reconstruction, can solve these problems. In this study, a parallel Stein algorithm based on TOC is proposed by analyzing the Stein algorithm and identifying the parts of the algorithm that can be computed in parallel. The algorithm employs the parity judge to determine the parity of the data and calculates the intra-group greatest common divisor of each group of data in parallel by reconstructing the composite arithmetic and MSD multiplier, with the final value being the greatest common divisor of all the data. By analyzing the energy consumption and clock cycles of the parallel algorithm and through experimental verification, it is concluded that the parallel Stein algorithm based on TOC exhibits good time performance and operational efficiency, fully leveraging the advantages of TOC in computing.

Applied Optics•Jul 21, 2025•1 citation

Quantum computing and a unified approach to fast unitary transforms

Sos С. Agaian, Andreas Klappenecker

A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.

arXiv:quant-ph/0201120•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 23, 2002•6 citations

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 framework for fast quantum mechanical algorithms

Lov K. Grover

A framework is presented for the design and analysis of quantum mechanical algorithms, the 0( fi) step quantum search algorithm is an immediate consequence of this framework.It leads to several other search-type applications -an example is presented where the Walsh-Hadamard (W-H) transform of the quantum search algorithm is replaced by another transform tailored to the parameters of the problem.Also, it leads to quantum mechanical algorithms for problems not immediately connected with search -two such algorithms are presented for calculating the mean and median of statistical distributions.In order to classically estimate either the mean or median of a given distribution to a precision E , needs a(~-~) steps.The best known quantum mechanical algorithm for estimating the median takes O(E-') steps, and that for estimating the mean takes O(E -1.5 ) steps.This paper presents O(E-l) step algorithms for both problems (all bounds are upto polylogarithmic factors).Both algorithms are considerably simpler than known algorithms.

arXiv:quant-ph/9711043•ACM Symposium on Theory of Computing (STOC)•Jan 1, 1998•246 citations

Pauli decomposition via the fast Walsh-Hadamard transform

Timothy N. Georges, Bjorn K. Berntson, Christoph Sünderhauf +1 more

Abstract The decomposition of a square matrix into a sum of Pauli strings is a classical pre-processing step required to realize many quantum algorithms. Such a decomposition requires significant computational resources for large matrices. We present an exact and explicit formula for the Pauli string coefficients which inspires an efficient algorithm to compute them. More specifically, we show that up to a permutation of the matrix elements, the decomposition coefficients are related to the original matrix by a multiplication of a generalised Hadamard matrix. This allows one to use the Fast Walsh-Hadamard transform and calculate all Pauli decomposition coefficients in O ( N 2 log ⁡ N ) time and using O ( 1 ) additional memory, for an N × N matrix. A numerical implementation of our equation outperforms currently available solutions.

arXiv:2408.06206•New Journal of Physics•Feb 10, 2025•11 citations

Quantum Computers Can Search Rapidly by Using Almost Any Transformation

Lov K. Grover

A quantum computer has a clear advantage over a classical computer for exhaustive search. The quantum mechanical algorithm for exhaustive search was originally derived by using subtle properties of a particular quantum mechanical operation called the Walsh-Hadamard (W-H) transform. This paper shows that this algorithm can be implemented by replacing the W-H transform by almost any quantum mechanical operation. This leads to several new applications where it improves the number of steps by a square root. It also broadens the scope for implementation since it demonstrates quantum mechanical algorithms that can adapt to available technology.

arXiv:quant-ph/9712011•Physical Review Letters•May 11, 1998•617 citations
In this paper, the fast algorithm to Walsh-Hadamard transform (WHT) is studied from the point of view of the optical computation. Firstly, MSD addition and butterfly calculation in discrete WHT are presented in detail. Then the design and implementation scheme of fast algorithm of WHT is proposed and the software simulations to fast WHT are carried out optically. Meanwhile, the computational complexity of the algorithms in time and space are analyzed. The analysis shows that the problem of WHT with large-scale data can be solved in a few of clock cycles with optical computational method. The scheme also provides a good way for the design of fast optical Walsh-Hadamard transformer and an application in ternary optical computer.
The Stein algorithm is used to solve the problem that the Euclidean algorithm is inefficient when dealing with large integers, and it is widely used in mathematics, physics, and cryptography. When the algorithm is implemented on a traditional electronic computer, the problems of slow computation speed, low computational efficiency, and large space occupation become more evident with the increase in the number of integer bits and the improvement of precision demands. The ternary optical computer (TOC), with low power consumption, abundant data bits, ease of expansion, and bitwise reconstruction, can solve these problems. In this study, a parallel Stein algorithm based on TOC is proposed by analyzing the Stein algorithm and identifying the parts of the algorithm that can be computed in parallel. The algorithm employs the parity judge to determine the parity of the data and calculates the intra-group greatest common divisor of each group of data in parallel by reconstructing the composite arithmetic and MSD multiplier, with the final value being the greatest common divisor of all the data. By analyzing the energy consumption and clock cycles of the parallel algorithm and through experimental verification, it is concluded that the parallel Stein algorithm based on TOC exhibits good time performance and operational efficiency, fully leveraging the advantages of TOC in computing.
A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.
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.
A framework is presented for the design and analysis of quantum mechanical algorithms, the 0( fi) step quantum search algorithm is an immediate consequence of this framework.It leads to several other search-type applications -an example is presented where the Walsh-Hadamard (W-H) transform of the quantum search algorithm is replaced by another transform tailored to the parameters of the problem.Also, it leads to quantum mechanical algorithms for problems not immediately connected with search -two such algorithms are presented for calculating the mean and median of statistical distributions.In order to classically estimate either the mean or median of a given distribution to a precision E , needs a(~-~) steps.The best known quantum mechanical algorithm for estimating the median takes O(E-') steps, and that for estimating the mean takes O(E -1.5 ) steps.This paper presents O(E-l) step algorithms for both problems (all bounds are upto polylogarithmic factors).Both algorithms are considerably simpler than known algorithms.
Abstract The decomposition of a square matrix into a sum of Pauli strings is a classical pre-processing step required to realize many quantum algorithms. Such a decomposition requires significant computational resources for large matrices. We present an exact and explicit formula for the Pauli string coefficients which inspires an efficient algorithm to compute them. More specifically, we show that up to a permutation of the matrix elements, the decomposition coefficients are related to the original matrix by a multiplication of a generalised Hadamard matrix. This allows one to use the Fast Walsh-Hadamard transform and calculate all Pauli decomposition coefficients in O ( N 2 log ⁡ N ) time and using O ( 1 ) additional memory, for an N × N matrix. A numerical implementation of our equation outperforms currently available solutions.
A quantum computer has a clear advantage over a classical computer for exhaustive search. The quantum mechanical algorithm for exhaustive search was originally derived by using subtle properties of a particular quantum mechanical operation called the Walsh-Hadamard (W-H) transform. This paper shows that this algorithm can be implemented by replacing the W-H transform by almost any quantum mechanical operation. This leads to several new applications where it improves the number of steps by a square root. It also broadens the scope for implementation since it demonstrates quantum mechanical algorithms that can adapt to available technology.