Maximum Searching Algorithm

An Introduction to Maximum Searching Algorithm

The algorithm for searching for the maximum value solves the problem of giving a data set and finding the element with the largest value. On a classic computer, to complete such a task requires a traversal of the database, the complexity is \(O(N)\). The quantum algorithm for searching for the maximum value is based on the Grover search algorithm. It was proposed by Christoph Durr and Peter Hoyer in January 1999 [A quantum algorithm for finding the minimum] (https://arxiv.org/pdf/quant-ph/9607014). Ashish Ahuja and Sanjiv Kapoor then made a better complexity analysis and yielded a bound than the original one of \(15\sqrt{N}\) [A Quantum Algorithm for finding the Maximum] (https://arxiv.org/abs/quant-ph/9911082v1). The complexity of the algorithm is \(O(\sqrt(N)),\) which is quadratic acceleration compared to the classical algorithm. Below we briefly introduce this quantum algorithm.

Basic idea of the quantum algorithm for searching the maximum value: For the search space A (a dataset), select one of the elements as the current maximum element randomly, and use the improved Grover search algorithm, that is, the Grover algorithm that does not know the number of target elements, to search for a larger element in A. Then replace the maximum element with the new one. The expected value of the total replacing times to get the maximum element is no more than \(O(log N)\). After finding the maximum element, the Grover algorithm cannot find a new element. Then the algorithm stops and outputs the maximum element.

Improved Grover search algorithm (Grover algorithm without knowing the number of target elements)

As can be seen from the above description, the improved Grover search algorithm plays an important role in the algorithm for searching for the maximum. We use the HiQ demo to implement an improved Grover search algorithm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def run_grover(eng, Dataset, oracle, threshold):
    """
    Args:
        eng (MainEngine): Main compiler engine to run Grover on.
        Dataset(list): The set to search for an element.
        oracle (function): The oracle black box, an n-qubit register. It is
         used to flip the relative phase for the correct bit string.
        threshold: The threshold, where the algorithm stops and outputs the local of the element in the database that is greater than the threshold.

    Returns:
        solution (list<int>): the location of Solution.
    """
    N = len(Dataset)
    n = math.ceil(math.log2(N))

    # number of maximum iterations we may run:
    num_it = int(math.sqrt(N)*9/4)

    # two arguments
    m = 1
    landa = 6/5

    # run i iterations
    i = 0
    while i<num_it:

        j = random.randint(0,int(m))
        x = eng.allocate_qureg(n)

        # start in uniform superposition, e.g. the index of all elements
        All(H) | x

        # prepare the oracle output qubit (the one that is flipped to indicate the solution. start in state 1/sqrt(2) * (|0> - |1>) s.t. a bit-flip turns into a (-1)-phase.
        oracle_out = eng.allocate_qubit()
        X | oracle_out
        H | oracle_out

         # run j iterations
        with Loop(eng, j):
            # oracle adds a (-1)-phase to the solution
            oracle(eng, x, Dataset,threshold, oracle_out)

            # reflection across uniform superposition
            with Compute(eng):
                All(H) | x
                All(X) | x
            with Control(eng, x[0:-1]):
                Z | x[-1]
            Uncompute(eng)

        # measure
        All(Measure) | x
        Measure | oracle_out

        # read the measure value
        k = 0
        xvalue = 0
        while k<n:
            xvalue = xvalue+int(x[k])*(2**k)
            k+ = 1

        # compare to threshold
        if Dataset[xvalue]>threshold:
            return xvalue
        m = m*landa
        i = i+1

For the function Oracle, the code for its implementation is as follows

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def oracle(eng, x, Dataset, n0, output):
  """
    Marks the solutions by flipping the output qubit,

    Args:
        eng (MainEngine): Main compiler engine the algorithm is being run on.
        x (Qureg): n-qubit quantum register Grover search is run on.
        Dataset(list): The dataset.
        n0: The threshold.
        output (Qubit): Output qubit to flip in order to mark the solution.
    """

    # The size relationship is represented by 0,1, which is set to 1 if greater than n0, otherwise 0.
    fun = [0]*len(Dataset)
    fun = [x-n0 for x in Dataset]
    fun = np.maximum(fun, 0)
    fun = np.minimum(fun, 1)
    a = sum(fun)
    n = math.ceil(math.log2(len(Dataset)))

    while a>0:
        num = [0]*n
        p = fun.tolist().index(1)
        fun[p] = 0
        i = 0
        a = a-1
        while p/2 != 0:
            num[i] = p % 2
            p = p//2
            i = i+1
        a1 = sum(num)
        num1 = num
        while a1>0:
            p = num1.index(1)
            a1 = a1-1
            num1[p] = 0
            X | x[p]
        with Control(eng, x):
            X | output
        a1 = sum(num)
        while a1>0:
            p = num.index(1)
            a1 = a1-1
            num[p] = 0
            X | x[p]

HiQ implementation of searching for the maximum value of the quantum algorithm

The code for quantum algorithm searching for the maximum value is as follows:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 import math

 from projectq.ops import H, Z, X, Measure, All, Ph, Rz
 from projectq.meta import Loop, Compute, Uncompute, Control

 from projectq.backends import CircuitDrawer, CommandPrinter
 from projectq.cengines import (MainEngine,
                             AutoReplacer,
                             LocalOptimizer,
                             TagRemover,
                             DecompositionRuleSet)
 import projectq.setups.decompositions

 from hiq.projectq.backends import SimulatorMPI
 from hiq.projectq.cengines import GreedyScheduler, HiQMainEngine

 from mpi4py import MPI

 def run_exactgrover(eng, n, oracle, oracle_modified):
     """
     Runs exact Grover's algorithm on n qubit using the two kind of provided
     quantum oracles (oracle and oracle_modified).
     This is an algorithm which can output solution with probability 1.

     Args:
         eng (MainEngine): Main compiler engine to run Grover on.
         n (int): Number of bits in the solution.
         oracle (function): Function accepting the engine, an n-qubit register,
             and an output qubit which is flipped by the oracle for the correct
             bit string.

     Returns:
         solution (list<int>): Solution bit-string.
     """
     x = eng.allocate_qureg(n)

     # start in uniform superposition
     All(H) | x

     # number of iterations we have to run:
     num_it = int(math.pi/4.*math.sqrt(1 << n))

     #phi is the parameter of modified oracle
     #varphi is the parameter of reflection across uniform superposition
     theta=math.asin(math.sqrt(1/(1 << n)))
     phi=math.acos(-math.cos(2*theta)/(math.sin(2*theta)*math.tan((2*num_it+1)*theta)))
     varphi=math.atan(1/(math.sin(2*theta)*math.sin(phi)*math.tan((2*num_it+1)*theta)))*2

     # prepare the oracle output qubit (the one that is flipped to indicate the
     # solution. start in state 1/sqrt(2) * (|0> - |1>) s.t. a bit-flip turns
     # into a (-1)-phase.
     oracle_out = eng.allocate_qubit()
     X | oracle_out
     H | oracle_out

     # run num_it iterations
     with Loop(eng, num_it):
         # oracle adds a (-1)-phase to the solution
         oracle(eng, x, oracle_out)

         # reflection across uniform superposition
         with Compute(eng):
             All(H) | x
             All(X) | x

         with Control(eng, x[0:-1]):
             Z | x[-1]

         Uncompute(eng)

     # prepare the oracle output qubit (the one that is flipped to indicate the
     # solution. start in state |1> s.t. a bit-flip turns into a e^(i*phi)-phase.
     H | oracle_out
     oracle_modified(eng, x, oracle_out, phi)

     with Compute(eng):
         All(H) | x
         All(X) | x

     with Control(eng, x[0:-1]):
         Rz(varphi) | x[-1]
         Ph(varphi/2) | x[-1]

     Uncompute(eng)

     All(Measure) | x
     Measure | oracle_out

     eng.flush()
     # return result
     return [int(qubit) for qubit in x]


 def alternating_bits_oracle(eng, qubits, output):
     """
     Marks the solution string 0, 1, 0,...,0 by flipping the

     qubit,
     conditioned on qubits being equal to the alternating bit-string.

     Args:
         eng (MainEngine): Main compiler engine the algorithm is being run on.
         qubits (Qureg): n-qubit quantum register Grover search is run on.
         output (Qubit): Output qubit to flip in order to mark the solution.
     """
     with Compute(eng):
         X | qubits[1]
     with Control(eng, qubits):
         X | output
     Uncompute(eng)

 def alternating_bits_oracle_modified(eng, qubits, output, phi):
     """
     Marks the solution string 0,1,0,... by applying phase gate to the output bits,
     conditioned on qubits being equal to the alternating bit-string.

     Args:
         eng (MainEngine): Main compiler engine the algorithm is being run on.
         qubits (Qureg): n-qubit quantum register Grover search is run on.
         output (Qubit): Output qubit to mark the solution by a phase gate with parameter phi.
     """
     with Compute(eng):
         All(X) | qubits[1::2]
     with Control(eng, qubits):
         Rz(phi) | output
         Ph(phi/2) | output

     Uncompute(eng)

 if __name__ == "__main__":
     # create a main compiler engine with a simulator backend:
     backend = SimulatorMPI(gate_fusion=True, num_local_qubits=20)
     # backend = CircuitDrawer()
     # locations = {}
     # for i in range(module.nqubits):
     #     locations[i] = i
     # backend.set_qubit_locations(locations)

     cache_depth = 10
     rule_set = DecompositionRuleSet(modules=[projectq.setups.decompositions])
     engines = [TagRemover(),
             LocalOptimizer(cache_depth),
             AutoReplacer(rule_set),
             TagRemover(),
             LocalOptimizer(cache_depth)
             #,CommandPrinter()
         , GreedyScheduler()
             ]

     eng = HiQMainEngine(backend, engines)
     # run Grover search to find a 7-bit solution

     print("=====================================================================")
     print("= This is the Grover algorithm demo")
     print("= Change the list to search by modifying alternating_bits_oracle")
     print("= The chosen list is: [0, 1, 0, ....]")
     print("= The second element is marked")
     print("= Calling ExactGrover algorithm to find the marked element now...")
     # run Grover search to find a 7-bit solution
     N = 12
     mark_bits = run_exactgrover(eng, N, alternating_bits_oracle, alternating_bits_oracle_modified)
     found = False
     for i in range(len(mark_bits)):
         if mark_bits[i] == 0:
             print("= Marked element is found, it index is: {}".format(i))
             found = True
     if not found:
         print("= Cannot found the marked element!")
     print("=====================================================================")

References: