Generalized Quantum Signal Processing
- URL: http://arxiv.org/abs/2308.01501v2
- Date: Fri, 19 Jan 2024 03:11:07 GMT
- Title: Generalized Quantum Signal Processing
- Authors: Danial Motlagh and Nathan Wiebe
- Abstract summary: We present a Generalized Quantum Signal Processing approach, employing general SU(2) rotations as our signal processing operators.
Our approach lifts all practical restrictions on the family of achievable transformations, with the sole remaining condition being that $|P|leq 1$.
In cases where only $P$ is known, we provide an efficient GPU optimization capable of identifying in under a minute of time, a corresponding $Q$ for degree on the order of $107$.
- Score: 0.6768558752130311
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum Signal Processing (QSP) and Quantum Singular Value Transformation
(QSVT) currently stand as the most efficient techniques for implementing
functions of block encoded matrices, a central task that lies at the heart of
most prominent quantum algorithms. However, current QSP approaches face several
challenges, such as the restrictions imposed on the family of achievable
polynomials and the difficulty of calculating the required phase angles for
specific transformations. In this paper, we present a Generalized Quantum
Signal Processing (GQSP) approach, employing general SU(2) rotations as our
signal processing operators, rather than relying solely on rotations in a
single basis. Our approach lifts all practical restrictions on the family of
achievable transformations, with the sole remaining condition being that
$|P|\leq 1$, a restriction necessary due to the unitary nature of quantum
computation. Furthermore, GQSP provides a straightforward recursive formula for
determining the rotation angles needed to construct the polynomials in cases
where $P$ and $Q$ are known. In cases where only $P$ is known, we provide an
efficient optimization algorithm capable of identifying in under a minute of
GPU time, a corresponding $Q$ for polynomials of degree on the order of $10^7$.
We further illustrate GQSP simplifies QSP-based strategies for Hamiltonian
simulation, offer an optimal solution to the $\epsilon$-approximate fractional
query problem that requires $O(\frac{1}{\delta} +
\log(\large\frac{1}{\epsilon}))$ queries to perform where $O(1/\delta)$ is a
proved lower bound, and introduces novel approaches for implementing bosonic
operators. Moreover, we propose a novel framework for the implementation of
normal matrices, demonstrating its applicability through the development of a
new convolution algorithm that runs in $O(d \log{N} + \log^2N)$ 1 and 2-qubit
gates for a filter of lengths $d$.
Related papers
- Parallel Quantum Signal Processing Via Polynomial Factorization [3.1981483719988235]
We develop a Quantum Parallel Signal Processing algorithm.
Our algorithm parallelizes the computation of $texttr (P(rho)$ over $k$ systems and reduces the query depth to $d/k$, thus enabling a family of time-space tradeoffs for QSP.
This furnishes a property estimation suitable for quantum computers, and is realized at the expense of increasing the number of measurements by factor $O(textpoly(d) 2(k) )$.
arXiv Detail & Related papers (2024-09-27T17:54:30Z) - Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
Quantum signal processing (QSP) provides a systematic framework for implementing a transformation of a linear operator.
Recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel.
Our algorithm implements a probabilistic mixture of randomizeds, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual.
arXiv Detail & Related papers (2024-09-05T17:56:51Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - High-Entanglement Capabilities for Variational Quantum Algorithms: The Poisson Equation Case [0.07366405857677226]
This research attempts to resolve problems by utilizing the IonQ Aria quantum computer capabilities.
We propose a decomposition of the discretized equation matrix (DPEM) based on 2- or 3-qubit entanglement gates and is shown to have $O(1)$ terms with respect to system size.
We also introduce the Globally-Entangling Ansatz which reduces the parameter space of the quantum ansatz while maintaining enough expressibility to find the solution.
arXiv Detail & Related papers (2024-06-14T16:16:50Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.
Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.
We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
arXiv Detail & Related papers (2024-05-14T15:28:37Z) - Polynomial-time Solver of Tridiagonal QUBO and QUDO problems with Tensor Networks [41.94295877935867]
We present an algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and Quadratic Unconstrained Discrete Optimization (QUDO) problems with one-neighbor interactions.
Our method is based on the simulation of a quantum state to which we will apply an imaginary time evolution and perform a series of partial traces to obtain the state of maximum amplitude.
arXiv Detail & Related papers (2023-09-19T10:45:15Z) - Quantum Signal Processing, Phase Extraction, and Proportional Sampling [0.0]
Quantum Signal Processing (QSP) is a technique that can be used to implement a transformation $P(x)$ applied to the eigenvalues of a unitary $U$.
We show that QSP can be used to tackle a new problem, which we call phase extraction, and that this can be used to provide quantum speed-up for proportional sampling.
arXiv Detail & Related papers (2023-03-20T13:05:29Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - K-sparse Pure State Tomography with Phase Estimation [1.2183405753834557]
Quantum state tomography (QST) for reconstructing pure states requires exponentially increasing resources and measurements with the number of qubits.
QST reconstruction for any pure state composed of the superposition of $K$ different computational basis states of $n$bits in a specific measurement set-up is presented.
arXiv Detail & Related papers (2021-11-08T09:43:12Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z)
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.