Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity Graph

Abstract

We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting) for a quantum device with restrictions on the application of two-qubit gates by a qubit connectivity graph. We present an optimization technique for the shallow circuit for quantum hashing in the case of a cactus as a qubit connectivity graph. The algorithm has $O(n^3)$ complexity to build the circuit, where $n$ is the number of qubits and $m$ is the number of connections (edges) in the graph. It is improvement compared to the existing exponential-time algorithm in the case of arbitrary graphs. The algorithm uses solution for the shortest non-simple 1-covering path problem as a subroutine. We present an $O(n^3)$-time solution for this graph-theory problem in the case of a cactus. This result can be interesting independently. The algorithm also used for improving of the quantum circuit for Quantum Fourier Transform.

More by Kamil Khadiev

• Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering PatharXiv · 2026
• Quantum k-means based on Quantum Local Sensitive Hashing with Application to Irrigation Machine Sensors Data ClusteringIEEE International Conference on Smart Computing Workshops and Other Affiliated Events · 2026
• Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs Based on 1-Cover PathInternational Conference on Quantum Communications, Networking, and Computing · 2026 · Citations: 1
• Quantum Random Forest for the Regression ProblemInternational Conference on Quantum Communications, Networking, and Computing · 2026