Implementation of Quantum Fourier Transform and Quantum Hashing for a Quantum Device with Arbitrary Qubits Connection Graphs

Abstract

In the paper, we consider quantum circuits for Quantum fingerprinting (quantum hashing) and quantum Fourier transform (QFT) algorithms. Quantum fingerprinting (quantum hashing) is a well-known technique for comparing large objects using small images. The QFT algorithm is a very popular technique used in many algorithms. We present a generic method for constructing quantum circuits for these algorithms for quantum devices with restrictions. Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates. The restrictions are presented by a qubits connection graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit. The heuristic version of the method is fast enough and works with $O(n^5)$ time complexity, where $n$ is the number of qubits. The certain version of the algorithm has an exponential time complexity that is $O(n^2{2}^n)$. We compare quantum circuits built by our algorithm with quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, ``sun'' (a cycle with tails, presented by 16-qubit IBMQ device) and ``two joint suns'' (two joint cycles with tails, presented by 27-qubit IBMQ device). Our generic method gives similar results with little bit more CNOT gates. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.

References in corpus (21)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Quantum fingerprinting
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Quantum circuits with uniformly controlled one-qubit gates
• Quantum query complexity of state conversion
• Quantum query complexity of some graph problems
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Quantum speedup of branch-and-bound algorithms
• Tradeoffs in the Quantum Search Algorithm
• Noisy intermediate-scale quantum simulation of the one-dimensional wave equation
• Exponential Separation of Quantum and Classical Online Space Complexity
• Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
• Quantum Algorithms for String Processing
• Multiqudit quantum hashing and its implementation based on orbital angular momentum encoding
• GAPs for Shallow Implementation of Quantum Finite Automata
• Shallow Implementation of Quantum Fingerprinting with Application to Quantum Finite Automata
• A Representative Framework for Implementing Quantum Finite Automata on Real Devices
• Quantum hashing. Group approach
• MLQM: Machine Learning Approach for Accelerating Optimal Qubit Mapping
• Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems