Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method
arXiv:2304.01501 · doi:10.1007/s11128-023-03878-6
Abstract
Several models have been proposed to build evolution operators to perform quantum walks in a theoretical way, although when wanting to map the resulting evolution operators into quantum circuits to run them in quantum computers, it is often the case that the mapping process is in fact complicated. Nevertheless, when the adjacency matrix of a graph can be decomposed into a sum of permutation matrices, we can always build a shift operator for a quantum walk that has a block diagonal matrix representation. In this paper, we analyze the mapping process of block diagonal operators into quantum circuit form, and apply this method to obtain quantum circuits that generate quantum walks on the most common topologies found in the literature: the straight line, the cyclic graph, the hypercube and the complete graph. The obtained circuits are then executed on quantum processors of the type Falcon r5.11L and Falcon r4T (two of each type) through IBM Quantum Composer platform and on the Qiskit Aer simulator, performing three steps for each topology. The resulting distributions were compared against analytical distributions, using the statistical distance as a performance metric. Regarding experimental executions, we obtained short distances in the cases of quantum circuits with a low amount of multi-control gates, being the quantum processors of the type Falcon r4T the ones that provided more accurate results.
arXiv comment36 pages
References in corpus (24)
- Quantum Computing in the NISQ era and beyond
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Quantum walks: a comprehensive review
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Discrete single-photon quantum walks with tunable decoherence
- Experimental Two-dimensional Quantum Walk on a Photonic Chip
- Faster quantum walk algorithm for the two dimensional spatial search
- Google in a Quantum Network
- Efficient Quantum Walk on a Quantum Processor
- Decompositions of general quantum gates
- Quantum walks can find a marked element on any graph
- Experimental Implementation of Quantum Walks on IBM Quantum Computers
- Staggered Quantum Walks on Graphs
- Quantum walks public key cryptographic system
- Discrete-time quantum walk algorithm for ranking nodes on a network
- Quantum walk-based search algorithms with multiple marked vertices
- Representation of binary classification trees with binary features by quantum circuits
- Efficient and scalable quantum walk algorithms via the quantum Fourier transform
- A Comparison of Quantum Walk Implementations on NISQ Computers
- Quantum walks on embedded hypercubes
- Discrete-Time Quantum Walk - Dynamics and Applications
- Quantum Walk to Train a Classical Artificial Neural Network
- Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits
Cited by in corpus (6)
- Efficient implementation of discrete-time quantum walks on quantum computers
- Quantum collision circuit, quantum invariants and quantum phase estimation procedure for fluid dynamic lattice gas automata
- Optimizing topology for quantum probing with discrete-time quantum walks
- Controlling quantum chaos via Parrondo strategies on noisy intermediate-scale quantum hardware
- Circuit Implementation of Discrete-Time Quantum Walks on Complex Networks
- Implementation of Continuous-Time Quantum Walks on Quantum Computers