The problem of finding lower and upper bounds on multivariate homogeneous polynomials is both difficult and important given its applications to questions ranging from dynamical stability in complex potential landscapes to data analysis. From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and the largest eigenvalues of the coefficient tensor corresponding to the given polynomial. Standard approaches outlined in the literature amount to running nonlinear iterations in search for the optimal rays along which the growth of the polynomial is fastest or slowest. Unlike the case of matrices (or their corresponding multivariate quadratic forms) convergence of such algorithms for higher-rank tensors is capricious due to the complex topography of polynomial objective functions. In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on polynomials. The original polynomial is replaced by an operator acting in a suitably chosen (large) space of states, such that in an appropriate "classical" limit this operator approaches the original polynomial expression made of commutative variables. As a result, approximating the smallest and largest eigenvalues of the coefficient tensor, and thus finding bounds on polynomials, amounts to diagonalizing the resulting quantum operator, represented as a large matrix, and then inspecting the smallest and largest eigenvalues of this matrix. This approach is then successfully applied to standard test examples from tensor eigenvalue literature and other problems of interest in mathematical physics including Strichartz-type inequalities.
The problem of finding lower and upper bounds on multivariate homogeneous polynomials is both difficult and important given its applications to questions ranging from dynamical stability in complex potential landscapes to data analysis. From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and the largest eigenvalues of the coefficient tensor corresponding to the given polynomial. Standard approaches outlined in the literature amount to running nonlinear iterations in search for the optimal rays along which the growth of the polynomial is fastest or slowest. Unlike the case of matrices (or their corresponding multivariate quadratic forms) convergence of such algorithms for higher-rank tensors is capricious due to the complex topography of polynomial objective functions. In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on polynomials. The original polynomial is replaced by an operator acting in a suitably chosen (large) space of states, such that in an appropriate "classical" limit this operator approaches the original polynomial expression made of commutative variables. As a result, approximating the smallest and largest eigenvalues of the coefficient tensor, and thus finding bounds on polynomials, amounts to diagonalizing the resulting quantum operator, represented as a large matrix, and then inspecting the smallest and largest eigenvalues of this matrix. This approach is then successfully applied to standard test examples from tensor eigenvalue literature and other problems of interest in mathematical physics including Strichartz-type inequalities.
Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with A,B symmetric, and B positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when B is invertible, B−1A is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when B is singular, any quantum algorithm uses at least Ω(n) queries to compute the eigenvalues, where n is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.
We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let f,g1,…,gm be real polynomials in n variables and f⋆ the infimum of f over the semialgebraic set S(g)={x:gi(x)≥0}. Let λk be the value of the order-k Lasserre relaxation. Assume either (i) f⋆=λk and the optimum is attained in the ℓ1-ball of radius 1/2, or (ii) S(g) lies in the simplex {x≥0:∑jxj≤1/2}, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates λk to accuracy ε>0 with runtime, for fixed k, O(nkε−4+nk/2ε−5),O(sg[nkε−4+(nk+∑i=1mnk−di)1/2ε−5]), where sg bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as O(n3kpoly(1/ε)) even in the unconstrained case. As an example, we obtain an O(nε−4+nε−5) quantum algorithm for portfolio optimization, improving over the classical O(nω+1log(1/ε)) bound with ω≈2.373.
Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.
Spectral methods are a leading approach for tensor PCA with a ``spiked" Gaussian tensor. The methods use the spectrum of a linear operator in a vector space with exponentially high dimension and in Ref. 1 it was shown that quantum algorithms could then lead to an exponential space saving as well as a quartic speedup over classical. Here we show how to accelerate both classical and quantum algorithms quadratically, while maintaining the same quartic separation between them. That is, our classical algorithm here is quadratically faster than the original classical algorithm, while the quantum algorithm is eigth-power faster than the original classical algorithm. We then give a further modification of the quantum algorithm, increasing its speedup over the modified classical algorithm to the sixth power. We only prove these speedups for detection, rather than recovery, but we give a strong plausibility argument that our algorithm achieves recovery also.
Note added: After this paper was prepared, A. Schmidhuber pointed out to me Ref. 3. This improves the best existing bounds on the spectral norm of a certain random operator. Because the norm of this operator enters into the runtime, with this improvement on the norm, we no longer have a provable polynomial speedup. Our results are phrased in terms of certain properties of the spectrum of this operator (not merely the largest eigenvalue but also the density of states). So, if these properties still hold, the speedup still holds. Rather than modify the paper, I have left it unchanged but added a section at the end discussing the needed property of density of states and considering for which problems (there are several problems for which this kind of quartic quantum speedup has been used and the techniques here will likely be applicable to several of them) the property is likely to hold.
Polynomial transformations are basic primitives in quantum algorithms: quantum signal processing and singular value transformation compile univariate polynomials into circuits with query complexity essentially set by degree. Multivariable transformations of noncommuting matrices, however, lack a comparable synthesis theory. We develop a complete constructive theory under joint block access for all polynomials contractive on the prescribed matrix domain. Given a compact finite-state description of a degree-D polynomial P and 0<τ<1, we synthesize P with (1+τ)-optimal normalization using O(D/τ) queries, and exactly D under row-block access, matching a degree lower bound. The complete circuit realization is classically computable in polynomial time with polylogarithmic dependence on accuracy. The key to our construction is a finite algorithmic Schur--Agler theorem: the coefficient recurrence defines a polynomial-dimensional continuation space supporting a complete semidefinite certificate for contractivity on the prescribed domain. Factoring this certificate yields the contractive realization underlying the query algorithm.
Beyond matrix transformations, our framework lifts multivariable polynomial synthesis to quantum channel transformations. Given coherent Kraus access K={Ka}a, we synthesize any finite jointly contractive family of noncommutative polynomial maps K↦{Fb(K)}b as completely positive operations, allowing coherent interference among Kraus histories. Furthermore, channel-level transformations specified by causal Choi data can be synthesized explicitly as fixed-order quantum combs. Collectively, these results point to a broader program: multivariable approximation as a language for multi-operator quantum algorithms and higher-order quantum information processing.
In this paper, we present a direct quantum adaptation of the classical shifted power method. The method is very similar to the iterative phase estimation algorithm; however, it does not require any initial estimate of an eigenvector and as in the classical case its convergence (the success probability) is directly related to the eigengap. If the amount of the gap is polynomial in the number of qubits n, then the algorithm can converge to the dominant eigenvalue in O(poly(n)) time. The method can be potentially used in any eigenvalue related problems and to find minimum/maximum of a quantum state in lieu of Grover's search algorithm. In addition, if the solution space of an optimization problem with n parameters can be encoded as the eigenspace of an 2n dimensional unitary operator in O(poly(n)) time, then the solution for such a problem can be found in O(poly(n)) if the eigengap is polynomial. As an example, using the quantum gates, we show how to generate the solution space of the quadratic unconstrained binary optimization as eigenvectors of a diagonal unitary matrix and find the solution for the problem.
Quantum subspace diagonalization methods are an exciting new class of algorithms for solving large-scale eigenvalue problems using quantum computers. Unfortunately, these methods require the solution of an ill-conditioned generalized eigenvalue problem, with a matrix pencil corrupted by a nonnegligible amount of noise that is far above the machine precision. Despite pessimistic predictions from classical worst-case perturbation theories, these methods can perform reliably well if the generalized eigenvalue problem is solved using a standard truncation strategy. By leveraging and advancing classical results in matrix perturbation theory, we provide a theoretical analysis of this surprising phenomenon, proving that under certain natural conditions, a quantum subspace diagonalization algorithm can accurately compute the smallest eigenvalue of a large Hermitian matrix. We give numerical experiments demonstrating the effectiveness of the theory and providing practical guidance for the choice of truncation level. Our new results can also be of independent interest to solving eigenvalue problems outside the context of quantum computation.