Abstract
We propose a modified version of the quantum walk-based search algorithm created by Shenvi, Kempe and Whaley, also known as the SKW algorithm. In our version of the algorithm, we modified the evolution operator of the system so that it is composed by the product of the shift operator associated to the [Formula: see text]-complete graph with self-loops and a perturbed coin operator based on the Hadamard operator that works as an oracle for the search. The modified evolution operator leads the opposite behavior as in the original algorithm, that is, the probability to measure the target state is reduced. We call this new behavior the search complement. Furthermore, we extend the functioning of the algorithm so that it targets at multiple nodes at the same time, which makes it suitable to be used as an initialization routine for the QAOA algorithm to solve restricted QUBO problems. Taking a multigraph and matrix approach, we were able to explain that the new algorithm decreases the probability of the target states given that there are less paths that lead towards the nodes that are associated to the target states in a Unitary Coined Discrete-Time Quantum Walk. The search complement algorithm was executed experimentally on IBM quantum processor ibmq_manila obtaining statistical distances [Formula: see text] when decreasing the probability of one state out of four.