IEEE/ACM International Workshop on Heterogeneous High-performance Reconfigurable Computing (H2RC)

Combining Perfect Shuffle and Bitonic Networks for Efficient Quantum Sorting

Naveed Mahmud, Bailey Srimoungchanh, Bennett Haase-Divine, Nolan Blankenau, Annika Kuhnke, Esam El‐Araby

Published Nov 1, 2019• 3 citations

Abstract

The emergence of quantum computers in the last decade has generated research interest in applications such as quantum sorting. Quantum sorting plays a critical role in creating ordered sets of data that can be better utilized, e.g., quantum ordered search or quantum network switching. In this paper, we propose a quantum sorting algorithm that combines highly parallelizable bitonic merge networks with perfect shuffle permutations (PSP), for sorting data represented in the quantum domain. The combination of bitonic networks with PSP improves the temporal complexity of bitonic merge sorting which is critical for reducing decoherence effects for quantum processing. We present space-efficient quantum circuits that can be used for quantum bit comparison and permutation. We also present a reconfigurable hardware quantum emulator for prototyping the proposed quantum algorithm. The emulator has a fully-pipelined architecture and supports double-precision floating-point computations, resulting in high throughput and accuracy. The proposed hardware architectures are implemented on a high-performance reconfigurable computer (HPRC). In our experiments, we emulated quantum sorting circuits of up to 31 fully-entangled quantum bits on a single FPGA node of the HPRC platform. To the best of our knowledge, our effort is the first to investigate a reconfigurable hardware emulation of quantum sorting using bitonic networks and perfect shuffle.

DOI: 10.1109/h2rc49586.2019.00011

Related papers

Improving Emulation of Quantum Algorithms using Space-Efficient Hardware Architectures

Naveed Mahmud, Esam El‐Araby

With rapid advancement in quantum computing technology, continuous efforts are being directed to simulation and emulation of quantum algorithms on classical platforms. A well-known limitation to classical emulation of quantum circuits is scalability. Existing hardware emulators implement gate-based circuit models of quantum circuits that result in heavy resource utilization and degrade the scalability of the system. Also, current quantum emulation hardware use fixedpoint arithmetic, which has an adverse effect on accuracy when the system is scaled up. In this work, we employ a complexmultiply-and-accumulate (CMAC) and lookup-based emulation approach that greatly reduces resource utilization and improves system scalability in terms of number of emulated qubits. We demonstrate emulation of up to 16 fully-entangled qubits which is highest among existing work. We design fully-pipelined, highthroughput hardware architectures that use floating-point precision for higher accuracy. Experimental evaluation and analysis of the architectures in terms of speed and area is also provided. The emulator is prototyped on a high-performance reconfigurable computing (HPRC) system and our results demonstrate quantitative improvement over existing Field-Programmable-Gate-Array (FPGA)-based hardware emulators.

IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP)Jul 1, 20192 citations

A Scalable High-Precision and High-Throughput Architecture for Emulation of Quantum Algorithms

Naveed Mahmud, Esam El‐Araby

Quantum hardware emulators using field programmable gate arrays (FPGAs) have been demonstrated to efficiently exploit the inherent parallelism of quantum algorithms and perform better than sequential software simulators. However, one key problem in mapping quantum circuits on FPGAs is the exponential increase in resource requirements with the increase in the number of quantum bits (qubits). As a result, the precision of hardware emulators is often reduced to save resources and accommodate larger quantum circuits which results in lower accuracy and lower throughput. In this paper, we present a full precision FPGA quantum emulator that uses 32-bit floating-point arithmetic and has a fully pipelined architecture. Our emulator is capable of emulating an entangled 4-qubit quantum system performing Quantum Fourier Transform, Grover's Search algorithms on a single FPGA node. Our experimental work was conducted on a highly scalable multi-node (multi-FPGA) state-of-the-art high-performance reconfigurable computer (HPRC). Experimental results show that our emulator is functionally accurate and has a higher operating frequency relative to other emulators. For emulating larger-scale circuits we propose using a multi-node architecture scheme with low latency, high bandwidth inter-node communication.

IEEE International System-on-Chip Conference (SOCC)Sep 1, 201812 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

Implementation Of Two Cross Two Switch To Implement Bitonic Sorting Circuit

Subhasree Bhattacharjee, Soumyadip Sarkar, Kunal Das +2 more

Abstract Reversible logic synthesis is becoming a significant research component for post-CMOS computing devices, particularly quantum computing. In this work we connect the reversible logic synthesis problem to sorting algorithms. Reversible logic has emerged as a promising technology in recent years, with applications in low power CMOS, quantum computing, nanotechnology, and optical computing. The classical gates AND, OR, and XOR are not reversible. This paper employs the control swap gate to implement a 2x2 switch. In multiprocessor system different computing operations are performed concurrently to get higher throughput. Sorting network can be used to tie up different parts of a large complex system efficiently with least amount of hardware to perform concurrent operations. A sorting network can be built using a multiple input and multiple output switching network. Following the implementation of the 2x2 switch, a bitonic sorting circuit is designed. The goal of developing a reversible sorting circuit is to reduce power consumption while maintaining reliable communication. The bitonic sorting circuit was successfully implemented, and the output was simulated in IBM qiskit. This presents efficient sorting circuit that can sort binary numbers in ascending/descending order.

Mar 6, 20240 citations

Towards Higher Scalability of Quantum Hardware Emulation Using Efficient Resource Scheduling

Naveed Mahmud, Esam El‐Araby

Quantum algorithms can be efficiently emulated on classical hardware such as field programmable gate arrays (FPGAs), achieving significant speedup over software simulations. However, the increase in the required hardware resources for emulating quantum systems becomes a critical limitation as the number of qubits is increased. In this paper, we propose a scalable emulation framework for modeling quantum algorithms on FPGAs that employs efficient resource scheduling such as space and space-time scheduling. In addition, full floating point precision arithmetic and dataflow non-linear (dynamic) pipelining are also used to achieve higher accuracy and higher throughput. We propose scalable and optimized hardware architectures for Quantum Fourier Transform (QFT) and Grover's search algorithm and demonstrate the scalability of our framework by scaling the system up to 5 fully-entangled qubits. A multi-node (multi-FPGA), state-of-the-art high-performance reconfigurable computer (HPRC) was used for implementation of the proposed architectures. Our experimental results show that by employing efficient resource scheduling techniques, the hardware resource constraints could be mitigated and the proposed emulation framework could be made feasible for emulation of more complex, larger-scale quantum algorithms while maintaining higher accuracy and throughput than existing work.

IEEE International Conference on Rebooting Computing (ICRC)Nov 1, 20189 citations

Utilization of Two Cross Two Switch for Bitonic Sorting Circuit

Subhasree Bhattacharjee, Soumyadip Sarkar, Kunal Das +2 more

Background: The synthesis of reversible logic has gained prominence as a crucial research area, particularly in the context of post-CMOS computing devices, notably quantum computing. Objective: To implement the bitonic sorting circuit, 2x2 switch, is used. The overarching objective of implementing a reversible sorting circuit is to mitigate power consumption while promising secure communication. The successful implementation of the bitonic sorting circuit utilizing the proposed 2x2 switch is validated through simulations conducted in IBM Qiskit. Methods: This study begins by employing the control swap gate to implement a 2x2 switch, aimed at enabling concurrent computing operations within multiprocessor systems to enhance throughput. Subsequently, following the successful implementation of the 2x2 switch, the study proceeds to design a bitonic sorting circuit. Results: Bitonic sort using a 2x2 switch on the IBM Quantum Experience (IBMQ) platform via the QISKit SDK in Python 3.6. Specifically, Qiskit v0.29.0 is utilized, with OpenQASM. OpenQASM serves as the quantum assembly and instruction language. Conclusion: This work presents a methodology for constructing a 2x2 switch, utilizing a reversible control swap gate as its core component. Additionally, it demonstrates the intricate development and implementation of a bitonic sorting circuit, capitalizing on this innovative switch architecture.

Micro and NanosystemsSep 27, 20241 citation