IEEE International Conference on Electron Devices and Solid-State Circuits (EDSSC)

The design of a quantum Benes switch

Jung-Shian Li, Ching‐Fang Yang

Published Jan 1, 2007• 0 citations

Abstract

In this paper, we propose a novel framework for building a NtimesN quantum Benes switch that can route quantum packets without blocking. Previous studies about quantum systems have discussed many switching algorithms including merge sorting (Cheng and Wang, 2006) or self-routing Banyan switch (Shukla et al., 2005) etc. We build a newly quantum parallel routing scheme that achieves internally conflict free and real-time path permutations by using the quantum logic circuit modules.

DOI: 10.1109/edssc.2007.4450181

Related papers

The Quantum Baseline Network

Manish Shukla, Rahul Ratan, A. Yavuz Oruç

We present the design of a self-routing quantum packet switch which improves on a previous design given by the authors [1]. Like the earlier design, this switch too routes packets represented by quantum bits (qubits) but it reduces the routing overhead per packet from O(log N) qubits to O(1) qubits by eliminating the need for an extra "dummy" inputoutput pair and their associated "dummy" packets at each 2 2 internal switch. The quantum self-routing switch creates a superposition of all the maximum size non-blocking subsets of input packets at its outputs, which cannot be achieved by any classical self-routing switching network that is internally blocking. In addition to the network design, we give a method to characterize the output quantum state of the switch using the concepts of frames and balanced matrices.

Jan 1, 20056 citations

Design and Analysis of a Fully Non-blocking Quantum Switch

Chuan-Ching Sue, Wei-Ren Chen, Chin-Yu Huang

A switching device is required to build a realistic network which can handle the explosive growth of network traffic. However, the drawback of the switching device is mainly focused on the blocking problem. Previous studies have presented the solutions in the quantum context to avoid blocking at the expense of increasing packet loss and the exponential size of quantum gates. In this paper, we design a fully non-blocking quantum switch using the linear number O(N2) of quantum SWAP gates. Comparisons with a previously proposed quantum self-routing packet switch is also presented in terms of the hardware complexity, the propagation delay and packet loss probability

International Conference on Innovative Computing, Information and ControlOct 24, 20063 citations

Quantum Switching Networks with Classical Routing

Rahul Ratan, Manish Kumar Shukla, A. Yavuz Oruç

Flexible distribution of data in the form of quantum bits (qubits) amongst spatially separated entities is an essential component of envisioned scalable quantum computing architectures. Since qubits cannot be copied, this operation of moving qubits can be relatively costly in terms of resources. Moreover, implementation of quantum gates requires precise and extensive classical control and computation too. Accordingly, we consider the problem of dynamically permuting groups of qubits, i.e., qubit packets using reconfigurable quantum switches in which routing information is calculated classically as a possible way to reduce this cost. We design a 2 x 2 switch based on the controlled-swap quantum gate and show that if switch settings are determined using efficient classical algorithms, then quantum switches can be mapped onto classical non-blocking interconnection switch topologies with low cost by using this switch. Specific quantum switch designs for the optimal Benes network and the planar Spanke-Bcnes network are given.

Conference on Information Sciences and SystemsMar 1, 200710 citations

An Enhanced Universal N x N Fully Nonblocking Quantum Switch

Chuan-Ching Sue

This study develops a quantum switching device with fully nonblocking properties. Although previous studies have also presented quantum-based solutions for the blocking problem, the proposed schemes are characterized by an increased packet loss, a large number of quantum SWAP gates and an increased propagation delay time complexity. The current study overcomes these drawbacks by designing an N x N fully nonblocking quantum switch, in which the packet payload is passed through quantum SWAP gates while the packet header is passed through quantum control gates designed by applying a modified quantum Karnaugh mapping method. The allocation of quantum SWAP gates to the different layers within the switch is solved using a Perfect Matching in Complete Graph (PMiCG) algorithm with a time complexity of O(N!/(2N/2(N/2)!)). A symmetry-based heuristic method is proposed to reduce the time complexity of the search process for all the perfect matching pairs to a time complexity of O(N2). The performance of the proposed quantum switch is compared with that of a quantum self-routing packet switch and a quantum switching/quantum merge sorting scheme, respectively, in terms of the hardware complexity, the propagation delay time complexity, the auxiliary qubit complexity, and the packet loss probability.

IEEE Transactions on ComputersSep 17, 20087 citations

Quantum switching and quantum merge sorting

Sheng-Tzong Cheng, Chun-Yen Wang

This paper proposes a quantum switching architecture that can dynamically permute each input quantum data to its destination port to avoid using the fully connected networks. In addition, in order to reduce the execution time of the quantum switching, an efficient quantum merge sorting (QMS) algorithm that provides a parallel quantum computation is also developed. The quantum switching utilizes the QMS algorithm as a subroutine so that the total running time can be reduced to polylogarithmic time. Furthermore, to evaluate the feasibility of the quantum switching, we also define three different kinds of performance factors that can be used to estimate the complexity in implementation and the time delay in execution for quantum instruments. From the evaluation results, it can be seen that the proposed quantum switching is feasible in practice.

IEEE Transactions on Circuits and Systems I Fundamental Theory and ApplicationsFeb 1, 200657 citations

Random routing and concentration in quantum switching networks

Rahul Ratan

Flexible distribution of data in the form of quantum bits or qubits among spatially separated entities is an essential component of envisioned scalable quantum computing architectures. Accordingly, we consider the problem of dynamically permuting groups of quantum bits, i.e., qubit packets, using networks of reconfigurable quantum switches. We demonstrate and then explore the equivalence between the quantum process of creation of packet superpositions and the process of randomly routing packets in the corresponding classical network. In particular, we consider an n × n Baseline network for which we explicitly relate the pairwise input-output routing probabilities in the classical random routing scenario to the probability amplitudes of the individual packet patterns superposed in the quantum output state. We then analyze the effect of using quantum random routing on a classically non-blocking configuration like the Benes network. We prove that for an n × n quantum Benes network, any input packet assignment with no output contention is probabilistically self-routable. In particular, we prove that with random routing on the first (log n-1) stages and bit controlled self-routing on the last log n stages of a quantum Benes network, the output packet pattern corresponding to routing with no blocking is always present in the output quantum state with a non-zero probability. We give a lower bound on the probability of observing such patterns on measurement at the output and identify a class of 2 n-1 permutation patterns for which this bound is equal to 1, i.e., for all the permutation patterns in this class the following is true: in every pattern in the quantum output assignment all the valid input packets are present at their correct output addresses. In the second part of this thesis we give the complete design of quantum sparse crossbar concentrators. Sparse crossbar concentrators are rectangular grids of simple 2 × 2 switches or crosspoints, with the switches arranged such that any k inputs can be connected to some k outputs. We give the design of the quantum crosspoints for such concentrators and devise a self-routing method to concentrate quantum packets. Our main result is a rigorous proof that certain crossbar structures, namely, the fat-slim and banded quantum crossbars allow, without blocking, the realization of all concentration patterns with self-routing. In the last part we consider the scenario in which quantum packets are queued at the inputs to an n × n quantum non-blocking switch. We assume that each packet is a superposition of m classical packets. Under the assumption of uniform traffic, i.e., any output is equally likely to be accessed by a packet at an input we find the minimum value of m such that the output quantum state contains at least one packet pattern in which no two packets contend for the same output. Our calculations show that for m=9 the probability of a non-contending output pattern occurring in the quantum output is greater than 0.99 for all n up to 64.

Jan 1, 20080 citations