d Layera, Alba Cervera-Lierta
A search algorithm is a computational process that is used to locate a specific item or group of items within a larger collection of data. Search algorithms constitute both a solid and widely studied set of computational tools used in scientific and industrial applications everyday (e.g.,1,2,3,4,5,6), partly due to the emergence of new computer platforms (e.g., mobile and distributed systems), as well as an active research area (e.g.,7,8). Concrete examples of fields that make extensive use of search algorithms in classical computing include Database Management9, Natural Language Processing10, Convolutional Neural Networks11, and Computer Networks12.
With the emergence of quantum computing, new search algorithms have been created. The most famous proposal is Grover’s search algorithm13, with which we can amplify the probability amplitude of a specific state encoded in an oracle operator within a uniform distribution of states with complexity (O(sqrt{N})) or solve combinatorial optimization problems14,15. Another example of a quantum search algorithm is the SKW algorithm16, proposed by Shenvi, Kempe and Whaley, which uses the framework of Unitary Coined Discrete-Time Quantum Walks (UCDTQW) to also increase the probability amplitude of a specific state encoded in an oracle operator.
According to17, a UCDTQW consists of three elements: the state of a quantum walker, ({|{psi }rangle }), the evolution operator of the system U and the set of measurement operators of the system ({M_k}). The quantum state of a walker is a bipartite state that is composed of a coin state, ({|{c_i}rangle }), that is part of an m-dimensional Hilbert space (H_C), and a position state, ({|{v_j}rangle }), that is part of an n-dimensional Hilbert space (H_C), such that ({|{psi }rangle }) is a linear combination of the tensor product between pairs of coin and position states, i.e. ({|{psi }rangle } = sum limits _{i}sum limits _{j} a_{ij}{|{c_i}rangle }otimes {|{v_j}rangle }.) The evolution operator of the system is a bipartite operator that takes the form (U = SC), where C is the coin operator of the system, which modifies only the coin state in ({|{psi }rangle }), i.e. it has the form (C=C'otimes I_n), and S is the shift operator of the system, which in principle could by any bipartite operator, and it codifies the information about connections of the graph where the UCDTQW takes place. In general, S is always associated to a directed multigraph. The elements of the set of measurement operators, ({M_k}), have the form (M_k = I_{m}otimes {|{v_k}rangle }{langle {v_k}|}). The SKW algorithm performs a UCDTQW to let a quantum walker move along the vertices of a hypercube graph and search for a marked node.
The SKW algorithm has been studied in detail through theoretical calculations and numerical simulations18,19,20,21,22, and, in fact, in21 the complexity of the quantum circuit was reduced by using the shift operator associated to the (2^n)-dimensional complete graph with self-loops, (mathscr {K}_{2^n}), instead of the shift operator associated to a hypercube. However, even after this improvement, the SKW algorithm has never been reported to be efficiently implemented in a general-purpose quantum computer given that the quantum circuit form of the algorithm uses a multi-control Grover operator as part of the coin operator of the UCDTQW, which decomposes into a polynomial number of quantum gates, following the decompositions proposed in23 and24, making it challenging to run efficiently on NISQ computers.
In view of the former statement, we propose to modify the coin operator of the UCDTQW to make the SKW algorithm more efficient. A natural option arises with the n-qubit Hadamard operator, a commonly used operator in the field of UCDTQW for the role of the coin operator, which is indeed less computationally expensive, given that it consists of n sigle-qubit Hadamard gates. Thus one of the purposes of this work is to study the behaviour of the UCDTQW using the Hadamard coin. Moreover, it is also our goal to efficiently implement the search algorithm in IBM’s general-purpose quantum computers, thus we decided to take the idea proposed in21 and perform the search algorithm on the graph (mathscr {K}_{2^n}). However we use the
