The query complexity of order-finding |
| |
Authors: | Richard Cleve |
| |
Affiliation: | Department of Computer Science, University of Calgary, Calgary, Alba., Canada T2N 1N4 |
| |
Abstract: | We consider the problem where π is an unknown permutation on {0,1,…,2n−1}, y0{0,1,…,2n−1}, and the goal is to determine the minimum r>0 such that πr(y0)=1. Information about π is available only via queries that yield πx(y) from any x{0,1,…,2m−1} and y{0,1,…,2n−1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|