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.
Abstract Grover’s search algorithms, including various partial Grover searches (PGS), experience scaling problems when multiple solutions are sought, as the number of iterations increases with the number of solutions or marked states, making implementation more computationally expensive. Inspired by recent PGS algorithms for multi-solution searchers, this article proposes a scalable Grover quantum search algorithm, referred to as Bi-directional Multi-solution scalable Grover Search (BMGS), to efficiently search for an arbitrary number of solutions from an unstructured database. We introduced a novel multi-segment bidirectional search tactic with PGS across multiple equal segments of each state, starting from an initial state and multiple marked states in parallel, obviating the need for merge operations. We have shown in this work that for each solution our novel approach requires at most N(1−b⌊dkr⌋1) N 1 - 1 b ⌊ r dk ⌋ iterations (here, N=2r N = 2 r elements, k=log2b k = log 2 b , d is the number of equal segments on r qubits, and b is the branching factor). Our proposed BMGS algorithm is benchmarked against state-of-the-art Depth-First Grover Search (DFGS) and PGS implementations for an arbitrary number of solutions, ranging from 2 to 20 qubits, as a proof of concept. We also show that our BMGS requires fewer iterations for shallow quantum circuits and achieves an optimal O O ( sN s N ) average complexity for s solutions, when dk<r d k < r . The Qiskit Python implementation of the proposed BMGS algorithm is available on GitHub ( https://github.com/hafeezzwiz21/Multi-Solution-DFGS-BMGS ).
Grover's search algorithm has attracted great attention due to its quadratic speedup over classical algorithms in unsorted database search problems. However, Grover's algorithm is inefficient in multi-target search problems, except in the case of 1/4 of the data in the database satisfying the search conditions. Long presented a modified version of Grover's search algorithm by introducing a phase-matching condition that can search for the target state with a zero theoretical failure rate. In this work, we present an optimized exact multi-target search algorithm based on the modified Grover's algorithm by transforming the canonical diffusion operator to a more efficient diffusion operator, which can solve the multi-target search problem with a 100% success rate while requiring fewer gate counts and shallower circuit depth. After that, the optimized multi-target algorithm for four different items, including 2-qubit with 2 targets, 5-qubit with 2 targets, 5-qubit with 4 targets, and 6-qubit with 3 targets, are implemented on MindSpore framework. The experimental results show that, compared with Grover's algorithm and the modified Grover's algorithm, the proposed algorithm can reduce the quantum gate count by at least 21.1% and the depth of the quantum circuit by at least 11.4% and maintain a 100% success probability. Our code are available at https://github.com/mindsporelab/models/tree/master/research/arxiv_papers/GROVER-OP. Thanks for the support provided by MindSpore Community.