{"id":"arxiv/2605.20789","url":"https://arxiv.org/abs/2605.20789","tags":["quant-ph","cs.DS"],"score":0,"title":"Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity Graph","domain":"quant-ph","source":"arxiv","authors":["Kamil Khadiev","Ilnur Valeev"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-05-20","reactions":{}}