Implementation of Quantum Fourier Transform and Quantum Hashing for Quantum Devices with Arbitrary Qubit Connectivity Graphs

Kamil Khadiev; Aliya Khadieva; Zeyu Chen; Junde Wu

doi:10.2478/qic-2025-0028

Full Article

1.

Introduction

The quantum Fourier transform (QFT) [1] is a well-known computational technique used in many quantum algorithms. The technique is used in quantum addition [2], quantum phase estimation (QPE) [1], quantum amplitude estimation (QAE) [3], the algorithm for solving linear systems of equations [4], Shor’s factoring algorithm [5], 1D wave equation [6], Quantum walks [7–9] with applications to quantum backtracking [10,11] and others.

In this paper, we are interested in the implementation of this technique on quantum devices as a quantum circuit with basic gates. There are different ways to optimize the circuits, such as invoking it in a parallel way [12] or approximate QFT [13]. We are focusing on the minimization of two-qubit quantum gates in such a circuit because they are the most “expensive” to implement. Many types of quantum computers (e.g., quantum devices based on superconductors) do not allow us to apply two-qubit gates to an arbitrary pair of qubits but have a graph that represents such a restriction. Vertices of the graph correspond to qubits, and two-qubit gates can be applied only to qubits corresponding to vertices connected by an edge. We say that such a graph represents the qubit topology for a device. In this paper, we focus on the number of CNOT gates in a quantum circuit for the QFT algorithm with respect to such a graph. Let a CNOT cost of a circuit be the number of CNOT gates in the circuit. The CNOT cost for a linear nearest-neighbor (LNN) architecture (where the graph is just a chain) was explored by Park and Ahn in [14]. They presenteda circuit that has n² + n – 4 CNOT cost, where n is the number of qubits. It improved the previous results of [15–22]. At the same time, as the authors mentioned, their technique cannot be generalized to more complex graphs. Khadieva in [23] suggested a quantum circuit for a more complex architecture that is a cycle with tails (like a “sun” or “two joint suns”). At the same time, the CNOT cost of this circuit is 1.5n².

Here, we present a general method that allows us to develop a quantum circuit of the QFT algorithm for an arbitrary connected graph that represents a qubit connectivity graph. Our solution is based on a solution for the Travelling salesman problem (TSP) for a modification of the original graph. Here we present a method and an algorithm for constructing a circuit with O(n²2ⁿ) time complexity, where n is the number of vertices of the original graph and the approximate solution with polynomial time complexity O(n⁶) and the differential approximation ratio $\frac{1}{2}$ {1 \over 2}.

The constructed circuit has the CNOT cost from n² – n – 4 to 3n² – 3n – 10 depending on the complexity of the graph. If the graph has a Hamiltonian path, then it has the minimum possible CNOT cost at most 1.5n² – 1.5n – 1. In addition, we compare our results with circuits for specific graphs. In the case of LNN, the CNOT cost is 1.5n² – 1.5n – 1, that is, 1.5 times larger than the result of [14]. The circuits built by our approach are larger by n CNOT gates than the circuit of [23] with the CNOT cost 1.5n² – 2.5n – 1. For more complex graphs such as 16-qubit and 27-qubit Eagle r3 architectures of IBMQ that is a cycle with tails (like a “sun”) or its modifications, our generic technique gives a CNOT cost a bit larger than the circuit [23] that was especially constructed for these architectures. Our circuits have CNOT cost 342 for the 16-qubit architecture and 1009 for the 27-qubit one; and [23] has CNOT cost 324 and 957, respectively. The difference is about 5%.

Another technique discussed in this paper is quantum fingerprinting, or quantum hashing. This technique is well known, and it allows us to compute a short hash or fingerprint that identifies an original large data with high probability. The nature of the technique and its implementation is similar to the QFT algorithm [23,24].

The probabilistic (randomized) technique was developed by Frievalds [25]. Then, Ambainis and Frievalds [26] developed its quantum counterpart for automata that was improved by Ambainis and Nahimovs in [27,28]. Later, Buhrman et al. in [29] provided an explicit definition of the quantum fingerprinting technique to construct an efficient quantum communication protocol for equality testing. The technique was applied for branching programs by Ablayev, Gainutdinova, Vasiliev, and co-authors [30–34]. Later, they developed the concept of cryptographic quantum hashing [35–46]. Then, different versions of hashing functions were applied by Ablayev, Vasiliev, Ziiatdinov, Zinnatullin, and other researchers [24, 47–50]. The technique was also extended for qudits [51]. This approach was widely used in different areas like stream processing algorithms [52,53], query model algorithms [54,55], online algorithms [56–62], branching programs [63–65], developing quantum devices [66], automata (discussed earlier, [67–71]), and others.

Turaykhanov, Akat’ev, and co-authors implemented the technique in a real quantum device based on photons [72,73]. The alternative implementation for photon-based real quantum devices was developed by Plachta et al. [74] and Zhao et al. [75]. At the same time, the algorithm was embedded in this device. When we discuss the implementation of the algorithm for “universal” quantum devices such as IBMQ quantum computers or similar, it is important to minimize the number of quantum gates with respect to the architecture restrictions of a quantum device, as we discussed for QFT above. The basic implementation part of quantum hashing circuits is a uniformly controlled rotation operator. The CNOT cost of this operator with respect to the qubit connectivity graph was previously discussed in [76,77] for the linear nearest-neighbor (LNN) architecture and in [78] for more complex graphs. At the same time, the presented approaches have issues with the rotation angle precision, which cannot be too small. This issue is discussed in [79,80].

Kālis in his master’s thesis [81] suggested a shallow circuit for quantum fingerprinting for 3 qubits. Later, the approach was developed in detail and presented in a general way for quantum hashing by Ziatdinov, Khadieva, and Yakaryilmaz [82,83]. The approach allows us to reduce the number of CNOT gates exponentially in computational experiments. At the same time, the theoretical exponential superiority of the shallow circuit is not shown [82,83]. By the way, the method is very perspective for current and near-future quantum devices that definitely cannot support a huge number of CNOT gates. The efficient implementation of the shallow circuit for an automaton that recognizes the MOD_p = {a^k : k mod p = 0} language based on the quantum hashing algorithm was proposed by Khadieva, Salehi, and Yakaryilmaz [79] for devices based on the LNN architecture. Later, a similar technique was applied by Khadieva [23] for a more complex architecture that is a cycle with tails (like a “sun” and “two joint suns”) represented by 16-qubit and 27-qubit Eagle r3 IBMQ architectures. Vasiliev [84] discussed a similar method, but for Rz gates instead of Ry gates.

In this paper, we present a general method that allows us to develop a quantum circuit of the quantum hashing algorithm for an arbitrary qubit connectivity graph. It uses the same tools and approaches as the algorithm for constructing the circuit of QFT. Note that the shallow circuit for quantum fingerprinting and the circuit for QFT have similar structures as was discussed by Khadieva [23]. That is why we consider these two topics together and use common methods for both algorithms.

The CNOT cost of the constructed circuit is from 2n – 2 to 6n – 11 depending on the complexity of the graph. The presented cost value is for one implementation step of the quantum hashing algorithm. If we present the complexity of ℓ steps of the algorithm, then the constructed circuit has the CNOT cost from (2n – 4)ℓ + 2 to (6n – 13)ℓ + 2, which depends on the complexity of the graph. When we apply our approach to the LNN architecture, we obtain a circuit with the same CNOT cost as the circuit specially built for the LNN architecture [79]. If we consider 16- and 27-qubit Eagle r3 IBMQ architectures, then we have a similar situation [23].

The structure of this paper is as follows: Section 2 describes the required notations and preliminaries. Graph theory tools are presented in Section 3. Section 4 provides an algorithm for generating a quantum circuit for quantum hashing. The circuit for the quantum Fourier transform is discussed in Section 5. The final Section 6 concludes the paper and contains some open questions.

2.

Preliminaries

2.1.

Graph Theory

Consider an undirected unweighted graph G = (V, E), where V is the set of vertices and E is the set of undirected edges. Let n = |V| be the number of vertices, and m = |E| be the number of edges.

A non-simple path P is a sequence of vertices (v_i₁, …, v_{i_h}) that are connected by edges, i.e., (v_{i_j}, v_{i_j+1}) ∈ E for all j ∈ {1, …, h – 1}. A path is called a non-simple cycle if v_i₁ = v_{i_h}. Note that a non-simple path and a non-simple cycle can contain duplicates. Let the length of the path be the number of edges in the path, len(P) = h – 1.

A path P = (v_i₁, … v_{i_h}) is called simple if there are no duplicates among v_i₁, …, v_{i_h}. A simple cycle C = (v_i₁ … v_{i_h}) is a non-simple path with only one duplicate v_i₁ = v_{i_h}. The distance dist(v, u) is the length of the shortest path between vertices v and u.

Let Neighbors (v) be a list of neighbors for a vertex v, i.e., Neighbors (v) = (u_i₁, …, u_{i_k}) such that (v, u_{i_j}) ∈ E.

Let us consider an undirected weighted graph S = (V′, E′), where V′ is the set of vertices, and E′ is the set of undirected weighted edges. Let w : V′ × V′ → ℝ be a weight function. We assume that w(v, u) = ∞ if (v, u) ∉ E.

For a path P = (v_i₁, …, v_{i_h}),the length w(P) is the sum of edge weights in the path, i.e., $w (P) = \sum_{j}^{h - 1} w (v_{i_{j}}, v_{i_{j + 1}})$ w(P) = \sum\limits_j^{h - 1} w \left( {{v_{{i_j}}},{v_{{i_{j + 1}}}}} \right).

2.2.

Quantum Circuits

Quantum circuits consist of qubits and gates. A state of a qubit is a column vector from the ℋ² Hilbert space. It can be represented by a₀|0〉 + a₁|1〉, where a₀, a₁ are complex numbers such that |a₀|² + |a₁|² = 1, and |0〉 and |1〉 are unit vectors. Here we use the Dirac notation. A state of n qubits is represented by a column vector from the ℋ^2ⁿ Hilbert space. It can be represented by $\sum_{i = 0}^{2^{n} - 1} a_{i} | i 〉$ {\sum\nolimits_{i = 0}^{{2^n} - 1} a _i}|i\rangle where a_i is a complex number such that $\sum_{i = 0}^{2^{n} - 1} {| a_{i} |}^{2} = 1$ \sum\nolimits_{i = 0}^{{2^n} - 1} {{{\left| {{a_i}} \right|}^2} = 1} , and |0〉, … |2ⁿ – 1〉 are unit vectors. Graphically, on a circuit, qubits are presented as lines.

As basic gates, we consider the following ones: $H = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}), X = (\begin{array}{l} 0 & 1 \\ 1 & 0 \end{array}), R_{y} (ξ) = (\begin{matrix} c o s (ξ / 2) & - s i n (ξ / 2) \\ s i n (ξ / 2) & c o s (ξ / 2) \end{matrix}),$ H = {1 \over {\sqrt 2 }}\left( {\matrix{ 1 & 1 \cr 1 & { - 1} \cr } } \right),X = \left( {\matrix{ 0 \hfill & 1 \hfill \cr 1 \hfill & 0 \hfill \cr } } \right),{R_y}(\xi ) = \left( {\matrix{ {cos(\xi /2)} & { - sin(\xi /2)} \cr {sin(\xi /2)} & {cos(\xi /2)} \cr } } \right), $R_{z} (ξ) = (\begin{matrix} e^{\frac{i ξ}{2}} & 0 \\ 0 & e^{- \frac{i ξ}{2}} \end{matrix}), C N O T = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}) .$ {R_z}(\xi ) = \left( {\matrix{ {{e^{{{i\xi } \over 2}}}} & 0 \cr 0 & {{e^{ - {{i\xi } \over 2}}}} \cr } } \right),{\rm{ }}CNOT{\rm{ }} = \left( {\matrix{ 1 & 0 & 0 & 0 \cr 0 & 1 & 0 & 0 \cr 0 & 0 & 0 & 1 \cr 0 & 0 & 1 & 0 \cr } } \right).

Additionally, we consider five non-basic gates $R_{d} = (\begin{matrix} 1 & 0 \\ 0 & e^{\frac{i π}{2^{d - 1}}} \end{matrix}), C R_{d} = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^{\frac{i π}{2^{d - 1}}} \end{matrix}), C R_{z} (ξ) = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & e^{\frac{i ξ}{2}} & 0 \\ 0 & 0 & 0 & e^{- \frac{i ξ}{2}} \end{matrix}),$ {R_d} = \left( {\matrix{ 1 & 0 \cr 0 & {{e^{{{i\pi } \over {{2^{d - 1}}}}}}} \cr } } \right),C{R_d} = \left( {\matrix{ 1 & 0 & 0 & 0 \cr 0 & 1 & 0 & 0 \cr 0 & 0 & 1 & 0 \cr 0 & 0 & 0 & {{e^{{{i\pi } \over {{2^{d - 1}}}}}}} \cr } } \right),C{R_z}(\xi ) = \left( {\matrix{ 1 & 0 & 0 & 0 \cr 0 & 1 & 0 & 0 \cr 0 & 0 & {{e^{{{i\xi } \over 2}}}} & 0 \cr 0 & 0 & 0 & {{e^{ - {{i\xi } \over 2}}}} \cr } } \right), $S W A P = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}), C R_{y} (ξ) = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & c o s (ξ / 2) & - s i n (ξ / 2) \\ 0 & 0 & s i n (ξ / 2) & c o s (ξ / 2) \end{matrix}) .$ SWAP = \left( {\matrix{ 1 & 0 & 0 & 0 \cr 0 & 0 & 1 & 0 \cr 0 & 1 & 0 & 0 \cr 0 & 0 & 0 & 1 \cr } } \right),C{R_y}(\xi ) = \left( {\matrix{ 1 & 0 & 0 & 0 \cr 0 & 1 & 0 & 0 \cr 0 & 0 & {cos(\xi /2)} & { - sin(\xi /2)} \cr 0 & 0 & {sin(\xi /2)} & {cos(\xi /2)} \cr } } \right).

The reader can find more information about quantum circuits in [15,85,86]

3.

Tools

Let us consider an undirected unweighted connected graph G = (V, E) such that n = |V| is the number of vertices and m = |E| is the number of edges.

In this section, we consider the problem of searching for the shortest non-simple path in the graph G that visits all vertices at least once. Formally, we want to construct a non-simple path P = (v_i₁, …, v_{i_k}) such that

the path visits all vertices, i.e., {v_i₁, …, v_{i_k}} = V; and
the length of the path P is as small as possible.

The problem is close to the Hamiltonian path problem [87], but here we are allowed to visit a vertex several times. That is why any connected graph has the required path.

To solve this problem, we construct a new complete weighted graph S = (V′, E′) such that

The set of vertices V′ is the same as the set of vertices V.
Each pair of vertices u′, v′ ∈ V′ is connected, and the weight w(u′, v′) is the length of the shortest path between the corresponding vertices u and v from V, i.e., w(u′, v′) = dist(u, v).

We call it the “supergraph.” Let a TSP path (or a Travelling salesman problem path) P′ be the shortest simple path in S that visits all vertices from V′ exactly once [87]. In a similar way, we can define a TSP cycle C′.

For a TSP path P′ = (v_i₁, …, v_{i_n}), let α(P′) be the path in G such that $α (P^{'}) = P_{v_{i_{1}}, v_{i_{2}}} ° {\tilde{P}}_{v_{i_{2}}, v_{i_{3}}} ° {\tilde{P}}_{v_{i_{3}}, v_{i_{4}}} ° \dots ° {\tilde{P}}_{v_{i_{n - 1}}}, v_{i_{n}} .$ \alpha \left( {{P^\prime }} \right) = {P_{{v_{{i_1}}},{v_{{i_2}}}}}^\circ {{\tilde P}_{{v_{{i_2}}},{v_{{i_3}}}}}^\circ {{\tilde P}_{{v_{{i_3}}},{v_{{i_4}}}}}^\circ \cdots ^\circ {{\tilde P}_{{v_{{i_{n - 1}}}},}},{v_{{i_n}}}.

Here P_{v_i₁, v_i₂} is the shortest path in G between v_i₁ and v_i₂; the path ${\tilde{P}}_{v_{i_{j}}, v_{i_{j + 1}}}$ {{\tilde P}_{{v_{{i_j}}},{v_{{i_{j + 1}}}}}} is the shortest path in G between v_{i_j} and v_{i_j+1} excluding the first vertex in the path that is v_{i_j}; ⚬ is the concatenation operation.

A TSP path for S and the shortest non-simple path in G that visits all vertices at least once has the following connection.

Lemma 1.

The shortest non-simple path P in G that visits all vertices can be obtained by a TSP path P′ for S as P = α(P′).

Proof.

Let P = α(P′). Assume that there is another non-simple path $\hat{P}$ {\hat P} that is shorter than P and visits all vertices of G at least once, i.e., $l e n (\hat{P}) < l e n (P)$ len(\hat P) < len(P). Let (i₁, …, i_n) be the permutation of (1, …, n) that presents the order of visiting vertices by $\hat{P}$ {\hat P} for the first time. The length of the simple path ${\hat{P}}^{'} = (v_{i_{1}}^{'}, \dots, v_{i_{n}}^{'})$ {{\hat P}^\prime } = \left( {v_{{i_1}}^\prime , \ldots ,v_{{i_n}}^\prime } \right) in S is less than or equal to the length of the non-simple path $\hat{P}$ {\hat P} in G, i.e., $l e n (\hat{P}) \geq w ({\hat{P}}^{'})$ len(\hat P) \ge w\left( {{{\hat P}^\prime }} \right). This happens because the weight of an edge in S is the length of the shortest path between the corresponding vertices of G. At the same time, we have no guarantee that $\hat{P}$ {\hat P} goes by this shortest path between vertices. Formally, for any index j, the weight of the edge in S between the vertices $v_{i_{j}}^{'}$ v_{{i_j}}^\prime and $v_{i_{j + 1}}^{'}$ v_{{i_{j + 1}}}^\prime is $w (v_{i_{j}}^{'}, v_{i_{j + 1}}^{'}) \leq i_{j + 1} - i_{j}$ w\left( {v_{{i_j}}^\prime ,v_{{i_{j + 1}}}^\prime } \right) \le {i_{j + 1}} - {i_j}. At the same time, ${\hat{p}}^{'}$ {{\hat p}^\prime } visits all vertices of S. So, $w (P^{'}) \leq w ({\hat{P}}^{'})$ w\left( {{P^\prime }} \right) \le w\left( {{{\hat P}^\prime }} \right) because P′ is a TSP path. Summarizing, $l e n (P) = w (P^{'}) \leq w ({\hat{P}}^{'}) \leq l e n (\hat{P})$ len(P) = w\left( {{P^\prime }} \right) \le w\left( {{{\hat P}^\prime }} \right) \le len(\hat P). It contradicts our assumption $l e n (P) > l e n (\hat{P})$ len(P) > len(\hat P).

There is also a similar connection for cycles.

Lemma 2.

The shortest non-simple cycle C in G that visits all vertices can be obtained by a TSP cycle C′ for S as C = α(C′).

Proof.

The proof is the same as for Lemma 1.

We can note the following property:

Lemma 3.

The length of the shortest non-simple path P that visits all vertices in G at least once is such that n – 1 ≤ len(P) ≤ 2n – 2. A similar result is for a cycle C, i.e., n ≤ len(C) ≤ 2n – 2

Proof.

Let us consider a spanning tree of the graph G = (V, E). It is a tree T = (V, E′), where E′ ⊂ E. The path should visit all vertices. So, we can construct a non-simple path P that is the Euler tour [87] of the tree T. The path covers all the vertices of the graph G, but may not be the shortest. Each edge in the tour is visited at most twice (in the up- and down-direction). There are n – 1 edges in the tree. Therefore, the length of the path is at most 2n – 2. For a cycle, we have a similar situation.

Based on this connection, we can suggest an algorithm for searching the shortest non-simple path in the graph G that visits all vertices at least once.

Assume that we have a procedure that finds a TSP path for S that is TSPpath(S). As an algorithm, we can use the Bellman-Held-Karp algorithm [88,89]. The algorithm has O(n²2ⁿ) time complexity.

Additionally, we have a procedure ShortestPaths(G) that constructs two n × n-matrices W and A by a graph G.

Elements of the matrix W are the lengths of the shortest paths between each pair of vertices in G, i.e., W[v, u] = dist(v, u). We can use W as a weight matrix for S. In other words, w(v′, u′) = W[v, u], where v′, u′ ∈ V′, and v and u are the corresponding vertices from V.

The matrix A represents the shortest paths between the vertices of G. The element A[v, u] is the last vertex before u in the shortest path from v to u. In other words, if t = A[v, u], then P_{v, u} = P_{v, t} ⚬ u. Based on this fact, we can present a procedure GetPath(v, u) that computes P_{v, u} using the matrix A. The implementation of the procedure is presented in Algorithm 1.

Algorithm 1 Implementation of GetPath(v, u)

t ← A[v, u]

P_{v, u} ← (u)

while t ≠ v do

P_{v, u} ← (t) ⚬ P_{v, u}

t ← A[v, t]

end while

P_{v, u} ← (v) ⚬ P_{v, u}

return P_{v, u}

Let the procedure GetPathNoFirst(v, u) return ${\tilde{P}}_{v, u}$ {{\tilde P}_{v,u}}, that is, the path P_{v, u} without the first element. The implementation is the same, but without the P_{v, u} ← (v) ⚬ P_{v, u} line.

We can construct these two matrices using n invocations of the Breadth First Search (BFS) algorithm [87]. The total time complexity for the construction of the matrices is O(n³). The algorithm for constructing A and W is presented in Appendix D for completeness of presentation.

Due to V′= V, and the matrix W representing the weights of the supergraph’s edges, we can say that ShortestPaths(G) constructs the graph S.

Finally, we can present Algorithm 2 to solve the problem.

Algorithm 2 Implementation Algorithm for searching a shortest non-simple path in the graph G that visits all vertices at least once

W, A ← ShortestPaths(G) ▷W and V define S

(v_i₁, …, v_{i_k}) = P′ ← TSPpath(S)

α(P′) ← GetPath(v_i₁, v_i₂)

for j ∈ {2, …, k – 1} do

α(P′) ← α(P′) ⚬ GetPathNoFirst(v_{i_j}, v_{i_j+1})

end for

Note that if we replace the procedure TSPpath(S) by the procedure TSPcycle(S) that finds a TSP cycle, then we find the shortest non-simple cycle in G that visits all vertices at least once. The time complexity of TSPcycle(S) is the same.We can also modify TSPpath(S) such that it finds a path from the fixed starting vertex v_start that is TSPpath(S, v_start).

Theorem 1.

The time complexity of the presented solution for searching the shortest non-simple path, a path with a fixed starting vertex or a cycle that visits all vertices at least once in the graph G = (V, E) is O(n²2ⁿ), where n = |V|.

Remark 1.

We can solve the same problem using quantum algorithms. For TSPpath(S), TSPpath(S, v_start) and TSPcycle(S), we can use the quantum analogue of Bellman-Held-Karp algorithm presented by Ambainis et al. [90]. For ShortestPaths(S), we can use the quantum version of the BFS algorithm [91–93] several times.

The query complexity of the algorithm [90] presented by Ambainis et al. is O* (1.728ⁿ), where O* hides logfactors. The algorithm is based on the Grover search algorithm, whose time complexity is more than the query complexity for an additional log factor [94,95]. So, the time complexity is also O* (1.728ⁿ). If we want to discuss it more precisely, then we can check [90,96] which claims the query complexity O(n³1.728ⁿ).

Finally, the complexity of the quantum algorithm for the problem is O* (1.728ⁿ). At the same time, for current applications, we need only a classical solution.

3.1.

Heuristic Solution for Searching a Shortest Non-simple Path That Visits All Vertices Problem

In the practical case, when we have more than 20–30 vertices in a graph, the exact algorithm presented before is too slow. In this section, we present a heuristic solution with polynomial-time complexity, and the outcome is close, under certain criteria, to the optimal solution.

Using a path P = (v_i₁, …, v_{i_h}), we can construct a sequence of edges ((v_i₁, v_i₂), (v_i₂, v_i₃), …, (v_{i_h–1}, v_{i_h})). We can say that these are two equivalent representations of the path. We use both in this section.

Note that the supergraph S defined in Section 3 satisfies the following conditions:

S is complete and weighted.
The weight of an edge from S is at most n because it is the distance between two vertices in the original graph. Formally, w(v′, u′) = dist(v, u) ≤ n, where v′, u′ ∈ V′, and v, u ∈ V.
S is metric. This means that the edges satisfy the triangle inequality: $w (v_{i}^{'}, v_{j}^{'}) \leq w (v_{i}^{'}, v_{k}^{'}) + w (v_{k}^{'}, v_{j}^{'})$ w\left( {v_i^\prime ,v_j^\prime } \right) \le w\left( {v_i^\prime ,v_k^\prime } \right) + w\left( {v_k^\prime ,v_j^\prime } \right) for any $v_{i}^{'}, v_{j}^{'}, v_{k}^{'} \in V^{'}$ v_i^\prime ,v_j^\prime ,v_k^\prime \in {V^\prime }.

Now we present a heuristic procedure 2-Opt(S) to find a good solution to the TSP problem. It finds a TSP cycle C. The algorithm for cycles in the case of general weighted metric graphs was presented in [97–99]. Here we present modifications for our graph and for searching a path.

We assume that we have two operations for modification of the list of edges that represents a cycle C:

Replace(C, (v_{i_j}, v_{i_j+1}), (u, v)) that replaces the edge (v_{i_j}, v_{i_j+1}) in C by the edge (u, v)
Reverse(C, (v_{i_j}, v_{i_j+1}), (v_{i_k}, v_{i_k+1})) that reverses all elements of the list between (v_{i_j}, v_{i_j+1}) and (v_{i_k}, v_{i_k+1}). Both elements (v_{i_j}, v_{i_j+1}) and (v_{i_k}, v_{i_k+1}) remain in place.

Both operations can be implemented with O(1) time complexity if C is implemented by the two-directional Linked List data structure [87].

Firstly, we initialize the cycle by ((v₁, v₂), …, (v_n–1, v_n), (v_n, v₁)). Then we repeatedly replace two edges of the cycle as long as this yields a shorter cycle. We check all possible pairs. The implementation is presented in Algorithm 3.

In the case of searching for a path, we have two modifications. That is, if a starting vertex v_s and a finishing vertex v_f are fixed, then we initialize the path by $\begin{matrix} C \leftarrow ((v_{s}, v_{1}), \dots, (v_{s - 2}, v_{s - 1}), (v_{s - 1}, v_{s + 1}), \dots, (v_{f - 2}, v_{f - 1}), \\ (v_{f - 1}, v_{f + 1}) (v_{f + 1}, v_{f + 2}), \dots, (v_{n - 1}, v_{n})), (v_{n}, v_{f})) . \end{matrix}$ \matrix{ {C \leftarrow \left( {\left( {{v_s},{v_1}} \right), \ldots ,\left( {{v_{s - 2}},{v_{s - 1}}} \right),\left( {{v_{s - 1}},{v_{s + 1}}} \right), \ldots ,\left( {{v_{f - 2}},{v_{f - 1}}} \right),} \right.} \cr {\left. {\left. {\left( {{v_{f - 1}},{v_{f + 1}}} \right)\left( {{v_{f + 1}},{v_{f + 2}}} \right), \ldots ,\left( {{v_{n - 1}},{v_n}} \right)} \right),\left( {{v_n},{v_f}} \right)} \right).} \cr }

Without loss of generality, we can assume that s < f. If the starting and finishing vertices are not fixed, then we check all possible vertices from V′ as v_s and v_f.

Experiments on real-world instances have shown that 2-Opt(S) achieves much better results than Christofide’s algorithm [100]. Generally, the worst case of 2-Opt(S) may lead to exponential complexity. However, direct analysis shows that the complexity of 2-Opt(S) in the case of supergraphs is O(n⁴) for cycles and for paths with a fixed starting vertex, where n is the number of vertices.

Algorithm 3 Implementation of 2-Opt(S)

C((v₁, v₂), …, (v_n–1, v_n), (v_n, v₁))

stopFlag ← False

while stopFlag = False do

stopFlag → True

for k ∈ {1, …, n} do

for j ∈ {k + 1,…, n} do

if w(v_{i_k}, v_{i_k+1}) + w(v_{i_j}, v_{i_j+1}) > w(v_{i_k}, v_{i_j}) + w(v_{i_k+1}, v_{i_j+1}) then

Reverse(C, (v_{i_k}, v_{i_k+1}), (v_{i_j}, v_{i_j+1}))

Replace(C, (v_{i_k}, v_{i_k+1}), (v_{i_k}, v_{i_j}))

Replace(C, (v_{i_j}, v_{i_j+1}), (v_{i_k+1}, v_{i_j+1}))

stopFlag ← False

break both For-loops

end if

end for

end while

return C

Theorem 2.

The time complexity of 2-Opt(S) for the supergraph S constructed by G is O(n⁴) in the case of a cycle; in the case of a path with a fixed starting vertex, it is O(n⁵); and in the case of a path, it is O(n⁶).

Proof.

Initialization of C takes O(n) time. Since the weights of the edges are bounded above by n, the weight of any Hamiltonian cycle C is bounded above by n². In each step of “replacing two edges,” the weight of C is reduced by at least 1, which implies that there are O(n²) steps of “replacing two edges.” In each step, there are O(n²) pairs of edges to compare, and the comparison and replacement of edges takes constant time. In summary, the total complexity is O(n⁴).

In the case of a path with a fixed starting vertex, we also check all finishing vertices. The number of finishing vertices is n. So, the complexity is O(n⁵) for searching the path.

In the case of a path, we also check all starting vertices. The number of starting vertices is n. So, the complexity is O(n⁶) for searching the path.

The heuristic algorithm 2-Opt(S) is designed to compute feasible solutions that are as close as possible to the optimal ones with respect to some criterion. We present two paradigms dealing with polynomial approximation. More details can be found in [98,101].

Definition 1.

Let I be an input and 𝒜 be an approximation algorithm. Let len_opt (I) be the length of a path that returns an optimal solution for the given instance I. Let len_w(I) be the worst possible length that a feasible solution returns for I. Let len_𝒜 (I) be the length of the approximation algorithm’s solution. Then, for an instance I

the standard approximation ratio is $ρ_{A} (I) = \frac{l e n_{A} (I)}{l e n_{o p t} (I)};$ {{\rm{\rho }}_{\cal A}}(I) = {{le{n_{\cal A}}(I)} \over {le{n_{opt}}(I)}}
the differential approximation ratio is $δ_{A} (I) = \frac{| l e n_{w} (I) - l e n_{A} (I) |}{| l e n_{w} (I) - l e n_{o p t} (I) |} .$ {\delta _{\cal A}}(I) = {{\left| {le{n_w}(I) - le{n_{\cal A}}(I)} \right|} \over {\left| {le{n_w}(I) - le{n_{opt}}(I)} \right|}}.

Note that if the ratios are close to 1, then the algorithm has better quality.

For the heuristic algorithms for the traveling salesman problem, we have the following results.

Lemma 4 ([97–99]).

The differential approximation ratio for the 2-Opt(𝒮) solution of the Traveling salesman problem achieves $\frac{1}{2}$ {1 \over 2}, and if the graph is metric, the standard approximation ratio achieves $\sqrt{\frac{n}{2}}$ \sqrt {{n \over 2}} . Both of the ratios are tight.

4.

Method for Constructing a Circuit for Quantum Hashing

In this section, we present a method that allows us to construct a circuit for the quantum fingerprinting or quantum hashing algorithm for a connected graph G = (V, E) that is the qubit connectivity graph for a device. More information on the quantum fingerprinting (quantum hashing) algorithm can be found in Appendix B. Here we consider a shallow circuit [81,82] for n control qubits. If we do not have restrictions for applying two-qubit gates (when G is a complete graph or a “star” graph), then the circuit is such that we presented in Figure 1. Here we assume that we have qubits q₁, …, q_n such that q₁, …, q_n–1 are control ones and q_n is the target one.

Let q_i be the logical qubits of the original circuit; the qubits of a physical device are associated with vertices of the graph G, and we call them v_i.

The algorithm for constructing a circuit is the following. We also present it in a flowchart in Figure 2.

Step 1.
We find the shortest non-simple path in the graph G that visits all vertices at least once using the algorithm from Section 3. Assume that the path is P = (v_i₁, …, v_{i_k}).
Step 2.
The target qubit q_n corresponds to the vertex v_i₂. The control qubits q₁, …, q_n–1 correspond to other vertices. We assume that we have a set U of control qubits that are already used. Initially, it is empty U ← ∅. Let j be the index of the element in the path P that corresponds to the target qubit. Initially, j ← 2.
Step 3.
We apply controlled rotation with the control v_i₁ and the target v_i₂ qubits. Then, we add v_i₁ to the set U, i.e., U ← U ∪ {v_i₁}.

In the next steps the target qubit travels along the path P.
Step 4.
If v_{i_j+1} ∉ U, then we apply a controlled rotation to the control v_{i_j+1} and the target v_{i_j} qubits. After that, we add v_{i_j+1} to the set U, i.e., U ← U ∪ {v_{i_j+1}}. If j = k – 1, then we terminate the algorithm. Otherwise, we go to Step 5.
Step 5.
If v_{i_j+2} ≠ v_{i_j}, then we continue; otherwise, we go to Step 6. We apply the SWAP gate to v_{i_j} and v_{i_j+1}. After that, we update j ← j + 1 because the value of the target qubit moves to v_{i_j+1}. Then, we go to Step 4.
Step 6.
If v_{i_j+2} = v_{i_j}, then we update j ← j + 2. Note that here we stay on the same vertex of the graph G. Then, we go to Step 4.

Let us present a procedure ConstructForPath(P) in Algorithm 4 that implements the above idea for a given path P = (v_i₁, …, v_{i_k}). We assume that we have cR(u, v) procedure that applies the controlled rotation operator CR_y to u as a control qubit and v as a target one. The angle ξ_r corresponds to the qubit q_r associated with the vertex v. Additionally, we have swap(u, v) procedure that applies the swap gate to u and v qubits.

We assume that ShortestNSPath(G) returns a shortest non-simple path in the graph G that visits all vertices at least once. The implementation of this procedure can be found in Algorithm 2 or Algorithm 3. Finally, we can present Algorithm 5 as an implementation of the quantum fingerprinting (quantum hashing) algorithm.

Proof.

Let us look to the shortest path P = (v_i₁, …, v_k) that visits all vertices at least once.

The shallow circuit (Figure 1) is such that we should apply controlled rotation operators with each qubit as the control qubit and a specific qubit as the target.

The algorithm places the target qubit at v_i₂. Then, we apply the controlled rotation operator with v_i₁ as the control qubit. After that, we apply the controlled rotation operator with v_i₃ as the control qubit. Then, we move the target qubit to v_i₃ using the swap operator and apply the controlled rotation operator with v_i₄ as the control qubit.

So, if the target qubit is in v_{i_j}, then we apply the controlled rotation operator with v_{i_j+1} as the control qubit and move the target qubit to v_{i_j+1} using the swap gate.

We apply the controlled rotation operator with v_{i_j+1} as the control qubit only if it is not in the set U and then add it to the set U. This action guarantees us that we apply the controlled rotation with each qubit only once. At the same time, the path visits each vertex at least once. This means that each qubit (vertex) occurs as v_{i_j+1} for some j. So, we apply the controlled rotation operator with each qubit exactly once, and there are no other modifications of the target qubit. Therefore, the circuit implements the shallow circuit of the quantum fingerprinting (quantum hashing) algorithm presented in Figure 1. At the same time, we apply the swap or controlled rotation operators only to neighboring qubits.

Algorithm 4 Implementation of ConstructForPath(P) procedure. Algorithm of constructing circuit for quantum hashing or quantum fingerprinting for a path P = (v_i₁, …, v_{i_k})

U ← ∅ ▷Step 2

j ← 2

cR(v_i₁, v_i₂) ▷Step 3

U ← U ∪ {v_i₁}

while j < k do

if v_{i_j+1} ∉ U then ▷Step 4

cR(v_{i_j+1}, v_{i_j})

U ← U ∪ {v_{i_j+1}}

end if

if j = k – 1 then

j ← + j + 1

else

if v_{i_j+2} = v_{i_j} then

j ← j + 2 ▷Step 6

else

swap(v_{i_j}, v_{i_j+1}) ▷Step 5

j ← j + 1

end if

end while

Algorithm 5 Algorithm of constructing circuit for quantum hashing or quantum fingerprinting for a path P = (v_i₁, …, v_{i_k})

P = (v_i₁, …, v_{i_k}) ← ShortestNSPath(G) ▷Step 1

ConstructForPath(P)

Let us show the correctness of the algorithm.

Theorem 3.

The quantum circuit produced by Algorithm 5 implements the shallow circuit of quantum hashing from Figure 1.

We can represent the controlled rotation operator cR(u, v) and the corresponding angle ξ as a sequence of R(v, ξ/2), cnot(u, v), R(v, –ξ/2), and cnot(u, v), (see Figure 3). Here R(v, ξ/2) is the R_y(ξ/2) gate applied to the qubit v; cnot(u, v) is the CNOT for u as a control and v as a target.

Additionally, the swap(u, v) gate can be represented as a sequence cnot(u, v), cnot(v, u), and cnot(u, v) (see Figure 4).

Two sequential operators CR_y and SWAP that are cR(u, v) and swap(u, v) procedures can be represented by a circuit in Figure 5.

Note that two sequential cnot(u, v) gates are annihilated, as presented in [23,79]. So, we obtain the circuit in Figure 6.

Let us look at the CNOT cost of these operators, where the CNOT cost is the number of CNOT operators in the representation of a circuit using only basic gates.

We can say that the CNOT cost of cR(u, v) is 2; CNOT cost of swap(u, v) is 3, CNOT cost of two sequential operators cR(u, v) and cnot(u, v) is 3.

Finally, we can discuss the CNOT cost of the constructed circuit.

Theorem 4.

CNOT cost of the circuit generated by Algorithm 5 is 3k – 4b – 5 ≤ 3k – 5, where k is the length of a shortest non-simple path P = (v_i₁, …, v_{i_k}) in the graph G that visits all vertices at least once, and b is the number of indices j such that v_{i_j} = v_{i_j+2}.

Proof.

If we look at Algorithm 5, then we can see that it is a sequence of one of three options:

a pair of CR_y and SWAP gates if v_j ≠ v_j+2 and v_j+1 ∉ U.
SWAP gate if v_j ≠ v_j+2 and v_j+1 ∈ U.
CR_y gate if v_j = v_j+2 and v_j+1 ∉ U.

Note that the option v_j = v_j+2 and v_j+1 ∈ U is not possible because v_j+1 ∈ U means that the corresponding qubit was already visited. In that case, we can just exclude it from the path because v_j = v_j+2. At the same time, it contradicts the condition that P is the shortest path.

The CNOT cost for pairs of CR_y and SWAP gates is 3; for the SWAP gate, it is 3; for the CR_y gate, it is 2.

Let b be the number of steps where we apply pairs of CR_y and SWAP gates or the SWAP gate, and let b be the number of steps where we apply CR_y (here we do not count the first and the last vertex from the path because they are processed by the different logic). Here a + 2b = k – 3 because (i) if v_j = v_j+2, then we use only CR_y to v_j+1 and skip v_j+2 (ii) we do not count the target qubit. So, the total number of CNOT gates is 3a + 2b + 4 = 3(a + 2b + 3) – 4b – 5 = 3k – 4b – 5.

Using Lemma 3 we can estimate the CNOT cost of the circuit and present it in the next corollary.

Corollary 1.

CNOT cost of the circuit that is generated using Algorithm 5 is between 2n – 2 and 6n – 11.

Proof.

The circuit has the minimal CNOT cost if each operation required only two CNOT gates, which means no SWAP gates. This happens if we have a “star” graph, where one vertex (a middle vertex) is connected to all other n – 1 vertices. In that case k = 2(n – 1) – 1 = 2n – 3, we start from a non-middle vertex and come to the middle vertex after each other, except the last one. The value b = n – 3 because each non-middle vertex, except the first and last in the path satisfies the required property. So, the CNOT cost according to Theorem 4 is 3(2n – 3) – 4(n – 3) – 5 = 6n – 9 – 4n + 12 – 5 = 2n – 2.

The maximum value is for k = 2n – 1, and the minimum value for b = 0. So, the maximum value for the CNOT cost is 3(2n – 1) – 5 = 6n – 6 – 5 = 6n – 11.

Typically, the quantum fingerprinting (quantum hashing) algorithm is used several times. For example, for hashing a string of ℓ symbols, we should apply the algorithm ℓ times (see Appendix B for examples). For this reason, we suggest two strategies.

Strategy with a Path

Let a step be a single application of the quantum fingerprinting algorithm. After each step, we reverse the path P. Then, the target qubit travels back. Additionally, we can see that the operator cR(v_{i_k-1}, v_{i_k}) is applied at the end of the odd step and at the beginning of the even step. We can apply it once with a double angle. The same situation with cR(v_i₁, v_i₂) on the meeting of even and odd steps. Therefore, we have the following CNOT cost for ℓ applications of the quantum hashing algorithm.

Theorem 5.

CNOT cost of the circuit to apply the quantum fingerprinting (quantum hashing) algorithm ℓ times is at most (3k – 4b – 7)ℓ + 2 ≤(3k – 7)ℓ + 2, where k is the length of the shortest non-simple path P = (v_i₁, …, v_{i_k}) in the graph G that visits all vertices at least once, and b is the number of indices j such that v_{i_j} = v_{i_j+2}.

Proof.

The first step costs 3k – 5 due to Theorem 4. Each next step skips the first cR gate because it is “merged” with the last cR from the previous step. So, its CNOT cost is 3k – 7 because cR costs 2. The total cost is 3k – 5 + (3k – 7)(ℓ – 1) = (3k – 7)ℓ + 2.

Similarly to Corollary 1 we can show the next result.

Corollary 2.

The CNOT cost of the circuit for application of the quantum fingerprinting (quantum hashing) algorithm ℓ times is between (2n – 4)ℓ + 2 and (6n – 13)ℓ + 2.

Strategy with a Cycle

At the beginning of each step, starting from the second one, we add swap(v_{i_k}, v_i₁) and swap(v_i₁, v_i₂) gates. We need the first swap because we should start from the beginning of the cycle next time. We add the second one because we should start from the second element of the cycle. These two gates increase the cost by 2 because they are jointed with corresponding cR gates. At the same time, all the logical qubits are moved to position 1 of the cycle. That is why we need only k – 1 travels by the cycle for doing k steps.

Therefore, we have the following CNOT cost for ℓ applications of the quantum hashing algorithm.

Theorem 6.

CNOT cost of the circuit for application of the quantum fingerprinting (quantum hashing) algorithm ℓ times is at most $3 (k - 1) (ℓ + 1) - (4 b + 3) (ℓ - \frac{ℓ}{k}) + 5 \leq 3 (k - 1) (ℓ + 1) - 3 (ℓ - \frac{ℓ}{k}) + 5$ 3(k - 1)(\ell + 1) - (4b + 3)\left( {\ell - {\ell \over k}} \right) + 5 \le 3(k - 1)(\ell + 1) - 3\left( {\ell - {\ell \over k}} \right) + 5, where k + 1 is the length of the shortest non-simple cycle C = (v_i₁, …, v_{i_k}, v_i₁) in the graph G that visits all vertices at least once, and b is the number of indices j such that v_{i_j} = v_{i_j+2}.

Proof.

The first step costs 3k – 4b – 5 due to Theorem 4. Each next step costs 3k – 4b – 3 because of two additional swap gates. At the same time, we should apply them only $ℓ - ⌊ \frac{ℓ}{k} ⌋$ \ell - \left\lfloor {{\ell \over k}} \right\rfloor due to the movement of the logic qubits by the cycle.

The total cost is $\begin{array}{l} 3 k - 4 b - 5 + (3 k - 4 b - 3) (ℓ - ⌊ \frac{ℓ}{k} ⌋ - 1) = (3 k - 4 b - 3) (ℓ - ⌊ \frac{ℓ}{k} ⌋) + 2 = \\ 3 k ℓ - 4 b ℓ - 3 ℓ - 3 k ⌊ \frac{ℓ}{k} ⌋ + (4 b + 3) ⌊ \frac{ℓ}{k} ⌋ + 2 \leq 3 k ℓ - 4 b ℓ - 3 ℓ - 3 k (\frac{ℓ}{k} - 1) + (4 b + 3) \frac{ℓ}{k} + 2 = 3 k ℓ - 4 b ℓ - \\ 3 ℓ - 3 ℓ + 3 k + 4 b \frac{ℓ}{k} + 3 \frac{ℓ}{k} + 2 = 3 k ℓ - 3 ℓ + 3 k - 4 b (ℓ - \frac{ℓ}{k}) - 3 (ℓ - \frac{ℓ}{k}) + 2 = 3 k ℓ - 3 ℓ + 3 k - (4 b + 3) (ℓ - \\ \frac{ℓ}{k}) + 2 = 3 k (ℓ + 1) - 3 (ℓ + 1) + 3 - (4 b + 3) (ℓ - \frac{ℓ}{k}) + 2 = 3 (k - 1) (ℓ + 1) - (4 b + 3) (ℓ - \frac{ℓ}{k}) + 5 \end{array}$ \matrix{ {3k - 4b - 5 + (3k - 4b - 3)\left( {\ell - \left\lfloor {{\ell \over k}} \right\rfloor - 1} \right) = (3k - 4b - 3)\left( {\ell - \left\lfloor {{\ell \over k}} \right\rfloor } \right) + 2 = } \hfill \cr {3k\ell - 4b\ell - 3\ell - 3k\left\lfloor {{\ell \over k}} \right\rfloor + (4b + 3)\left\lfloor {{\ell \over k}} \right\rfloor + 2 \le 3k\ell - 4b\ell - 3\ell - 3k\left( {{\ell \over k} - 1} \right) + (4b + 3){\ell \over k} + 2 = 3k\ell - 4b\ell - } \hfill \cr {3\ell - 3\ell + 3k + 4b{\ell \over k} + 3{\ell \over k} + 2 = 3k\ell - 3\ell + 3k - 4b\left( {\ell - {\ell \over k}} \right) - 3\left( {\ell - {\ell \over k}} \right) + 2 = 3k\ell - 3\ell + 3k - (4b + 3)(\ell - } \hfill \cr {\left. {{\ell \over k}} \right) + 2 = 3k(\ell + 1) - 3(\ell + 1) + 3 - (4b + 3)\left( {\ell - {\ell \over k}} \right) + 2 = 3(k - 1)(\ell + 1) - (4b + 3)\left( {\ell - {\ell \over k}} \right) + 5.} \hfill \cr } .

Due to b ≥ 0, we have $3 (k - 1) (ℓ + 1) - (4 b + 3) (ℓ - \frac{ℓ}{k}) + 5 \leq 3 (k - 1) (ℓ + 1) - 3 (ℓ - \frac{ℓ}{k}) + 5$ 3(k - 1)(\ell + 1) - (4b + 3)\left( {\ell - {\ell \over k}} \right) + 5 \le 3(k - 1)(\ell + 1) - 3\left( {\ell - {\ell \over k}} \right) + 5.

Similarly to Corollary 1 we can show the next result.

Corollary 3.

The CNOT cost of the circuit for application of the quantum hashing (quantum fingerprinting) algorithm ℓ times is between $(2 n - 4) ℓ + 2 ℓ - \frac{2 ℓ}{n - 1} - 2$ (2n - 4)\ell + 2\ell - {{2\ell } \over {n - 1}} - 2 and $(6 n - 13) ℓ + ℓ + 6 n + \frac{6 ℓ}{2 n - 1} - 11$ (6n - 13)\ell + \ell + 6n + {{6\ell } \over {2n - 1}} - 11.

Proof.

Let us estimate the minimal cost similarly to Corollary 1. The first step costs 2n – 2. Each next step costs 2n – 2 + 2 = 2n. The total complexity is $\begin{array}{l} 2 n - 2 + 2 n (ℓ - ⌊ \frac{ℓ}{k} ⌋ - 1) = 2 n (ℓ - ⌊ \frac{ℓ}{k} ⌋) - 2 \geq 2 n (ℓ - \frac{ℓ}{k}) - 2 \geq \\ 2 n (ℓ - \frac{ℓ}{n - 1}) - 2 = 2 n ℓ - \frac{(2 n - 2 + 2) ℓ}{n - 1} - 2 = 2 n ℓ - \frac{2 (n - 1) ℓ}{n - 1} - \frac{2 ℓ}{n - 1} - 2 = 2 n ℓ - 2 ℓ - \frac{2 ℓ}{n - 1} - 2 = (2 n - 4) ℓ + 2 ℓ - \frac{2 ℓ}{n - 1} - 2 \end{array}$ \matrix{ {2n - 2 + 2n\left( {\ell - \left\lfloor {{\ell \over k}} \right\rfloor - 1} \right) = 2n\left( {\ell - \left\lfloor {{\ell \over k}} \right\rfloor } \right) - 2 \ge 2n\left( {\ell - {\ell \over k}} \right) - 2 \ge } \hfill \cr {2n\left( {\ell - {\ell \over {n - 1}}} \right) - 2 = 2n\ell - {{(2n - 2 + 2)\ell } \over {n - 1}} - 2 = 2n\ell - {{2(n - 1)\ell } \over {n - 1}} - {{2\ell } \over {n - 1}} - 2 = 2n\ell - 2\ell - {{2\ell } \over {n - 1}} - 2 = (2n - 4)\ell + 2\ell - {{2\ell } \over {n - 1}} - 2} \hfill \cr } .

Let us estimate the maximal cost similarly to Corollary 1. The first step costs 6n – 11. Each next step costs 6n – 11 + 2 = 6n – 9. The total complexity is $6 n - 11 + (6 n - 9) (ℓ - ⌊ \frac{ℓ}{k} ⌋ - 1) = (6 n - 9) (ℓ - ⌊ \frac{ℓ}{k} ⌋) - 2 \leq (6 n - 9) (ℓ - ⌊ \frac{ℓ}{2 n - 1} ⌋) - 2 \leq (6 n - 9) (ℓ - \frac{ℓ}{2 n - 1} + 1) - 2 = (6 n - 9) ℓ + (6 n - 9) - 3 \frac{(2 n - 1 - 2) ℓ}{2 n - 1} - 2 = (6 n - 9) ℓ + (6 n - 9) - 3 ℓ + 6 \frac{ℓ}{2 n - 1} - 2 = (6 n - 13) ℓ + ℓ + 6 n + \frac{6 ℓ}{2 n - 1} - 11$ 6n - 11 + (6n - 9)\left( {\ell - \left\lfloor {{\ell \over k}} \right\rfloor - 1} \right) = (6n - 9)\left( {\ell - \left\lfloor {{\ell \over k}} \right\rfloor } \right) - 2 \le (6n - 9)\left( {\ell - \left\lfloor {{\ell \over {2n - 1}}} \right\rfloor } \right) - 2 \le (6n - 9)\left( {\ell - {\ell \over {2n - 1}} + 1} \right) - 2 = (6n - 9)\ell + (6n - 9) - 3{{(2n - 1 - 2)\ell } \over {2n - 1}} - 2 = (6n - 9)\ell + (6n - 9) - 3\ell + 6{\ell \over {2n - 1}} - 2 = (6n - 13)\ell + \ell + 6n + {{6\ell } \over {2n - 1}} - 11.

We can see that the complexity presented in Corollary 1 is less than the result from Corollary 3 because each cycle that visits all the vertices at least once can be converted to a path by removing the last edge. At the same time, the repeated application of the same pattern of gates for each step can be useful in some hardware implementations.

4.1.

Comparing with Existing Results

Let us compare our generic approach with existing circuits for specific graphs. The LNN architecture is a common layout graph for many quantum devices. The graph is a chain where v₁ is connected with v₂; v_i is connected with v_i–1 and v_i+1 for i ∈ {2, …, n – 1}; v_n is connected with v_n–1.

The quantum fingerprinting (quantum hashing) algorithm for the LNN architecture was discussed in [79]. The path that visits all vertices in the graph is simply P = (v₁, …, v_n) (see Figure 7). So, our method gives us the same circuit as in [79]. The circuit for the quantum fingerprinting algorithm on 5 qubits is presented in Figure 8.

The CNOT cost of the circuit is presented in the next lemma.

Lemma 5.

The CNOT cost of the produced circuit of the quantum fingerprinting (quantum hashing) algorithm with n qubits for the LNN architecture is 3n – 5 for one application and 3nℓ – 7ℓ + 2 for ℓ applications.

Let us consider more complex graphs like a cycle with tails (like a “sun” or “two joint suns”). The 16- and 27-qubit IBM machines of this architecture were considered in [23]. The graphs and paths are presented in Figures 9 and 10.

Note that the red part of the path is such that v_j+2 = v_j. Therefore, we do not apply a SWAP gate on this part of the path, but only a CR_y gate. So, our generic method gives the same circuits as the circuits specially constructed for these devices [23]. The CNOT cost is 40 for the 16-qubit architecture, and 69 for the 27-qubit one.

We collect the results for the discussed architectures in Table 1 for LNN and Table 2 for others. Additionally, we added results in Table 3 for connectivity graphs of IBMQ Melbourne, Rigetti Aspen-4, and a 5 × 5-grid as a connectivity graph that can be found, for example, in [102]. They are presented in Figure 11.

Table 1.

The CNOT cost for the LNN architecture. The CNOT cost of circuits produced by algorithms from [79] and this paper is 3n – 5

The number of qubits n	[79] and this paper	Qiskit transpiler
5	10	14
10	25	39

Table 2.

The CNOT cost for “sun” and “two joint suns” architectures

Connectivity graph’s type	[23] and this paper	Qiskit transpiler
16-qubit “sun” architecture	40	57
27-qubit “two joint suns” architecture	69	115

Table 3.

The CNOT cost for IBMQ Melbourne, Regetti Aspen-4, and 5 × 5-grid

Connectivity graph’s type	This paper	Qiskit transpiler
14-qubit IBMQ Melbourne	36	44
16-qubit Regetti Aspen-4	43	66
25-qubit 5 × 5-grid	70	84

Moreover, we compare our algorithm with Qiskit transpiler [103] optimized circuit for the mentioned architectures. The Qiskit’s algorithm is randomized heuristic algorithm for circuit optimization. That is why we invoke it 100 times and choose the minimum of the produced circuits’ CNOT costs. We added the results to the tables.

The results were obtained using the algorithm implemented in C++. The implementation can be found in GitLab repository [104].

Remark 2.

In this paper, we focus on the CNOT cost (the number of CNOT gates) because two-qubit gates are harder to implement on real devices and give larger computational error compared to one-qubit gates. At the same time, there is another common metric of circuit quality that is depth (the number of steps, where each step is a layer of gates that can be done in parallel on different qubits). Often, the depth of a circuit is associated with time complexity. We do not optimize this metric in this paper. However, if we compute the depth of the circuit, then it can be obtained from the CNOT cost by adding 2(n – 1) because we do n – 1 controlled rotations in total and each of them requires two rotation gates as shown in Figure 3.

5.

Method for Constructing a Circuit for Quantum Fourier Transform

Here we present a method that allows us to construct a circuit for the Quantum Fourier Transform (QFT) for a connected graph G = (V, E) that is a qubit connectivity graph for a device. More information about the QFT algorithm can be found in Appendix C. If we do not have restrictions for applying two-qubit gates (when G is a complete graph for instance), then the circuit is as presented in Figure 12.

The author of [23] shows that the circuit for QFT is a series of CNOT cascades. Each of the cascades has a gate structure similar to the shallow circuit for the quantum hashing algorithm. Assume that we have a ConstructQFTForPath(P′, k′, r) procedure that constructs the r-th cascade of the circuit for QFT for a path P′of length k′. Note that for QFT, the size of each cascade is different. Here P′ is a path that visits only the vertices corresponding to the qubits used in the current cascade. Firstly, we present the main algorithm in Section 5.1. Then we present an algorithm for the ConstructQFTForPath(P′, k′, r) procedure in Section 5.2. After that we discuss the complexity of the circuit in Section 5.3. Finally, we compare the circuit with existing results in Section 5.4.

5.1.

The Main Algorithm

Let us present the whole algorithm for constructing the quantum circuit for the QFT algorithm.

Firstly, we find a non-simple path P = (v_i₁, …, v_{j_k}) that visits all vertices at least once. Then we assign logical qubits to the vertices according to this path. Let indices j₁, …, j_n be the indices of the first occurrence of each vertex. In other words, j_r is such that i_{j_r} = r, and i_h ≠ r for each 1 ≤ h < j_r.

Then, we assign Q_r ← j_r the position of r-th logical qubit in the graph, and T_{j_r} ← r the index of the logical qubit associated with a vertex.

After that, we start to construct the circuit for cascades. For the first cascade, we invoke ConstructQFTForPath(P, k). Similarly to the quantum hashing (quantum fingerprinting) algorithm, the target qubit (i.e., 1st logical qubit) moves to the end of the path, i.e., Q₁ = i_k.

For the second cascade, we exclude the vertex with index Q₁ from the graph and find the path P′ that visits all vertices at least once in the updated graph such that it starts from the vertex v_Q₂. The vertex v_Q₂ contains the 2nd logical qubit that should be the target in the second cascade. Then, we invoke ConstructQFTForPath(P′, k′), where k′ is the length of P′.

For the next cascades, we act in a similar way. For the r-th cascade, we exclude v_{Q_r–1}, find the path P′ that visits all vertices at least once in the updated graph such that it starts from the vertex v_{Q_r}, and invoke ConstructQFTForPath(P′, k′).

Note that a path in the updated graph always exists because it is connected. We have at least one path that visits all vertices at least once, and we exclude only one vertex, that is, the last one on this path.

During the implementation, we do not remove the vertex from the graph; we just store a set of “deleted” vertices and we prohibit visiting vertices from this set during the algorithm for the path search.

Let us present the algorithm.

Step 1.
We find a non-simple path P = (v_i₁, …, v_{i_k}) that visits all vertices at least once.
Step 2.
We find indices j₁, …, j_n, where j_r is such that i_h ≠ i_{j_r} for each 1 ≤ h < j_r. Then, we assign Q_r ← j_r and T_{i_{j_r}} ← r for 1 ≤ r ≤ n.
Step 3.
We assign P′ ← P, and k′ is the length of P′. We assign r ← 1, which is an index of the cascade.

The next steps are repeated while the graph contains at least one vertex.

Step 4.
We find a non-simple path P′ of length k′ that visits all non-deleted vertices of the graph and starts from v_{Q_r}. If r = 1, then we do nothing because P′ was already found in Steps 1-3.
Step 5.
We invoke ConstructQFTForPath(P′, k′, r), which is the r-th cascade. Assume that the procedure keeps the Q and T indices actual.
Step 6.
We exclude v_{Q_r} from the graph.
Step 7.
If r = n, then we terminate the algorithm. Otherwise, we increase the index of the cascade r ← r + 1 and go to Step 4.

The implementation of the algorithm is presented in Algorithm 6. Assume that we have the ShortestNSPath(G) procedure that returns the shortest non-simple path visiting all vertices, and the ShortestNSPath(G, v) procedure that returns a similar path that starts from the vertex v. Let getFirstIndices(P) be a procedure that returns j₁, …, j_n. The implementation of this procedure is simple, has O(k log n) time complexity, and is presented in Appendix D.

Algorithm 6 Implementation of the algorithm for constructing the whole circuit for QFT for a path P = (v_i₁, …, v_{i_k})

P ← ShortestNSPath(G), k ← len(P)

(j₁, …, j_n) ← getFirstIndices(P)

for r ∈ {1, …, n} do

Q_r ← j_r

T_{i_{j_r}} ← r

end for

P′ ← P, k′ ← k, r ← 1

while r ≤ n do

ConstructQFTForPath(P′, k′, r)

V ← V\{v_{Q_r}}

r ← r + 1

if r ≤ n then

P′ ← ShortestNSPath(G, v_{Q_r}), k′ ← len(P′)

end if

end while

Let us discuss the time complexity of the algorithm. The time complexity of ShortestNSPath(G) and ShortestNSPath(G, v) is O(n²2ⁿ) due to Theorem 1. In each step, the number of vertices is reduced by 1. So, the total complexity is $O (\sum_{i = 1}^{n} (i^{2} 2^{i})) = O (n^{2} 2^{n})$ O\left( {\sum\limits_{i = 1}^n {\left( {{i^2}{2^i}} \right)} } \right) = O\left( {{n^2}{2^n}} \right). In the case of the heuristic solution, we have a similar situation. The complexity of the presented solution from Section 3.1 is $O (\sum_{i = 1}^{n} i^{5}) = O (n^{6})$ O\left( {\sum\limits_{i = 1}^n {{i^5}} } \right) = O\left( {{n^6}} \right).

5.2.

Quantum Circuit for One Cascade

The procedure ConstructQFTForPath(P′, k′, r) is very similar to the ConstructForPath(P) procedure that constructs the circuit for the quantum hashing algorithm. At the same time, there are many small, specific modifications. That is why we present the whole algorithm here.

Step 1.
We start with the first qubit in the path j ← 1. We apply the Hadamard transformation to the qubit corresponding to the vertex v_i₁. We denote this action by H(v_i₁). If k′ = 1, then we terminate our algorithm; otherwise, go to Step 2.
Step 2.
If j = k′, then we terminate the algorithm; otherwise, we continue. If v_{i_j+1} ∉ U, then we apply the controlled phase gate CR_d with the control v_{i_j+1} and the target v_{i_j}. qubits, where d = T_{i_j+1} – r. Then, we add v_{i_j+1} to the set U, i.e., U ← U ∪ {v_{i_j+1} }. Then, we go to Step 3.
Step 3.
If j = k′ – 1 or v_{i_j+2} ≠ v_{i_j}, then we continue; otherwise, we go to Step 4. We apply the SWAP gate to v_{i_j} and v_{i_j+1}, and swap the indices of qubits for these vertices. In other words, if w₁ = T_{i_j} and w₂ = T_{i_j+1} are indices of the corresponding logical qubits, then we swap Q_w₁ and Q_w₂ values, and T_{i_j} and T_{i_j+1} values. Then, we update j ← j + 1 because the value of the target qubit moves to v_{i_j+1}. Then, we go to Step 2.
Step 4.
If v_{i_j+2} = v_{i_j}, then we update j ← j + 2. Note that here we stay on the same vertex of the graph G. Then, we go to Step 2.

Finally, we obtain ConstructQFTForPath(P′, r) procedure whose implementation is presented in Algorithm 7. This procedure constructs the r-th part (cascade) of the circuit for QFT for the path P′.

Algorithm 7 Implementation of ConstructQFTForPath(P′, k′, r) procedure. Algorithm of constructing the circuit for the r-th cascade for the path P′ = (v_i₁, …, v_{i_k}′)

j ← 1 ▷Step 1

H(v_{i_j})

U ← ∅

while j ≤ k′ do ▷Step 2

if v_{i_j+1} ∉ U then

d ← T_{i_j+1} – r

CR_d(v_{i_j+1}, v_{i_j})

U ← U ∪{v_{i_j+1}}

end if

if j = k′ or v_{i_j+2} ≠ v_{i_j}. then ▷Step 3

if k′ = 2 then

swap(v_{i_j}, v_{i_j+1})

w₁ ← T_{i_j}, w₂ ← T_{i_j+1}

Q_w₁ ← i_j+1, Q_w₂ ← i_j

T_{i_j} ← w₂, T_{i_j+1} ← w₁

end if

j ← j + 1

else ▷Step 4

j ← j + 2

end if

end while

5.3.

The CNOT Cost of the Circuit and Correctness of the Algorithm

Let us start with discussion correctness of the algorithm.

Theorem 7.

The quantum circuit produced by Algorithm 6 implements the circuit of the quantum Fourier transform algorithm from Figure 12.

Proof.

The r-th cascade of the QFT circuit is such that we should apply controlled phase operators with each logical qubit with indexes larger than r as the control qubit and r-th qubit as the target.

For the cascade, the algorithm computes the path that starts from the vertex corresponding to the r-th logical qubit and visits all vertices corresponding to the logical qubit with indexes larger than r. Let the path be $P^{'} = (v_{i_{1}}, \dots, v_{i_{k}^{'}})$ {P^\prime } = \left( {{v_{{i_1}}}, \ldots ,{v_{i_k^\prime }}} \right). Here we use the qubit from v_i₁ as a target qubit. It corresponds to the r-th logical qubit. Then, we apply the controlled phase operator with v_i₂ as the control qubit. After that, we move the target qubit to v_i₂ using the swap operator and apply the controlled phase operator with v_i₃ as the control qubit.

So, if the target qubit is in v_{i_j}, then we apply the controlled phase operator with v_{i_j+1} as the control qubit and move the target qubit to v_{i_j+1} using the swap gate.

We apply the controlled rotation phase with v_{i_j+1} as the control qubit only if it is not in the set U, and then add it to the set U. This action guarantees us that we apply the controlled phase operator with each required qubit only once. At the same time, the path visits each vertex corresponding to logical qubits with indexes larger than r at least once. This means that each qubit (vertex) occurs as v_{i_j+1} for some j. So, we apply the controlled phase operator with each qubit exactly once, and there are no other modifications of the target qubit. Therefore, the circuit implements the r-th cascade.

After that we exclude the vertex corresponding to r-th logical qubit from the graph. Note that the rest of the graph is connected because the r-th logical qubit moved to the end of the path P′. So, we can be sure that all vertices corresponding to logical qubits with indexes larger than r are connected with path P′ without the last vertex. Therefore, we can repeat the algorithm for the next cascades.

So, the produced circuit implements all cascades of the QFT circuit presented in Figure 1. At the same time, we apply the swap or controlled phase operators only to neighboring qubits.

Let us continue with CNOT cost of the circuit.

Note that the CR_d gate can be represented using only two CNOT gates and three R_z gates similar to CR_y [105] (see Figure 13).

A pair CR_d and SWAP can be represented using three CNOT gates. (See Figure 14).

Theorem 8.

If the graph G with n vertices has a Hamiltonian path, then the CNOT cost of the produced circuit for the QFT algorithm is 1.5n² – 1.5n – 1.

Proof.

Because the graph has a Hamiltonian path, the path P = (v_i₁, …, v_{i_n}) is exactly this path. So, in each step, we move the target qubit. We can say that in constructing the r-th cascade, we use the path P′ = (v_i₁, …, v_{i_n–r+1}). The CNOT cost of the r-th cascade for 1 ≤ r ≤ n – 2 is 3(n – r) because we apply SWAP and the controlled phase gates for each edge of the path. The CNOT cost of the (n – 1)-th cascade is 2 because we do not apply the SWAP gate. The CNOT cost of the n-th cascade is 0. Therefore, the total cost is $\sum_{r = 1}^{n - 1} (3 (n - r)) - 1 = 1.5 n^{2} - 1.5 n - 1$ \sum\limits_{r = 1}^{n - 1} {(3(} n - r)) - 1 = 1.5{n^2} - 1.5n - 1.

Let us discuss the CNOT cost of the algorithm in the next theorem.

Theorem 9.

The CNOT cost of a circuit that is generated using Algorithm 5 is between n²+ n – 4 and 3n² – 3n – 10.

Proof.

Similarly to Corollary 1, the minimal possible cost is when we move the target qubit the minimum possible times. It is the situation with the “star” graph where we have a vertex connected with all others. The cost of the r-th cascade in that case is 3 + 3 + 2 · (n – 2 – r) = 2(n – r) + 2, because we always remove one “non-middle” vertex. The path starts from “non-middle” and finishes in “non-middle.” Therefore, we should make two moves of the target qubit. For the (n – 1)-th cascade, the cost is only 2. So, the total complexity is at least $\sum_{r = 1}^{n - 2} (2 (n - r) + 2) + 2 = n^{2} + n - 4$ \sum\limits_{r = 1}^{n - 2} {(2(} n - r) + 2) + 2 = {n^2} + n - 4.

Similarly to the proof of Theorem 4, we can show that the CNOT cost of one cascade is at most 3(k – 1). After each cascade, the number of vertices is decreased by 1. The maximum possible value for k is 2n – 1. In the r-cascade, it is 2(n – r + 1) – 1 = 2(n – r) + 1. The cost of the (n – 1)-th cascade is 2, not 3, because we do not move the target qubit. The cost of the (n – 2)-th cascade is 6, because the length of the path in the graph with 3 vertices is always 3. So, the total complexity is at most $\sum_{r = 1}^{n - 3} (3 \cdot 2 (n - r)) + 6 + 2 = 3 n^{2} - 3 n - 10$ \sum\limits_{r = 1}^{n - 3} {(3\;\cdot\;2(n - r))} + 6 + 2 = 3{n^2} - 3n - 10.

5.4.

Comparing with Other Results

Similarly to Section 4.1 we discuss the LNN architecture and the more complex architecture. Firstly, let us consider the LNN architecture. As discussed earlier (see Figure 7), the path visits all vertices from v₁ to v_n one by one. The paths constructed for each cascade are presented in Appendix E. The circuit is similar to the circuit developed in [23]. The presented path is the Hamiltonian path in the graph. Due to Theorem 8, we get the following CNOT cost for the LNN architecture.

Lemma 6.

The CNOT cost of the produced circuit of the QFT algorithm using n qubits for the LNN architecture is 1.5n²– 1.5n – 1.

At the same time, [14] gives the circuit with n² + n – 4 CNOT cost, and [23] gives the circuit with 1.5n² – 2.5n + 1 CNOT cost. Our circuit is better than [14] only if n ≤ 3. The result from [23] is better than our result. However, it is not known how to apply the results of [14] for more complex architectures, and the results of [23] are presented only for a specific architecture.

Secondly, let us consider more complex architectures like 16-qubit “sun” (Figure 9), and 27-qubit “two joint suns” (Figure 10). The paths are presented in figures. Note that the red part of the path is such that v_j₊₂ = v_j. Therefore, we do not apply a SWAP gate on this step, but only the controlled phase operator. The CNOT cost for the 16-qubit machine is 342, and for the 27-qubit machine is 1009.

So, our generic method gives circuits that are a bit worse than the circuits constructed especially for these devices [23], which CNOT costs are 324 and 957 for the 16-qubit and the 27-qubit architectures, respectively. The difference is about 5%.

We have collected the results of discussed architectures in Table 4 for LNN and Table 5 for others. Additionally, we added results in Table 6 for connectivity graphs of IBMQ Melbourne, Rigetti Aspen-4, and a 5 × 5-grid as a connectivity graph that can be found, for example, in [102]. They are presented in Figure 11.

Table 4.

The CNOT cost of quantum circuit for the QFT algorithm for LNN architecture. The CNOT cost of circuits produced by the algorithm from [14] is n² + n – 4; by the algorithm from [79] is 1.5n² – 2.5n + 1; the algorithm from this paper is 1.5n² – 1.5n – 1.

The number of qubits n	This paper	[14]	[79]	Qiskit transpiler
3	8	8	7	9
4	17	16	15	21
5	29	26	26	38
10	134	106	126	207

Table 5.

The CNOT cost of quantum circuit for the QFT algorithm for “sun” and “two joint suns” architectures

Connectivity graph’s type	This paper	[23]	Qiskit transpiler
16-qubit “sun” architecture	342	324	549
27-qubit “two joint suns” architecture	1009	957	1839

Table 6.

The CNOT cost of quantum circuit for the QFT algorithm for IBMQ Melbourne, Regetti Aspen-4, and 5 × 5-grid

Connectivity graph’s type	This paper	Qiskit transpiler
14-qubit IBMQ Melbourne	269	335
16-qubit Regetti Aspen-4	359	585
25-qubit 5 × 5-grid	899	1158

Moreover, we compare our algorithm with the Qiskit transpiler [103] optimized circuit for the mentioned architectures. The Qiskit’s algorithm is a randomized heuristic algorithm for circuit optimization. That is why we invoke it 100 times and choose the minimum of the produced circuits’ CNOT costs. We added the results to the tables.

The results were obtained using the algorithm implemented in C++. The implementation can be found in the GitLab repository [104].

Remark 3.

As we discussed in Remark 2, here, we focus on the CNOT cost but not the depth of the circuit. If we compute the depth of the circuit, then it can be obtained from the CNOT cost by adding n² because for r-th cascade we do n – r controlled phase gates in total and each of them required two additional layers for rotation gates as shown in Figure 13. Moreover, we add one H gate. So, the depth of the r-th cascade is 2(n – r) + 1. The total depth is $c + \sum_{r = 1}^{n} (2 (n - r) + 1) = c + n^{2}$ c + \sum\limits_{r = 1}^n {(2(} n - r) + 1) = c + {n^2}, where c is the CNOT cost of the produced circuit.

6.

Conclusion

We present a generic method for constructing quantum circuits for quantum fingerprinting (quantum hashing) and quantum Fourier transform algorithms for an arbitrary connected qubit connectivity graph for hardware. The heuristic version of the method is fast enough and works with O(n⁶) time complexity. The certain version has an exponential time complexity that is O(n²2ⁿ). The algorithm works for an arbitrary qubit connectivity graph.

At the same time, if we consider samples of graphs like LNN, “sun” (16-qubit IBMQ Eagle r3 architecture), “two joint suns” (27-qubit IBMQ Eagle r3 architecture), then our generic algorithm gives us the same circuit as the techniques provided especially for these graphs [23,79] in the case of quantum hashing. In the case of QFT, our algorithm gives a bit worse circuit compared to the techniques optimized for these graphs [14,23]. At the same time, our approach works for arbitrary connected graphs, but the existing results work only for some specific graphs. Additionally, we consider other different architectures like IBMQ Melbourne, Rigetti Aspen-4, and a 5 × 5-grid as a connectivity graph. We show that for all of the considered connectivity graphs, including LNN, “sun,” and “two joint suns,” our algorithm produces circuit better than standard Qiskit transpiler optimization.

An open question is to develop a technique for QFT for an arbitrary connected graph that gives us the same or better results than the existing ones for specific architectures like LNN, “sun” and “two joint suns.”

Implementation of Quantum Fourier Transform and Quantum Hashing for Quantum Devices with Arbitrary Qubit Connectivity Graphs

Full Article

Paradigm

My account