Quantum walks can be implemented in the hypercube and general graphs, where hypercube is a regular graph. According to quantum walk algorithm, unitary property of quantum walks can be preserved. In the regular graph, to develop quantum walks algorithm is focused on quantum search algorithm. Quantum switching is the reversible and parallel computation circuits, where parallel computation circuit can achieve the better performance in time complexity and space complexity. Especially, this switching can trace the behavior of quantum walks from input sequence to output sequence, looking as quantum search algorithm. Furthermore, application of unicasting and multicasting can be implemented in this circuit.
Quantum walks can be implemented in the hypercube and general graphs, where hypercube is a regular graph. According to quantum walk algorithm, unitary property of quantum walks can be preserved. In the regular graph, to develop quantum walks algorithm is focused on quantum search algorithm. Quantum switching is the reversible and parallel computation circuits, where parallel computation circuit can achieve the better performance in time complexity and space complexity. Especially, this switching can trace the behavior of quantum walks from input sequence to output sequence, looking as quantum search algorithm. Furthermore, application of unicasting and multicasting can be implemented in this circuit.
This paper proposes a quantum switching on crossed cube, the diameter of the crossed cube is almost half of that of the hypercube, to execute quantum walks. Quantum walks can be implemented in the hypercube and general graphs. Hypercube is a regular graph. According to quantum walk algorithm, the system can preserve unitary property of quantum walks. In the regular graph, to develop quantum walks algorithm is focused on quantum search algorithm. The proposed circuit is to use quantum state, transferring from source node to destination for find the searching object. The small diameter is the best criterion to simulate the behavior of the proposed mechanism. This work selects crossed cube as the research topics with the following two major clauses. One is the small diameter and the other is the exchanged crossed state. The crossed cube has the half diameter of the hypercube. This cube owns the exchanged crossed state that can be used to present the behavior of the entangled particles. Quantum switching is reversible circuit and parallel computation circuit. By using parallel computation circuit, the system can achieve the better performance in time complexity and space complexity. Based on quantum switching, the system can trace the behavior of quantum walks from input sequence to output sequence, and obtains the benefit in time complexity and space complexity for quantum search algorithm.
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.
As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.
This paper presents a set of highly efficient quantum circuits for discrete-time quantum walks on non-degree-regular graphs. In particular, we describe a general procedure for constructing highly efficient quantum circuits for quantum walks on star graphs of any degree and Cayley trees with an arbitrary number of layers, which are nonsparse in general. We also show how to modify these circuits to implement a full quantum-walk search algorithm on these graphs, without reference to a ``black-box'' oracle. This provides a practically implementable method to explore quantum-walk-based algorithms with the aim of eventual real-world applications.
The application of quantum principles in computing has garnered interest since the 1980s. Today, this concept is not only theoretical, but we have the means to design and execute techniques that leverage the quantum principles to perform calculations. The emergence of the quantum walk search technique exemplifies the practical application of quantum concepts and their potential to revolutionize information technologies. It promises to be versatile and may be applied to various problems. For example, the coined quantum walk search allows for identifying a marked item in a combinatorial search space, such as the quantum hypercube. The quantum hypercube organizes the qubits such that the qubit states represent the vertices and the edges represent the transitions to the states differing by one qubit state. It offers a novel framework to represent k-mer graphs in the quantum realm. Thus, the quantum hypercube facilitates the exploitation of parallelism, which is made possible through superposition and entanglement to search for a marked k-mer. However, as found in the analysis of the results, the search is only sometimes successful in hitting the target. Thus, through a meticulous examination of the quantum walk search circuit outcomes, evaluating what input-target combinations are useful, and a visionary exploration of DNA k-mer search, this paper opens the door to innovative possibilities, laying down the groundwork for further research to bridge the gap between theoretical conjecture in quantum computing and a tangible impact in bioinformatics.
Quantum switching networks are analogs of classical switching networks in which classical switches are replaced by quantum switches. These networks are used to switch quantum data among a set of quantum sources and receivers. They can also be used to efficiently switch classical data, and help overcome some limitations of classical switching networks by utilizing the unique properties of quantum information systems, such as superposition and parallelism. In this thesis, we design several such networks which can be broadly put in the following three categories: 1. Quantum unicast networks: We give the design of quantum Baseline network (QBN) which is a self-routing and unicast quantum packet switch that uses the Baseline topology. The classical version of the network blocks packets internally even when there are no output contentions and each input packet is addressed to a different output. The QBN uses the principles of quantum superposition and parallelism to overcome such blocking. Also, for assignments that have multiple input packets addressed to an output, this network creates a quantum superposition of all these packets on that output, ensuring that all packets have non-zero probabilities of being observed on that output. 2. Quantum concentrators: We introduce a new network called quantum concentrator, which is a key component of our quantum multicasting network design. This concentrator is also an n × n quantum switching network, to be denoted by n-QC, and which, for any m, 1 ≤ m ≤ n, routes arbitrary quantum states on any m of its inputs to its top m outputs. This network uses O(n log n) quantum gates, and has a gate level depth of O(log 2 n). We also give several variations of this network, the main ones being order-preserving and priority quantum concentrators. 3. Quantum multicast networks: We first design a quantum multicasting network, called a generalized quantum connector (GQC) which can be used to multicast quantum information from n input sources to n outputs. Since general quantum states cannot be copied due to the no-cloning theorem, this network actually multicasts superposed classical information packets, contained in a finite number of qubits at each input. Copying needed for such multicasting is obtained by Wootters and Zurek's quantum copying machines or controlled-not gates. This n-input and n-output (n × n) network, to be denoted by n-GQC, is recursively constructed using n/2-GQCs and uses O(n log 2 n) quantum gates. The time complexity of this network in terms of gate level depth is O(log 3 n). We also give two variations of this network which improve its behavior when routing multicast assignments that have multiple input packets contending for same outputs.