Non-Linear Transformations of Quantum Amplitudes: Exponential Improvement, Generalization, and Applications
read the original abstract
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 $\epsilon$, with worst-case query complexity of $O(\log(N/\epsilon))$, in comparison to the $O(\sqrt{N}\log(N/\epsilon))$ 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 11 Pith papers
-
Quantum enhanced rare event discovery and sampling
A quantum algorithm discovers and samples rare events with optimal quantum scaling without prior knowledge of the events, yielding quadratic speedup for heavy-tailed systems and polynomial speedup for stationary processes.
-
Quantum analog-encoding for correlated Gaussian vectors and their exponentiation with application to rough volatility
Quantum algorithms are constructed for exact analog encoding of correlated Gaussian vectors and their exponentiation, achieving subcubic gate-depth complexity under polylogarithmic data-loading assumptions, with end-t...
-
Quantum analog-encoding for correlated Gaussian vectors and their exponentiation with application to rough volatility
Quantum algorithms prepare states for normalized correlated Gaussians and their exponentials with gate complexities scaling as Õ(‖Σ‖_F/λ_max ⋅ κ^1.5), achieving subcubic scaling in N for fractional processes and enab...
-
Efficient Quantum Algorithms for Higher-Order Coupled Oscillators
Quantum algorithms achieve polynomial advantage for synchronization estimation and super-polynomial advantage for no-phase-locking certification in higher-order simplicial Kuramoto models under stated assumptions.
-
Accelerating Inference for Multilayer Neural Networks with Quantum Computers
Quantum circuits for coherent multilayer neural network inference achieve quadratic to polylogarithmic speedups over classical methods depending on quantum data access models for inputs and weights.
-
QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
QKAN is a quantum algorithmic framework using block-encodings and QSVT to implement wide-and-shallow networks for quantum learning and compositional state preparation.
-
Schr\"odingerization based quantum algorithms for regularized Wasserstein proximal operators
Quantum algorithm solves regularized Wasserstein proximal operator via Schrödingerization of Cole-Hopf transformed heat equations with O(d N_x T log²(1/ε)) query complexity.
-
A Variational Quantum Algorithm for Nonlinear Finite Element Analysis of Hyperelastic Materials
A hybrid quantum-classical variational method using polynomial approximations to the energy functional enables finite element analysis of a 1D Neo-Hookean hyperelastic model on near-term quantum hardware.
-
Analog photonic simulator for large-scale transport
Continuous-variable photonic platform with 20,000-mode cluster state simulates advection transport equation, achieving relative errors of 0.8% and 0.92% on first- and second-order moments via homodyne readout.
-
Spectral methods: crucial for machine learning, natural for quantum computers?
Quantum computers may enable more natural manipulation of Fourier spectra in ML models via the Quantum Fourier Transform, potentially leading to resource-efficient spectral methods.
-
Unitaria: Quantum Linear Algebra via Block Encodings
Unitaria is a new open-source Python library that provides a high-level, composable interface for block encodings in quantum computing, enabling automatic circuit generation and classical simulation-based verification.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.