Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the spatial quantum search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal spatial search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the spatial quantum search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal spatial search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
Systematic dimensionality reduction allows for the optimization of quantum search and transport problems on particular graphs. In the past, the Lanczos Algorithm has been used to perform systematic dimensionality reduction on matrices of graphs including the Complete Graph (CG), the CG with symmetry broken, and Complete Multipartite Graphs (CMPGs), including the Complete Bipartite Graph (CBG). We focus on expanding the scope of these reductions to the CBG with symmetry broken in order to allow the optimization of Quantum Walks on this type of graph.We show that similarly to the CG, the Lanczos Algorithm can be expanded to the CBG with broken symmetry, which has k random edges removed with the constraints that no more than one edge per node is removed and that no edges that connect to the solution node are removed. Unlike the CG with broken edges, which, after reduction, has 3 types of nodes and a resulting 3×3 matrix, the CBG with broken edges reduces to a graph with 5 types of nodes, resulting in a reduction from an NxN matrix to a 5×5 matrix. From these results, it may be further explored whether or not the more general CMPG reduction may also be expanded by breaking the graph's symmetry, and if so, how the dimensions of the reduced matrices will be affected as the number of partitions grows.
One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of n nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in O(n) time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size Θ(N), for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.
Search and state transfer between hubs, i.e., fully connected vertices, on otherwise arbitrary connected graph is investigated. Motivated by a recent result of Razzoli et al. [J. Phys. A: Math. Theor. 55, 265303 (2022)] on the universality of hubs in continuous-time quantum walks and spatial search, we extend the investigation to state transfer and also to the discrete-time case. We show that the continuous-time quantum walk allows for perfect state transfer between multiple hubs if the numbers of senders and receivers are close. Turning to the discrete-time case, we show that the search for hubs is successful provided that the initial state is locally modified to account for a degree of each individual vertex. Concerning state transfer using discrete-time quantum walk, it is shown that between a single sender and a single receiver one can transfer two orthogonal states in the same run time. Hence, it is possible to transfer an arbitrary quantum state of a qubit between two hubs. In addition, if the sender and the receiver know each other location, another linearly independent state can be transferred, allowing for exchange of a qutrit state. Finally, we consider the case of transfer between multiple senders and receivers. In this case we cannot transfer specific quantum states. Nevertheless, quantum walker can be transferred with high probability in two regimes---either when there is a similar number of senders and receivers, which is the same as for the continuous-time quantum walk, or when the number of receivers is considerably larger than the number of senders. Our investigation is based on dimensional reduction utilizing the invariant subspaces of the respective evolutions and the fact that for the appropriate choice of the loop weights the problem can be reduced to the complete graph with loops.
In a recent work by Novo et al. (Sci. Rep. 5, 13304, 2015), the invariant subspace method was applied to the study of continuous-time quantum walk (CTQW). The method helps to reduce a graph into a simpler version that allows more transparent analyses of the quantum walk model. In this work, we adopt the aforementioned method to investigate the optimality of a quantum walk search of a marked element on a complete multi-partite graph. We formulate the eigenbasis that would facilitate the transport between the two lowest energy eigenstates and demonstrate how to set the appropriate coupling factor to preserve the optimality.
Continuous-time quantum walk describes the propagation of a quantum particle (or an excitation) evolving continuously in time on a graph. As such, it provides a natural framework for modeling transport processes, e.g., in light-harvesting systems. In particular, the transport properties strongly depend on the initial state and specific features of the graph under investigation. In this paper, we address the role of graph topology, and investigate the transport properties of graphs with different regularity, symmetry, and connectivity. We neglect disorder and decoherence, and assume a single trap vertex that is accountable for the loss processes. In particular, for each graph, we analytically determine the subspace of states having maximum transport efficiency. Our results provide a set of benchmarks for environment-assisted quantum transport, and suggest that connectivity is a poor indicator for transport efficiency. Indeed, we observe some specific correlations between transport efficiency and connectivity for certain graphs, but, in general, they are uncorrelated.