Search

Recently, Kieu derived a new class of time–energy uncertainty relations, which is not only formal but also suitable for evaluating the speed limit of quantum dynamics. However, when this time–energy uncertainty relation was applied to study the quantum adiabatic Grover's search, some approximation had been done for reaching the right conclusion. That is, the final state being orthogonal to the initial state in this problem was assumed which may cause confusion, while the truth is that the overlap between these two states is indeed very small when the problem size is very big but not equal to zero exactly. In this paper, we modify the time–energy uncertainty relation of Kieu applied to two quantum evolutions of Grover's problem, and find that the resulting computational complexities match well with the previous works on this topic but without the need of making the assumption like that in the work of Kieu. [ABSTRACT FROM AUTHOR]

We propose a homomorphic search protocol based on quantum homomorphic encryption, in which a client Alice with limited quantum ability can give her encrypted data to a powerful but untrusted quantum server and let the server search for her without decryption. By outsourcing the interactive key-update process to a trusted key center, Alice only needs to prepare and encrypt her original data and to decrypt the ciphered search result in linear time. Besides, we also present a compact and perfectly secure quantum homomorphic evaluation protocol for Clifford circuits, where the decryption key can be calculated by Alice with polynomial overhead with respect to the key length. [ABSTRACT FROM AUTHOR]

Wei et al. have shown an accurate relation between the running time and the distance of the initial state and the final state of a local adiabatic evolution, that is, the adiabatic running time can be completely determined by the distance between the states. They also asked whether more complicated adiabatic evolutions have similar simple relation. We show that the adiabatic evolution with a general class of models of interpolation path proposed by Das et al. is just such another kind of adiabatic evolution which enjoys the relation discussed by Wei et al. [ABSTRACT FROM AUTHOR]

In this paper, we propose a quantum version of the differential cryptanalysis which offers a quadratic speedup over the existing classical one and show the quantum circuit implementing it. The quantum differential cryptanalysis is based on the quantum minimum/maximum-finding algorithm, where the values to be compared and filtered are obtained by calling the quantum counting algorithm. Any cipher which is vulnerable to the classical differential cryptanalysis based on counting procedures can be cracked more quickly under this quantum differential attack. [ABSTRACT FROM AUTHOR]

Due to the intrinsic similarity between partial adiabatic evolution and global adiabatic evolution, we generalize the partial adiabatic evolution proposed recently to its local adiabatic algorithm version. However, unlike that the local adiabatic evolution can speed up the global adiabatic algorithm quadratically, we prove that this new quantum algorithm presented here just has the same time complexity as the original partial adiabatic evolution. This may imply the optimality of the original partial adiabatic evolution or its generalized version. Additionally, a concrete example is given to further support our conclusion. [ABSTRACT FROM AUTHOR]

We consider the problem of finding one or more desired items out of an unsorted database. Patel has shown that if the database permits quantum queries, then mere digitization is sufficient for efficient search for one desired item. The algorithm, called factorized quantum search algorithm, presented by him can locate the desired item in an unsorted database using O( $$log_4N$$) queries to factorized oracles. But the algorithm requires that all the attribute values must be distinct from each other. In this paper, we discuss how to make a database satisfy the requirements, and present a quantum search engine based on the algorithm. Our goal is achieved by introducing auxiliary files for the attribute values that are not distinct, and converting every complex query request into a sequence of calls to factorized quantum search algorithm. The query complexity of our algorithm is O( $$log_4N$$) for most cases. [ABSTRACT FROM AUTHOR]