Infinite quantum signal processing
- URL: http://arxiv.org/abs/2209.10162v1
- Date: Wed, 21 Sep 2022 07:50:26 GMT
- Title: Infinite quantum signal processing
- Authors: Yulong Dong, Lin Lin, Hongkang Ni, Jiasu Wang
- Abstract summary: Quantum signal processing (QSP) represents a real scalar of degree $d$.
We show that QSP can be used to represent a large class of non-polynomial functions.
Our analysis reveals a surprising connection between the regularity of the target function and the decay properties of the factors.
- Score: 1.3614427997190908
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum signal processing (QSP) represents a real scalar polynomial of degree
$d$ using a product of unitary matrices of size $2\times 2$, parameterized by
$(d+1)$ real numbers called the phase factors. This innovative representation
of polynomials has a wide range of applications in quantum computation. When
the polynomial of interest is obtained by truncating an infinite polynomial
series, a natural question is whether the phase factors have a well defined
limit as the degree $d\to \infty$. While the phase factors are generally not
unique, we find that there exists a consistent choice of parameterization so
that the limit is well defined in the $\ell^1$ space. This generalization of
QSP, called the infinite quantum signal processing, can be used to represent a
large class of non-polynomial functions. Our analysis reveals a surprising
connection between the regularity of the target function and the decay
properties of the phase factors. Our analysis also inspires a very simple and
efficient algorithm to approximately compute the phase factors in the $\ell^1$
space. The algorithm uses only double precision arithmetic operations, and
provably converges when the $\ell^1$ norm of the Chebyshev coefficients of the
target function is upper bounded by a constant that is independent of $d$. This
is also the first numerically stable algorithm for finding phase factors with
provable performance guarantees in the limit $d\to \infty$.
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) - 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) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$.
In particular, we design global protocols for small set expansion, unique games, and PCP verification.
We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
arXiv Detail & Related papers (2024-02-29T01:35:46Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Generalized Quantum Signal Processing [0.6768558752130311]
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$.
arXiv Detail & Related papers (2023-08-03T01:51:52Z) - 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) - On the energy landscape of symmetric quantum signal processing [1.5301252700705212]
We prove that one particular global (called the global minimum) solution belongs to a $0$ on which the cost function is on which the cost function is a global.
We provide an explanation of a partial explanation of optimization algorithms.
arXiv Detail & Related papers (2021-10-11T04:16:48Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
We consider the global minimization of smooth functions based solely on function evaluations.
In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
arXiv Detail & Related papers (2020-12-22T12:59:30Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Quantum Legendre-Fenchel Transform [6.643082745560234]
We present a quantum algorithm to compute the discrete Legendre-Fenchel transform.
We show that our quantum algorithm is optimal up to polylogarithmic factors.
arXiv Detail & Related papers (2020-06-08T18:00:05Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions.
In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
arXiv Detail & Related papers (2020-02-10T23:23:04Z)
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.