Characterizations of symmetrically partial Boolean functions with exact quantum query complexity
arXiv:1603.06505
Abstract
We give and prove an optimal exact quantum query algorithm with complexity for computing the promise problem (i.e., symmetric and partial Boolean function) defined as: for , for in the set , and it is undefined for the rest cases, where is even, is the Hamming weight of . The case of is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function has exact quantum 1-query complexity if and only if can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight and Hamming weight in the set for all odd . In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.
arXiv comment33 pages, comments are welcome. Some languages are further revised
References in corpus (14)
- Quantum Algorithms Revisited
- Quantum algorithms for algebraic problems
- An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
- A Limit on the Speed of Quantum Computation in Determining Parity
- Deutsch-Jozsa algorithm as a test of quantum computation
- Quantum computation with classical light: implementation of the Deutsch-Jozsa Algorithm
- Lower Bounds on Quantum Query Complexity
- Generalizations of the distributed Deutsch-Jozsa promise problem
- Exact quantum query complexity of EXACT and THRESHOLD
- Round elimination in exact communication complexity
- The Quantum Query Complexity of Algebraic Properties
- From Quantum Query Complexity to State Complexity
- Computing Boolean Functions: Exact Quantum Query Algorithms and Low Degree Polynomials
- Quantum Algorithm for Generalized Deutsch-Jozsa Problem