Quantum Walks in a Superconducting Quantum Computer

  • Jaime Santos Universidade de Aveiro / INESC TEC
  • Bruno Chagas Irish Centre for High-End Computing / National University of Ireland
  • Rodrigo Chaves Universidade Federal de Minas Gerais


Quantum Walks are among the most widely used techniques with which we can construct new quantum algorithms. This paper aims to outline how to construct a circuit for the continuous-time quantum walk (CTQW) over circulant graphs using the Quantum Fourier Transform (QFT) due to the spectral properties of those graphs. Furthermore, we examine how the Approximate Quantum Fourier Transform (AQFT) allows us to shorten the size of the circuit by reducing the number of controlled rotation gates. The contributions of this paper consist of the development of a general circuit implementation of the CTQW for an important class of graphs that does not scale up with time, and the study of the cases where the AQFT decreases the error by controlling the approximation. Finally, we provide a statistical analysis for several circulant graphs, running experiments in a IBM's superconducting quantum computer, and we also explore the pretty good state transfer (PGST) for some graphs.


Acasiete, F., Agostini, F. P., Moqadam, J. K., and Portugal, R. (2020). Implementation of quantum walks on IBM quantum computers. Quantum Information Processing, 19(12).

Ambainis, A. (2008). Quantum Algorithm for Element Distinctness, pages 686–689. Springer US, Boston, MA.

Balu, R., Castillo, D., and Siopsis, G. (2018). Physical realization of topological quantum walks on IBM-q and beyond. Quantum Science and Technology, 3(3):035001.

Bullock, S. S. and Markov, I. L. (2004). Smaller circuits for arbitrary n-qubit diagonal computations. Quant. Info. and Comp., 4(27).

Chakraborty, S., Luh, K., and Roland, J. (2020). How fast do quantum walks mix? Phys. Rev. Lett., 124:050501.

Childs, A. M. and Goldstone, J. (2004). Spatial search by quantum walk. Physical Review A, 70(2):022314.

Coutinho, G. (2014). Quantum State Transfer in Graphs. PhD thesis, University of Waterloo.

Farhi, E. and Gutmann, S. (1998). Quantum computation and decision trees. Physical Review A, 58:915-928.

Pal, H. and Bhattacharjya, B. (2017). Pretty good state transfer on circulant graphs. The Electronic Journal of Combinatorics, 24.

Qiang, X., Loke, T., Montanaro, A., Aungskunsiri, K., Zhou, X., O’Brien, J. L., Wang, J. B., and Matthews, J. C. F. (2016). Efficient quantum walk on a quantum processor. Nature Communications, 7:11511.

Shakeel, A. (2020). Efficient and scalable quantum walk algorithms via the quantum Fourier transform. Quantum Information Processing, 19(9):323.

Shende, V., Bullock, S., and Markov, I. (2006). Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(6):1000–1010.
Como Citar

Selecione um Formato
SANTOS, Jaime; CHAGAS, Bruno; CHAVES, Rodrigo. Quantum Walks in a Superconducting Quantum Computer. In: WORKSHOP DE COMUNICAÇÃO E COMPUTAÇÃO QUÂNTICA (WQUANTUM), 1. , 2021, Uberlândia. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2021 . p. 25-30. DOI: https://doi.org/10.5753/wquantum.2021.17223.