6533b828fe1ef96bd1288253
RESEARCH PRODUCT
Enlarging the gap between quantum and classical query complexity of multifunctions
Taisia Mischenko-slatenkovaElena ShishovaAlina Vasilievasubject
CombinatoricsDiscrete mathematicsQuantum sortQuantum networkQuantum phase estimation algorithmQuantum algorithmSimon's problemQuantum informationQuantum computerQuantum complexity theoryMathematicsdescription
Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: Q UD (M′) ≤ N versus C UD (M′) ≥ 3N, and Q RD (M′′) = 1 versus N/2 + 1 ≤ C RD (M′′) ≤ N.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2013-07-01 | 2013 Ninth International Conference on Natural Computation (ICNC) |