Polynomial representation of general partial Boolean functions with a single quantum query

• URL: http://arxiv.org/abs/2112.12416v3
• Date: Tue, 10 Oct 2023 03:09:26 GMT
• Title: Polynomial representation of general partial Boolean functions with a single quantum query
• Authors: Xu Guoliang, Qiu Daowen
• Abstract summary: Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query. This paper proves and discovers three new results.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Until recent years, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Establishing a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one; (2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query; (3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm. Essentially, the first discovery represent a step forward for a fundamental conclusion that the polynomial degree of partial Boolean functions with a single quantum query is one or two, and the last two results contribute a way for searching more nontrival partial Boolean functions that have quantum advantages.

Related papers

• Quantum advantage and lower bounds in parallel query complexity [0.0]
  We investigate quantum, randomized and deterministic (sequential) query complexities for total functions. We find that significantly larger separations between the parallel generalizations of these measures are possible. We develop a new technique for deriving parallel quantum lower bounds from sequential upper bounds.
  arXiv  Detail & Related papers  (2024-10-03T16:50:00Z)
• Quantum and Classical Communication Complexity of Permutation-Invariant Functions [4.410515368583671]
  We show that the quantum and randomized communication complexity of the permutation-invariant Boolean functions are quadratically equivalent (up to a logarithmic factor) Our results extend a recent line of research regarding query complexity citeAA14, Cha19, BCG+20 to communication complexity.
  arXiv  Detail & Related papers  (2023-12-31T11:07:49Z)
• 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)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• On the Fine-Grained Query Complexity of Symmetric Functions [4.956977275061968]
  This paper explores a fine-grained version of the Watrous conjecture. It includes the randomized and quantum algorithms with success probabilities arbitrarily close to $1/2$.
  arXiv  Detail & Related papers  (2023-09-20T13:04:45Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• The power of qutrits for non-adaptive measurement-based quantum computing [0.0]
  We prove that quantum correlations enable the computation of all ternary functions using the generalised qutrit Greenberger-Horne-Zeilinger (GHZ) state as a resource and at most $3n-1$ qutrits. This yields a corresponding generalised GHZ type paradox for any ternary function that LHVs cannot compute.
  arXiv  Detail & Related papers  (2022-03-23T13:41:22Z)
• Characterization of exact one-query quantum algorithms (ii): for partial functions [0.2741266294612775]
  The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity.
  arXiv  Detail & Related papers  (2020-08-27T09:06:34Z)

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.