Complementary polynomials in quantum signal processing

• URL: http://arxiv.org/abs/2406.04246v1
• Date: Thu, 6 Jun 2024 16:47:11 GMT
• Title: Complementary polynomials in quantum signal processing
• Authors: Bjorn K. Berntson, Christoph Sünderhauf,
• Abstract summary: To implement a given $P$, one must first construct a corresponding complementary $Q$. Existing approaches to this problem employ numerical methods that are not amenable to explicit error analysis. We present a new approach to complementarys using complex analysis.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum signal processing is a framework for implementing polynomial functions on quantum computers. To implement a given polynomial $P$, one must first construct a corresponding complementary polynomial $Q$. Existing approaches to this problem employ numerical methods that are not amenable to explicit error analysis. We present a new approach to complementary polynomials using complex analysis. Our main mathematical result is a contour integral representation for a canonical complementary polynomial. The integral representation on the unit circle has a particularly simple and efficacious Fourier analytic interpretation, which we use to develop a Fast Fourier Transform-based algorithm for the efficient calculation of $Q$ in the monomial basis with explicit error guarantees. Numerical evidence that our algorithm outperforms the state-of-the-art optimization-based method for computing complementary polynomials is provided.

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)
• Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$ [8.264300525515097]
  Quantum signal processing and quantum value transformation are powerful tools to implement transformations of block-encoded matrices on quantum computers. We propose a framework which realizes multiples simultaneously from a block-encoded input. We also give an algorithm to construct the quantum circuit that gives the desired transformation.
  arXiv  Detail & Related papers  (2024-07-19T14:15:20Z)
• Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networks [40.137069931650444]
  Tropical geometry has recently found several applications in the analysis of neural networks with piecewise linear activation functions. This paper presents a new look at the problem of tropical division and its application to the simplification of neural networks.
  arXiv  Detail & Related papers  (2023-06-27T02:26:07Z)
• GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
  We present a novel approach to non-cube optimization with certificates, which handles smooth functions on the hypercube or on the torus. By exploiting the regularity of the target function intrinsic in the decay of its spectrum, we allow at the same time to obtain precise certificates and leverage the advanced and powerful neural networks.
  arXiv  Detail & Related papers  (2023-06-26T09:42:59Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• 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)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• Quantum Gradient Algorithm for General Polynomials [5.008814514502094]
  Gradient-based algorithms, popular strategies to optimization problems, are essential for many modern machine-learning techniques. We propose a quantum gradient algorithm for optimizing numericals with the dressed amplitude. For the potential values in high-dimension optimizations, this quantum algorithm is supposed to facilitate gradient-optimizations.
  arXiv  Detail & Related papers  (2020-04-23T11:28:45Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
  arXiv  Detail & Related papers  (2020-02-22T01:03:33Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.