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.08443

Quantum Kravchuk Transform using $\mathfrak{su}(2)$ fast-forwarding

Chaowen Guan, Akshit Katiyar

quant-phcs.CCSubmitted Jun 7, 2026• Announced Jun 9, 2026• 0 citations• Revised Sep 8, 2026 (v2)
v1 · Jun 7, 2026v2 · Sep 8, 2026
arXivHTMLPDF

Abstract

We present a quantum algorithm for the Kravchuk transform that scales logarithmically in both the dimension and the inverse of the error parameter. The quantum Kravchuk transform maps computational basis states to states with amplitudes proportional to Kravchuk functions. We achieve this by combining two key techniques: the structural relationship between the Kravchuk transform and the Lie algebras $\mathfrak{su}(2)$, and a recent fast-forwarding simulation method for $\mathfrak{su}(2)$ operators in the oscillator representation. More precisely, we first establish the map from Kravchuk transform in computational basis to $\mathfrak{su}(2)$ in Fock basis. Then built on this connection, we apply the fast-forwarding to achieve an efficient quantum Kravchuk transform.

Comments
fixed some typos

Related papers

Efficient Quantum Hermite Transform

Siddhartha Jain, Vishnu Iyer, Rolando D. Somma +2 more

We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that is polylogarithmic in the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted as the Gaussian analogue of the Fourier transform. Our algorithm is based on a method to exponentially fast-forward the evolution of the quantum harmonic oscillator, giving a simulation algorithm with nearly optimal circuit complexity for a fundamental Hamiltonian more than four decades after Feynman posed the simulation of quantum physics as an application of quantum computers.

arXiv:2510.04929•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•2 citations

Quantum algorithms for orthogonal polynomial transforms

Anupam Prakash, Shree Hari Sureshbabu, Dylan Herman +1 more

A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states $\sum_k α_{k} \ket{k}$ coherently to a basis of normalized univariate polynomials orthogonal with respect to a probability measure $μ(x)$. We provide new discrete and continuous QOPTs for polynomial families in the Askey scheme extending the results for the quantum Hermite transform (Jain et al., STOC'26). Our efficient QOPT algorithms require time $O(\text{polylog}(N, 1/ε))$, where $N$ is the grid size and $ε$ is the error, for the discrete Charlier, Meixner and Krawtchouk transforms and for the integer-order Laguerre transform in the continuous setting. The efficient QOPTs are obtained by uncovering the links between Askey scheme polynomials and Gaussian quantum optical gates and developing a compilation framework for $SU(2)$ and $SU(1,1)$ optical gates on Cartesian grids extending the framework developed by Iyer et al. (arXiv:2602.15180). Further, we reduce the continuous Jacobi transform to the discrete Hahn transform and provide an $O\!\left(N\operatorname{polylog}((N+α+β+1)/ε)\right)$-time Hahn transform, a quadratic speedup over the naive implementation. This is based on a more efficient compilation of the Clebsch--Gordan transform for coupling $\mathrm{SU}(2)$ representations with spins $(j_{1}, j_{2})$. Finally, we develop a new framework for Laguerre transforms for all orders $ν>0$ by fast-forwarding the corresponding radial oscillator using a 3-term chirp decomposition and an efficient algorithm for the Quantum Hankel Transform on a logarithmic grid.

quant-pharXiv:2610.03581•Oct 5, 2026•0 citations

Efficient quantum algorithms for state measurement and linear algebra applications

Apoorva D. Patel, Anjani Priyadarsini

We present an algorithm for measurement of [Formula: see text]-local operators in a quantum state, which scales logarithmically both in the system size and the output accuracy. The key ingredients of the algorithm are a digital representation of the quantum state, and a decomposition of the measurement operator in a basis of operators with known discrete spectra. We then show how this algorithm can be combined with (a) Hamiltonian evolution to make quantum simulations efficient, (b) the Newton–Raphson method based solution of matrix inverse to efficiently solve linear simultaneous equations, and (c) Chebyshev expansion of matrix exponentials to efficiently evaluate thermal expectation values. The general strategy may be useful in solving many other linear algebra problems efficiently.

arXiv:1710.01984•International Journal of Quantum Information•Sep 1, 2018•4 citations

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

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders

Vishnu Iyer, Siddhartha Jain, Stephen Jordan +1 more

We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of $SU(n)$, where $n \ge 2$ is constant. For dimension $N$ and error $ε$, the number of quantum gates in our circuits is polynomial in $\log(N)$ and $\log(1/ε)$. Our construction relies on the Jordan-Schwinger representation, which allows us to realize irreps of $SU(n)$ in the Hilbert space of $n$ quantum harmonic oscillators. Together with a recent efficient quantum Hermite transform, which allows us to map the computational basis states to the eigenstates of the quantum harmonic oscillator, this allows us to implement these irreps efficiently. Our quantum circuits can be used to construct explicit Ramanujan quantum expanders, a longstanding open problem. They can also be used to fast-forward the evolution of certain quantum systems.

quant-pharXiv:2602.15180•Feb 18, 2026•0 citations

Logarithmic-depth quantum state preparation of polynomials

Baptiste Claudon, Alexis Lucas, Jean-Philip Piquemal +2 more

Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree$-d$ polynomial, using circuits with logarithmic depth in the number $n$ of qubits and only $\mathcal O(n)$ ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only $n$ terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state $|1\rangle$. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using $14$ qubits and more than $500$ primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.

quant-pharXiv:2603.16527•Mar 18, 2026•0 citations
Quantum Kravchuk Transform using su(2)\mathfrak{su}(2)su(2) fast-forwarding
We present a quantum algorithm for the Kravchuk transform that scales logarithmically in both the dimension and the inverse of the error parameter. The quantum Kravchuk transform maps computational basis states to states with amplitudes proportional to Kravchuk functions. We achieve this by combining two key techniques: the structural relationship between the Kravchuk transform and the Lie algebras su(2)\mathfrak{su}(2)su(2), and a recent fast-forwarding simulation method for su(2)\mathfrak{su}(2)su(2) operators in the oscillator representation. More precisely, we first establish the map from Kravchuk transform in computational basis to su(2)\mathfrak{su}(2)su(2) in Fock basis. Then built on this connection, we apply the fast-forwarding to achieve an efficient quantum Kravchuk transform.
We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that is polylogarithmic in the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted as the Gaussian analogue of the Fourier transform. Our algorithm is based on a method to exponentially fast-forward the evolution of the quantum harmonic oscillator, giving a simulation algorithm with nearly optimal circuit complexity for a fundamental Hamiltonian more than four decades after Feynman posed the simulation of quantum physics as an application of quantum computers.
A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states ∑kαk∣k⟩\sum_k α_{k} \ket{k}∑k​αk​∣k⟩ coherently to a basis of normalized univariate polynomials orthogonal with respect to a probability measure μ(x)μ(x)μ(x). We provide new discrete and continuous QOPTs for polynomial families in the Askey scheme extending the results for the quantum Hermite transform (Jain et al., STOC'26). Our efficient QOPT algorithms require time O(polylog(N,1/ε))O(\text{polylog}(N, 1/ε))O(polylog(N,1/ε)), where NNN is the grid size and εεε is the error, for the discrete Charlier, Meixner and Krawtchouk transforms and for the integer-order Laguerre transform in the continuous setting. The efficient QOPTs are obtained by uncovering the links between Askey scheme polynomials and Gaussian quantum optical gates and developing a compilation framework for SU(2)SU(2)SU(2) and SU(1,1)SU(1,1)SU(1,1) optical gates on Cartesian grids extending the framework developed by Iyer et al. (arXiv:2602.15180). Further, we reduce the continuous Jacobi transform to the discrete Hahn transform and provide an O ⁣(Npolylog⁡((N+α+β+1)/ε))O\!\left(N\operatorname{polylog}((N+α+β+1)/ε)\right)O(Npolylog((N+α+β+1)/ε))-time Hahn transform, a quadratic speedup over the naive implementation. This is based on a more efficient compilation of the Clebsch--Gordan transform for coupling SU(2)\mathrm{SU}(2)SU(2) representations with spins (j1,j2)(j_{1}, j_{2})(j1​,j2​). Finally, we develop a new framework for Laguerre transforms for all orders ν>0ν>0ν>0 by fast-forwarding the corresponding radial oscillator using a 3-term chirp decomposition and an efficient algorithm for the Quantum Hankel Transform on a logarithmic grid.
We present an algorithm for measurement of [Formula: see text]-local operators in a quantum state, which scales logarithmically both in the system size and the output accuracy. The key ingredients of the algorithm are a digital representation of the quantum state, and a decomposition of the measurement operator in a basis of operators with known discrete spectra. We then show how this algorithm can be combined with (a) Hamiltonian evolution to make quantum simulations efficient, (b) the Newton–Raphson method based solution of matrix inverse to efficiently solve linear simultaneous equations, and (c) Chebyshev expansion of matrix exponentials to efficiently evaluate thermal expectation values. The general strategy may be useful in solving many other linear algebra problems efficiently.
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.
We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of SU(n)SU(n)SU(n), where n≥2n \ge 2n≥2 is constant. For dimension NNN and error εεε, the number of quantum gates in our circuits is polynomial in log⁡(N)\log(N)log(N) and log⁡(1/ε)\log(1/ε)log(1/ε). Our construction relies on the Jordan-Schwinger representation, which allows us to realize irreps of SU(n)SU(n)SU(n) in the Hilbert space of nnn quantum harmonic oscillators. Together with a recent efficient quantum Hermite transform, which allows us to map the computational basis states to the eigenstates of the quantum harmonic oscillator, this allows us to implement these irreps efficiently. Our quantum circuits can be used to construct explicit Ramanujan quantum expanders, a longstanding open problem. They can also be used to fast-forward the evolution of certain quantum systems.
Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree−d-d−d polynomial, using circuits with logarithmic depth in the number nnn of qubits and only O(n)\mathcal O(n)O(n) ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only nnn terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state ∣1⟩|1\rangle∣1⟩. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using 141414 qubits and more than 500500500 primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.