Journal
QUANTUM INFORMATION PROCESSING
Volume 20, Issue 1, Pages -Publisher
SPRINGER
DOI: 10.1007/s11128-020-02975-0
Keywords
Quantum computation; Quantum query algorithm; Algorithm framework; Boolean function; Sum-of-squares representation
Funding
- National Natural Science Foundation of China [61876195, 61572532]
- Natural Science Foundation of Guangdong Province of China [2017B030311011]
Ask authors/readers for more resources
In quantum computation, designing an optimal exact quantum query algorithm for small input Boolean functions is a fundamental problem. The paper proposes a basic algorithm framework with three steps, although there are some intractable issues. The framework can be used to study quantum query models with low complexity.
In quantum computation, designing an optimal exact quantum query algorithm (i.e., a quantum decision tree algorithm) for any small input Boolean function is a fundamental and abstract problem. As we are aware, there is not a general method for this problem. Due to the fact that every Boolean function can be represented by a sum-of-squares of some multilinear polynomials, in this paper a primary algorithm framework is proposed with three basic steps: The first basic step is to find sum-of-squares representations of the Boolean function and its negation function; the second basic step is to construct a state which is assumed to be the final state of an optimal exact quantum query algorithm; the third basic step is to find each unitary operator in the undetermined algorithm. However, there still exist some intractable problems such that the algorithm framework may not be feasible in some cases, but it can be used to investigate the quantum query model with low complexity, such as Deutsch's problem, a five-bit symmetric Boolean function and the characterization of Boolean functions with exact quantum 2-query complexity.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available