Since their theoretical introduction in 1980, quantum computers have progressed significantly in both theory and experimentation. Quantum computers have the potential to solve certain problems significantly faster than their classical counterparts. One particularly promising area is search algorithms. In 1996, Lov Grover introduced a quantum search algorithm that laid the foundation for numerous variants. Among them, the alternating phase-walk stands out as a method for searching an element in an ordered list, which is modeled as a graph. However, a major challenge in practical quantum computing remains quantum decoherence.
The objective of this project was to model decoherence as bond percolation on a star graph during an alternating phase-walk, and to investigate its resulting effects. The introduction of decoherence transformed the search algorithm from a deterministic process into a probabilistic one, as the probability of measuring the marked state is no longer guaranteed to be 100% on every run of the algorithm. The most significant results were observed when varying the walk time in the continuous-time quantum walk (CTQW), both with and without a varying initial state. Here, the optimal time topt and its corresponding maximum average value μmax are presented for each value of p.