Quantum Algorithm for Element Distinctness
- PDF / 243,122 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 15 Downloads / 216 Views
Q
Quantum Algorithm for Element Distinctness
7. Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1997) 8. Nielsen, M., Chuang, I.: Quantum computation and quantum information. Cambridge University Press, Cambridge (2000) 9. Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
Quantum Algorithm for Element Distinctness 2004; Ambainis ANDRIS AMBAINIS Department of Computer Science, University of Latvia, Riga, Latvia Problem Definition In the element distinctness problem, one is given a list of N elements x1 ; : : : ; x N 2 f1; : : : ; mg and one must determine if the list contains two equal elements. Access to the list is granted by submitting queries to a black box, and there are two possible types of query. Value queries. In this type of query, the input to the black box is an index i. The black box outputs xi as the answer. In the quantum version of this model, the input is a quantum state that may be entangled with the workspace of the algorithm. The joint state of the query, the answer register, and the workspace may be repreP sented as i;y;z a i;y;z ji; y; zi, with y being an extra register which will contain the answer to the query and z being the workspace of the algorithm. The black box transforms P this state into i;y;z a i;y;z ji; (y + x i ) mod m; zi. The simplest particular case is if the input to the black box is of the P P form i a i ji; 0i. Then, the black box outputs i a i ji; x i i. That is, a quantum state consisting of the index i is transformed into a quantum state, each component of which contains xi together with the corresponding index i. Comparison queries. In this type of query, the input to the black box consists of two indices i, j. The black box gives one of three possible answers: “x i > x j ”, “x i < x j ” or “x i = x j ”. In the quantum version, the input is a quantum state consisting of basis states ji; j; zi, with i, j being two indices and z being algorithm’s workspace. There are several reasons why the element distinctness problem is interesting to study. First of all, it is related to sorting. Being able to sort x1 ,. . . ,xN enables one to solve the element distinctness by first sorting x1 ,. . . ,xN in increasing order. If there are two equal elements x i = x j , then they will be next one to another in the sorted list. Therefore, after one has sorted x1 ,. . . ,xN , one must only check
the sorted list to see if each element is different from the next one. Because of this relation, the element distinctness problem might capture some of the same difficulty as sorting. This has lead to a long line of research on classical lower bounds for the element distinctness problem (cf [6,8,15]. and many other papers). Second, the central concept of the algorithms for the element distinctness problem is the notion of a collision. This notion can be generalized in different ways, and its generalizations are useful for building quantum algorithms fo
Data Loading...
