Noname manuscript No.
(will be inserted by the editor)

Approaching unstructured search from function bilateral
symmetry detection - A quantum algorithm
Polynomial time Turing reduction of unstructured search into function
bilateral symmetry detection problem

arXiv:1505.01116v3 [quant-ph] 10 Apr 2016

Dinesh Kumar · Pankaj Srivastava

Received: date / Accepted: date

Abstract Detection of symmetry is vital to problem solving. Most of the problems of computer vision and computer graphics and machine intelligence in general, can be reduced to
symmetry detection problem. Unstructured search problem can also be looked upon from
symmetry detection point of view. Unstructured search can be thought as searching a binary
string satisfying some search condition in an unsorted list of binary strings. In this paper
unstructured search problem is reduced to function bilateral symmetry detection problem
with polynomial overhead in terms of the size of the input.
Keywords Unstructured Search · Function symmetry detection · Decision Problem ·
Quantum algorithm

1 Introduction
Searching something has always been an interesting computational problem in algorithm
design. It’s the most primitive and most frequent operation performed in day to day computational tasks. As information is encoded most often in binary strings, searching often
means searching a string item in a search space of string items. There have been algorithms
designed which work fine for a limited unstructured search space. For faster search operation it is required to maintain some structure in the the search space. The structure may
be the order of the elements (sorted list) or some other structure like Search tree, Heap etc.
Any way, maintaining the structure is a costly operation as inserting a new element to the
Dinesh Kumar
Computational Nanoscience and Technology Lab. (CNTL)
ABV Indian Institute of Information Technology and Management Gwalior, India
Tel.: +91 8950411980
E-mail: dinesh.gjust@gmail.com
Pankaj Srivastava
Computational Nanoscience and Technology Lab. (CNTL)
ABV Indian Institute of Information Technology and Management Gwalior, India
Tel.: +91-751-2449814
Fax: +91-751-2449814
E-mail: pankajs@iiitm.ac.in

2

Dinesh Kumar, Pankaj Srivastava

existing structure or deleting an element from the existing structure are both costly. So depending upon which operation we want to be perform fast some structure is maintained or
no structure is maintained. Sometimes a trade-off is made between the two.
Power of quantum computing has been widely established. There are computational tasks
which can be performed faster using a quantum computer for which no efficient classical algorithm exists [8], [3], [7]. In [4] a quantum
√ search algorithm was designed which can solve
the unstructured search problem in O( N) time. N is the number of string items in the
search space. The Grover’s algorithm has found extensive application in solving other computational problems. Quantum algorithms like quantum counting, amplitude amplification
and applications like collision problem, finding the median, minimum etc, graph problems
(spanning trees, matchings, flows....) and many others are based on Grover’s Unstructured
search algorithm. In his remarkable work [7] Peter W. Shor solved the problem of prime
factorization in polynomial time. Problem of prime factorization can be viewed as unstructured search problem. Prime factorization can be thought as searching the prime numbers
in the solution space of integers which divides the composite number whose factors has to
be found. Once the solution is known it is easy to verify its correctness. The search part
is crucial in solving to most of the problems and time consuming classically. Performing
search on sorted list of items or database is easy and already solved in [5] with just one
query complexity.
Over the past years it’s widely believed that the Grover’s unstructured
search algorithm is
√
optimized and the time complexity can not be reduced beyond O( N). Many work already
exist that shows that the quantum lower bound is exactly optimal [1], [2] √
and more. Using
the quantum random walk model [6] solved the same search problem in O( N) time. In this
paper the unstructured search problem is reduced to function bilateral symmetry detection
problem with polynomial overhead in terms of size of input search space in bits.

Unstructured Search Problem Given a list L of string items of length m bits, find the index i
of the string item s in the list that satisfies some search criteria f1 : {0, 1}n → {0, 1} defined
below, if it exists.

1 if f2 (L[i]) = z
f1 (i) =
0
otherwise
Here f2 : {0, 1}m → {0, 1}l , m ≥ l, can be any function which runs in polynomial time. z is
a bit string of arbitrary length ≤ m. Setting f2 and z can be thought as specifying the search
criteria f1 over L. Parameters L, f2 and z are fixed for a particular search. Only i is varied
over whole search domain. The above search criteria can be read as find the string in the list
which results in z when applied to f2 . A simple case is when f2 is identity function i.e. when
the search condition is to find just the match for z in the list L. It is possible that multiple
item strings in the list satisfies the search criteria f1 . So the search problem is to find the
indexes for which f1 (i) equals 1.
Symmetry detection and its significance in computation has already been recognized [9].
Mathematically, a symmetry can be thought as a mapping or transformation from a set of
points S of an object into itself such that the whole object remains invariant after the transformation. The concept of symmetry has found its application in almost all fields of study
including but not limited to Arts, Mathematics, Physics, Biology, Chemistry and Social interaction. Symmetry is inherent in nature, so in sciences.
In the following section, concept of function bilateral symmetry is discussed. Next, conversion of unstructured search problem into symmetry detection problem is presented. Finally

Approaching unstructured search from function bilateral symmetry detection

3

two quantum algorithms are proposed to solve unstructured search problem. Both algorithms
use the concept of function bilateral symmetry detection for solving the search problem.

2 Function bilateral symmetry detection
A function f possesses bilateral symmetry or reflection symmetry if it is even i.e. f (x) =
f (−x). This section discusses the concept of function bilateral symmetry detection.
Problem Definition:
Given a black box function f from {0, 1}n1 to {0, 1}m1 , determine weather the function is
symmetrical about y axis or not.
In other words we have to check weather the function is a even function or not. Function
bilateral symmetry detection is a decision problem. Classically, we have to query (call) the
black box function for all its input domain and make one halve the comparison of the number
of elements in the input domain to determine the evenness of the function f . That is weather
f (x) = f (−x) ∀ x ε [+ve domain of f ]. It requires O(2n1 ) steps to do so. Let us assume
that we can design a quantum algorithm for function bilateral symmetry detection with time
overhead of O(q = F(n1 )), where F is some yet to be known function of n1 . Figure 1 refers
to the the high level design of such a quantum algorithm.

|0i
|0i

H ⊗n1

|0i
|0i

|xi

QC
|0i
|0i
|0i

|yi

Fig. 1 Function bilateral symmetry [EvenOrNot()] detection algorithm

QC is some quantum circuit which makes use of f . y is the output register. The input
register is initialized to |000..00i state. The circuit outputs y = 00..0 if f possesses bilateral
symmetry. A non zero value of y indicates that the function f is not an even function. Above
algorithm can be referred to as EvenOrNot( f , i), where f is the function whose symmetry
needs to be tested and i refers to the input register of EvenOrNot detection algorithm. Value
of register i can be used to control the input domain for which evenness of f needs to be

4

Dinesh Kumar, Pankaj Srivastava

tested. For example a value |+i|−i|0i|0i....|0i of register i can be used to test the evenness
of f for all possible input values starting with 01.
3 Reducing unstructured search into function bilateral symmetry detection problem
Function bilateral symmetry detection is a decision problem as the answer to the problem
is yes or no only. Unstructured search requires finding the index i of the searched item s in
the list which satisfy some search condition f1 . Index i is log2 N bit string where N is the
size of the search space. Determining i requires making decisions about individual bits of
i. The decision weather the bit value should be 0 or 1 has to be made for all log2 N bits. In
this way unstructured search can be viewed as a decision problem. Conversion of the search
problem into the symmetry detection problem requires the search problem to be converted
to some function such that its symmetry checking helps in determining the bits of index i.
If we query (call) the function f1 () one by one for all the items in the list L (fig. 2) then at
some index i we get 1 as output and remaining of the times we get 0 as result of the query to
f1 (). To check the symmetry, we need to define function f1 () for negative values too. Let’s
define a new function f3 : {0, 1}n+1 → {0, 1} as follows:

f1 (in−1 in−2 ...i1 i0 )
if in = 0
f3 (i) =
0
otherwise
The newly defined search criteria f3 can be thought as searching the same string item s in
the big list (figure 3) of length 2N string items. Signed number representation is used for

S0
0

S1
1

S2
2

3

4

i

Sn−1
N−1

Fig. 2 Unstructured search problem

1S
−(N−1)

1S
−4 −3

1S
−2

1S
S0
S1
S2
−1 −0 +0 1
2
3

4

i

Sn−1
N−1

Fig. 3 New search problem

index i values. Due to this there are two representation of 0 in the new list (00..00 is +ve
zero, 10..00 indicates -ve zero). The MSB determines the sign of the number and rest bits
determine the magnitude of the number. The prepended string 1S in the new list can be any
arbitrary string of length m + 1 bits. As the solution index i can not be -ve as per definition
of f3 , it will remain the same for the new search problem except now it will be a n + 1
bit number with MSB 0 (positive number). The newly defined function f3 () is checked for
bilateral symmetry (evenness). A non zero output from EvenOrNot() quantum algorithm
shows that string item s satisfying the search criteria f3 () is present in the list. Next, We
divide the positive domain of f3 () in two equal halves. Check the evenness of f3 () for both
positive halves with corresponding negative halves. The item s must be present in the half
in which the function is not even. We divide that half further and repeat the above procedure
until the domain of f3 () is reduced to contain only a single integer index i.

Approaching unstructured search from function bilateral symmetry detection

5

4 Quantum unstructured search algorithm
4.1 For single item search
Algorithm 1 describes the pseudo code. It takes as input the search criteria f3 () and a (n + 1)
qubit register i as input. Search criteria f3 () is constructed by setting f1 which in turn requires setting f2 , L and z. At any point of time during the algorithm execution, i is indirectly
used to refer to the domain of the item strings in which searched string s satisfying the search
criteria f3 could be present. In fact, applying Hadamard transform H ⊗(n+1) to i results in a
superposition state which corresponds to the domain of item

Algorithm 1 Quantum Unstructured Search Algo to find single searched item
Algo QuantumUnstructuredSearch( f3 (), i)
Initialize: Register i[ ] ← {|0i, |0i, |0i ... upto log2 N}
i[0] ← |+i
if EvenOrNot( f3 , i) = 0 then
print ”Item not present”
exit()
end if
for j ← 1 to log2 N do
i[ j] ← |+i
if EvenOrNot( f3 , i) = 0 then
i[ j] ← |+i
else
i[ j] ← |−i
end if
end for
Apply H ⊗(n+1) on register i
print ”String item present at location i”

strings in which searched string s could be present. For example its value |+i|+i|−i|0i|0i
....|0i indicates that index of searched string s lies in the set of all (n + 1) bit values starting
with 001. At the end of the algorithm it will refer to the particular index i of the searched
item s. The first i f statement in the algorithm checks weather the searched item s is present
in the list or not. EvenOrNot( f3 (), i) will return 0 only if f3 is even otherwise it will return
a non-zero value. If EvenOrNot( f3 (), i) returns y equal to zero it indicates that the searched
item is not present in the list. In case searched item is present in the search domain of
f3 then atleast for one value in the search domain, f3 will be 1. It will result into uneven
detection and EvenOrNot() algorithm will return y equal to some non-zero value. If the
searched item is present in the list then the positive domain of f3 () is divided into two equal
halves. Evenness is checked for i equal to |+i|+i|0i0i.....|0i and |+i|−i|0i0i.....|0i. The
former value of i corresponds to left sub-domain and later value of i corresponds to right
sub-domain of the divided domain. Depending upon the result, i is set. If the searched item
is present in the left sub-domain, corresponding qubit of i distinguishing two sub-domains
is set to |+i. Otherwise it is set to |−i. The above procedure is repeated until we determine
all qubits of i. Finally a Hadamard Transform is performed on register i to get the index of
the searched item s.

6

Dinesh Kumar, Pankaj Srivastava

Algorithm 2 Quantum Unstructured Search Algo to find one or more items
Algo QuantumUnstructuredSearch( f3 (x), i, k)
i[0] ← |+i
if k = 1 and EvenOrNot( f3 , i) = 0 then
print ”Item not present”
exit()
end if
for j ← k to log2 N do
i[ j] ← |+i
y1 ← EvenOrNot( f3 ,i)
i[ j] ← |−i
y2 ← EvenOrNot( f3 ,i)
if y1 6= 0 and y2 = 0 then
i[ j] = |+i
else
if y1 = 0 and y2 6= 0 then
i[ j] ← |−i
else
i[ j] ← |+i
QuantumUnstructuredSearch( f3 , i, k + 1)
i[ j] ← |−i
QuantumUnstructuredSearch( f3 , i, k + 1)
exit()
end if
end if
k=k+1
end for
Apply H ⊗(n+1) on register i
print ”String item present at location i”

4.2 For multiple item search
Algorithm 2 defines the pseudo code for multiple string item search. The algorithm works
in a similar way as in the case for single item search. Search condition f3 (x) is constructed
by setting f1 which in turn requires setting s, f2 and L. Register i is passed with initial value
i[ ] = {|0i, |0i, |0i ... upto log2 N}. Register k stores the bit position of index i such that all
bits of i to the left of bit position k have been determined. It is passed with initial value k = 1
as the first qubit of the solution index i is bound to be 0 if an item is present in the list. The
first if statement of the algorithm checks weather any searched item is present or not. The
following for loop runs log2 N times. Each iteration of the for loop determines one qubit of
the solution indexes. In each iteration the domain is divided into two halves. There can be
three cases possible for the searched strings. All the searched strings can be present in the left
sub-domain, right sub-domain or both sub-domains simultaneously. In case when the items
are present in both sub-domains the algorithm calls itself recursively for both sub-domains.
The newly called instances of the algorithm starts their work from the smaller sub-domain
for which they are called.

Complexity analysis
Search for single item: For a search space of N items the algorithm requires (log2 N + 1)
calls to EvenOrNot() quantum algorithm. First call to EvenOrNot() determines the pres-

Approaching unstructured search from function bilateral symmetry detection

7

ence of the item in the list and the rest log2 N calls determines a bit of solution index i. If
EvenOrNot() quantum algorithm takes O(q = F(n1 )) time, the total time complexity of the
algorithm for single item search will be O(qlog2 N).
When two items are present: Let i1 and i2 are n bit indexes of the searched items present
in the list meeting the search criteria. Let i1 and i2 be same for a MSB’s (Most significant bits) i.e. bn−1 bn−2 bn−3 ...bn−a bn−a−1 bn−a−2 ....b1 b0 . The algorithm will make (a + 1)
|
{z
}|
{z
}
a

n−a

calls to EvenOrNot() to determine the first a bits of i. For the remaining (n − a) bits, two
separate instances of algorithm 2 will be running. Each instance will make (n − a) calls to
EvenOrNot() algorithm. Hence total calls will be ((a + 1) + 2(n − a)) ⇒ O(n) ⇒ O(log2 N)
and time complexity for this case will be O(qlog2 N).
In case of more than two items: Let i1 , i2 ...ic be the indexes of the string items matching the
search criteria. Let a initial MSB’s are same for all the indexes. Then a total (a + 1) steps
will be required to determine initial a bits of all indexes. The indexes can be divided into
two different classes or sets depending upon the similarity in initial (a + 1) bits. The above
procedure of division of indexes is continued until all bits of all indexes are determined. In
a loose setting, searching c string items can be thought as running the search algorithm 1 c
times finding a new index in each search. So The upper bound is clog2 N times. In this way,
it still requires O(qlog2 N) steps to solve the problem.

5 Conclusion
Looking at the unstructured search problem from the view point of symmetry is a completely
different approach towards solving the search problem. Even though no efficient algorithm
to solve the function bilateral symmetry detection problem is known yet, function bilateral
symmetry detection may have more structure to it that may be utilized to solve the search
problem more efficiently. Solving unstructured search problem can be viewed as making
a sequence of decisions. This paper establishes that function bilateral symmetry detection
problem is atleast as hard as solving the unstructured search problem. Most of the problems
can be viewed as search problem. Problem of prime factorization and 3-SAT are examples
of such problems. Such problems can be viewed as unstructured search problem with the
verification function f2 (problem dependent) as part of the search criteria f1 . Verification
function f2 tests weather a given solution is correct or not. If an efficient quantum algorithm
can be designed for the function bilateral symmetry detection, we can solve the unstructured
search problem and many other problems efficiently using quantum computing.

References
1. Ambainis A (2000) Quantum lower bounds by quantum arguments. In: Proceedings of
the thirty-second annual ACM symposium on Theory of computing, ACM, pp 636–643
2. Beals R, Buhrman H, Cleve R, Mosca M, de Wolf R (2001) Quantum lower bounds by
polynomials. J ACM 48(4):778–797, DOI 10.1145/502090.502097, URL http://doi.
acm.org/10.1145/502090.502097
3. Bernstein E, Vazirani U (1993) Quantum complexity theory. In: Proceedings of the
twenty-fifth annual ACM symposium on Theory of computing, ACM, pp 11–20

8

Dinesh Kumar, Pankaj Srivastava

4. Grover LK (1996) A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing pp 212–
219, DOI 10.1145/237814.237866, URL http://doi.acm.org/10.1145/237814.
237866
5. Grover LK (1997) Quantum computers can search arbitrarily large databases by a single
query. Physical review letters 79(23):4709
6. Shenvi N, Kempe J, Whaley KB (2003) Quantum random-walk search algorithm. Phys
Rev A 67:052,307, DOI 10.1103/PhysRevA.67.052307, URL http://link.aps.org/
doi/10.1103/PhysRevA.67.052307
7. Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM journal on computing 26(5):1484–1509
8. Simon DR (1997) On the power of quantum computation. SIAM Journal on Computing
26(5):1474–1483, DOI 10.1137/S0097539796298637, URL http://dx.doi.org/10.
1137/S0097539796298637
9. Yanxi Liu H Hel-Or, Kaplan CS (2010) Computational symmetry in computer vision and
computer graphics. Now publishers Inc

