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

• URL: http://arxiv.org/abs/2605.20789v1
• Date: Wed, 20 May 2026 06:35:05 GMT
• Title: Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity Graph
• Abstract summary: We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting) for a quantum device.<n>We present an optimization technique for the shallow circuit for quantum hashing in the case of a cactus as a qubit connectivity graph.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering Path [0.0]
  Current quantum hardware has limited connections between qubits, with each qubit connected to only a few others.<n>We present an algorithm that converts a circuit containing a sequence of CNOT gates into a form that is suitable for arbitrary quantum computer architectures.
  arXiv  Detail & Related papers  (2026-08-10T05:26:52Z)
• Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs [0.0]
  Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates.<n>We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit for implementing on such architecture.
  arXiv  Detail & Related papers  (2025-10-10T19:54:00Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
  We use global interactions, such as the Global Molmer-Sorensen gate present in ion trap hardware, to optimize and synthesize quantum circuits.<n>The algorithm is based on the ZX-calculus and uses a specialized circuit extraction routine that groups entangling gates into Global MolmerSorensen gates.<n>We benchmark the algorithm in a variety of circuits, and show how it improves their performance under state-of-the-art hardware considerations.
  arXiv  Detail & Related papers  (2025-07-28T10:25:31Z)
• Implementation of Quantum Fourier Transform and Quantum Hashing for a Quantum Device with Arbitrary Qubits Connection Graphs [10.113567783910167]
  We consider quantum circuits for Quantum fingerprinting (quantum hashing) and quantum Fourier transform (QFT) algorithms.<n>We present a generic method for constructing quantum circuits for these algorithms for quantum devices with restrictions.
  arXiv  Detail & Related papers  (2025-01-30T18:59:59Z)
• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  lattice-based cryptography is one of the main candidates of post-quantum cryptography.<n> cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP)<n>Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
  arXiv  Detail & Related papers  (2024-10-17T16:54:41Z)
• Quantum hashing algorithm implementation [0.0]
  We implement a quantum hashing algorithm which is based on a fingerprinting technique presented by Ambainis and Frievalds, 1988, on gate-based quantum computers. We consider 16-qubit and 27-qubit IBMQ computers with the special graphs of qubits representing nearest neighbor architecture that is not Linear Nearest Neighbor (LNN) one.
  arXiv  Detail & Related papers  (2024-07-14T09:41:16Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
  We introduce a multiple-circuit algorithm for a quantum lattice Boltzmann method (QLBM) solve of the incompressible Navier--Stokes equations.<n>The presented method is validated and demonstrated for 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
  We present a quantum circuit compiler that prepares an algorithm-specific graph state from quantum circuits described in high level languages. The computation can then be implemented using a series of non-Pauli measurements on this graph state.
  arXiv  Detail & Related papers  (2022-09-15T14:52:31Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.