Intermediate-qudit assisted Improved quantum algorithm for string
matching with an Advanced Decomposition of Fredkin gate
- URL: http://arxiv.org/abs/2304.03050v1
- Date: Thu, 6 Apr 2023 13:11:07 GMT
- Title: Intermediate-qudit assisted Improved quantum algorithm for string
matching with an Advanced Decomposition of Fredkin gate
- Authors: Amit Saha and Om Khanna
- Abstract summary: This article shows an improved quantum circuit implementation for the string-matching problem with the help of higher-dimensional intermediate temporary qudits.
It is also shown that with the help of intermediate qudits not only the complexity of depth can be reduced but also query complexity can be reduced for a quantum algorithm.
- Score: 1.9798034349981157
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The circuit-level implementation of a quantum string-matching algorithm,
which matches a search string (pattern) of length $M$ inside a longer text of
length $N$, has already been demonstrated in the literature to outperform its
classical counterparts in terms of time complexity and space complexity.
Higher-dimensional quantum computing is becoming more and more common as a
result of its powerful storage and processing capabilities. In this article, we
have shown an improved quantum circuit implementation for the string-matching
problem with the help of higher-dimensional intermediate temporary qudits. It
is also shown that with the help of intermediate qudits not only the complexity
of depth can be reduced but also query complexity can be reduced for a quantum
algorithm, for the first time to the best of our knowledge. Our algorithm has
an improved query complexity of $O(\sqrt{N-M+1})$ with overall time complexity
$O\left(\sqrt{N-M+1}\left((\log {(N-M+1)} \log N)+\log (M)\right)\right)$ as
compared to the state-of-the-art work which has a query complexity of
$O(\sqrt{N})$ with overall time complexity $O\left(\sqrt{N}\left((\log
N)^{2}+\log (M)\right)\right)$, while the ancilla count also reduces to
$\frac{N}{2}$ from $\frac{N}{2}+M$. The cost of state-of-the-art quantum
circuit for string-matching problem is colossal due to a huge number of Fredkin
gates and multi-controlled Toffoli gates. We have exhibited an improved gate
cost and depth over the circuit by applying a proposed Fredkin gate
decomposition with intermediate qutrits (3-dimensional qudits or ternary
systems) and already existing logarithmic-depth decomposition of $n$-qubit
Toffoli or multi-controlled Toffoli gate (MCT) with intermediate ququarts
(4-dimensional qudits or quaternary systems). We have also asserted that the
quantum circuit cost is relevant instead of using higher dimensional qudits
through error analysis.
Related papers
- 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) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - $T$-depth-optimized Quantum Search with Quantum Data-access Machine [0.0]
We introduce an efficient quantum data-access process, dubbed as quantum data-access machine (QDAM)
We analyze the runtime of our algorithm in view of the fault-tolerant quantum computation (FTQC) consisting of logical qubits within an effective quantum error correction code.
arXiv Detail & Related papers (2022-11-08T01:36:02Z) - A Note on Quantum Divide and Conquer for Minimal String Rotation [1.8275108630751844]
Lexicographically minimal string rotation is a fundamental problem on string processing.
Near-optimal quantum algorithms have been proposed during its development, with new ideas such as quantum divide and conquer introduced.
arXiv Detail & Related papers (2022-10-17T14:51:49Z) - Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
Dihedral Coset Problem (DCP) in $Z_N$ has been extensively studied in quantum computing and post-quantum cryptography.
Ettinger-Hoyer algorithm is known to solve the DCP in $O(log(N))$ queries.
We introduce the first algorithm to improve in the linear queries regime over the Ettinger-Hoyer algorithm.
arXiv Detail & Related papers (2022-06-29T05:30:54Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - Variational learning algorithms for quantum query complexity [3.980076328494117]
We develop variational learning algorithms to study quantum query complexity.
We apply our method to analyze various cases of quantum query complexity.
Our method can be readily implemented on the near-term Noisy Intermediate-Scale Quantum (NISQ) devices.
arXiv Detail & Related papers (2022-05-16T05:16:15Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$.
We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
arXiv Detail & Related papers (2021-03-03T22:42:15Z) - Span programs and quantum time complexity [2.4182732872327186]
We show how to convert a quantum algorithm for $f$ with time complexity $T$ into a span program for $f$ such that it compiles back into a quantum algorithm for $f$ with time complexity $widetildeO(T)$.
In particular, we show how to convert a quantum algorithm for $f$ with time complexity $T$ into a span program for $f$ such that it compiles back into a quantum algorithm for $f$ with time complexity $widetildeO(T)$.
arXiv Detail & Related papers (2020-05-04T08:43:14Z)
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.