An Algebraic Model for Simulation of Percolation Decoherence on Quantum-Walk-Based Search Algorithms

• Gabriel Mauricio Oswald Vieira UFRJ
• Rui Aldé Lopes UFRJ
• Nelson Maculan UFRJ
• Franklin de Lima Marquezino UFRJ / University of Latvia

DOI: https://doi.org/10.5753/etc.2024.2031

Resumo

In this paper, we propose a linear algebra based model for percolation noise simulation in quantum-walk-based searches to analyze the impact on the success probability of the search. The model was built to allow an open and simultaneous simulation of any type of noise that represents an edge-break, which we show to be a well-behaved family of permutation matrices that maintain a particular set theory relation when acting as some system evolution operators. The simulation evolves using only linear algebra operations, opening avenues for easier analyses of unexpected observed convergence behaviour. As a use case, we investigate the simulation of a lackadaisical quantum walk with percolation noise.

Referências

Abal, G., Donangelo, R., Marquezino, F. L., Oliveira, A. C., and Portugal, R. (2009). Decoherence in search algorithms. In Proceedings of the XXIX Brazilian Computer Society Congress (CSBC), 36th Seminar on Software and Hardware (SEMISH), pages 293–306, Bento Conçalves, Brazil. Brazilian Computer Society.

Hoyer, P. and Yu, Z. (2020). Analysis of lackadaisical quantum walks. Quantum Information and Computation, 20(13 14):1138–1153.

Portugal, R. (2013). Quantum Walks and Search Algorithms. Springer.

Santos, R. A. M. and Marquezino, F. L. (2022). Decoherence on staggered quantum walks. Physical Review A, 105(3).

Wong, T. G. (2018). Faster search by lackadaisical quantum walk. Quantum Information Processing, 17(3).