The Unitary Coin Discrete-Time Quantum Walk (UCDTQW) serves as a universal model for quantum computers. In this paper, we conduct matrix analysis based on the unitary operator of UCDTQW, constructing the system’s shift operator as the unitary form of the adjacency matrix corresponding to the complete graph [Formula: see text]. Through a set of transformation equations, we realize the reciprocal mapping between the adjacency matrix and the shift operator. Specifically, by splitting the undirected edges of [Formula: see text] into multiple directed arcs, we construct a directed multigraph structure. Our study reveals that the unitary evolution operator of this multigraph exhibits properties analogous to those of the shift operator, particularly uncovers the periodic characteristics of the wave function. Furthermore, under another edge connection scheme, we achieve the construction of the quantum circuit representation for the shift operator.
In this paper, continuous-time quantum walk is discussed based on the view of quantum probability, i.e. the quantum decomposition of the adjacency matrix A of graph. Regard adjacency matrix A as Hamiltonian which is a real symmetric matrix with elements 0 or 1, so we regard [Formula: see text] as an unbiased evolution operator, which is related to the calculation of probability amplitude. Combining the quantum decomposition and spectral distribution [Formula: see text] of adjacency matrix A, we calculate the probability amplitude reaching each stratum in continuous-time quantum walk on complete bipartite graphs, finite two-dimensional lattices, binary tree, [Formula: see text]-ary tree and [Formula: see text]-fold star power [Formula: see text]. Of course, this method is also suitable for studying some other graphs, such as growing graphs, hypercube graphs and so on, in addition, the applicability of this method is also explained.
Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study the implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator ${e}^{\ensuremath{-}iHt}$, where $H=\ensuremath{\gamma}A$ ($\ensuremath{\gamma}$ is a constant and
A corresponds to the adjacency matrix of a graph). Our result is, for a
d-sparse graph with
N vertices and evolution time
t, we can approximate ${e}^{\ensuremath{-}iHt}$ by a quantum circuit with gate complexity $({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}$. For sparse graphs, for instance,
d=O(1), we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian
H can be represented as the sum of some Hamiltonians
Hj, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.
Perfect state transfer (PST) is a key requirement for high-fidelity quantum communication. In discrete-time quantum walks, the shift matrix governs the system dynamics and plays a central role in enabling PST. This work presents a shift-matrix construction based on shunt decompositions of d-regular directed graphs, under which path, cycle, and complete graphs exhibit both perfect state transfer and periodic dynamics. Unlike existing permutation-based approaches that yield periodicity without PST, the proposed method achieves both properties. A SHAP-like attribution analysis is performed to identify the arcs essential for PST. In addition, quantum-circuit implementations of the shift matrices and benchmark results under ideal and noisy conditions are reported. The framework is further extended to a unitary construction of a reset channel, whose reduced Kraus representation leverages the underlying graph structure to minimize information loss.
Quantum walks, both discrete and continuous, serve as fundamental tools in quantum information processing with diverse applications. This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks. Through systematic analysis of probability distributions, standard deviations, and entanglement entropy on fundamental graph structures, we reveal distinctive dynamical characteristics that differentiate our model from conventional quantum walk paradigms. The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases. Two significant applications emerge from this hybrid architecture: (1) We develop a novel protocol for perfect state transfer(PST) in general connected graphs, overcoming the limitations of previous graph-specific approaches. A PST on a tree graph has been implemented on a quantum superconducting processor. (2) We devise a quantum algorithm for multiplying K adjacency matrices of n -vertex regular graphs with time complexity O ( n 2 d 1 ⋯ d K ), outperforming classical matrix multiplication ( O ( n 2.371552 )) when vertex degrees d i are bounded. The algorithm’s efficacy for triangle counting is experimentally validated through the quantum simulation on PennyLane. These results establish the hybrid quantum walk as a versatile framework bridging discrete and continuous paradigms while enabling practical quantum advantage in graph computation tasks.
Matrix representations of quantum operators are computationally complete but often obscure the structural topology of information flow within a quantum circuit \cite{nielsen2000}. In this paper, we introduce a generalized graph-theoretic framework for analyzing quantum operators by mapping unitary matrices to directed graphs; we term these structures \emph{Imperfect Graphs} or more formally as \emph{Topological Structure of Superpositions}(TSS) as a tool to devise better Quantum Algorithms. In this framework, we represent computational basis states as vertices. A directed edge exists between two vertices if and only if there is a non-zero amplitude transition between them, effectively mapping the support of the unitary operator. In this paper we deliberately discard probability amplitudes and phase information to isolate the connectivity and reachability properties of the operator. We demonstrate how TSS intuitively helps describe gates such as the Hadamard, Pauli-(X,Y,Z) gates, etc \cite{nielsen2000}. This framework provides a novel perspective for viewing quantum circuits as discrete dynamical systems \cite{childs2009,aharonov2001}
Keywords: Quantum Algorithms, Unitary Matrix Approach, Topological Structure of Superpositions (TSS), Graph Theory
Quantum walks are the quantum-mechanical analog of random walks, in which a quantum ``walker'' evolves between initial and final states by traversing the edges of a graph, either in discrete steps from node to node or via continuous evolution under the Hamiltonian furnished by the adjacency matrix of the graph. We present a hybrid scheme for universal quantum computation in which a quantum walker takes discrete steps of continuous evolution. This ``discontinuous'' quantum walk employs perfect quantum-state transfer between two nodes of specific subgraphs chosen to implement a universal gate set, thereby ensuring unitary evolution without requiring the introduction of an ancillary coin space. The run time is linear in the number of simulated qubits and gates. The scheme allows multiple runs of the algorithm to be executed almost simultaneously by starting walkers one time step apart.