Have a personal or library account? Click to login
Reducing T-Count In Quantum String Matching Algorithm Using Relative-Phase Fredkin Gate Cover

Reducing T-Count In Quantum String Matching Algorithm Using Relative-Phase Fredkin Gate

Quantum Information & Computation
Volume 25 (2025): Issue 4 (August 2025)
By: Byeongyong Park,  Hansol Noh and  Doyeol Ahn  
Open Access
|Aug 2025

Figures & Tables

Figure 1.

Decomposition of the Fredkin gate and the relative-phase Fredkin gate into the Clifford + T gate set. (a) Decomposition of the Fredkin gate used in Ref. [4], which requires seven T gates. (b) Decomposition of the relative-phase Fredkin gate used in this study, which requires four T gates. Implementing the QSM algorithm with the relative-phase Fredkin gate significantly reduces the T-count, a critical factor in minimizing space-time costs in fault-tolerant quantum computing.
Decomposition of the Fredkin gate and the relative-phase Fredkin gate into the Clifford + T gate set. (a) Decomposition of the Fredkin gate used in Ref. [4], which requires seven T gates. (b) Decomposition of the relative-phase Fredkin gate used in this study, which requires four T gates. Implementing the QSM algorithm with the relative-phase Fredkin gate significantly reduces the T-count, a critical factor in minimizing space-time costs in fault-tolerant quantum computing.

Figure 2.

Construction of a C20 operator. In this figure, we show a C20 circuit when N = 8.
Construction of a C20 operator. In this figure, we show a C20 circuit when N = 8.

Figure 3.

Construction of Grover’s operator Q = AR0A−1Rg for QSM algorithm. (a) Structure of the initialization operator A. XL and XP represent X gates to encode L and P, respectively. C represents the cyclic shift operator. XOR transforms state |ψ2〉 in Eq. (12) into state |ψ〉 in Eq. (13). (b) Example of constructing an XOR operation when N = 4 and M = 2. (c) Structure of Grover’s operator Q = AR0A−1Rg for the QSM algorithm. Operators R0 and Rg can be constructed using multi-qubit controlled-Z gates and single-qubit gates. Repeated application of Grover’s operator amplifies the amplitude of the desired matching states.
Construction of Grover’s operator Q = AR0A−1Rg for QSM algorithm. (a) Structure of the initialization operator A. XL and XP represent X gates to encode L and P, respectively. C represents the cyclic shift operator. XOR transforms state |ψ2〉 in Eq. (12) into state |ψ〉 in Eq. (13). (b) Example of constructing an XOR operation when N = 4 and M = 2. (c) Structure of Grover’s operator Q = AR0A−1Rg for the QSM algorithm. Operators R0 and Rg can be constructed using multi-qubit controlled-Z gates and single-qubit gates. Repeated application of Grover’s operator amplifies the amplitude of the desired matching states.

Figure 4.

Decomposition of Fredkin gate and relative-phase Fredkin gate. (a) Construction of a Fredkin gate using a Toffoli gate and two CNOT gates reported in Ref. [24]. (b) Construction of a relative-phase Fredkin gate using a relative-phase Toffoli gate and two CNOT gates.
Decomposition of Fredkin gate and relative-phase Fredkin gate. (a) Construction of a Fredkin gate using a Toffoli gate and two CNOT gates reported in Ref. [24]. (b) Construction of a relative-phase Fredkin gate using a relative-phase Toffoli gate and two CNOT gates.

Figure 5.

Comparison of the theoretical probabilities of Grover’s search and the results of the QSM simulation with relative-phase Fredkin gates. Each QSM simulation was executed 10,000 times to estimate the probabilities. The designed circuit was intended to identify the pattern “11” within the data sequence “00110000”. The x-axis shows the number of Grover iterations, and the y-axis displays the corresponding probabilities. The red line plot with “x” markers represents the theoretical probabilities of Grover’s search algorithm functioning correctly, while the blue bar graph indicates the simulation results of the QSM algorithm with relative-phase Fredkin gates. The simulation data aligns closely with the theoretical expectations, demonstrating the correctness of the QSM algorithm with relative-phase Fredkin gates.
Comparison of the theoretical probabilities of Grover’s search and the results of the QSM simulation with relative-phase Fredkin gates. Each QSM simulation was executed 10,000 times to estimate the probabilities. The designed circuit was intended to identify the pattern “11” within the data sequence “00110000”. The x-axis shows the number of Grover iterations, and the y-axis displays the corresponding probabilities. The red line plot with “x” markers represents the theoretical probabilities of Grover’s search algorithm functioning correctly, while the blue bar graph indicates the simulation results of the QSM algorithm with relative-phase Fredkin gates. The simulation data aligns closely with the theoretical expectations, demonstrating the correctness of the QSM algorithm with relative-phase Fredkin gates.

Figure 6.

Circuit of A′R0(A′)−1. The gates within the dashed green box are cancelled out, resulting in a reduction of 2N T-count.
Circuit of A′R0(A′)−1. The gates within the dashed green box are cancelled out, resulting in a reduction of 2N T-count.

Figure 7.

Automatic parallelization of T gates in constructing the cyclic shift operator when using the relative-phase Fredkin gate shown in Figure 1b.
Automatic parallelization of T gates in constructing the cyclic shift operator when using the relative-phase Fredkin gate shown in Figure 1b.

Figure 8.

Comparison of the T-counts for the QSM algorithm. The red dashed line indicates the T-count derived in this study, while the blue solid line corresponds to the T-count reported in Ref. [4]. For consistency in comparison, the pattern size M is fixed at 100.
Comparison of the T-counts for the QSM algorithm. The red dashed line indicates the T-count derived in this study, while the blue solid line corresponds to the T-count reported in Ref. [4]. For consistency in comparison, the pattern size M is fixed at 100.

Figure A1.

One-qubit sorting module. (a) Circuit diagram of the one-qubit sorting module employed in Ref. [33]. (b) Circuit of the four-qubit relative-phase Fredkin gate, constructed using the four-qubit relative-phase Toffoli gate proposed in Ref. [23], along with two CNOT gates. By replacing the Fredkin and Toffoli gates in Figure A1a with the four-qubit relative-phase Fredkin and relative-phase Toffoli gates from Ref. [23], the T-count of the one-qubit sorting module can be reduced from 29 to 16.
One-qubit sorting module. (a) Circuit diagram of the one-qubit sorting module employed in Ref. [33]. (b) Circuit of the four-qubit relative-phase Fredkin gate, constructed using the four-qubit relative-phase Toffoli gate proposed in Ref. [23], along with two CNOT gates. By replacing the Fredkin and Toffoli gates in Figure A1a with the four-qubit relative-phase Fredkin and relative-phase Toffoli gates from Ref. [23], the T-count of the one-qubit sorting module can be reduced from 29 to 16.

Figure A2.

q-qubit sorting module. (a) Circuit diagram of the q-qubit comparator presented in Ref. [36], which compares the quantum states |a〉 = |aq–1 aq–2 … a0〉 and |b〉 = |bq – 1bq–2 … b0〉. (b) Circuit diagram of the q-qubit sorting module utilized in Ref. [33].
q-qubit sorting module. (a) Circuit diagram of the q-qubit comparator presented in Ref. [36], which compares the quantum states |a〉 = |aq–1 aq–2 … a0〉 and |b〉 = |bq – 1bq–2 … b0〉. (b) Circuit diagram of the q-qubit sorting module utilized in Ref. [33].

Figure A3.

Equivalence transformation of the Fredkin–D–Fredkin structure, where D is a circuit block represented by a diagonal unitary matrix. A pair of Fredkin gates surrounding D can be replaced with a relative-phase Fredkin gate and its Hermitian conjugate. According to Lemma 1, each relative-phase Fredkin gate can be decomposed as RFred = D1 · Fred and RFred †= Fred ·D1†{\rm{RFred}}{{\rm{ }}^\dag } = {\rm{ Fred }}\cdotD_1^\dag , where D1 has a diagonal matrix representation. Substituting these into the circuit yields (D1 ⊗ I)†D(D1 ⊗ I) = D, showing that the transformation preserves the circuit’s behavior.
Equivalence transformation of the Fredkin–D–Fredkin structure, where D is a circuit block represented by a diagonal unitary matrix. A pair of Fredkin gates surrounding D can be replaced with a relative-phase Fredkin gate and its Hermitian conjugate. According to Lemma 1, each relative-phase Fredkin gate can be decomposed as RFred = D1 · Fred and RFred †= Fred ·D1†{\rm{RFred}}{{\rm{ }}^\dag } = {\rm{ Fred }}\cdotD_1^\dag , where D1 has a diagonal matrix representation. Substituting these into the circuit yields (D1 ⊗ I)†D(D1 ⊗ I) = D, showing that the transformation preserves the circuit’s behavior.

Figure A4.

Circuit diagram of the q-qubit comparator presented in Ref. [37], which compares the quantum states |a〉 = |aq – 1aq – 2 … a0〉 and |b〉 = |bq – 1bq – 2 … b0〉. The output qubit |e〉 indicates the comparison result: if |e〉 = 0, then a ≤ b; if |e〉 = 1, then a > b. When decomposed into the Clifford+T gate set using the Fredkin gate decomposition adopted in Ref. [4], the circuit requires a T-count of 14q.
Circuit diagram of the q-qubit comparator presented in Ref. [37], which compares the quantum states |a〉 = |aq – 1aq – 2 … a0〉 and |b〉 = |bq – 1bq – 2 … b0〉. The output qubit |e〉 indicates the comparison result: if |e〉 = 0, then a ≤ b; if |e〉 = 1, then a > b. When decomposed into the Clifford+T gate set using the Fredkin gate decomposition adopted in Ref. [4], the circuit requires a T-count of 14q.

Figure A5.

Optimization of the q-qubit comparator circuit presented in Ref. [37]. (a) Decomposition of the CNOT gate highlighted in the red box of Figure A4 into a controlled-Z gate and two Hadamard gates, which ensures that each subcircuit enclosed by the green boxes admits a diagonal matrix representation. (b) Optimized circuit obtained by replacing each pair of Fredkin gates in Figure A4 with the relative-phase Fredkin gate shown in Figure 1b and its Hermitian conjugate, thereby reducing the total T-count from 14q to 8q.
Optimization of the q-qubit comparator circuit presented in Ref. [37]. (a) Decomposition of the CNOT gate highlighted in the red box of Figure A4 into a controlled-Z gate and two Hadamard gates, which ensures that each subcircuit enclosed by the green boxes admits a diagonal matrix representation. (b) Optimized circuit obtained by replacing each pair of Fredkin gates in Figure A4 with the relative-phase Fredkin gate shown in Figure 1b and its Hermitian conjugate, thereby reducing the total T-count from 14q to 8q.

The table presents the required resources for the QSM algorithms, including T-count (the number of T gates), T-depth (the depth of T gates), CNOT-count (the number of CNOT gates), and Qubit-count (the number of qubits)_ Here, N represents the size of the database to be searched, and M represents the size of the pattern_ For the comparison, we assume that N1/2 Grover iterations are implemented_

SourceRef. [4]This Work
T-count14N3/2 log2 N – 14N3/2 + 7N log2 N – 7N + 8N1/2 log2 N + N1/2(8M – 20) + 7 = 14N3/2 log2 N – O(N3/2)8N3/2 log2 N – 10N3/2 + 4N log2 N – 4N + 8N1/2 log2 N + N1/2(8M – 26) + 1 = 8N3/2 log2 N – O(N3/2)
T-depth5N1/2log22N + 9N1/2log2N + N1/2(4M+2) + 52 log22N + 52 log2N=5N1/2log22N+O(N1/2logN)5{N^{1/2}}\log _2^2N\, + \,9{N^{1/2}}{\log _2}N\, + \,{N^{1/2}}(4M + 2)\, + \,{5 \over 2}\,\log _2^2N\, + \;{5 \over 2}\;{\log _2}N = 5{N^{1/2}}\log _2^2N + O\left( {{N^{1/2}}\log N} \right)4N1/2log22N + 8N1/2log2N + N1/2(4M−2) + 2log22N + 2log2N=4N1/2log22N+O(N1/2logN)4{N^{1/2}}\log _2^2N\; + \;8{N^{1/2}}{\log _2}N\; + \;{N^{1/2}}(4M - 2)\; + \;2\log _2^2N\; + \;2{\log _2}N = 4{N^{1/2}}\log _2^2N + O\left( {{N^{1/2}}\log N} \right)
CONT-count16N3/2 log2 N – 14N3/2 + 7N log2 N – 7N + 10N1/2 log2 N + N1/2(8M – 10) + M + 7 = 16N3/2 log2 N – O(N3/2)10N3/2 log2 N – 10N3/2 + 5N log2 N – 5N + 6N1/2 log2 N + N1/2(8M– 14) + M + 5 = 10N3/2 log2 N – O(N3/2)
Qubit-count32N + log2N+M−1{3 \over 2}N\; + \;{\log _2}N + M - 1N + log2 N + M
DOI: https://doi.org/10.2478/qic-2025-0016 | Journal eISSN: 3106-0544 | Journal ISSN: 1533-7146
Journal RSS Feed
Language: English
Page range: 299 - 314
Submitted on: Oct 25, 2024
Accepted on: Jun 2, 2025
Published on: Aug 22, 2025
Published by: Cerebration Science Publishing Co., Limited
In partnership with: Paradigm Publishing Services
Publication frequency: 1 issue per year
Keywords:
quantum circuit,
quantum string matching,
T-count,
relative phase Fredkin gate,
Grover’s search algorithm
Related subjects:
Physics,
Quantum physics,
Mathematics,
Applied mathematics,
Computer sciences,
Computer sciences in the humanities,
Computer sciences,
Computer sciences in natural sciences

© 2025 Byeongyong Park, Hansol Noh, Doyeol Ahn, published by Cerebration Science Publishing Co., Limited
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 25 (2025): Issue 4 (August 2025)Next article