On the energy landscape of symmetric quantum signal processing
- URL: http://arxiv.org/abs/2110.04993v2
- Date: Thu, 27 Oct 2022 00:54:15 GMT
- Title: On the energy landscape of symmetric quantum signal processing
- Authors: Jiasu Wang, Yulong Dong, Lin Lin
- Abstract summary: 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.
- Score: 1.5301252700705212
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Symmetric quantum signal processing provides a parameterized representation
of a real polynomial, which can be translated into an efficient quantum circuit
for performing a wide range of computational tasks on quantum computers. For a
given polynomial $f$, the parameters (called phase factors) can be obtained by
solving an optimization problem. However, the cost function is non-convex, and
has a very complex energy landscape with numerous global and local minima. It
is therefore surprising that the solution can be robustly obtained in practice,
starting from a fixed initial guess $\Phi^0$ that contains no information of
the input polynomial. To investigate this phenomenon, we first explicitly
characterize all the global minima of the cost function. We then prove that one
particular global minimum (called the maximal solution) belongs to a
neighborhood of $\Phi^0$, on which the cost function is strongly convex under
the condition ${\left\lVert f\right\rVert}_{\infty}=\mathcal{O}(d^{-1})$ with
$d=\mathrm{deg}(f)$. Our result provides a partial explanation of the
aforementioned success of optimization algorithms.
Related papers
- 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) - 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) - Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss [16.91814406135565]
We conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of $N$ convex, Lipschitz functions.
We prove that quantum algorithms must take $tildeOmega(sqrtNepsilon-2/3)$ queries to a first order quantum oracle.
arXiv Detail & Related papers (2024-02-20T06:23:36Z) - 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) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization.
In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
arXiv Detail & Related papers (2023-01-10T20:43:29Z) - Dueling Convex Optimization with General Preferences [85.14061196945599]
We address the problem of emph optimization with dueling feedback, where the goal is to minimize a convex function given a weaker form of emphilonling feedback.
Our main contribution is an efficient algorithm with convergence $smashwidetilde O(epsilon-4p)$ for a smooth convex objective function, and an efficient $smashwidetilde O(epsilon-2p) when the objective is smooth and convex.
arXiv Detail & Related papers (2022-09-27T11:10:41Z) - Infinite quantum signal processing [1.3614427997190908]
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.
arXiv Detail & Related papers (2022-09-21T07:50:26Z) - 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) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - 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)
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.