Since their theoretical introduction in 1980, quantum computers have progressed significantly in
both theory and experimentation. Quantum computers have the potential to solve certain prob-
lems significantly faster than their classical counterparts. One particularly prom
...
Since their theoretical introduction in 1980, quantum computers have progressed significantly in
both theory and experimentation. Quantum computers have the potential to solve certain prob-
lems 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 founda-
tion 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.
Static Initial State
• N = 3 star graph:
[p = 0.1, topt = 2.46 τ3, μmax = 0.67]
[p = 0.5, topt = 0.62 τ3, μmax = 0.91]
[p = 0.9, topt = 0.37 τ3, μmax = 1.00]
• N = 7 star graph:
[p = 0.1, topt = 2.21 τ7, μmax = 0.56]
[p = 0.5, topt = 0.59 τ7, μmax = 0.96]
[p = 0.9, topt = 0.34 τ7, μmax = 0.99]
• N = 14 star graph:
[p = 0.1, topt = 5.50 τ14, μmax = 0.55]
[p = 0.5, topt = 0.62 τ14, μmax = 0.96]
[p = 0.9, topt = 0.35 τ14, μmax = 0.99]
Varying Initial State
• N = 3 star graph:
[p = 0.1, topt = 2.30 τ3, μmax = 0.68]
[p = 0.5, topt = 0.37 τ3, μmax = 0.70]
[p = 0.9, topt = 0.36 τ3, μmax = 0.99]
• N = 7 star graph:
[p = 0.1, topt = 2.30 τ7, μmax = 0.57]
[p = 0.5, topt = 0.37 τ7, μmax = 0.66]
[p = 0.9, topt = 0.33 τ7, μmax = 0.99]
• N = 14 star graph:
[p = 0.1, topt = 6.42 τ14, μmax = 0.58]
[p = 0.5, topt = 0.39 τ14, μmax = 0.60]
[p = 0.9, topt = 0.34 τ14, μmax = 0.98]
