An efficient framework to utilize Grover search

Shigeru, Yamashita, Masaki Masaki +1 more

This paper proposes an efficient framework to utilize quantum search practically.To the best of our knowledge,this is the first paper to show a concrete usage of quantum search in general programming.In our framework,we can utilize a quantum computer as a coprocessor to speed-up some parts of a program that runs on a classical computer.To do so,we propose several new ideas and techniques,such as a practical method to design a large quantum circuits for search problems and an efficient quantum comparator.

Byung-Soo Choi

Shigeru Yamashita

It is widely believed that quantum computers (if realized) will be more powerful than today’s computers from the viewpoint of computational complexity . However, it is not obvious how to utilize quantum computers in practical situations. For practical purposes, a Grover search may be one of the most promising quantum algorithms known so far. Thus, in this paper, we propose an efficient framework where we can use Grover search for general programming. Our framework has the following steps. (1) A programmer writes a program by using standard C++ programming language. (2) Some if expressions within for loops in the C++ source code are chosen as candidates to be performed as a Grover search on a quantum computer. (3) The framework automatically generates a corresponding quantum circuit for each Grover search chosen in (2). Unlike the existing quantum circuit design methods, we can treat large problems in our quantum circuit design. (4) By evaluating the number of primitive quantum gates in the quantum circuit generated in (3), the framework determines whether the processing time of the quantum circuit is faster than the processing time of the corresponding if expression on a classical computer. If the framework determines that the quantum circuit is faster, it generates some interface source codes for a classical computer. Thus, in our framework, a programmer can use a Grover search with almost no effort.

Iram Fatima,Syed Khaldoon Khurshid,Fareed Ud Din Mehmood Jafri,Sanam Shoukat,Haroon Bashir

茂 山下

F. Masafumi Toyama, W. van Dijk

In the Grover-type quantum search process a search operator is iteratively applied, say, k times, on the initial uniform superposition database state. We present an additive decomposition scheme such that the iteration process is expressed, in the computational space, as a linear combination of k operators, each of which consists of a single Grover-search followed by an overall phase-rotation. The value of k and the rotation phase are the same as those determined in the framework of the search with certainty. We discuss how the additive form can be effectively utilized and we propose an alternative gate that realizes the same outcome as the iterative search.