Efficient Quantum Algorithm for All Quantum Wavelet Transforms

• URL: http://arxiv.org/abs/2309.09350v2
• Date: Mon, 22 Apr 2024 15:48:58 GMT
• Title: Efficient Quantum Algorithm for All Quantum Wavelet Transforms
• Authors: Mohsen Bagherimehrab, Alan Aspuru-Guzik,
• Abstract summary: We develop a simple yet efficient quantum algorithm for executing any wavelet transform on a quantum computer. Our proposed quantum wavelet transforms could be used in quantum computing algorithms in a similar manner to their well-established counterpart, the quantum Fourier transform.
• Score: 0.08968838300743379
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Wavelet transforms are widely used in various fields of science and engineering as a mathematical tool with features that reveal information ignored by the Fourier transform. Unlike the Fourier transform, which is unique, a wavelet transform is specified by a sequence of numbers associated with the type of wavelet used and an order parameter specifying the length of the sequence. While the quantum Fourier transform, a quantum analog of the classical Fourier transform, has been pivotal in quantum computing, prior works on quantum wavelet transforms~(QWTs) were limited to the second and fourth order of a particular wavelet, the Daubechies wavelet. Here we develop a simple yet efficient quantum algorithm for executing any wavelet transform on a quantum computer. Our approach is to decompose the kernel matrix of a wavelet transform as a linear combination of unitaries (LCU) that are compilable by easy-to-implement modular quantum arithmetic operations and use the LCU technique to construct a probabilistic procedure to implement a QWT with a \textit{known} success probability. We then use properties of wavelets to make this approach deterministic by a few executions of the amplitude amplification strategy. We extend our approach to a multilevel wavelet transform and a generalized version, the packet wavelet transform, establishing computational complexities in terms of three parameters: the wavelet order $M$, the dimension $N$ of the transformation matrix, and the transformation level $d$. We show the cost is logarithmic in $N$, linear in $d$ and superlinear in $M$. Moreover, we show the cost is independent of $M$ for practical applications. Our proposed quantum wavelet transforms could be used in quantum computing algorithms in a similar manner to their well-established counterpart, the quantum Fourier transform.

Related papers

• Quantum-Inspired Algorithms beyond Unitary Circuits: the Laplace Transform [0.0]
  Quantum-inspired algorithms can deliver substantial speedups over classical state-of-the-art methods.<n>We introduce a tensor-network approach to compute the discrete Laplace transform, a non-unitary, aperiodic transform.<n>We demonstrate simulations up to $N=230$ input data points, with up to $260$ output data points, and quantify how bond dimension controls runtime and accuracy.
  arXiv  Detail & Related papers  (2026-01-25T07:19:56Z)
• Efficient Quantum Circuits for the Hilbert Transform [0.0]
  This letter presents a novel construction for a quantum Hilbert transform in polylogarithmic size and logarithmic depth for a signal of length $N$.<n>We generalize this algorithm to create any $d$-dimensional Hilbert transform in depth $O(dlog N)$.<n> Simulations demonstrate effectiveness for tasks such as power systems control and image processing, with exact agreement with classical results.
  arXiv  Detail & Related papers  (2026-01-15T22:02:32Z)
• Processing through encoding: Quantum circuit approaches for point-wise multiplication and convolution [1.3521721488318912]
  This paper introduces quantum circuit methodologies for pointwise multiplication and convolution of complex functions.<n>We describe an approach where multiple complex functions are encoded onto auxiliary qubits.<n>We discuss the simulation of these techniques, their integration into an extended verb|quantumaudio| package for audio signal processing, and present initial experimental validations.
  arXiv  Detail & Related papers  (2025-12-12T10:52:06Z)
• Variational noise mitigation in quantum circuits: the case of Quantum Fourier Transform [35.18016233072556]
  We perform numerical simulations for two qubits under both coherent and incoherent noise.<n>Our results show that the variational circuit can reproduce the QFT with higher fidelity in scenarios dominated by coherent noise.<n>This demonstrates the potential of the approach as an effective error-mitigation strategy for small- to medium-scale quantum systems.
  arXiv  Detail & Related papers  (2025-11-07T14:35:55Z)
• Quantum Wave Atom Transforms [0.5831737970661137]
  This paper constructs the first quantum algorithm for wavelet packet transforms with a tree structure, sometimes called wave atom transforms.<n>The result can be used to improve existing quantum algorithms for solving hyperbolic partial differential equations.
  arXiv  Detail & Related papers  (2025-07-14T19:03:22Z)
• Generalized tensor transforms and their applications in classical and quantum computing [0.0]
  We introduce a novel framework for Generalized Transforms (GTTs), constructed through an $n$-fold tensor product of an arbitrary $b times b$ unitary matrix $W$.<n>For quantum applications, our GTT-based algorithm achieves both gate complexity and circuit depth of $O(log_b N)$, where $N = bn$ denotes the length of the vector input.<n>We explore diverse applications of GTTs in quantum computing, including quantum state compression and transmission, function encoding and quantum digital signal processing.
  arXiv  Detail & Related papers  (2025-07-03T08:28:00Z)
• Public-Key Quantum Money and Fast Real Transforms [5.088380954865327]
  We propose a public-key quantum money scheme based on group actions and the Hartley transform. We show how to efficiently compute the serial number associated with a money state using a new algorithm based on continuous-time quantum walks.
  arXiv  Detail & Related papers  (2025-03-24T17:03:37Z)
• Hybrid Oscillator-Qubit Quantum Processors: Simulating Fermions, Bosons, and Gauge Fields [31.51988323782987]
  We develop a hybrid oscillator-qubit processor framework for quantum simulation of strongly correlated fermions and bosons. This framework gives exact decompositions of particle interactions as well as approximate methods based on the Baker-Campbell Hausdorff formulas. While our work focusses on an implementation in superconducting hardware, our framework can also be used in trapped ion, and neutral atom hardware.
  arXiv  Detail & Related papers  (2024-09-05T17:58:20Z)
• Simulating electronic structure on bosonic quantum computers [35.884125235274865]
  One of the most promising applications of quantum computing is the simulation of many-fermion problems. We show how an electronic structure Hamiltonian can be transformed into a system of qumodes through qubit-assisted fermion-to-qumode mapping.
  arXiv  Detail & Related papers  (2024-04-16T02:04:11Z)
• Learning with SASQuaTCh: a Novel Variational Quantum Transformer Architecture with Kernel-Based Self-Attention [0.464982780843177]
  We show that quantum circuits can efficiently express a self-attention mechanism through the perspective of kernel-based operator learning. In this work, we are able to represent deep layers of a vision transformer network using simple gate operations and a set of multi-dimensional quantum Fourier transforms. We analyze our novel variational quantum circuit, which we call Self-Attention Sequential Quantum Transformer Channel (SASTQuaCh), and demonstrate its utility on simplified classification problems.
  arXiv  Detail & Related papers  (2024-03-21T18:00:04Z)
• Variational-quantum-eigensolver-inspired optimization for spin-chain work extraction [39.58317527488534]
  Energy extraction from quantum sources is a key task to develop new quantum devices such as quantum batteries. One of the main issues to fully extract energy from the quantum source is the assumption that any unitary operation can be done on the system. We propose an approach to optimize the extractable energy inspired by the variational quantum eigensolver (VQE) algorithm.
  arXiv  Detail & Related papers  (2023-10-11T15:59:54Z)
• Noisy Tensor Ring approximation for computing gradients of Variational Quantum Eigensolver for Combinatorial Optimization [33.12181620473604]
  Variational Quantum algorithms have established their potential to provide computational advantage in the realm of optimization. These algorithms suffer from classically intractable gradients limiting the scalability. This work proposes a classical gradient method which utilizes the parameter shift rule but computes the expected values from the circuits using a tensor ring approximation.
  arXiv  Detail & Related papers  (2023-07-08T03:14:28Z)
• Efficient Light Propagation Algorithm using Quantum Computers [0.3124884279860061]
  One of the cornerstones in modern optics is the beam propagation algorithm. We show that the propagation can be performed as a quantum computation with $mathcalO(logN)$ single-controlled phase gates. We highlight the importance of the selection of suitable observables to retain the quantum advantage.
  arXiv  Detail & Related papers  (2023-03-13T11:47:09Z)
• Variational waveguide QED simulators [58.720142291102135]
  Waveguide QED simulators are made by quantum emitters interacting with one-dimensional photonic band-gap materials. Here, we demonstrate how these interactions can be a resource to develop more efficient variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-02-03T18:55:08Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• Quantum state preparation without coherent arithmetic [5.478764356647437]
  We introduce a versatile method for preparing a quantum state whose amplitudes are given by some known function.magnitude existing approaches. We use a template quantum eigenvalue transformation circuit to convert a low cost block encoding of the sine function into the desired function.
  arXiv  Detail & Related papers  (2022-10-26T17:48:31Z)
• Quantum Phase Processing and its Applications in Estimating Phase and Entropies [10.8525801756287]
  "quantum phase processing" can directly apply arbitrary trigonometric transformations to eigenphases of a unitary operator. Quantum phase processing can extract the eigen-information of quantum systems by simply measuring the ancilla qubit. We propose a new quantum phase estimation algorithm without quantum Fourier transform, which requires the fewest ancilla qubits and matches the best performance so far.
  arXiv  Detail & Related papers  (2022-09-28T17:41:19Z)
• 3-Qubit Circular Quantum Convolution Computation using Fourier Transform with Illustrative Examples [3.6296396308298795]
  We describe examples for calculating the 1-D circular convolution of signals represented by 3-qubit superpositions. The frequency characteristics of many linear time-invariant systems and filters are well known. The considered method of convolution can be used for these systems in quantum computation.
  arXiv  Detail & Related papers  (2022-05-11T18:53:43Z)
• An Introduction to Quantum Machine Learning for Engineers [36.18344598412261]
  Quantum machine learning is emerging as a dominant paradigm to program gate-based quantum computers. This book provides a self-contained introduction to quantum machine learning for an audience of engineers with a background in probability and linear algebra.
  arXiv  Detail & Related papers  (2022-05-11T12:10:52Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Logical Abstractions for Noisy Variational Quantum Algorithm Simulation [25.515765956985188]
  Existing quantum circuit simulators do not address the common traits of variational algorithms. We present a quantum circuit simulation toolchain based on logical abstractions targeted for simulating variational algorithms.
  arXiv  Detail & Related papers  (2021-03-31T17:20:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.