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

arXiv:2606.03612

An efficient quantum Hadamard product algorithm for functions

Xinchi Huang, Hirofumi Nishi, Tomofumi Zushi, Yu-ichiro Matsushita

quant-phSubmitted Jun 2, 2026• Announced Jun 3, 2026• 0 citations
arXivHTMLPDF

Abstract

We propose an efficient quantum algorithm for preparing the Hadamard product state of two quantum states whose amplitudes are generated by functions on a uniform grid with grid number $N$. As the Hadamard product operation is non-unitary, the conventional approach generally suffer from a success probability that scales as $O(1/N)$, leading to an $O(\sqrt{N})$ query complexity even with quantum amplitude amplification. Our method exploits the Fourier-space representation of the input functions, where the Hadamard product can be treated through a convolution structure and approximated using localized Fourier coefficients. The resulting quantum circuit has complexity governed by the Fourier regularity of the underlying functions rather than directly by the grid number. In particular, when either of the input functions has finitely many non-zero Fourier coefficients, the algorithm prepares the exact quantum Hadamard product state under $N$-independent query complexity. Moreover, we also propose a novel quantum circuit for the partial inner product as one of its applications.

Related papers

Efficient quantum amplitude encoding of polynomial functions

Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa +1 more

Loading functions into quantum computers represents an essential step in several quantum algorithms, such as quantum partial differential equation solvers. Therefore, the inefficiency of this process leads to a major bottleneck for the application of these algorithms. Here, we present and compare two efficient methods for the amplitude encoding of real polynomial functions on n qubits. This case holds special relevance, as any continuous function on a closed interval can be uniformly approximated with arbitrary precision by a polynomial function. The first approach relies on the matrix product state representation (MPS). We study and benchmark the approximations of the target state when the bond dimension is assumed to be small. The second algorithm combines two subroutines. Initially we encode the linear function into the quantum registers either via its MPS or with a shallow sequence of multi-controlled gates that loads the linear function's Hadamard-Walsh series, and we explore how truncating the Hadamard-Walsh series of the linear function affects the final fidelity. Applying the inverse discrete Hadamard-Walsh transform converts the state encoding the series coefficients into an amplitude encoding of the linear function. Thus, we use this construction as a building block to achieve an exact block encoding of the amplitudes corresponding to the linear function on k0 qubits and apply the quantum singular value transformation that implements a polynomial transformation to the block encoding of the amplitudes. This unitary together with the Amplitude Amplification algorithm will enable us to prepare the quantum state that encodes the polynomial function on k0 qubits. Finally we pad n−k0 qubits to generate an approximated encoding of the polynomial on n qubits, analyzing the error depending on k0 . In this regard, our methodology proposes a method to improve the state-of-the-art complexity by introducing controllable errors.

arXiv:2307.10917•Quantum•Mar 21, 2024•40 citations

Fourier space readout method for efficiently recovering functions encoded in quantum states

Xinchi Huang, Hirofumi Nishi, Yoshifumi Kawada +2 more

Abstract Applying quantum computing to computer-aided engineering (CAE) problems is highly expected since quantum computers yield potential exponential speedups for the operations between extremely large matrices and vectors. Although efficient quantum algorithms for the above problems have been intensively investigated, it remains a crucial task to extract all the grid-point values encoded in the prepared quantum states, which was believed to eliminate the achieved quantum advantage. In this paper, we propose a quantum–classical hybrid Fourier space readout method to efficiently recover the underlying function from its corresponding quantum state. We provide explicit quantum circuits, followed by theoretical and numerical discussions on its complexity. In particular, the complexity on quantum computers has only a logarithmic dependence on the grid number, while its complexity on classical computers has a linear dependence on the number of target points instead of the grid number. Our result implies that the achieved quantum speedups are not necessarily ruined when we read out the solutions to the CAE problems.

arXiv:2507.20599•Quantum Science and Technology•Jul 10, 2026•1 citation

Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity

Yin Yang, Yue Yu, Long Zhang

Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution $\bb{x}$ as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity $\mathcal{O}(κ_A\log\frac1\varepsilon)$ without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.

quant-pharXiv:2609.19676•Sep 18, 2026•0 citations

Preparation of digital-encoded and analog-encoded quantum states corresponding to matrix operations

Kaitian Gao, Youlong Yang, Zhenye Du

Abstract Efficient implementation of fundamental matrix operations on quantum computers, such as matrix products and Hadamard operations, holds significant potential for accelerating machine learning algorithms. A critical prerequisite for quantum implementations is the effective encoding of classical data into quantum states. We propose two quantum computing frameworks for preparing the distinct encoded states corresponding to matrix operations, including the matrix product, matrix sum, matrix Hadamard product and division. Quantum algorithms based on the digital encoding computing framework are capable of implementing the matrix Hadamard operation with a time complexity of O (poly log( mn / ε )) and the matrix product with a time complexity of O (poly log( mnl / ε )), achieving an exponential speedup in contrast to the classical methods of O ( mn ) and O ( mnl ). Quantum algorithms based on the analog-encoding framework are capable of implementing the matrix Hadamard operation with a time complexity of O ( k 1 m n ⋅ poly log ( m n / ε ) ) and the matrix product with a time complexity of O ( k 2 l ⋅ poly log ( m n l / ε ) ) , where k 1 and k 2 are coefficients correlated with the elements of the matrix, achieving a square speedup in contrast to the classical counterparts. As applications, we construct an oracle that can access the trace of a matrix within logarithmic time, and propose several algorithms to respectively estimate the trace of a matrix, the trace of the product of two matrices, and the trace inner product of two matrices within logarithmic time.

Chinese Physics B•Jun 12, 2025•0 citations

Non-Linear Transformations of Quantum Amplitudes: Exponential Improvement, Generalization, and Applications

Arthur G. Rattew, Patrick Rebentrost

Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems. In this work, we present a framework for applying a general class of non-linear functions to the amplitudes of quantum states, with up-to an exponential improvement over the previous work. Our framework accepts a state preparation unitary (or block-encoding), specified as a quantum circuit, defining an $N$-dimensional quantum state. We then construct a diagonal block-encoding of the amplitudes of the quantum state, building on and simplifying previous work. Techniques from the QSVT literature are then used to process this block-encoding. The source of our exponential speedup comes from the quantum analog of importance sampling. We then derive new error-bounds relevant for end-to-end applications, giving the error in terms of $\ell_2$-norm error. We demonstrate the power of this framework with four key applications. First, our algorithm can apply the important function $\tanh(x)$ to the amplitudes of an arbitrary quantum state with at most an $\ell_2$-norm error of $ε$, with worst-case query complexity of $O(\log(N/ε))$, in comparison to the $O(\sqrt{N}\log(N/ε))$ of prior work. Second, we present an algorithm solving a new formulation of maximum finding in the unitary input model. Third, we prove efficient end-to-end complexities in applying a number of common non-linear functions to arbitrary quantum states. Finally, we generalize and unify existing quantum arithmetic-free state-preparation techniques. Our work provides an important and efficient algorithmic building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.

arXiv:2309.09839•Sep 18, 2023•3 citations

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

Keshav Bhateja, Mehdi Esmaili, Atul Mantri

Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we show that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness. First, exceeding the ideal score by a constant requires $Ω(N^{1/3})$ queries for the Haar and Fourier oracle ensembles with $N$ outcomes, and this bound is tight; this proves an earlier conjecture for Haar-random states and extends it to Fourier sampling. Second, for Fourier sampling and for Haar-random states accessed through the canonical state-preparation oracle, the $n$-bit output of a device that makes polynomially many queries and scores within $o(1)$ of the ideal score has $n-O(\log n)$ bits of smooth min-entropy, even against an adversary who is entangled with the device and later learns the oracle; this is nearly optimal. As a corollary, sampling the collision distribution, which is proportional to the square of the ideal distribution, has query complexity $Θ(N^{1/3})$, and a coherent version of the same algorithm approximately prepares quantum Hadamard products of states with uniform amplitude magnitudes. Both lower bounds rest on progress measures that bound the excess over the ideal score and increase only slightly with each query. For Fourier sampling the measure is the norm of the coherent amplitudes for removing pairs in a purification of the random function, combining the polynomial method with the compressed oracle technique; for Haar-random states it is the square root of the average level in an expansion in Dirichlet orthogonal polynomials, controlled by an exact identity for the effect of one observation.

quant-pharXiv:2610.06721•Oct 6, 2026•0 citations
We propose an efficient quantum algorithm for preparing the Hadamard product state of two quantum states whose amplitudes are generated by functions on a uniform grid with grid number NNN. As the Hadamard product operation is non-unitary, the conventional approach generally suffer from a success probability that scales as O(1/N)O(1/N)O(1/N), leading to an O(N)O(\sqrt{N})O(N​) query complexity even with quantum amplitude amplification. Our method exploits the Fourier-space representation of the input functions, where the Hadamard product can be treated through a convolution structure and approximated using localized Fourier coefficients. The resulting quantum circuit has complexity governed by the Fourier regularity of the underlying functions rather than directly by the grid number. In particular, when either of the input functions has finitely many non-zero Fourier coefficients, the algorithm prepares the exact quantum Hadamard product state under NNN-independent query complexity. Moreover, we also propose a novel quantum circuit for the partial inner product as one of its applications.
Loading functions into quantum computers represents an essential step in several quantum algorithms, such as quantum partial differential equation solvers. Therefore, the inefficiency of this process leads to a major bottleneck for the application of these algorithms. Here, we present and compare two efficient methods for the amplitude encoding of real polynomial functions on n qubits. This case holds special relevance, as any continuous function on a closed interval can be uniformly approximated with arbitrary precision by a polynomial function. The first approach relies on the matrix product state representation (MPS). We study and benchmark the approximations of the target state when the bond dimension is assumed to be small. The second algorithm combines two subroutines. Initially we encode the linear function into the quantum registers either via its MPS or with a shallow sequence of multi-controlled gates that loads the linear function's Hadamard-Walsh series, and we explore how truncating the Hadamard-Walsh series of the linear function affects the final fidelity. Applying the inverse discrete Hadamard-Walsh transform converts the state encoding the series coefficients into an amplitude encoding of the linear function. Thus, we use this construction as a building block to achieve an exact block encoding of the amplitudes corresponding to the linear function on k0 qubits and apply the quantum singular value transformation that implements a polynomial transformation to the block encoding of the amplitudes. This unitary together with the Amplitude Amplification algorithm will enable us to prepare the quantum state that encodes the polynomial function on k0 qubits. Finally we pad n−k0 qubits to generate an approximated encoding of the polynomial on n qubits, analyzing the error depending on k0 . In this regard, our methodology proposes a method to improve the state-of-the-art complexity by introducing controllable errors.
Abstract Applying quantum computing to computer-aided engineering (CAE) problems is highly expected since quantum computers yield potential exponential speedups for the operations between extremely large matrices and vectors. Although efficient quantum algorithms for the above problems have been intensively investigated, it remains a crucial task to extract all the grid-point values encoded in the prepared quantum states, which was believed to eliminate the achieved quantum advantage. In this paper, we propose a quantum–classical hybrid Fourier space readout method to efficiently recover the underlying function from its corresponding quantum state. We provide explicit quantum circuits, followed by theoretical and numerical discussions on its complexity. In particular, the complexity on quantum computers has only a logarithmic dependence on the grid number, while its complexity on classical computers has a linear dependence on the number of target points instead of the grid number. Our result implies that the achieved quantum speedups are not necessarily ruined when we read out the solutions to the CAE problems.
Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution $\bb{x}$ as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity O(κAlog⁡1ε)\mathcal{O}(κ_A\log\frac1\varepsilon)O(κA​logε1​) without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.
Abstract Efficient implementation of fundamental matrix operations on quantum computers, such as matrix products and Hadamard operations, holds significant potential for accelerating machine learning algorithms. A critical prerequisite for quantum implementations is the effective encoding of classical data into quantum states. We propose two quantum computing frameworks for preparing the distinct encoded states corresponding to matrix operations, including the matrix product, matrix sum, matrix Hadamard product and division. Quantum algorithms based on the digital encoding computing framework are capable of implementing the matrix Hadamard operation with a time complexity of O (poly log( mn / ε )) and the matrix product with a time complexity of O (poly log( mnl / ε )), achieving an exponential speedup in contrast to the classical methods of O ( mn ) and O ( mnl ). Quantum algorithms based on the analog-encoding framework are capable of implementing the matrix Hadamard operation with a time complexity of O ( k 1 m n ⋅ poly log ( m n / ε ) ) and the matrix product with a time complexity of O ( k 2 l ⋅ poly log ( m n l / ε ) ) , where k 1 and k 2 are coefficients correlated with the elements of the matrix, achieving a square speedup in contrast to the classical counterparts. As applications, we construct an oracle that can access the trace of a matrix within logarithmic time, and propose several algorithms to respectively estimate the trace of a matrix, the trace of the product of two matrices, and the trace inner product of two matrices within logarithmic time.
Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems. In this work, we present a framework for applying a general class of non-linear functions to the amplitudes of quantum states, with up-to an exponential improvement over the previous work. Our framework accepts a state preparation unitary (or block-encoding), specified as a quantum circuit, defining an NNN-dimensional quantum state. We then construct a diagonal block-encoding of the amplitudes of the quantum state, building on and simplifying previous work. Techniques from the QSVT literature are then used to process this block-encoding. The source of our exponential speedup comes from the quantum analog of importance sampling. We then derive new error-bounds relevant for end-to-end applications, giving the error in terms of ℓ2\ell_2ℓ2​-norm error. We demonstrate the power of this framework with four key applications. First, our algorithm can apply the important function tanh⁡(x)\tanh(x)tanh(x) to the amplitudes of an arbitrary quantum state with at most an ℓ2\ell_2ℓ2​-norm error of εεε, with worst-case query complexity of O(log⁡(N/ε))O(\log(N/ε))O(log(N/ε)), in comparison to the O(Nlog⁡(N/ε))O(\sqrt{N}\log(N/ε))O(N​log(N/ε)) of prior work. Second, we present an algorithm solving a new formulation of maximum finding in the unitary input model. Third, we prove efficient end-to-end complexities in applying a number of common non-linear functions to arbitrary quantum states. Finally, we generalize and unify existing quantum arithmetic-free state-preparation techniques. Our work provides an important and efficient algorithmic building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.
Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we show that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness. First, exceeding the ideal score by a constant requires Ω(N1/3)Ω(N^{1/3})Ω(N1/3) queries for the Haar and Fourier oracle ensembles with NNN outcomes, and this bound is tight; this proves an earlier conjecture for Haar-random states and extends it to Fourier sampling. Second, for Fourier sampling and for Haar-random states accessed through the canonical state-preparation oracle, the nnn-bit output of a device that makes polynomially many queries and scores within o(1)o(1)o(1) of the ideal score has n−O(log⁡n)n-O(\log n)n−O(logn) bits of smooth min-entropy, even against an adversary who is entangled with the device and later learns the oracle; this is nearly optimal. As a corollary, sampling the collision distribution, which is proportional to the square of the ideal distribution, has query complexity Θ(N1/3)Θ(N^{1/3})Θ(N1/3), and a coherent version of the same algorithm approximately prepares quantum Hadamard products of states with uniform amplitude magnitudes. Both lower bounds rest on progress measures that bound the excess over the ideal score and increase only slightly with each query. For Fourier sampling the measure is the norm of the coherent amplitudes for removing pairs in a purification of the random function, combining the polynomial method with the compressed oracle technique; for Haar-random states it is the square root of the average level in an expansion in Dirichlet orthogonal polynomials, controlled by an exact identity for the effect of one observation.