Due to scalability issue in current quantum technologies, many quantum algorithms can only be implemented for small size problems. Scalability remains a bottleneck for current quantum technologies. For solving real-life size hard problems in the near-term, we explore classes of search graphs that can be efficiently reduced to a implementable scale for many quantum algorithms. The reduced Hamiltonian preserves the dynamics of the original Hamiltonian. One of the quantum algorithms we choose for the reduced Hamiltonian is continuous time quantum walk (CTQW). We further show how to determine the correct value of the coupling factor of the underlying CTQW. With wrong couple factor values, the optimality (quadratic speedup) from CTQW might be lost. In this work, we extend the class of reducible graphs to complete bipartite graphs with random $k$ edges removed. We further demonstrate through mathematical proof and simulation experiment using IBM Qiskit to show that the quadratic speed-up is preserved for the CTQW.
Due to scalability issue in current quantum technologies, many quantum algorithms can only be implemented for small size problems. Scalability remains a bottleneck for current quantum technologies. For solving real-life size hard problems in the near-term, we explore classes of search graphs that can be efficiently reduced to a implementable scale for many quantum algorithms. The reduced Hamiltonian preserves the dynamics of the original Hamiltonian. One of the quantum algorithms we choose for the reduced Hamiltonian is continuous time quantum walk (CTQW). We further show how to determine the correct value of the coupling factor of the underlying CTQW. With wrong couple factor values, the optimality (quadratic speedup) from CTQW might be lost. In this work, we extend the class of reducible graphs to complete bipartite graphs with random k edges removed. We further demonstrate through mathematical proof and simulation experiment using IBM Qiskit to show that the quadratic speed-up is preserved for the CTQW.
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.
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.
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.
Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.
To extend the continuous-time quantum walk (CTQW) to simulate P distinguishable particles on a graph G composed of N vertices, the Hamiltonian of the system is expanded to act on an N^{P}-dimensional Hilbert space, in effect, simulating the multiparticle CTQW on graph G via a single-particle CTQW propagating on the Cartesian graph product G^{□P}. The properties of the Cartesian graph product have been well studied, and classical simulation of multiparticle CTQWs are common in the literature. However, the above approach is generally applied as is when simulating indistinguishable particles, with the particle statistics then applied to the propagated N^{P} state vector to determine walker probabilities. We address the following question: How can we modify the underlying graph structure G^{□P} in order to simulate multiple interacting fermionic CTQWs with a reduction in the size of the state space? In this paper, we present an algorithm for systematically removing "redundant" and forbidden quantum states from consideration, which provides a significant reduction in the effective dimension of the Hilbert space of the fermionic CTQW. As a result, as the number of interacting fermions in the system increases, the classical computational resources required no longer increases exponentially for fixed N.
Abstract How to design deterministic spatial search algorithms is a difficult but important problem. This paper presents a deterministic search algorithm on complete bipartite graphs with optimal runtime scaling. Our algorithm adopts the simple form of alternating iterations of an oracle and a continuous-time quantum walk operator, which is a generalization of Grover's search algorithm. To address the case of the number of marked vertices being unknown, we construct a quantum counting algorithm based on the spectrum structure of the search operator. This is a non-trivial example of quantum counting for spatial search. To implement the continuous-time quantum walk operator, we perform Hamiltonian simulation in the quantum circuit model and simulate it on the IBM quantum computing platform Qiskit.