An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

• URL: http://arxiv.org/abs/2301.09218v2
• Date: Thu, 11 May 2023 11:43:44 GMT
• Title: An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
• Authors: Andris Ambainis and Aleksandrs Belovs
• Abstract summary: 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.
• Score: 79.43134049617873
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While it is known that there is at most a polynomial separation between quantum query complexity and the polynomial degree for total functions, the precise relationship between the two is not clear for partial functions. In this paper, we demonstrate an exponential separation between exact polynomial degree and approximate quantum query complexity for a partial Boolean function. For an unbounded alphabet size, we have a constant versus polynomial separation.

Related papers

• Separations in query complexity for total search problems [0.0]
  We study the query complexity analogue of the class TFNP of total search problems. We give a way to convert partial functions to total search problems under certain settings. We also give a way to convert search problems back into partial functions.
  arXiv  Detail & Related papers  (2024-10-21T17:51:24Z)
• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  We establish a continuity relation between the topological space of quantum channels and the quotient of the complex Stiefel manifold. The established relation can be applied to various quantum optimization problems.
  arXiv  Detail & Related papers  (2024-08-19T09:15:54Z)
• Complementary polynomials in quantum signal processing [0.0]
  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.
  arXiv  Detail & Related papers  (2024-06-06T16:47:11Z)
• Learning quantum Hamiltonians at any temperature in polynomial time with Chebyshev and bit complexity [3.2634122554914]
  We consider the problem of learning local quantum Hamiltonians given copies of their state at a known inverse temperature. Our main technical contribution is a new flat approximation of the exponential function based on the Chebyshev expansion.
  arXiv  Detail & Related papers  (2024-02-08T10:42:47Z)
• The polygon relation and subadditivity of entropic measures for discrete and continuous multipartite entanglement [0.6759148939470331]
  We study the relationship between the polygon relation and the subadditivity of entropy. Our work provides a better understanding of the rich structure of multipartite states.
  arXiv  Detail & Related papers  (2024-01-04T05:09:37Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  We establish an abstraction of on-the-fly determinization of finite-state automata and demonstrate how it can be applied to bound the automatons. A special case of our findings is that automata with many non-deterministic transitions almost always admit a determinization of complexity.
  arXiv  Detail & Related papers  (2023-08-27T11:51:27Z)
• Polynomial decompositions with invariance and positivity inspired by tensors [1.433758865948252]
  This framework has been recently introduced for tensor decompositions, in particular for quantum many-body systems. We define invariant decompositions of structures, approximations, and undecidability to reals. Our work sheds new light on footings by putting them on an equal footing with tensors, and opens the door to extending this framework to other product structures.
  arXiv  Detail & Related papers  (2021-09-14T13:30:50Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• 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.